Лекция №3 - Хорошая схема БД - Соединение без потерь

Пусть F и G - два множества ФЗ.

G называется покрытием F, если имеет место равенство G += F +

Существуют различные виды покрытий. Но мы рассмотрим только один - условно-неизбыточное покрытие.

Алгоритм построения условно-неизбыточного покрытия

1) если в множестве ФЗ F встречаются ФЗ с одинаковой левой частью X, то следует объединить эти ФЗ в одну ФЗ. Это следует из леммы объединения. Получившееся множество ФЗ обозначим G;

2) для каждой ФЗ X → Y из G заменить её на X → X +− X;

После выполнения 1) и 2) получаем замыкание G += F +

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

1)

Докажем, что если ФЗ X → Y ∈ F (из этого следует, что Y ⊆ X + (1) по определению замыкания множества аттрибутов), то эта ФЗ принадежит G +

По построению G имеет место ФЗ: X → X +− X (2)

Пополним эту ФЗ: X →(X +− X)⋃ X, получится, что X → X + (3)

Теперь по первой аксиоме Армстронга из (1) имеем X +→ Y (4)

Значит, X → Y ∈ G +, по третьей аксиоме Армстронга, исходя из (3) и (4).

2)

Докажем обратное, что если X → Y ∈ G, то X → Y ∈ F +

По построению G имеем: Y = X +− X (5)

Для F имеем:

X → X + (по определению) (6)

X +→ X +− X (1 аксиома Армстронга, так как X +− X ⊆ X +) (7)

X → X +− X = Y (3 аксимома Армстронга из (6)и (7), и по равенству (5))

В итоге получили X → Y ∈ F +.

Теорема доказана.

Пример

УСО: R =(A, B, C)

Множество ФЗ: F =(A → B, B → A, C → A, A → C, B → C)

1)

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

2)

A += ABC, A +− A = BC

B += BAC, B +− B = AC

C += CAB, C +− C = AB

Тогда G =(A → BC, B → AC, C → AB) будет являться УНП.

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

"Хорошая", но не оптимальная. Должна обладать следующими свойствами:

• соединение без потерь;
• сохранение ФЗ;
• каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
• избыточность;
• потенциальная противоречивсть;
• аномалия обновления;
• аномалия удаления.

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

Чтобы схема БД обладала свойством соединения без потерь, необходимо, чтобы хотя бы одна из таблиц содержала ключ универсальной схемы отношений.

Пусть ρ =(R 1... Rn) - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения r из R справедливо равенство: r =Π R 1(r)⋈Π R 2(r)⋈...⋈Π Rn (r), где Π Ri (r) - это проекция экземпляра отношения r на множество атрибутов Ri

Пример БД, не обладающей свойством соединения без потерь

R =(A, B, C)

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

F =(A → B)

Достаточно привести пример экземпляра r, для которого равенство не выполняется:

Полученное соединение не будет равняться r:

Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.