X→A1A2...Ak

на

X→A1, X→A2, ..., X→Ak.

Обозначить полученную ФЗ как G;

3) выбрать очередную ФЗ из G. Найти такую схему отношения Ri, для которой справедливо включение XA⊆Ri.

Если такой схемы отношений не существует, то поместить ФЗ X→A в множество H;

4) если все ФЗ из G рассмотрены, то перейти к следующему пункту, иначе к предыдущему;

5) если H пусто, то завершить алгоритм. ρ обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту;

6) просмотреть все ФЗ из H. Если какая-либо ФЗ X→A∈H не выводится из множества G−H, то завершить алгоритм. ρ не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда ρ обладает свойством сохранения ФЗ.

Лекция №5 - Третья нормальная форма

Свойства "хорошей" схемы БД

Свойство сохранения ФЗ

Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ

Пример 1

Пусть R=(A,B,C), ρ=(AB,BC)=(R1,R2) и F=(A→B,B→C)

Обладает ли ρ сохранением ФЗ?

Смотрим:

1)

H=∅, УНП=(A→BC,B→C)

2)

G=(A→B,A→C,B→C)

3)

A→B, AB⊆R1

A→C, AC⊈R2, H=(A→C)

B→C, BC⊆R2

4) пропускаем, так как не выполнилось условие в 3)

5)

H не пустое.

6)

выполняется ли A→C∈(G−H)+=(A→B,B→C)+

A+=ABC, C∈A+, значит ρ обладает сохранением ФЗ.

Пример 2

Пусть R=(A,B,C), ρ=(AB,AC)=(R1,R2) и F=(A→B,B→C)

Обладает ли ρ сохранением ФЗ?

1-4)

H=∅, УНП=(A→BC,B→C)

H=(B→C))

5)

H не пустое.

6)

выполняется ли B→C∈(G−H)+=(A→BC)+

B+=B, C∉B+, значит ρ не обладает сохранением ФЗ.

Ключ схемы отношения

Ключ схемы отношения – это подмножество исходной схемы, состоящая из одного или нескольких атрибутов, которые задают уникальность значений в кортежах отношений.

Если атрибут Ai∈R входит в какой-либо ключ схемы отношения R, то он называется первичным. А если не входит ни в один, то называется непервичным.

Пусть

R=(A1...An) - некоторая схема отношения.

F - множество ФЗ.

Тогда

X⊆R называется ключом схемы, если выполняются:

• X→A1...An∈F+

• ∀Z⊂X, Z→A1...An∉F+. То есть X содержит минимальное число атрибутов, для которых выполняется предыдущее свойство.

Алгоритм построения ключа

Базируется на определении ключа. Позволяет построить только один ключ.

1)

i=0, X0=A1...An

2)

цикл по атрибутам Aj в Xi

Если (Xi−Aj)+=R, то Xi+1=Xi−Aj, i=i+1 и выйти из цикла;

иначе продолжить цикл

3)

если i возросло, то перейти к шагу 2);

иначе X=Xi - это найденный ключ.

Пример построения ключа

Пусть R=(A,B,C,D), F=(AB→DC,BC→AD)

Надо построить ключ.

1)

i=0, X0=ABCD

2)

(X0−A)+=(BCD)+=BCDA=R, значит X1=BCD, i=1

3)

i, как видим, возросло, значит опять 2)

2)

(CD)+=CD≠R

(BD)+=BD≠R

(BC)+=BCAD=R, X2=BC, i=2

3)

i, как видим, возросло, значит опять 2)

2)

C+=C≠R

B+=B≠R

3)

i, как видим, не возросло. Значит, X=BC - ключ. Но не единственный, X=AB - тоже ключ, просто у нас получился сначала этот.

Значит, A,B,C - первичные атрибуты, а D - непервичный.

Третья нормальная форма

Отношение находится в 3НФ, если не существует тройки:

• ключа X,

• Y⊆R,

• непервичного атрибута H∉Y,

для которой выполняются:

• X→Y∈F+;

• Y→H∈F+;

• Y→X∉F+.

Если такую тройку можно найти, то схема не находится в 3НФ.

Если схема отношения находится в 3НФ, то в большинстве случаев эта схема отношения не обладает аномалиями. Но существуют условия, когда схема в 3НФ обладает этими аномалиями. Хотя, встречаются они редко. Вот они:

