Методические указания По выполнению курсовой работы Для обучающихся по направлению

Определение:

Естественное соединение (англ. natural join) отношений R1

и R2: R1⋈R2={r1∪r2|r1∈R1,r2∈R2∧πY(r1)=πY(r2)} — отношение с заголовком {X,Y,Z} и телом, состоящим из всех таких кортежей {Хi:хi, Yj:yj, . . . , Zk:zk}, что любой из этих кортежей присутствует и в отношении R1, со значением xi атрибута Хi и значением yj атрибута Yj, и в отношении R2, со значением yi атрибута Yi и значением zk атрибута Zk

.

• 
  Можно понимать как соединение по совпадающим атрибутам
  
• 
  Коммутативно: R1⋈R2=R2⋈R1
  

  Ассоциативно: (R1⋈R2)⋈R3=R1⋈(R2⋈R3)

• 
  

Декомпозиция

Процедура нормализации предусматривает разбиение, или декомпозицию, данной переменной отношения на другие переменные отношения, причем декомпозиция должна быть обратимой, т.е. выполняться без потерь информации, то есть, соединение отношений, полученных при декомпозиции множества, должно давать исходное отношение Декомпозиция отношения R
на множества атрибутов A и B: R(A,B)=πA(R)⋈πB(R)

Пример корректной декомпозиции

Проекции на CId Phone и Lecturer Phone	Соединение CId Lecturer и Lecturer Phone

Пример некорректной декомпозиции

При обратном соединении полученных отношений исходное отношений не было восстановлено — появились записи, которых не было ⇒ декомпозиция некорректна.

Проекции на CId Phone и Lecturer Phone	Соединение CId Phone и Lecturer Phone

Теорема Хита

Теорема Хита утверждает, что если некоторая декомпозиция выполняется в соответствии с определенной функциональной зависимостью, то она будет выполнена без потерь.

Теорема (Хит):

Пусть R(XYZ)

является отношением, где X, Y и Z — неперескающиеся множества атрибутов. Если R удовлетворяет функциональной зависимости X→Y, то R равно соединению его проекций по атрибутам X, Y и X, Z: R=πXY(R)⋈πXZ(R)

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

▹

Докажем равенство в обе стороны: 1. Докажем, что исходное отношение R

— подмножество соединения проекций.
Рассмотрим произвольный кортеж r
из отношения R
.
Для проекций кортежа r
на XY и XZ выполняетя: πXY(r)∈πXY(R),πXZ(r)∈πXZ(R)
.
Из этого следует, что r
— подмножество соединения проекций ⇒∀r∈R:r∈πXY(R)⋈πXZ(R)
.
2. Докажем, что любой кортеж полученного соединения является кортежем отношения R
.
Рассмотрим кортеж (x,y,z)
, принадлежащий соединению πXY(R)⋈πXZ(R)
Для того, чтобы (x,y,z)
был в соеденении, необходимо, чтобы существовали кортежи (x,y)∈πXY(R) и (x,z)∈πXZ(R)
Из (x,z)∈πXZ(R)
следует, что существует кортеж (x,y′,z)∈R для некоторого y′. Это означает, что должен существовать кортеж (x,y′)∈πXY(R)
Поскольку X→Y, существует единственный y:(x,y)∈πXY(R)⇒y=y′⇒(x,y,z)∈R

◃

Доказательсто первого пункта не опирается на наличие функциональной зависимости ⇒ справедливо следствие:
Следствие Исходное отношение R
всегда является подмножеством соединения отношений, полученных при декомпозиции.

Заключение

В этой работе было введено понятие функциональной зависимости и исследовались важные свойства функциональных зависимостей. Одна из целей состояла в том, чтобы на основе некоторого множества функциональных зависимостей суметь построить минимальное эквивалентное множество функциональных зависимостей. Мы начали обсуждение с понятия замыканий множества функциональных зависимостей и аксиом Амстронга, теоретически позволяющих построить такое замыкание. Замыкание множества функциональных зависимостей содержит все функциональные зависимости, выводимые из функциональных зависимостей заданного множества. Рассмотренный далее алгоритм построения замыкания множества атрибутов над заданным множеством функциональных зависимостей упрощает задачу, позволяя определить принадлежность заданной функциональной зависимости к замыканию заданного множества функциональных зависимостей без потребности в реальном построении замыкания.
Далее мы занялись покрытиями множеств функциональных зависимостей и минимальными множествами функциональных зависимостей. Наиболее важным результатом этой части работы является доказательство существования и наметки алгоритма построения минимального покрытия заданного множества функциональных зависимостей – минимального множества функциональных зависимостей, эквивалентного исходному множеству.
Наконец, последний раздел лекции был посвящен критерию декомпозиции отношения без потерь, т. е. такому способу проецирования заданного отношения на два отношения, при котором результат естественного соединения проекций в точности совпадает с исходным отношением. Достаточное (и очень естественное) условие декомпозиции без потерь обеспечивает теорема Хита.