Проектиране на функционални зависимости

атрибути на S.

Нека новата релация е S (A, C, D). За да намерим функционалните зависимости за S изчисляваме покритията на всички подмножества на

{ A, C, D } относно F. Естествено, можем да пропуснем  и { A, C, D}, тъй като от тях не може да се получи нетривиална функционална зависимост. Имаме { A} ⁺ = { A, B, C, D }, { C} ⁺ = { C, D }, { D} ⁺ = { D}.

Така получаваме функционални зависимости A  C, A  D, C  D.

Няма смисъл да разглеждаме надмножества на { A}, тъй като { A} ⁺ съдържа всички атрибути на S. Така остава само { C, D} ⁺ = { C, D}, от което не получаваме нова функционална зависимост.

Окончателно, в S се проектират следните функционални зависимости:

A  C, A  D, C  D.
Аксиоми на Армстронг
Както вече видяхме, чрез алгоритъма за намиране на покритие винаги можем да определим дали дадена функционална зависимост следва от дадено множество от функционални зависимости.

Аксиомите на Армстронг са правила, чрез които може да се извлече всяка функционална зависимост, която следва от дадено множество функционални зависимости. Те са следните:

1. 
   Рефлексивност - ако { B₁, B₂, …, B_m}  { A₁, A₂, …, A_n}, то
   

2. 
   Нарастване – ако A₁ A₂ …A_n  B₁ B₂ …B_m и C₁, C₂, …, C_k са произволни атрибути, то
   

3. 
   Транзитивност – ако A₁ A₂ …A_n  B₁ B₂ …B_m и
   

1. 
   Излишество – информацията безсмислено да се дублира в кортежите.
   
2. 
   Аномалии на обновяването – при обновяване на данните да не са актуализирани всички засегнати кортежи.
   
3. 
   Аномалии на изтриването – при изтриване на данни да се губи друга информация като страничен ефект.
   

Като пример да разгледаме следният екземпляр на релацията Movies, към която е присъединена релацията за връзката StarsIn.

title	year	length	type	studioName	starName
Star Wars	1977	124	color	Fox	Carrie Fisher
Star Wars	1977	124	color	Fox	Mark Hamill
Star Wars	1977	124	color	Fox	Harrison Ford
Mighty Duck	1991	104	color	Disney	Emilio Estevez
Wayne’s World	1992	95	color	Paramount	Dana Carvey
Wayne’s World	1992	95	color	Paramount	Mike Meyers

Тази релация съдържа и трите аномалии:

1. 
   Информацията type, length излишно се дублира.
   
2. 
   Ако обновяваме length на Star Wars, например, трябва да засегнем всичките три кортежа – това увеличава вероятността за грешка.
   
3. 
   Ако трябва да изтрием Emilio Estevez от звездите, които участват във филма Mighty Duck, то трябва да премахнем целият кортеж, което ще доведе до загуба на останалата информация за филма.
   

Тогава тя се декомпозира на две нови релации

S (B₁, B₂, …, B_m) и T (C₁, C₂, …, C_k), ако:

1. 
   { B₁, B₂, …, B_m}  { C₁, C₂, …, C_k} = { A₁, A₂, …, A_n}.
   
2. 
   Кортежите в S са проекции на кортежите на R по B₁, B₂, …, B_m.
   

3. 
   Аналогично, кортежите в T са проекции на кортежите на R по
   

Movies (title, year, length, type, studioName, starName) от по-горе и да я декомпозираме на следните две релации:

Movies1 (title, year, length, type, studioName)

Movies2 (title, year, starName)

Съответният екземпляр на Movies1 ще е следния:

title	year	length	type	studioName
Star Wars	1977	124	color	Fox
Mighty Duck	1991	104	color	Disney
Wayne’s World	1992	95	color	Paramount

Съответният екземпляр на Movies2 ще е следния:

title	year	starName
Star Wars	1977	Carrie Fisher
Star Wars	1977	Mark Hamill
Star Wars	1977	Harrison Ford
Mighty Duck	1991	Emilio Estevez
Wayne’s World	1992	Dana Carvey
Wayne’s World	1992	Mike Meyers

По този начин елиминираме всички аномалии. Действително:

1. 
   Няма излишество на информация – length и type за всеки филм се появяват само веднъж в екземпляра на Movies1. Повторението на title, year в Movies2 не може да се избегне, тъй като те образуват ключ за филмите, чрез който те се идентифицират.
   
2. 
   Избегната е аномалията за обновяване – промяната на length или type за всеки филм трябва да се извърши само на едно място в съответния кортеж от Movies1.
   
3. 
   Избегната е аномалията на изтриването – при премахване на участието на звезда в даден филм, информацията за филма в Movies1 се запазва.
   

Целта на декомпозицията е да разбие релациите на по-малки релации, за които е в сила условието за нормална форма.

A₁ A₂ …A_n  B за R имаме, че { A₁, A₂, …, A_n} е суперключ.

Еквивалентна дефиниция е следната: във всяка нетривиална функционална зависимост A₁ A₂ …A_n  B₁ B₂ …B_m за R имаме, че

