R =(A, B, C, D) и F =(A → B, B → A, AC → D)
Два ключа:
первый - AC:
(AC)+= ACBD = R
A += AB ≠ R
C += C ≠ R
второй - BC:
(BC)+= BCAD = R
B += BA ≠ R
Покажем, что в этом случае R находится в 3НФ:
1)
неключевой атрибут H, H = D
2)
Y → H, H ∉ Y, Y = AC
3)
X = BC, X = AC
Нельзя подобрать нужную тройку, потому R находится в 3НФ. Однако, отношение всё равно обладает аномалиями:
- избыточности: наименование поставщика повторяется для каждой поставляемой делали;
- противоречивости при изменении наименования поставщика надо изменить его во всех записях, куда оно входит;
- включения: нельзя включить информацию о поставщике, если он ничего не поставляет;
- удаления: при удалении детали удаляется информация о поставщике.
Для устранения этого вводится усиленная 3НФ - Бойса-Кодда.
Нормальная форма Бойса-Кодда
ФЗ X → Y является неприводимой, если для любого подмножества Z ⊂ X выполняется Z ↛ Y или Z → Y ∉ F +
Пусть есть отношение R и F включает в себя нетривиальные неприводимые ФЗ. Тогда отношение R находится в нормальной форме Бойса-Кодда, если для любого X → Y ∈ F => X - ключ.
|
|
Пример:
R 1= AB, F 1=(A → B, B → A), A - ключ, B - ключ.
или
R 2= ACD, F 2=(AC → D), AC - ключ.
Алгоритм синтеза "хорошей" БД
Пусть U - универсальная схема отношения (множество всех атрибутов предметной области) и F - множество ФЗ.
Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно.
Алгоритм:
- построить УНП для F;
- если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из U, то добавить в УНП тривиальную ФЗ U →∅. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;
- привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);
- разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости Xi → Yi и Xj → Yj будем называть эквивалентными, если XiYi = XjYj. Далее введём обозначение Kr = XiYi - множество атрибутов в левой и правой частях ФЗ r -того класса эквивалентности;
- построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: j -ый узел соединяем снизу с i -ым узлом, если Kj ⊂ Ki. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;
- из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:
- удалить из класса эквивалентности лишние ФЗ;
- если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;
- если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) атрибуты справа у ФЗ, расположенных выше в графе иерархии;
- если в результате не удалось выбрать ни одной, то выбрать произвольную;
- редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:
- пусть X → Y - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;
- для тривиальной ФЗ U →∅ атрибуты вычёркиваются слева;
- исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ U →∅). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;
- каждую оставшуюся в графе иерархий ФЗ V → W заменить на множество VW. Получившееся множество схем отношений обозначить как ρ;
- для полученной на предыдущем шаге схемы БД проверить:
- обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы U в эту схему;
- обладает ли ρ свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию X → Y ∉Π Ri (F), для построения новых схем отношений, то есть добавить в ρXY.
После выполнения всех шагов полученная схема ρ:
|
|
- обладает свойством соединения без потерь;
- обладает свойством сохранения ФЗ;
- находится в 3НФ или НФБК;
- содержит минимальное число схем отношений.
Пример
U =(поставщик,фирма,деталь,количество)=(A, B, C, D)
F =(A → B, B → A, AC → D, BC → D)
Строим ρ:
1)
УНП=(A → B, B → A, AC → BD, BC → AD)
2)
пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из U
3)
уменьшить число атрибутов не удаётся
4)
1 класс: A → B, B → A, K 1= AB
2 класс: AC → BD, BC → AD, K 2= ABCD
5)
6)
для K 2:
способ 1 - как во втором семинаре
можно ли вывести AC → BD ∈(BC → AD)+?
(AC)+= AC, BD ⊈(AC)+, значит нельзя
можно ли вывести BC → AD ∈(AC → BD)+?
(BC)+= BC, AD ⊈(BC)+, значит нельзя
способ 2 - вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.
AC → B
BC → A
выше по иерархии ничего нет, выбираем BC → AD
нет лишних ФЗ, потому...