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

Причиной отмеченных аномалий является то, что в требованиях 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. Возможное значение переменной отношения СЛУЖ_ПРО_ЗАДАН (четвертый вариант)