Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма





Доверь свою работу кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

 

Заметим, что последний вариант переменной отношения СЛУЖ_ПРО_ЗАДАН находится в BCNF, поскольку все атрибуты заголовка отношения входят в состав единственного возможного ключа. В этом отношении вообще отсутствуют нетривиальные FD. Поэтому ранее обсуждавшиеся принципы нормализации здесь неприменимы, но, тем не менее, мы получили полезную декомпозицию. Все дело в том, что в случае четвертого варианта отношения СЛУЖ_ПРО_ЗАДАН мы имеем дело с новым видом зависимости, впервые обнаруженном Роном Фейджином в 1971 г. Фейджин назвал зависимости этого вида многозначными (multi-valued dependency – MVD). Как мы увидим немного позже, MVD является обобщением понятия FD.

 

В отношении СЛУЖ_ПРО_ЗАДАН выполняются две MVD: СЛУ_НОМ®® ПРО_НОМи СЛУ_НОМ®®СЛУ_ЗАДАН. Первая MVD означает, что каждому значению атрибута СЛУ_НОМсоответствует определяемое только этим значением множество значений атрибута ПРО_НОМ. Другими словами, в результате вычисления алгебраического выражения

 

(СЛУЖ_ПРО_НОМWHERE (СЛУ_НОМ= сн AND СЛУ_ЗАДАН= сз))
PROJECT {ПРО_НОМ}

 

для фиксированного допустимого значения сн и любого допустимого значения сз мы всегда получим одно и то же множество значений атрибута ПРО_НОМ. Аналогично трактуется вторая MVD.

 

Определение 8.1. Многозначная зависимость

В переменной отношения r с атрибутами A, B, C (в общем случае, составными) имеется многозначная зависимость B от A (A ®® B) в том и только в том случае, когда множество значений атрибута B, соответствующее паре значений атрибутов A и C, зависит от значения A и не зависит от значения C. Конец определения.

Многозначные зависимости обладают интересным свойством “двойственности”, которое демонстрирует следующая лемма.

Лемма Фейджина

В отношении r {A, B, C} выполняется MVD A ®® B в том и только в том случае, когда выполняется MVD A ®® C.

 

Доказательство достаточности условия леммы. Пусть выполняется MVD A ®® B. Пусть имеется некоторое удовлетворяющее этой зависимости значение Vr переменной отношения r, a обозначает значение атрибута A в некотором кортеже тела Vr, а {b} – множество значений атрибута B, взятых из всех кортежей тела Vr, в которых значением атрибута A является a. Предположим, что для этого значения a MVD A ®® C не выполняется. Это означает, что существуют такое допустимое значение c атрибута C и такое значение b Î {b}, что кортеж <a, b, c> Ï Vr. Но это противоречит наличию MVD A ®® B. Следовательно, если выполняется MVD A ®® B, то выполняется и MVD A ®® C. Аналогично можно доказать необходимость условия леммы.



 

Таким образом, MVD A ®® B и A ®® C всегда составляют пару. Поэтому обычно их представляют вместе в форме A ®® B | C.

 

FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FD A ® B, то выполняется и MVD A ®® B. *

 

Легко видеть, что отношения СЛУЖ_ПРО_НОМи СЛУЖ_ЗАДАНИЕне содержат MVD, отличных от FD, и именно в этом выигрывает декомпозиция с рис. 6.2. Правомочность этой декомпозиции доказывается приводимой ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хита.

 

Теорема Фейджина

Пусть имеется переменная отношения r с атрибутами A, B, C (в общем случае, составными). Отношение r декомпозируется без потерь на проекции {A, B} и {A, C} тогда и только тогда, когда для него выполняется MVD A ®® B | C.

 

Докажем достаточность условия теоремы. Пусть Vr является некоторым допустимым значением переменной отношений r. Пусть a обозначает значение атрибута A в некотором кортеже тела Vr, {b} – множество значений атрибута B, взятых из всех кортежей тела Vr, в которых значением атрибута A является a, и {c} – множество значений атрибута C, взятых из всех кортежей тела Vr, в которых значением атрибута A является a. Тогда очевидно, что в тело значения переменной отношения r PROJECT {A, B} будут входить все кортежи вида {a, bi}, где bi Î {b}, и если некоторый кортеж {a, bj} входит в тело значения переменной отношения r PROJECT {A, B}, то bj Î {b}. Аналогичные рассуждения применимы к r PROJECT {A, C}. Очевидно, что из этого следует, что при наличии многозначной зависомости A ®® B | C в переменной отношения r{A, B, C} декомпозиция r на проекции r PROJECT {A, B} и r PROJECT {A, C} является декомпозицией без потерь.

 

Для доказательства необходимости условия теоремы предположим, что декомпозиция переменной отношения r {A, B, C} на проекции r PROJECT {A, B} и r PROJECT {A, C} является декомпозицией без потерь для любого допустимого значения Vr переменной отношения r. Мы должны показать, что в теле ТСПЗ значения-отношения Vr поддерживается ограничение

 

IF (<сн, пн1, сз1> Î ТСПЗAND <сн, пн2, сз2> Î ТСПЗ)
THEN (<сн, пн1, сз2> Î ТСПЗAND <сн, пн1, сз2> Î ТСПЗ)

 

Действительно, пусть в ТСПЗ входят кортежи <сн, пн1, сз1> и <сн, пн2, сз2>. Предположим, что <сн, пн1, сз2> Ï ТСПЗ OR <сн, пн1, сз2> Ï ТСПЗ. Но в тело значения переменной отношения r PROJECT {A, B} входят кортежи <сн, пн1> и <сн, пн2>, а в тело значения переменной отношения r PROJECT {A, C} – <сн, сз1> и <сн, сз2>. Очевидно, что в тело значения естественного соединения r PROJECT {A, B} NATURAL JOIN r PROJECT {A, C} войдут кортежи <сн, пн1, сз2> и <сн, пн1, сз2>, и наше предположение об отсутствии, по крайней мере, одного из этих кортежей в ТСПЗ противоречит исходному предположению о том, что декомпозиция r на проекции r PROJECT {A, B} и r PROJECT {A, C} является декомпозицией без потерь. Тем самым, теорема Фейджина полностью доказана.

 

Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей “аномальные” многозначные зависимости, с приведением отношений в четвертую нормальную форму.

 

Определение 8.2. Четвертая нормальная форма

Переменная отношения r находится в четвертой нормальной форме (4NF) в том и только в том случае, когда находится в BCNF, и все MVD r являются FD с детерминантами – возможными ключами отношения r. Конец определения.



 

Грубо говоря, 4NF является BCNF, в которой многозначные зависимости вырождаются в функциональные (позволим себе на один момент отказаться от сокращений). Понятно, что отношение СЛУЖ_ПРО_ЗАДАН не находится в 4NF, поскольку детерминант MVD СЛУ_НОМ®® ПРО_НОМи СЛУ_НОМ®®СЛУ_ЗАДАНне является возможным ключом, и эти MVD не являются функциональными. С другой стороны, отношения СЛУЖ_ПРО_НОМи СЛУЖ_ЗАДАНИЕнаходятся в BCNF и не содержат MVD, отличных от FD с детерминантом – возможным ключом. Поэтому они находятся в 4NF.

 

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-01-03; Просмотров: 745; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.021 сек.