X→Y⊆F+

Y⊆(A1,A2...An) и таких подмножеств может быть 2n

Поэтому "в лоб" замыкание F+ никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ X→Y к F+

Для этого применяется замыкание множества атрибутов.

Пусть R - универсальная схема отношения, а X - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов X+ называется совокупность атрибутов Ai1,Ai2...Aik таких, что X→Ai1,X→Ai2...X→Aik

Алгоритм построения

Алгоритм является итерационной процедурой.

1. полагаем i=0 и X+0=X, а X+i - замыкание множества атрибутов на i-том шаге;

2. X+i+1=X+i⋃V, где V - такое множество атрибутов в F, что существует ФЗ Y→Z, где Y⊆X+i, V⊆Z;

3. если X+i+1=X+i, то X+=X+i, иначе i=i+1 и возвращаемся в пункт 2.

Пример построения

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

F=(AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG)

X=BD

Надо построить X+:

1) i=0, X+0=BD

2)

Получили, что X+4=X+3, а значит X+=X+3=BDEGCA

Это означает, что имеют место следующие ФЗ: BD→B, BD→D, BD→E, BD→G, BD→C, BD→A, и все они ⊆F+

Короче, чтобы проверить X→Y⊆F+, необходимо построить X+

Лекция №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НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:

  • избыточность;

  • потенциальная противоречивсть;

  • аномалия обновления;

  • аномалия удаления.

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

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

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

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

R=(A,B,C)

ρ=(AB,BC)=(R1,R2)

F=(A→B)

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

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

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

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

R=(A,B,C)

ρ=(AB,AC)=(R1,R2)

F=(A→B)

Возьмём тот же экземпляр:

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

Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.

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

ρ=(R1...Rn)

R=(A1...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)=(R1,R2)

F=(A→B)

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

1)

2)

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

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

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

ρ=(AB,ACDPS,BCPS,DEF)=(R1,R2,R3,R4)

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

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

1)

2)

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

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

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

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

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

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

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

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

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

• R1⋂R2→R1−R2 (1)

• R1⋂R2→R2−R1 (2)

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

1)

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

2)

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

r=ΠR1(r)⋈ΠR2(r) (3)

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

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

1) bi≠bj, i≠j;

2) некоторые bi совпадают, b1=b2.

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

• a1=a2;

• c1=c2.

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

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

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

• для варианта bi≠bj имеют место обе ФЗ : (1) и (2);

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

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

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

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

R1⋂R2=A

R1−R2=B

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

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

Пусть дана схема БД ρ=(R1...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)=(R1,R2)

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

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

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

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

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

B+=B, C∉B+

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

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

F=(A→B,B→C)

ρ=(AB,BC)=(R1,R2)

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

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

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

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

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

ρ=(R1...Rn)

Алгоритм:

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

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

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