Главная Обратная связь Поможем написать вашу работу!

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Нормальная форма Бойса-Кодда



Причиной отмеченных аномалий является то, что в требованиях 2NF и 3NF не требовалась минимальная функциональная зависимость от первичного ключа атрибутов, являющихся компонентами других возможных ключей. Проблему решает нормальная форма, которую исторически принято называть нормальной формой Бойса-Кодда и которая является уточнением 3NF в случае наличия нескольких перекрывающихся возможных ключей. Переменная отношения находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, когда любая выполняемая для этой переменной отношения нетривиальная и минимальная FD имеет в качестве детерминанта некоторый возможный ключ данного отношения.

Переменная отношения СЛУЖ_ПРО_ЗАДАН1 может быть приведена к BCNF путем одной из двух декомпозиций:

1) СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и

СЛУЖ_НОМ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН}

2) СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и

СЛУЖ_ИМЯ_ПРО_ЗАДАН {СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН} (FD и значения результирующих переменных отношений выглядят аналогично).

Очевидно, что каждая из декомпозиций устраняет трудности, связанные с обновлением отношения СЛУЖ_ПРО_ЗАДАН1.


 

Многозначные зависимости. Двойственность многозначной зависимости. Лемма Фейджина. Теорема Фейджина (с доказательством).

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

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

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

Если в отношении R {A, B, C} выполняется MVD AB, то выполняется MVD AC. (Записывается как A->>B|C).

Доказательство леммы. Пусть <a,b,c’> принадлежит r и <a,b’,c> принадлежит r. Из того, что A->>B следует, что <a,b’,c>=<a,b,c> принадлежит r, следовательно, с от b не зависит, но зависит от а. По определению A->>C.



Доказано.

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

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

 

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

r PROJECT (AB) NJ r PROJECT (AC) = r тогда и только тогда, когда A->>B|C. (то есть отношение декомпозируется без потерь)

Докажем достаточность условия теоремы.

Пусть <a,b,c’> и <a,b’,c> принадлежaт r. Следовательно, <a,b> принадлежит r1 <a,c> принадлежит r2. Следовательно, <a,b,c> принадлежит r1 NJ r2. Значит, <a,b,c> принадлежит r. По определению A->>B|C.

Доказательство необходимости условия теоремы.

1)Предположим, что <a,b,c> принадлежит r , следовательно, <a,b> принадлежит r1 <a,c> принадлежит r2. Следовательно, <a,b,c> принадлежит r1 NJ r2.

2)Из того, что <a,b,c> принадлежит r1 NJ r2, следует, что <a,b> принадлежит r1 <a,c> принадлежит r2. Значит, существуют такие <a,b,c’> и <a,b’,c>, принадлежащие r, что <a,b,c> также принадлежит r (т.к. существует многозначная зависимость A->>B|C)

Конец доказательства.

 

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



 

(прим. Доказательства леммы и теоремы взяты из лекций Маши)


 

Многозначные зависимости. Аномалии, возникающие из-за наличия MVD. Пример декомпозиции, решающий проблему (на чем основывается). 4НФ. Нетривиальная и тривиальная многозначные зависимости.

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

Чтобы перейти к вопросам дальнейшей нормализации, рассмотрим еще одну возможную (четвертую) интерпретацию переменной отношения СЛУЖ_ПРО_ЗАДАН. Предположим, что каждый служащий может участвовать в нескольких проектах, но в каждом проекте, в котором он участвует, им должны выполняться одни и те же задания. Возможное значение четвертого варианта переменной отношения СЛУЖ_ПРО_ЗАДАН показано на рис. 9.1.

Рис. 9.1. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (четвертый вариант)


Просмотров 508

Эта страница нарушает авторские права




allrefrs.ru - 2021 год. Все права принадлежат их авторам!