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

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

Замыкание множества атрибутов на множестве 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. Нарушение авторских прав; Мы поможем в написании вашей работы!




Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


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

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Шов первичный, первично отсроченный, вторичный (показания) В зависимости от времени и условий наложения выделяют швы: 1) первичные...

Предпосылки, условия и движущие силы психического развития Предпосылки –это факторы. Факторы психического развития –это ведущие детерминанты развития чел. К ним относят: среду...

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