{ A₁, A₂, …, A_n} е суперключ.

title year  length type studioName е нетривиална функционална зависимост, но { title, year} не е суперключ, тъй като ключът е

{ title, year, starName}.

От друга страна, релациите Movies1 и Movies2 са в нормална форма на Boyce-Codd. Действително, ключът на Movies1 е { title, year } и той със сигурност присъства в лявата част на всяка нетривиална функционална зависимост. В Movies2 няма нетривиални функционални зависимости.

Нека R (A, B) e релация с два атрибута.

1. 
   Ако за R няма нетривиални функционални зависимости, то R естествено е в BCNF. В този случай R има единствен ключ - { A, B}.
   
2. 
   Нека за R е в сила A  B, но не е в сила B  A. Тогава R има единствен ключ { A} и той се съдържа във всяка нетривиална функционална зависимост за R (тя е единствена – A  B).
   
3. 
   Нека за R е в сила B  A, но не е в сила A  B. Този случай е аналогичен на предния.
   
4. 
   Нека за R е в сила A  B и B  A. Тогава R има два ключа
   

A  B и B  A и те не нарушават BCNF.

1. 
   Всички получени релации да са в BCNF.
   
2. 
   Информацията трябва да се запазва, т.е. от екземпляри на новополучените релации еднозначно да се възстановява съответният екземпляр на първоначалната релация.
   

Най-простият вариант е да разбием схемата на релацията на схеми с по два атрибута, които със сигурност ще са в BCNF. При такава произволна декомпозиция, обаче, се нарушава условие 2. както ще видим

по-нататък.
Стратегията за декомпозиция, която възприемаме е следната.

Нека A₁ A₂ …A_n  B₁ B₂ …B_m е нетривиална функционална зависимост и

{ A₁, A₂, …, A_n} не е суперключ. При това ще предполагаме, че в дясната част на функционалната зависимост участват всички атрибути от

{ A₁, A₂, …, A_n } ⁺. Това условие не е задължително, но може да се приеме като оптимизация. Тогава декомпозираме релацията R на следните две релации:

1. 
   Първата релация има атрибути A₁, A₂, …, A_n, B₁, B₂, …, B_m.
   
2. 
   Втората релация има атрибути A₁, A₂, …, A_n и всички останали атрибути на R, които не участват във функционалната зависимост.
   

MovieStudio (title, year, length, type, studioName, studioAddress).

Ключът е { title, year } и функционалната зависимост

studioName  studioAddress нарушава BCNF и съдържа максимална дясна част. Следвайки стратегията за декомпозиция разбиваме релацията MovieStudio на две нови релации със следните схеми:

MovieStudio1 (title, year, length, type, studioName) и

MovieStudio2 (studioName, studioAddress).

Лесно се вижда, че ключът на MovieStudio1 е { title, year }, а ключът на MovieStudio2 е { studioName}. Новите релации са в BCNF, тъй като

title year  length type studioName е единствената нетривиална функционална зависимост за MovieStudio1, а MovieStudio2 има два атрибута. Така процесът на декомпозиция приключва.

MovieStudioPres (title, year, studioName, president, presAddress).

Функционалните зависимости, които предполагаме са следните:

title year  studioName

studioName  president

president  presAddress.

Единственият ключ на MovieStudioPres е { title, year }, така че последните две функционални зависимости нарушават BCNF.

Да предположим, че започваме с първата функционална зависимост

studioName  president. Първо добавяме в дясна част всевъзможните атрибути от { studioName} ⁺ и получаваме функционалната зависимост

studioName  president presAddress. След това декомпозираме на две релации със следните схеми:

MovieStudioPres1 (title, year, studioName)

MovieStudioPres2 (studioName, president, presAddress).

Първата релация е в BCNF, тъй като единствената функционална зависимост е title year  studioName и { title, year } е единственият ключ.

Втората релация не е в BCNF, тъй като функционалната зависимост

president  presAddress се е проектирала в нея, а studioName е единственият ключ. Така разбиваме MovieStudioPres2 на две релации със следните схеми:

MovieStudioPres21 (studioName, president)

MovieStudioPres22 (president, presAddress).

Новополучените релации са в BCNF. Ключът на първата релация е studioName, а ключът на втората релация е president.

Лесно се вижда, че ако започнем с втората функционална зависимост ще достигнем до същия резултат.
Възстановяване на информацията след декомпозиция
Ще покажем, че след декомпозиция извършена по гореописаната стратегия информацията може да се възстанови, т.е. екземплярите на получените релации еднозначно определят екземпляра на декомпозираната релация. Идеята е да използваме съединение на кортежите.
За да не претрупваме означенията ще си мислим, че разглеждаме релация с три атрибута R (A, B, C). Да предположим, че функционалната зависимост B  C нарушава BCNF. Ако A  B е функционална зависимост, то { A} е единственият ключ. В противен случай, единственият ключ е { A, B }. И в двата случая декомпозицията по функционалната зависимост B  C води до релации със следните схеми:

R1 (A, B), R2 (B, C). Нека t (a, b, c) е кортеж в екземпляр на релацията R.

