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

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 11Следующая ⇒

ρ =(R 1... R n)

Алгоритм:

1) построить условно-неизбыточное покрытие (УНП), взять H =∅;

2) каждую ФЗ из УНП разбить на совокупность ФЗ с одним атрибутом в правой части,

то есть заменить

X → A 1 A 2... A k

на

X → A 1, X → A 2,..., X → A k.

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

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

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

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

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

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

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

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

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

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

Пример 1

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

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

Смотрим:

1)

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

2)

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

3)

A → B, AB ⊆ R 1

A → C, AC ⊈ R 2, H =(A → C)

B → C, BC ⊆ R 2

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

5)

H не пустое.

6)

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

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

Пример 2

Пусть R =(A, B, C), ρ =(AB, AC)=(R 1, R 2) и 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 +, значит ρ не обладает сохранением ФЗ.

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

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

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

Пусть

R =(A 1... A n) - некоторая схема отношения.

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

Тогда

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

· X → A 1... A n ∈ F +

· ∀ Z ⊂ X, Z → A 1... A n ∉ 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 → DC, BC → 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 ≠ R

(BD)+= BD ≠ R

(BC)+= BCAD = R, X 2= 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, X 0= 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, X 2= AC, i =2

3)

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

2)

C += C ≠ R

A += AB ≠ R

3)

i не возросло, значит X = X 2= 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)=(R 1, R 2)

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

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

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

· Y, X → Y, Y ↛ X

Y = B, A → B, B ↛ A

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

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

Теперь покажем 3НФ у R 2=(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

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

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте