R =(A, B, C)
ρ =(AB, AC)=(R 1, R 2)
F =(A → B)
Возьмём тот же экземпляр:
Полученное соединение будет равняться r:
Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.
Алгоритм проверки схемы БД на свойство соединения без потерь
ρ =(R 1... Rn)
R =(A 1... An)
1) построить таблицу T:
И заполнить таблицу T по правилу: если Aj ∈ Ri, то Tij = a, иначе Tij = bi
2) изменить таблицу T - циклически просматривать ФЗ из F в любом порядке, и для очередной ФЗ X → Y ∈ F выполнить следующие действия:
- найти в таблице T строки, совпадающие по атрибутам X (по левой части);
- если хотя бы в одной такой строке значение атрибута Am ∈ Y = a, то во всех найденных строках присвоить Am = a, иначе присвоить Am = bi (i - номер одной из найденных строк), bi должно быть одинаково во всех указанных строках);
- выполнить предыдущие два пункта для всех атрибутов Al ∈ 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) bi ≠ bj, i ≠ j;
2) некоторые bi совпадают, 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, но тогда получаем:
· для варианта bi ≠ bj имеют место обе ФЗ: (1) и (2);
· для варианта с некоторыми совпадающими bi работает либо (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, так как является ключом.