Тогава проекцията на t в R1 е (a, b), проекцията на t в R2 е (b, c).

Съединението представлява следното: от всеки два кортежа от екземплярите на R1 и R2, които се съгласуват по съединяващите атрибути (в случая B), т.е. имат еднакви компоненти, съответни на съединяващите атрибути, образуваме кортеж от екземпляра на R.

В случая кортежът (a, b) на R1 и (b, c) на R2 се съгласуват по съединяващия атрибут B и от тях получаваме кортежът t (a, b, c) от екземпляра на R.

Ясно е, че при съединението се възстановяват всички кортежи на екземпляра на релацията R. Въпросът е дали няма да се получат излишни кортежи.

Да предположим, че в екземпляра на R има друг кортеж v (d, b, e).

Тогава проекцията на v в R1 е (d, b), проекцията на v в R2 е (b, e).

При съединението кортежът (а, b) от екземпляра на R1 се съгласува с кортежа (b, e) от екземпляра на R2. По този начин получаваме кортеж

w (a, b, e). Въпросът е дали w е кортеж от екземляра на R. Тъй като B  C е функционална зависимост в R и кортежите t, v имат еднакви компоненти за B, то те трябва да имат еднакви компоненти за C, т.е. получаваме c = e, така че x = w. Така w действително е кортеж от екземпляра на R. По този начин, ако декомпозицията се извършва използвайки функционална зависимост по описаната стратегия, то със сигурност чрез съединение еднозначно можем да възстановяваме екземплярите на декомпозираната релация.

Аргументите, които приведохме естествено се обобщават когато A, B, C са множества от атрибути.
Ще покажем, че при произволна декомпозиция не е сигурно, че екземплярът на първоначалната релация ще може да се възстанови.

Нека R (A, B, C) е същата релация, но функционалната зависимост B  C не е в сила. Нека разгледаме екземпляр на R, който се състои от следните два кортежа: (a, b, c), (d, b, e). Да предположим, че декомпозираме релацията на R1 (A, B) и R2 (B, C). Тогава проектираният екземпляр на R1 ще бъде (a, b), (d, b), а проектираният екземпляр на R2 ще бъде

(b, c), (b, e). Като извършим съединение получаваме следните кортежи:

(a, b, c), (a, b, e), (d, b, c), (d, b, e). Така екземплярът на R не се възстановява правилно – има два излишни кортежа (a, b, e) и (d, b, c).

Този пример показва, че не трябва да се извършва безпринципна декомпозиция.
Трета нормална форма
Третата нормална форма е по-слаба от нормалната форма на

Boyce-Codd, но тя също се използва.

Bookings (title, theater, city).

Кортежът (p, t, c) интерпретираме по следния начин: пиесата p се играе в театъра t, който се намира в град c.

Разумни са следните функционални зависимости:

theater  city и city title  theater.

Чрез втората функционална зависимост предполагаме, че една пиеса не може да се играе по едно и също време в два различни театъра на един и същи град.

Ключовете на релацията са следните: { title, city }, { title, theater}.

Естествено, { city, theater } не е ключ. При това положение е очевидно, че релацията Bookings не е в BCNF - theater  city е нетривиална функционална зависимост и theater не е суперключ. По стратегията за декомпозиция разпадаме Bookings на две релации със следните схеми:

Bookings1 (theater, title)

Bookings2 (theater, city)

При тази декомпозиция, обаче, функционалната зависимост

city title  theater се изгубва. Действително, ако да разгледаме следните екземпляри на Bookings1 и Bookings2:

theater	title				theater	city
Guild	The Net				Guild	Menlo Park
Park	The Net				Park	Menlo Park

theater	title	city
Guild	The Net	Menlo Park
Park	The Net	Menlo Park

title city  theater.

По този начин при декомпозиране към нормална форма на Boyce-Codd не винаги запазваме функционалните зависимости.

Решението на проблема е да отслабим условието на Boyce-Codd.

{ A₁, A₂, …, A_k} е суперключ или B е част от ключ.

Четвъртата нормална форма ще разгледаме по-нататък.

Да разгледаме следният екземпляр на релацията

StarsIn (name, street, city, title, year), която описва участие на актьор във филм заедно с неговия адрес. Предполагаме, че една звезда може да има повече от един адрес.

name	street	city	title	year
Carrie Fisher	123 Maple Str.	Hollywood	Star Wars	1977
Carrie Fisher	5 Locust Ln.	Malibu	Star Wars	1977
Carrie Fisher	123 Maple Str.	Hollywood	Empire Strikes Back	1980
Carrie Fisher	5 Locust Ln.	Malibu	Empire Strikes Back	1980
Carrie Fisher	123 Maple Str.	Hollywood	Return of the Jedi	1983
Carrie Fisher	5 Locust Ln.	Malibu	Return of the Jedi	1983

Звездата Carrie Fisher има два адреса и играе в три филма. За да се отрази това в релацията трябва да се комбинира всеки адрес с всеки филм, което води до очевидно излишество. Въпреки това, релацията е в BCNF, тъй като в нея няма функционални зависимости и всички атрибути образуват ключ.