ТОРА (9) - Лекция №5 - Третья нормальная форма

...начало

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

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

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

Пример 1

Пусть $$R = (A, B, C)$$, $$\rho = (AB, BC) = (R_1, R_2)$$ и $$F = (A\rightarrow B, B\rightarrow C)$$

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

Смотрим:

1)

$$H=\varnothing$$, $$УНП = (A\rightarrow BC, B\rightarrow C)$$

2)

$$G = (A\rightarrow B, A\rightarrow C, B\rightarrow C)$$

3)

$$A\rightarrow B$$, $$AB\subseteq R_1$$

$$A\rightarrow C$$, $$AC\nsubseteq R_2$$, $$H=(A\rightarrow C)$$

$$B\rightarrow C$$, $$BC\subseteq R_2$$

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

5)

$$H$$ не пустое.

6)

выполняется ли $$A\rightarrow C\in(G-H)^+ = (A\rightarrow B, B\rightarrow C)^+$$

$$A^+=ABC$$, $$C\in A^+$$, значит $$\rho$$ обладает сохранением ФЗ.

Пример 2

Пусть $$R = (A, B, C)$$, $$\rho = (AB, AC) = (R_1, R_2)$$ и $$F = (A\rightarrow B, B\rightarrow C)$$

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

1-4)

$$H = \varnothing$$, $$УНП = (A\rightarrow BC, B\rightarrow C)$$

$$H = (B\rightarrow C))$$

5)

$$H$$ не пустое.

6)

выполняется ли $$B\rightarrow C\in(G - H)^+ = (A\rightarrow BC)^+$$

$$B^+ = B$$, $$C\notin B^+$$, значит $$\rho$$ не обладает сохранением ФЗ.

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

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

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

Пусть

$$R = (A_1 ... A_n)$$ - некоторая схема отношения.

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

Тогда

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

• $$X\rightarrow A_1 ... A_n\in F^+$$
• $$\forall Z\subset X$$, $$Z\rightarrow A_1 ... A_n\notin F^+$$. То есть $$X$$ содержит минимальное число атрибутов, для которых выполняется предыдущее свойство.

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

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

1)

$$i = 0$$, $$X_0 = A_1 ... A_n$$

2)

цикл по атрибутам $$A_j$$ в $$X_i$$

Если $$(X_i - A_j)^+ = R$$, то $$X_{i+1} = X_i - A_j$$, $$i = i + 1$$ и выйти из цикла;

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

3)

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

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

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

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

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

1)

$$i = 0$$, $$X_0 = ABCD$$

2)

$$(X_0 - A)^+ = (BCD)^+ = BCDA = R$$, значит $$X_1 = BCD$$, $$i = 1$$

3)

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

2)

$$(CD)^+ = CD\neq R$$

$$(BD)^+ = BD\neq R$$

$$(BC)^+ = BCAD = R$$, $$X_2 = BC$$, $$i = 2$$

3)

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

2)

$$C^+ = C\neq R$$

$$B^+ = B\neq R$$

3)

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

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

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

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

• ключа $$X$$,
• $$Y\subseteq R$$,
• непервичного атрибута $$H\notin Y$$,

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

• $$X\rightarrow Y\in F^+$$;
• $$Y\rightarrow H\in F^+$$;
• $$Y\rightarrow X\notin F^+$$.

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

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

• схема отношения имеет 2 или больше ключей,
  • и любые 2 из них являются составными,
    • и имеют общий атрибут.

Пример 1

Пусть $$R = (A, B, C, D)$$, $$F = (A\rightarrow B, AC\rightarrow D)$$ и $$\rho = R$$

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

Доказываем:

1)

$$i = 0$$, $$X_0 = ABCD$$

2)

$$(BCD)^+ = BCD\neq R$$

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

3)

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

2)

$$(CD)^+ = CD\neq R$$

$$(AD)+^ = ADB\neq R$$

$$(AC)^+ = ACBD = R$$, $$X_2 = AC$$, $$i = 2$$

3)

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

2)

$$C^+ = C\neq R$$

$$A^+ = AB\neq R$$

3)

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

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

• $$X = AC$$
• $$Y = A\subseteq R$$
• $$H = B$$ - непервичный атрибут, $$B\notin X$$

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

1)

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

2)

$$Y\rightarrow H$$, $$A\rightarrow B$$ по условию;

3)

$$Y\nrightarrow X$$, $$A\nrightarrow AC$$

$$A^+ = AB$$, $$AC\nsubseteq A^+$$

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

Пример 2

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

$$R = (A, B, C, D)$$

$$F = (A\rightarrow B, AC\rightarrow D)$$

$$\rho = (AB, ACD) = (R_1, R_2)$$

Если $$R_1$$ и $$R_2$$ находятся в 3НФ, то значит всё $$\rho$$ будет в 3НФ.

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

• $$X = A$$ - выберем ключом
• $$Y$$, $$X\rightarrow Y$$, $$Y\nrightarrow X$$

$$Y = B$$, $$A\rightarrow B$$, $$B\nrightarrow A$$

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

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

Теперь покажем 3НФ у $$R_2 = (ACD)$$, $$F = (AC\rightarrow D)$$:

• $$X = AC$$ - выберем ключом
• $$Y$$, $$X\rightarrow Y$$, $$Y\nrightarrow X$$

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

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

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

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

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

• $$H\notin Y$$, $$H = D$$

а) $$Y = A$$, $$Y\nrightarrow H$$

б) $$Y = C$$, $$Y\nrightarrow H$$

в-д) $$H\in Y$$

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