С.Д. Кузнецов - Основы баз данных (1121716), страница 24
Текст из файла (страница 24)
Это означает, что в некотором допустимом теле отношения найдутся два кортежа с! и г2, такие, что г! (Ас) = гл (Ас1 (а), но г1 (вс) м гл (вс) (Ь) (здесь г (А) обозначаетпроекцию кортежа г на множество атрибутов А). По аксиоме рефлексивности из равенства (а) следует, что г1 (А) = гг (А). поскольку имеется ГР А- в,должно соблюдатьсяравенство г2 (в) = гв (в1. Тогдаизнеравенства(ь) следует, что г2 (с1 ы гг (с), чтопротиворечитналичиютривиальной ГР Ас с. Следовательно, предположение об отсутствии ГР АС ВС не является верным, и справедливость второй аксиомы доказана. Аналогично докажем истинность третьей аксиомы Армстронга.
Предположим, что ГР А с не соблюдается. Это означает, что в некото- ' К сожалениях классическая статья Армстронга — ПЗ )т'. Аоиззлзлх. !)ерелвеасу Яоислзгез о! Ваза Вазе Яе(алелзлдрз, Рок. Гетр Соихгезз, озсс(сйе!м, Я»свел, )974 — так и не переведена на русский язык (на самом деле, ее нелегко найти и а оригинате). Поэтому я не могу рекоменаоаать ее для лооолнительного чтения, хотя обязан сослаться.
114 Функциональные зависимости и декомпозиция без потерь Лекция 6 ром допустимом теле отношения найдутся два кортежа «1 и г2, такие, что «) (л) = с2 (л), но г) (с) и гя (С). Но из наличия ГРл лследует, что «1 (В) = «2 (В),апотомунз наличия ГР в- сследует, что г1 (с) ся (с). Следовательно, предположение об отсутствии ГР л сне является верным, и справедливость третьей аксиомы доказана. Можно доказать, что система правил вывода Армстронга полна и совершенна (зоилд апл сотр)еге) в том смысле, что для данного множества ГР ялюбая ГР, потенциально выводимая из я, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней ГР. Тем не менее, Дейт по практическим соображениям предложил расширить базовый набор правил вывода еше пятью правилами: (4) л л (самодетерминированность) — прямо следует из правила (1); (5) если л-вб; то л- в и л- с (декомпозиция) — из правила (1) следует, что вс-6; по правилу (3) л- в; аналогично, из вс с и правила (3) следует А — С; (6) если л- в и л с, то л- вс(объединение) — из правила (2) следует, что л лв и лл лс; из правила (3) следует, что л вс; (7) если л- в и с (), то лс вп (композиция) — из правила (2) следует, что лс вс и вс в)7; из правила (3) следует, что лс в)7; (8) если л лс и в- и, то л нп>(накопление) — из правила (2) следует, что нс-всо, из правила (3) следует, что л нт.
Определение 6.5. Замыкание множества атрибутов Пусть заданы отношение «, множество г атрибутов этого отношения (подмножество заголовка «, или составной атрибут «) и некоторое множество ГР 6, выполняемых для «. Тогда замыканием я над я называется наибольшее множество я' таких атрибутов у отношения «, что ГР г- у входит в я'. Конец определения.
Алгоритм вычисления я очень прост. Один из его вариантов показан на рис. 6.2. Рис. 6.2. Алгоритм построения замыкания атрибутов над заданным множеством ГР 116 Основы баэ данных Курс Докажем корректность алгоритма по индукции. На нулевом шаге 2[0] = Я, Я[] Я Я[т], очевидно, принадлежит ь (тривиальная ГР »выводится» из любого множества ГР). Пусть для некоторого к выполняется ГР 2 2[К], И ПуетЬМЫ Нащдн В ятаКуЮ ГРА я, Чтслг:-2[К]. ТОГдаМОжно представить я [к] в виде Ас, и, следовательно, выполняется ГР г-дс. Но по правилу (8) мы имеем ГР 2-АСВ, т.е. ГР 2 [г [К] ЛПО][ я] входит во множество о, что переводит нас на следующий шаг индукции. Пусть для примера имеется отношение с заголовком [А, я, О, Р, я, И и заданным множеством ГР я = [А ]э, Ав я, вя я, со я, я с].
Пусть требуется найти [АЯ]' над Я. На первом проходе тела цикла 00 2['] равно Ая. В теле цикла гоп ядснбудут найдены ГР А ]]и я с, и в конце цикла 2 [1] станет равным Ас]эя. На втором проходе тела цикла РО при 2[2], равном Агря, в теле цикла яОП яАСН будет найдена ГР со я, и в конце цикла я [2] станет равным АС]]ЯЯ. Следующий проход тела цикла 00 не изменит 2 [ 3], и 2 ( [Ая) ') будет равно АС]зяя. Алгоритм построения замыкания множества атрибутов 2 над заданным множеством ГР я помогает легко установить, входит ли заданная ГР 2 в в замыкание о .
Очевидно, что необходимым и достаточным условием для этого является я=я', т. е. вхождение составного атрибута в в замыкание г.» Определение 6.6. Суперключ отношения Суперключом отношения г называется любое подмножество к заголовка г, включающее, по меньшей мере, хотя бы один возможный ключ г. Конец определения. Одно из следствий этого определения состоит в том, что подмножество К заголовка отношения г является суперключом тогда и только тогда, когда для любого атрибута А (возможно, составного) заголовка отношения г выполняется ГР к-А. В терминах замыкания множества атрибутов к является суперключом тогда и только тогда, когда я' совпадает с заголовком г.
Минимальное покрытие множества функциональных зависимостей Определение 6.7. Покрытие множества ГР Множество ГР я2 называется покрытием множества ГР я1, если любая ГР, выводимая из я1, выводится также из я2. Конец определения. Легко заметить, что Я2 является покрытием И тогда и только тогда, когда я1'~я2'. Два множества ГР я1 и я2 называются эквивалентнылги, если каждое из них является покрытием другого, т. е. ЯЯ = Я2'. " Мы используем здесь знаки операций проверки включения множеств, что не совсем корректно, поскольку если, например, множество 8 состоит иэ одного элемента, толля его обозначения используется имя соответствуюгдего атрибута, и в этом случае правильнее было бы использовать знак «е» (проверка вхождения элемента во мноиество).
116 Функциональные зависимости и декомпозиция бвз поте ь Лекция 6 Определение 6.8. Минимальное множество Л) Множество Г0 е называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам: а) правая часть любой Г0 из е является множеством из одного атрибута (простым атрибутом); Ь) детерминант каждой Г0 из Б обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания ь, т.
е. порождению множества Г0, не эквивалентного е;е с) удаление любой Г0 из Е приводит к изменению ~, т. е. порождению множества Г0, не эквивалентного Е. Конец определения. Чтобы продемонстрировать минимальные и неминимальные мно- жества Г0, вернемся к примеру отношения служАПие ПРОектн !СЛУ НОМ, СЛУ ИМЯ, СЛУ ЗАРП, ПРО НОМ, ПРОЕКТ РУК) с рис.б.). Если считать, что единственным возмо:кным ключом этого отношения являет- ся атрибут слу ном, то множество Г0 (слу ном-слу имя, слУ ном-слУ зАРп, слУ ном-про ном, про ном-проект Рук) будет минимальным.
Действительно, в правых частях Г0 этого множества на- ходятся множества, состоящие ровно из одного атрибута; каждый из де- терминантов тоже является множеством из одного атрибута, удаление которого, очевидно, недопустимо; удаление каждой Г0 явно приводит к изменению замыкания множества Г0, поскольку утрачиваемая инфор- мация не выводится с помощью аксиом Армстронга.
С дру~ой стороны, множества Г0 (*) (СЛУ НОМ- (СЛУ ИМЯ, СЛУ ЗАРП), СЛУ НОМ-ПРО НОМ, СЛУ НОМ ПРОЕКТ РУК, ЛРО НОМ ПРОЕКТ РУК), (е*) (СЛУ НОМ СЛУ ИМЯ, (СЛУ НОМ, СЛУ ИМЯ) СЛУ ЗАРП, СЛУ НОМ ПРО НОМ, СЛУ НОМ ПРОЕКТ РУК, ПРО НОМ ПРОЕКТ РУК) И (е**) (СЛУ НОМ СЛУ НОМ, СЛУ НОМ СЛУ ИМЯ, СЛУ НОМ СЛУ ЗАРП, СЛУ НОМ ПРО НОМ, СЛУ НОМ ПРОЕКТ РУК, ПРО НОМ ПРОЕКТ РУК) не являются минимальными.
Для множества (') в правой части первой Г0 присутствует множество из двух элементов. Для множества (**) удале- ние атрибута слУ имя из детерминанта второй Г0 не меняет замыкание множества Г0. Для множества (***) удаление первой Г0 не приводит к изменению замыкания. Эти примеры показывают, что для определения минимальности множества Г0 не всегда требуется явное построение за- мыкания данного множества. Интересным и важным является тот факт, что длн любого множества Л) 8 существует (и даже может быть посероено) эквивалентное ему ми- нимальное множество Б . РО с минимальным детерминантам называется минимальной слева. ыт Основы бвз данных Курс Приведем общую схему построения к по заданному множеству ГО З. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество З к эквивалентному множеству ГО ЗЗ, правые части ГО которого содержат только одноэлементные множества (простые атрибуты).
Далее,для каждой ГО изб,детерминант(з (и,, и„..., (з,,) которойсодержит более одного атрибута, будем пытаться удалять атрибуты ()„получая множество ГР ЗЗ. Если после удаления атрибута (), ЗЗ эквивалентно Я2, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем зЗ множество ГР, полученное путем допустимого удаления атрибутов из всех детерминантов ГО множества з2. Наконец, для каждой ГО г из множества зЗ будем проверять эквивалентность множеств зЗ и ЗЗ м|Н()д (Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
