Введение в системы БД (542480), страница 100
Текст из файла (страница 100)
А -+ ВС Е вЂ” з СЕ З г'гножеспгво функциональных зависимостей с атрибутаии Е распаложенны.ии слева, представляет собой множество из всех функциональных зависимоспгей аида Л вЂ” ЗЕ ', где Я ' является некоторым подмножеством Я . Тогда залгыкание Б исходного.иножества Б представляет собой объединение все» пгакггх множеспгв функиионолиных зависгсиоспгей, взялгых для всех вомгожных множеств атрибутов 2 407 Глава з О. Функиионалвныв зависимости  — э Е СΠ— > ЕР Вычислим замыкание (А,В) множества атрибутов (А,В), исходя из заданного множества функциональных зависимостей.
1. Присвоим замыканию СЬОЯОЕЕ [ Х, Б ] начальное значение — множество (А, В). 2. Выполним внутренний цикл четыре раза — по одному разу лля каждой заданной функциональной зависимости. На первой итерации (для зависимости А -+ ВС) будет обнаружено, что левая часть действительно является подмножеством замыкания СЕОЯОЕЕ[Х,Я]. Таким образом, к результату можно добавить атрибуты В и С. Замыкание СЕОБОЕЕ[Х,Я) теперь представляет собой множество (А,В,С). 3. На второй итерации (для зависимости Š— э СР) обнаруживается, что левая часть не является подмножеством полученного до этого момента результата, который, таким образом, остается неизменным.
4. На третьей итерации (для зависимости  — э Е) к замыканию СЬОБОКЕ[Х,Я] будет добавлено множество Е, которое теперь будет иметь вид (А,В,С, Е]. 5. На четвертой итерации (для зависимости СΠ— э ЕР) замыкание СЬОБОЕЕ[Х,Б] останется неизменным. 6. Далее внутренний цикл выполняется еще четыре раза. На первой итерации результат останется прежним, на второй он булет расширен до (А, В, С, Е, Р), а на третьей и четвертой — снова не изменится. 7. Наконец после еще одного четырехкратного прохождения цикла замыкание СЕОБОКЕ[Х,Б] останется неизменным и весь процесс завершится с результатом (А,В) = (А,В,С,Е,Р). ° Из сказанного выше можно сдела~ь очень важное заключение: для заданного множества функциональных зависимостей Б легко можно указать, будет ли заданная функциональная зависимость Х вЂ” г У следовать из Я, поскольку это возможно тогда и только тогда, когда множество У является подмножеством замыкания Х множества Х для заданного множества Б.
Иначе говоря, таким образом представлен простой способ определения, будет ли данная функциональная зависимость Х -+ Х включена в замыкание Я множества Б. Еше одно важное заключение основано на следующем факте. Прежде всего, вспомним определение понятия суперключ из главы Б.
Суперключ переменной-отношения К вЂ” это множество атрибутов переменной-отношения К, которое в виде подмножества (но необязательно собственного подмножества) содержит по крайней мере один погпенлиаэьный ключ. Из этого определения прямо следует, что суперключи для данной переменной-отношения Š— это такие подмножества К множества атрибутов переменной- отношения Е, что функциональная зависимость К вЂ” > А будет истинна для каждого атрибута А переменной-отношения Е.
Другими словами, множество К является суперключом тогда и только тогда, когда замыкание К лля множества К в пределах заданного множества функциональных зависимостей является множеством абсолютно всех атрибутов переменной-отношения В. (Кроме того, множество К является погпенииаэьны.и ключом тогда и только тогда, когда оно является неприводимым суперключом). 408 Часть 1П Проектирование базы данньп 10.б. Неприводимые множества зависимостей Пусть Я1 и Б2 — два множества функциональных зависимостей.
Если любая функциональная зависимость, которая выводится из множества зависимостей Я1, также выводится из множества зависимостей Я2 (т.е. если замыкание Б1 является подмножеством замыкания Б2", то множество Я2 называется покрытием для множества Я1з. Это значит, что если СУБД обеспечит соблюдение ограничений, представленных зависимостями множества Б2, то автоматически будут соблюдены и все ограничения, устанавливаемые зависимостями множества Б1.
Далее, если множество Я2 является покрытием для множества Б1, а множество Б1 одновременно является покрытием для множества Я2 (т.е. если Я1 =Я2'), то множества Б1 и Б2 эквивалентны. Ясно, что если множества Б1 и Я2 эквивалентны, то соблюдение СУБД ограничений, представленных зависимостями множества Б2, автоматически обеспечит соблюдение ограничений, представленных зависимостями множества Б1, и наоборот. Множество функциональных зависимостей называется неприводимымл тогда и только тогда, когда оно обладает всеми перечисленными ниже свойствами. !. Правая (зависимая) часть каждой функциональной зависимости из множества Б содержит только один атрибут (т.е.
является одноэлементным множеством). 2. Левая часть (детерминант) каждой функциональной зависимости из множества Я является неприводимой, т.е. ни один атрибут из детерминанта не может быть опушен без изменения замыкания Б' (без конвертирования множества Б в некоторое иное множество, не эквивалентное множеству Я). В этом случае функциональная зависимость называется неприводимой слева.
3. Ни одна функциональная зависимость из множества Я не может быть удалена из множества Я без изменения его замыкания Я (т.е. без конвертирования множества Я в некоторое иное множество, не эквивалентное множеству Я). В отношении пп. 2 и 3 следует отметить, что необязательно иметь точную информацию о составе замыкания Б для получения ответа на вопрос, изменится ли это замыкание при удалении из исходного множества какой-либо функциональной зависимости. В качестве примера рассмотрим уже знакомую переменную-отношение деталей Р с функциональными зависимостями, перечисленными ниже. Р$ -+ РййНЕ РР†> СОЬОН Р$ -э ИЕ16НТ РЯ -э ОХАХ Нетрудно заметить, что это множество функциональных зависимостей является не- приводимым: правая часть каждой зависимости содержит только один атрибут, а левая часть, очевидно, является неприводимой.
Кроме того, ни одна из перечисленных функ- Некоторые оаторы используют термин "покрытие" для обозначения эквивалентного множесп|еа 4 В литературе подобное множестео часто назыаается минимальным. 409 Глава 10. Функг(иональные зависимости циональных зависимостей не может быть опущена без изменения замыкания множества (т.е. без >траты некоторой иифор.иаиии). В противоположность этому приведенные ниже множества функциональных зависимостей не являются неприводимыми.
Е Р() †> ( РИАИЕ, СОВОК ) Р() -э ИЕ16НТ Р() †> С1ТХ (Правая часть первой ФЗ не является одноэлементным множеством.) 2. ( Р(), РИАИЕ ) э С010К Р)) — э РНАИЕ Рт -+ ИЕ10НТ Р( -+ С1ТХ (Первую ФЗ можно упростить, опустив атрибут РНАМЕ в левой части без изменения замыкания, т.е. она не является неприволимой слева.) 3. Р) — э Р$ Р$ — э РНАМЕ Р)) †> СОЬОК РŠ†> ИЕ10НТ Р() — э С1ТХ(Здесь первую ФЗ можно опустить без изменения замыкания.) Теперь можно слелать утверждение, что лля любого множества функциональных зависимостей существует по крайней мере одно эквивалентное множество, которое является неприволимым.
Это достаточно легко продемонстрировать на следующем примере. Пусть дано исходное множество зависимостей Б. Тогда благодаря правилу декомпозиции можно без утраты общности предположить, что каждая функциональная зависимость в этом множестве Б имеет одноэлементную правую часть. Далее лля каждой зависимости Х из этого множества Б следует проверить каждый атрибут А в левой части зависимое~и Х. Если множество Б и множество зависимостей, полученное в результате устранения атрибута й в левой части зависимости Х, эквивалентны, значит, этот атрибут следует удалить. Затем лля каждой оставшейся в множестве Б зависимости Х, если множества Б и Б — Х эквивалентны, следует удалить зависимость Х из множества Б. Получившееся в результате таких действий множество Б является неприволимым и эквивалентно исходному множеству Б. Лрииер. Пусть дана переменная-отношение К с атрибутами й, В, С, Р и следующими функциональными зависимостями.
й — + ВС В вЂ” > С й — > В АВ э С йС вЂ” ~ 0 Теперь попробуем найти неприводимое множество функциональных зависимостей, эквивалентное данному множеству. 410 Часть 1П. Проектирование базы данных 1. Прежде всего следует переписать заданные ФЗ таким образом, чтобы каждая из них имела одноэлементную правую часть. А — э В А — э С В вЂ” э С А — э В АС -+ Р Нетрудно заметить, что зависимость А -э В записана дважды, так что одну из них можно удалить. 2. Затем в левой части зависимости АС вЂ” > Р может быть опущен атрибут С, поскольку дана зависимость А э С, из которой по правилу дополнения можно получить зависимость А — > АС.
Кроме того, дана зависимость АС -э Р, из которой по правилу транзитивности можно получить зависимость А -э Р. Таким образом, атрибут С в левой части исходной зависимости АС вЂ” э Р является избыточным. 3. Далее можно заметить, что зависимость А — э С может быть исключена, поскольку дана зависимость А -+ С, из которой по правилу дополнения можно получить зависимость А — > СВ, а затем по правилу декомпозиции — зависимость АВ -+ С. 4.
Наконец зависимость А — > С подразумевается зависимостями А — > В и В э С, так что она также может быть отброшена. В результате мы получили неприводимое множество зависимостей. А-э  — э С А — э Р Множество функциональных зависимостей 1, которое неприводимо и эквивалентно другому множеству функциональных зависимостей Б, называется неприводимым покрытием множества Б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
