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

Пусть дана схема БД ρ =(R 1... Rn) и F - множество ФЗ.

Проекцией F на Ri называется такое множество ФЗ, принадлежащее F +, что XY ⊆ Ri, Π Ri (F)

Схема ρ обладает свойством сохранения ФЗ, если:

(⋃ ni =1Π Ri (F))+= F + - ФЗ могут быть декомпозированны по схеме отношений (тогда проверку надо будет выполнять только в рамках отдельных таблиц при включении новой записи).

Пример схемы БД без свойства сохранения ФЗ

R =(A, B, C) - универсальная схема отношений.

F =(A → B, B → C)

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

Надо доказать, что ρ не обладает свойством сохранения ФЗ.

Первая проекция: Π R 1(F)= F 1=(A → A, B → B, AB → A, AB → B, AB → AB, A → B, A → AB)

Вторая проекция: Π R 2(F)= F 2=(A → A, C → C, AC → A, AC → C, AC → AC, A → C, A → AC)

B → C ∈ F + по определению.

B → C ∉(F 1⋃ F 2)+ - не работает, так что эта БД не обладает свойством сохранения ФЗ.

B += B, C ∉ B +

Пример схемы БД со свойством сохранения ФЗ

R =(A, B, C) - универсальная схема отношений.

F =(A → B, B → C)

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

Надо доказать, что ρ обладает свойством сохранения ФЗ.

Первая проекция: Π R 1(F)= F 1=(тривиальные ФЗ, A → B, A → AB)

Вторая проекция: Π R 2(F)= F 2=(тривиальные ФЗ, B → C, B → BC)

(F 1⋃ F 2)+=(тривиальные ФЗ, A → B, A → AB, B → C, B → BC, A → C, A → AC), а это и есть по определению само F +, что и доказывает, что данная схема БД обладает свойством сохранения ФЗ.

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

ρ =(R 1... Rn)

Алгоритм:

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

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

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

X → A 1 A 2... Ak

на

X → A 1, X → A 2,..., 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)=(R 1, R 2) и F =(A → B, B → C)

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

Смотрим:

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

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

A → B, AB ⊆ R 1

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

B → C, BC ⊆ R 2

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

H не пустое.

выполняется ли 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))

H не пустое.

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

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

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

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

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

Пусть

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

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

Тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

i =0, X 0= ABCD

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

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

(CD)+= CD ≠ R

(BD)+= BD ≠ R

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

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

C += C ≠ R

B += B ≠ R

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НФ обладает этими аномалиями. Хотя, встречаются они редко. Вот они: