ТОРА (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НФ.