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

ρ =(R 1... R n)

R =(A 1... A n)

1) построить таблицу T:

И заполнить таблицу T по правилу: если A j ∈ R i, то T ij = a, иначе T ij = b i

2) изменить таблицу T - циклически просматривать ФЗ из F в любом порядке, и для очередной ФЗ X → Y ∈ F выполнить следующие действия:

• найти в таблице T строки, совпадающие по атрибутам X (по левой части);
• если хотя бы в одной такой строке значение атрибута A m ∈ Y = a, то во всех найденных строках присвоить A m = a, иначе присвоить A m = b i (i - номер одной из найденных строк), b i должно быть одинаково во всех указанных строках);
• выполнить предыдущие два пункта для всех атрибутов A l ∈ Y;
• выполнить предыдущие три пункта для всех ФЗ из F, циклически их просматривая.

3) алгоритм останавливается, если при очередном просмотре ФЗ из F:

• не произошло никаких изменений в таблице T;
• какая-нибудь строка в T не стала состоять сплошь из символов a (наличие такой строки и говорит о выполнении свойства соединения без потерь).

Пример

Пусть R =(A, B, C)

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

F =(A → B)

Доказать, что ρ обладает свойством соединения без потерь.

1)

2)

Получили строку, сплошь состоящую из a. Значит ρ обладает свойством соединения без потерь.

Другой пример

Пусть R =(A, B, C, D, E, F, P, S)

ρ =(AB, ACDPS, BCPS, DEF)=(R 1, R 2, R 3, R 4)

F =(B → C, D → EF, B → PS, A → CDPS, AP → S)

Доказать, что ρ обладает свойством соединения без потерь.

1)

2)

первый просмотр:

второй просмотр:

Вот и получили строку, сплошь состоящую из a. Значит ρ обладает свойством соединения без потерь.

 

Лекция №4 - Хорошая схема БД - Сохранение ФЗ

 

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

Соединение без потерь

Теорема о свойстве соединения без потерь

Пусть ρ =(R 1, R 2) и F - множество ФЗ.

ρ обладает свойством соединения без потерь тогда и только тогда, когда выполняется хотя бы одно из:

• R 1⋂ R 2→ R 1− R 2 (1)
• R 1⋂ R 2→ R 2− R 1 (2)

Доказательство

1)

Получили строку, сплошь состоящую из a.

2)

Теперь докажем обратное, что если ρ обладает соединением без потерь, то имеет место одна из ФЗ: (1) или (2).

r =Π R 1(r)⋈Π R 2(r) (3)

r - это R 1⋃ R 2 (экземпляр универсальной схемы отношений)

Если выполняется равенство (3), то возможны два варианта:

1) b i ≠ b j, i ≠ j;

2) некоторые b i совпадают, b 1= b 2.

Тогда для выполнения равенства (3) необходимо, чтобы выполнялось одно из двух:

· a 1= a 2;

· c 1= c 2.

2 и 3 кортежи - лишние. Чтобы они не были лишними, они должны совпадать с одним из других кортежей, чтобы их можно было вычеркнуть.

Предположим, a 1= a 2, тогда что-то там насовпадало и 2 и 3 кортежи можно вычеркнуть.

Аналогичные рассуждения можно провести для случая, когда c 1= c 2, но тогда получаем:

· для варианта b i ≠ b j имеют место обе ФЗ: (1) и (2);

· для варианта с некоторыми совпадающими b i работает либо (1), либо (2).

Всё, теорема доказана.

Следствие из теоремы

Пусть R 1 и R 2 - это сущности БД и они связаны между собой. Тогда схема БД обладает соединением без потерь, если общий атрибут R 1 и R 2 содержит ключ одной из этих схем отношений.

R 1⋂ R 2= A

R 1− R 2= B

R 1⋂ R 2→ R 1− R 2, потому что A → B, так как является ключом.

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

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

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

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

(⋃ ni =1Π R i (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 +, что и доказывает, что данная схема БД обладает свойством сохранения ФЗ.