Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Замыкание множества атрибутов на множестве FD. Алгоритм построения. Пример. Польза. Суперключ отношения, его связь с замыканием и FD.





Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения R, что FD Z –> Y входит в S+.

 

Алгоритм вычисления Z+

 

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством

FD S = {A –> D, AB –> E, BF –> E, CD –> F, E –> C}. Пусть требуется найти {AE}+ над S.

 

 

На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD A –> D и E –> C, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CD –> F, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.

 

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z –> B в замыкание S+. Очевидно, что необходимым и достаточным условием для этого является вхождение составного атрибута B в замыкание Z.

 

Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя бы один возможный ключ R.

 

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD K –> A. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком R.

 


 

Покрытие множества FD. Эквивалентные покрытия. Минимальное множество FD. Примеры. Алгоритм построения минимального эквивалентного множества. Минимальное покрытие множества функциональных зависимостей.

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+ принадлежит S2+.

Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1+ = S2+.

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

· правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);

· детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S;

· удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

Пример:

Рассмотрим отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК}. Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ->СЛУ_ИМЯ,

СЛУ_НОМ->СЛУ_ЗАРП,

СЛУ_НОМ->ПРО_НОМ,

СЛУ_НОМ->ПРОЕКТ_РУК} будет минимальным.

С другой стороны, множество FD

{СЛУ_НОМ->(СЛУ_ИМЯ, СЛУ_ЗАРП),

СЛУ_НОМ->СЛУ_ИМЯ,

СЛУ_НОМ->СЛУ_ЗАРП,

СЛУ_НОМ->ПРО_НОМ,

СЛУ_НОМ->ПРОЕКТ_РУК} не является минимальными.







Дата добавления: 2015-09-15; просмотров: 1038. Нарушение авторских прав; Мы поможем в написании вашей работы!




Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...


Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

СПИД: морально-этические проблемы Среди тысяч заболеваний совершенно особое, даже исключительное, место занимает ВИЧ-инфекция...

Субъективные признаки контрабанды огнестрельного оружия или его основных частей   Переходя к рассмотрению субъективной стороны контрабанды, остановимся на теоретическом понятии субъективной стороны состава преступления...

ЛЕЧЕБНО-ПРОФИЛАКТИЧЕСКОЙ ПОМОЩИ НАСЕЛЕНИЮ В УСЛОВИЯХ ОМС 001. Основными путями развития поликлинической помощи взрослому населению в новых экономических условиях являются все...

МЕТОДИКА ИЗУЧЕНИЯ МОРФЕМНОГО СОСТАВА СЛОВА В НАЧАЛЬНЫХ КЛАССАХ В практике речевого общения широко известен следующий факт: как взрослые...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия