Введение в системы БД (542480), страница 113
Текст из файла (страница 113)
Кеп! 9!Г. А Бппр!е бп(де !о Ггче Ыоппа! Гоппз !и Ке1айопа! Оа!аЬазе ТЬеогу 0 САСМ. — ГеЬгпагу, 1983. — 26, № 2. 456 Часть 1П. Проектирование базы данных Эта публикация является первоисточником следующей весьма притягательной и несколько перефразированной характеристики ЗНФ (точнее, НФБК); каждый атрибут должен представлять некоторый факт о ключе, о ключе целиком и ни о чем более, кроме ключа.
11.6. К)ззапеп 3. !пс)ерепс(епс Согпропепсв оС' Ке!алоиз // АСМ ТО(ЗБ.— (ЗесешЬег ! 977. — 2, № 4. 11.7. Лап(о!о С. А )»Сесе )»Соппа! гопп СЬг сйе Оез!Вп оГ Ке!абопа! ОасаЬазе Бсйешаса // !Ь!с!. — БерсеспЬег, 1982, — 7, № 3. Первоисточник элегантных определений ЗНФ и НФБК, упомянутых в этой главе. Основное назначение статьи — определение новой нормальной формы, нормасьной формы с элементарными ключами (НФЭ/О, которая занимает промежуточное положение между ЗНФ и НФБК и "содержит все преимушества обеих этих форм", но лишена всех их недостатков (например, ЗНФ является "очень нестрогой", а НФБК "склонна к вычислительной сложности"). В статье также показано, что алгоритм Бернштейна (!1.
!] приводит к генерации переменных-отношений, которые находятся в НФЭК, но не в ЗНФ. Ответы к упражнениям 11,1. Теорема Хита утверждает, что если переменная-отношение К(А, В, С) удовле- творяет функциональной зависимости А -з В (где А, В и С являются множествами атрибутов), то К равносильна соединению ее проекций К1 с атрибутами (А, В) и К2 с атрибутами (А, С». Далее в этом доказательстве будет использован сокрашенный неформальный вариант записи вида (а, Ь, с) для представления кортежа (А: а, В: Ь, С . "с ). Сначала следует показать, что ни один кортеж переменной-отношения К не утрачивается при разбиении на проекции и обратном соединении зтих проекций.
Пусть (а, Ь, с) и К, тогда (а, Ь) и К1 и (а, с) и К2, а значит, (а, Ь, с) и К1 301И К2. ° Затем следует показать, что каждый кортеж этого соединения действительно является кортежем переменной-отношения К (т.е. при соединении не было получено никаких "побочных" и нежелательных кортежей). Пусть (а, Ь, с) и К! 3018 К2. Тогда для генерации кортежа соединения должны выполняться зависимости (а, Ь) и К1 и (а, с) ц К2. Следовательно, для генерации кортежа (а, с) и К2 для некоторого атрибута Ь* должен сушествовать кортеж (а, Ь*, с) и К.
Тогда должен также существовать кортеж (а, Ь*) и К1. Теперь у нас есть (а, Ь) и К1 и (а, Ь*) и К1, а поскольку А -» В, значит, Ь»Ь». Отсюда (а, Ь, с) и К. ° Теорема, обратная теореме Хита, утверждает, что если переменная-отношение К(А, В, С) равносильна соединению ее проекций К1 с атрибутами (А, В) и К2 с атрибутами (А, С), то К удовлетворяет зависимости А » В. Это утверждение неверно. В качестве примера переменной-отношения, которая равняется соединению двух ее проекций и вовсе не удовлетворяет никакой нетривиальной ФЗ, можно предложить переменную-отношение СТХ, которая показана на рис. 12.2. Глава 11. Дальнейшая нормализация; формы 1НФ, 2НФ, ЗНФ и НФБК 457 11.2.
Это утверждение почти (но не совсем) верно, Приведенный ниже экзотический пример обратной ситуации взят из (5.5]. Рассмотрим переменную отношение ОБа (СООЕТЕТ, БТаТЕ), которая интерпретируется как "БИТЕ (штат) является членом СООЕТВУ (страны)", где под страной в каждом кортеже подразумеваются Соединенные Штаты Америки. Тогда в ланной переменной-отношении будет выполняться приведенная ниже ФЗ. ( ) -+ СООЕТЕУ А поскольку пустое множество ( ) не является потенциальным ключом, переменная-отношеиие ОБа не находится в НФБК (она может быть декомпозирована без потерь на две унарные проекции, хотя остается спорным утверждение о том, что она может быть подвергнута дальнейшей нормализации).
Попутно следует заметить, что в обшем случае вполне возможно сушествование потенциального ключа, который является пустым множеством! Подробности можно найти в ответе к упр. 8.7 из главы 8. 11.3. На рис. 11.20 показаны все наиболее важные функциональные зависимости: как те, которые подразумевались в упражнении, так и те, которые соответствуют разумным семантическим утверждениям (они перечислены ниже).
Атрибутам присвоены имена, поясняюшие их значения. Рис. 11,20. Диаграмма зависимостей для упр. ! 1.3 Семантические утверждения ° Нн один сотрудник не является руководителем одновременно нескольких отделов. ° Ни один сотрудник не работает одновременно более чем в одном отделе. ° Ни один сотрудник не работает одновременно более чем с одним проектом.
° Ни олин сотрудник не имеет одновременно более одного офиса. ° Ни один сотрудник не имеет одновременно более одного телефона. ° Нн один сотрудник не имеет одновременно более одного задания. ° Ни один проект не выполняется одновременно более чем одним отделом. ° Ни олин офис не принадлежит одновременно более чем одному отделу. Этап О. Определение структуры исходной переменной-отношения Прежде всего отметим, что исходную иерархическую структуру можно рассматривать как ненормализованную переменную-отношение ОЕРТО с атрибутами, содержашими значения типа отношений. 458 Часть 111. Проектирование базы данньп РЕРТО ( РЕРТ$, РВРРБЕТ, МОВ ЕМР$, ХЕМРО, ХРВОУО, ХОГГТСЕО ) КЕМ ( РЕРТ4 КЕГ ( МБН ЕМР$ ) Здесь смысл атрибутов РЕРТ$ (номер отдела), РВОРОЕТ (бюджет) и МОЕ ЕМР$ (личный номер руководителя отдела) ясен из их названиИ, а домены, соответствующие атрибутам ХЕМРО (сотрудник), ХРКОЮО (проект) и ХОГГ1СЕО (офис), состоят из значений, представляющих собой отношения, и нуждаются в дополнительных разъяснениях.
° Значение атрибута ХРЕОЮО в составе каждого кортежа переменной-отношения РЕРТО представляет собой отношение с атрибутами РНОЮ$ и РВРРБЕТ. ° Аналогично значение атрибута ХОГГ1СЕО в составе каждого кортежа переменной- отношения РЕРТО представляет собой отношение с атрибутами ОГГ4, АЕЕА и, скажем, ХРНОНЕО, где атрибут ХРНОИЕО, в свою очередь, имеет значения, представляющие собой отношения. Отношения, являющиеся значениями атрибута ХРНОНЕО, имеют только один атрибут РНОНЕ4.
° Наконец, значение атрибута ХЕМРО в составе каждого кортежа переменной- отношения РЕРТО представляет собой отношение с атрибутами ЕМР$, РНОЮ$, ОГГ4, РНОИЕ$ и, скажем, ХЮОВО, где атрибут ХЛОВО, в свою очередь, имеет значения, представляющие собой отношения. Отношения, являющиеся значениями атрибута ХЮОВО, имеют атрибуты ЛОВТ1ТЬЕ и, скажем, ХЯАРН1ЯТО, где атрибут ХБАРН1ЯТО, опять же, имеет значения, представляющие собой отношения.
Отношения, являющиеся значениями атрибута ХЯАЬН1ЯТО, содержат атрибуты ВАТЕ и ЯАЬАКТ. Таким образом, вся иерархия может быть представлена следующей вложенной структурой. РЕРТО ( РЕРТ$, РВРРБЕТ, МОХ ЕМР$, ХЕМРО ( ЕМР$, РНОЮ$, ОГГ$, РНОИЕ$, ХЮОВО ( ЮОВТ17ЬЕ, ХЯА1Н1ЯТО ( РЛТЕ, БАРАНУ ) ХРНОЮО ( РНО7$, РВОРБЕТ ), ХОРГ1СЕО ( ОГГ$, АНЕА, ХРНОНЕО ( РНОМЕ$ ) ) ) Замечание. Вместо описания потенциальных ключей здесь использовано выде- ление курсивом для обозначения тех атрибутов, которые по крайней мере "уникальны внутри родителя" (на самом деле атрибуты РЕРТ$, ЕМР$, РМОй$, ОГГ$ и РНОМЕ$ являются глобально уникальными согласно утверждениям, сде- ланным выше), Этап А Исключение атрибутов, содержаших значения-отношения Для простоты предположим, что каждая переменная-отношение имеет первичный ключ, т.е. всегда на каком-то основании (не важно, на каком) можно выбрать один из потенциальных ключей в качестве первичного.
В частности, для переменной- отношения РЕРТО в качестве первичного ключа выберем атрибут РЕРТ$ (таким об- разом, атрибут МОН ЕМР$ становится альтернативным ключом). Глава 11. Дальнейшая нормализация: формы 1НФ, 2НФ, ЗНФ и НФБК 459 Теперь можно приступить к исключению из переменной-отношения ВЕРТО атрибутов, содержащих значения-отношения, поскольку (как отмечалось в разделе ! !.б) они являются нежелательными'з.
° Для каждого атрибута переменной-отношения ВЕРТО, значениями которого являются отношения (т.е. для атрибутов ХЕМРО, ХРКОЮО и ХОГГ1СЕО), создадим новую переменную-отношение с атрибутами, состоящими из атрибутов соответствующего отношения плюс атрибут первичного ключа переменной-отношения ВЕРТО. Первичным ключом каждой из вновь созданных расширенных переменных-отношений будет комбинация того атрибута, который в исходном отношении являлся "уникальным внутри родителя", и первичного ключа переменной-отношения ВЕРТО. (Обратите внимание, что многие из созданных "первичных ключей'* содержат атрибуты, которые являются избыточными для уникальной идентификации кортежей; впоследствии они будут исключены.) Удаляем атрибуты ХЕМРО, ХРКОЛО и ХОГГ1СЕО из переменной-отношения ВЕРТО.
° Если какая-либо переменная-отношение К все еще имеет какие-либо атрибуты, значениями которых являются отношения, то описанную последовательность действий для этой переменной-отношения К необходимо повторить. После выполнения указанных действий будет получен приведенный ниже набор переменных-отношений, из которых исключены все атрибуты, содержащие значения-отношения. Обратите внимание на то, что полученные переменные- отношения, безусловно, находятся в 1НФ, но необязательно в какой-то более высокой нормальной форме. РЕРТ1 ( РКРТ!), ВВ006ЕТ, МОК НИРО ) РК1ИАКХ КЕХ ( РЕРТР ) АВТЕККАТЕ КЕХ ( И6К ЕИРО ) ЕИР1 ( ВЕРИ, НИРО, РКОое, ОГГО, РНОИЕО ) РР1ИАКХ КЕХ ( РКРТ(э ЕИРО ) ЮОВ1 ( ВЕРТО, ЕМРе, ЮОВТ1ТХЕ ) РК1ИАВХ КЕХ ( РКРТ(г ЕМР(с ЮОБТ1ТЬЕ БАЬН1БТХ ( ВЕРХ(, ВИРР, ЮОБТХТЬЕ, РйТЕ, БАРАКХ ) РК1ИАКХ КЕХ ( ВЕРХ(, ЕМРО, ЮОВТ1ТЬЕ, ВАТЕ ) РКОЮ1 ( ВЕРХ(, РКОЮ(, РВ006ЕТ ) РК1ИАКХ КЕХ ( ВЕРХ(, РВОТА!) зл Заметим, что представленная здесь процедура исключения атрибутов, значениями которых являются отношения, предусматривает многократное выполнение оператора 0))СКОВР !си.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