• схема отношения имеет 2 или больше ключей,

  • и любые 2 из них являются составными,

    • и имеют общий атрибут.

Пример 1

Пусть R=(A,B,C,D), F=(A→B,AC→D) и ρ=R

Доказать, что это отношение не находится в 3НФ.

Доказываем:

1)

i=0, X0=ABCD

2)

(BCD)+=BCD≠R

(ACD)+=ACDB=R, X=ACD, i=1

3)

i, как видим, возросло, значит опять 2)

2)

(CD)+=CD≠R

(AD)+=ADB≠R

(AC)+=ACBD=R, X2=AC, i=2

3)

i, как видим, возросло, значит опять 2)

2)

C+=C≠R

A+=AB≠R

3)

i не возросло, значит X=X2=AC - это ключ. Причём, можно показать, что он единственный.

Теперь предполагаем тройку:

• X=AC

• Y=A⊆R

• H=B - непервичный атрибут, B∉X

Проверям три условия для неё:

1)

X→Y, так как AC→A по 1 аксиоме Армстронга;

2)

Y→H, A→B по условию;

3)

Y↛X, A↛AC

A+=AB, AC⊈A+

Таким образом, найдена тройка, для которой выполняются все три условия, а значит отношение не находится в 3НФ.

Пример 2

Декомпозируем эту схему отношения R на две схему отношений.

R=(A,B,C,D)

F=(A→B,AC→D)

ρ=(AB,ACD)=(R1,R2)

Если R1 и R2 находятся в 3НФ, то значит всё ρ будет в 3НФ.

Сначала покажем 3НФ у R1=(AB), F=(A→B):

• X=A - выберем ключом

• Y, X→Y, Y↛X

Y=B, A→B, B↛A

• невозможно подобрать непервичный атрибут H∉Y, потому что непервичным может быть только B.

Таким образом, нельзя подобрать необходимую тройку. Значит, R1 находится в 3НФ.

Теперь покажем 3НФ у R2=(ACD), F=(AC→D):

• X=AC - выберем ключом

• Y, X→Y, Y↛X

а) A - что-то как-то не выполняется;

б) C - что-то как-то не выполняется;

в) D - что-то как-то не выполняется;

г) AD - что-то как-то не выполняется;

д) CD - что-то как-то не выполняется.

• H∉Y, H=D

а) Y=A, Y↛H

б) Y=C, Y↛H

в-д) H∈Y

Не удалось подобрать нужную тройку, так что R2 тоже находится в 3НФ.

Лекция №6 - Алгоритм построения хорошей БД

Третья нормальная форма

Пример аномалий у 3НФ

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 - ключ.

Пример:

R1=AB, F1=(A→B,B→A), A - ключ, B - ключ.

или

R2=ACD, F2=(AC→D), AC - ключ.

Алгоритм синтеза "хорошей" БД

Пусть U - универсальная схема отношения (множество всех атрибутов предметной области) и F - множество ФЗ.

Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно.

Алгоритм:

1. построить УНП для F;

2. если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из U, то добавить в УНП тривиальную ФЗ U→∅. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;

3. привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);

4. разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости Xi→Yi и Xj→Yj будем называть эквивалентными, если XiYi=XjYj. Далее введём обозначение Kr=XiYi - множество атрибутов в левой и правой частях ФЗ r-того класса эквивалентности;

5. построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: j-ый узел соединяем снизу с i-ым узлом, если Kj⊂Ki. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;

6. из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:

   1. удалить из класса эквивалентности лишние ФЗ;

   2. если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;

   3. если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) атрибуты справа у ФЗ, расположенных выше в графе иерархии;

   4. если в результате не удалось выбрать ни одной, то выбрать произвольную;

7. редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:

   1. пусть X→Y - это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;

   2. для тривиальной ФЗ U→∅ атрибуты вычёркиваются слева;

8. исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ U→∅). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;

9. каждую оставшуюся в графе иерархий ФЗ V→W заменить на множество VW. Получившееся множество схем отношений обозначить как ρ;

10. для полученной на предыдущем шаге схемы БД проверить:

    1. обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы U в эту схему;

    2. обладает ли ρ свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию 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)