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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



ρ =(R 1... R n)

Алгоритм:

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

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

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

XA 1 A 2... A k

на

XA 1, XA 2,..., XA k.

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

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

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

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

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

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


 

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

 

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

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

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

Пример 1

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

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

Смотрим:

1)

H =∅, УНП=(ABC, BC)

2)

G =(AB, AC, BC)

3)

AB, ABR 1

AC, ACR 2, H =(AC)

BC, BCR 2

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

5)

H не пустое.

6)

выполняется ли AC ∈(GH)+=(AB, BC)+

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

Пример 2

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

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

1-4)

H =∅, УНП=(ABC, BC)

H =(BC))

5)

H не пустое.

6)

выполняется ли BC ∈(GH)+=(ABC)+

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

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

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

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

Пусть

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

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

Тогда

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

· XA 1... A nF +

· ∀ ZX, ZA 1... A nF +. То есть X содержит минимальное число атрибутов, для которых выполняется предыдущее свойство.

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

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

1)

i =0, X 0= A 1... A n

2)

цикл по атрибутам A j в X i

Если (X iA j)+= R, то X i +1= X iA j, i = i +1 и выйти из цикла;

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

3)

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

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

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

Пусть R =(A, B, C, D), F =(ABDC, BCAD)

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

1)

i =0, X 0= ABCD

2)

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

3)

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

2)

(CD)+= CDR

(BD)+= BDR

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

3)

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

2)

C += CR

B += BR

3)

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

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

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

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

  • ключа X,
  • YR,
  • непервичного атрибута HY,

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

  • XYF +;
  • YHF +;
  • YXF +.

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

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

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

Пример 1

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

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

Доказываем:

1)

i =0, X 0= ABCD

2)

(BCD)+= BCDR

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

3)

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

2)

(CD)+= CDR

(AD)+= ADBR

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

3)

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

2)

C += CR

A += ABR

3)

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

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

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

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

1)

XY, так как ACA по 1 аксиоме Армстронга;

2)

YH, AB по условию;

3)

YX, AAC

A += AB, ACA +

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

Пример 2

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

R =(A, B, C, D)

F =(AB, ACD)

ρ =(AB, ACD)=(R 1, R 2)

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

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

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

· Y, XY, YX

Y = B, AB, BA

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

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

Теперь покажем 3НФ у R 2=(ACD), F =(ACD):

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

· Y, XY, YX

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

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

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

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

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

· HY, H = D

а) Y = A, YH

б) Y = C, YH

в-д) HY

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


 



Поделиться:


Последнее изменение этой страницы: 2021-04-12; просмотров: 73; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.146.105.137 (0.021 с.)