Лекции по бази данни

Типична ситуация е следната: имаме две множества същности E, F и връзка R много към един от E към F. В този случай ключовите атрибути на E се съдържат както в релацията за E (заедно с останалите атрибути на E), така и в релацията за R. Релацията за R съдържа още ключовите атрибути на F, както и атрибутите на R, ако има такива. Тъй като R е връзка много към един, последните атрибути се определят еднозначно от ключовите на атрибути на E, което означава, че можем да комбинираме релациите на E и R в една релация със следните атрибути:

• 
  всички атрибути на E;
  
• 
  ключовите атрибути на F;
  
• 
  атрибутите на R.
  

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

Получаваме следната схема:

Movies (title, year, length, type, starName). Тъй като в един филм може да участва повече от една звезда, то за всяко такова участие трябва да има по един кортеж в екземпляр за Movies. Това, обаче, води до дублиране на останалата информация за филмите.

Преобразуването се извършва по следния начин:

• 
  релацията за слабото множество W включва атрибутите на W и всички останали атрибути, които формират ключа на W; тези атрибути се определят от поддържащите връзки на W;
  
• 
  релацията за една връзка, в която участва W, трябва да съдържа всички ключови атрибути на W, включително тези, които не са собствени атрибути на W; това важи само за връзки, които не са поддържащи;
  
• 
  поддържащите връзки въобще не се преобразуват в релации – ако имат атрибути, те се добавят към атрибутите на релацията за W.
  

Като пример да преобразуваме слабото множество Crews, което разгледахме по-горе. Получаваме следните две схеми на релации:

Studios (name, address)

Crews (crewNumber, studioName).

Да предположим, все пак, че сме добавили и схема за връзката unit_of:

UnitOf (crewNumber, studioName, studioName1). Тук сме включили, както обикновено, ключовете на множествата същности Studios и Crews.

При това положение, кортежите във всеки екземпляр на релацията ще имат еднакви стойности за studioName и studioName1. Поради тази причина можем да премахнем атрибутът studioName1 от схемата.

Новополучената схема е абсолютно идентична на Crews, затова можем да я премахнем.

Това не може да се осъществи, ако между релациите няма семантична връзка - например, релациите Studios и Stars имат едни и същи атрибути, но представляват съвсем различни същности.

Има случаи, в които между релациите има връзка, но елиминирането отново не може да се извърши.

Да разгледаме следния пример с две релации:

People (name, #ss)

TaxPayers (name, #ss, money)

Кортежите на първата релация отговарят на всички хора, които имат социални осигуровки. Кортежите на втората релация отговарят на хората, които имат социални осигуровки и са платили определена сума.

Ако премахнем релацията People, ще загубим информацията за хората, които са социално осигурени, но не са плащали данъци.

Movies (title, year, length, type)

Cartoons (title, year)

MurderMysteries (title, year, weapon)

За всеки филм има кортеж в екземпляра на Movies. Ако един филм е конкретна същност от Cartoons, то за него ще има кортеж както в екземпляра на Movies, така и в екземпляра на Cartoons. Аналогично, ако един филм е конкретна същност от MurderMysteries, то за него ще има кортеж както в Movies, така и в MurderMysteries.

Ако един филм е едновременно конкретна същност както в Cartoons, така и в MurderMysteries, то за него ще има кортежи и в трите релации.

Връзката voice_of се преобразува към следната релация:

VoiceOf (starName, title, year).

Тук starName е ключът на множеството същности Star, title, year е ключът на Cartoons, който съвпада с ключа на Movies.

Да отбележим, че схемата на релацията Cartoons е подсхема на релацията Voices. Въпреки това, можем да елиминираме релацията Cartoons само ако сме сигурни, че всички анимационни филми са озвучени.

• 
  поддървото, съставено само от Movies;
  
• 
  поддървото, съставено от Movies и Cartoons;
  
• 
  поддървото, съставено от Movies и МurderMysteries;
  
• 
  поддървото, съставено от Movies, Cartoons и MurderMysteries.
  

Movies (title, year, length, type)

MoviesC (title, year, length, type)

MoviesMM (title, year, length, type, weapon)

MoviesCMM (title, year, length, type, weapon)
За всяка конкретна същност от Movies има точно един кортеж в точно една от дефинираните релации. Затова подходът е обектно-ориентиран – всяка същност принадлежи на собствения си клас.

Връзката voice_of отново трябва да преобразуваме към следната схема на релация: VoiceOf (title, year, starName).

Ако има значение в коя релация е кортежът за даден филм от Cartoon, то за връзката voice_of трябва да съставим по една релация за всяко съответно поддърво. Ако поставим такова изискване връзката Voices ще се преобразува към следните две релации:

VoicesC (title, year, starName)

VoicesCMM (title, year, starName)
Използване на null-стойности
Създава се една обща релация, която включва всички атрибути на всички множества същности от йерархията. За всяка конкретна същност има точно един кортеж в релацията. Ако тази същност не принадлежи на някое множество същности от йерархията, то компонентите в кортежа, съответни на собствените атрибути на това множество същности трябва да съдържат null-стойности.
В примера с йерархията Моvies трябва да образуваме една релация:

Movies (title, year, length, type, weapon).

За филмите, в които няма мистериозни убийства стойността на атрибута weapon ще е null. Връзката voice_of се преобразува аналогично към релация VoiceOf (title, year, starName). И в този случай могат да се дефинират няколко релации за връзката voice_of, ако има значение в кои множества същности от йерархията попада съответния анимационен филм.
Сега ще сравним трите подхода по някои критерии.

1. 
   Скъпо е да се отговаря на заявки, в които участват няколко релации. По този критерий най-добрият подход е с null-стойностите. Другите два подхода имат предимства и недостатъци в зависимост от заявките. Например:
   
   1. 
      Нека заявката е “кои филми от 1999г. са по-дълги от 150 минути?”. Тогава при ER подхода търсенето ще се осъществи само в релацията Movies, докато при обектно-ориентирания подход трябва да се търси във всяка една от релациите.
      
   2. 
      Нека заявката е “какво оръжие се използва в анимационните филми, които са по-дълги от 150 минути?”. Тогава при ER подхода търсенето ще започне в релацията Movies, където ще се определят филмите, които са по-дълги от 150 минути. След това ще продължи в релацията Cartoons за да се определят кои от намерените са анимационни филми, след това в релацията MurderMysteries за да се определи в кои от тях има мистериозни убийства. Така търсенето засяга и трите релации. При обектно-ориентирания подход трябва да се търси само в една релация – MoviesCMM, където е налице всичката нужна информация.
      
2. 
   Добре е да не използваме много релации. Тук отново подходът с null-стойности е най-добър. Обектно-ориентираният подход е най-лош, тъй като броят на поддърветата расте експоненциално с нарастване на броя на множествата същности в йерархията.
   
3. 
   Минимизиране на пространството и избягване на повторенията. Тук най-добър е обектно-ориентираният подход, тъй като за всяка същност има точно един кортеж, който съдържа точно тази информация, която е смислена за кортежа. При ER подхода за една същност може да има няколко кортежа, но в тях се дублират само ключовете. Подходът с null-стойности е най-лош по този критерий за големи йерархии, въпреки че отново за всяка същност има единствен кортеж – при него има огромно разхищение на пространство.
   

При конкретни СУБД, които поддържат ER модела има опции коя от трите стратегии да се използва.

Освен тях се използват многозначни зависимости и ограничения за референтна цялостност. Всички тези ограничения се използват за усъвършенстване на схемата на една база от данни.

A₁, A₂, …, A_n функционално определят атрибута B.

Бележим функционалната зависимост по следния начин: A₁ A₂ … A_n  B.

Ако A₁, A₂, …, A_n функционално определят повече от един атрибут, т.е.

имаме A₁ A₂ … A_n  B₁, A₁ A₂ … A_n  B₂, …, A₁ A₂ … A_n  B_k, то съкратено записваме A₁ A₂ … A_n  B₁ B₂ …B_k.
Като пример в релацията

Movies (title, year, length, type, studioName, starName)

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

title year  length, title year  type, title year  studioName или съкратено

title year  length type studioName.

Първите две зависимости произтичат от това, че в диаграмата ER

title, year е ключ на множеството същности Movies, а третата зависимост произтича от това, че има връзка много към един от Movies към Studios.

От друга страна, за релацията Movies не е в сила функционалната зависимост title year  starName, тъй като в един филм може да участва повече от една звезда.

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

Естествено, добре е първичният ключ да съдържа колкото се може

по-малко атрибути.
В означението за схемата на релацията ще подчертаваме атрибутите, които образуват първичния ключ на тази релация. Например:

Movies (title, year, length, type, studioName, starName).

За минималност на ключа можем да съдим само ако разполагаме с пълния набор от функционални зависимости между атрибутите.

Movies (title, year, length, type)

Stars (name, address)

Ако една релация се получава от бинарна връзка, то нейният ключ се определя в зависимост от типа на връзката:

• 
  ако връзката е много към много, то ключът на релацията за връзката се състои от ключовете на двете множества същности;
  
• 
  ако връзката е много към един от E към F, то ключът на релацията за връзката се състои от ключовите атрибути на E;
  
• 
  ако връзката е един към един между E и F, то ключът на релацията за връзката се състои или от ключовите атрибути на E или от ключовите атрибути на F, т.е. релацията няма единствен ключ.
  

Owns (title, year, studioName)

StarsIn (title, year, starName)
Ако една релация се получава от небинарна връзка, то от диаграмата ER не може да се определят всички функционални зависимости, които съществуват между нейните атрибути. Със сигурност е изпълнено следното: ако връзката е много към един към някое множество същности E, т.е. има стрелка към E, то със сигурност съществува ключ на релацията за връзката, който не съдържа ключовите атрибути на E.
Правила за функционалните зависимости
Ще разгледаме някои правила, чрез които от даден набор функционални зависимости в релация можем да извличаме нови функционални зависимости в тази релация.
Функционалните зависимости за една релация често могат да бъдат представени по различен начин. По-формално, казваме че множествата S и T от функционални зависимости са еквивалентни, ако множеството от екземплярите на релацията, удоволетворяващи S съвпада с множеството от екземплярите на релацията, удоволетворяващи T.

По-общо, множеството функционални зависимости S следва от множеството от функционални зависимости T, ако всеки екземпляр на релацията, който удоволетворява T, удоволетворява и S.

Естествено, ако от S следва T и от T следва S тогава и само тогава, когато S и T са еквивалентни.
Нека е дадена функционална зависимост A₁ A₂ …A_n  B₁ B₂ …B_m.

Тогава можем да заменим тази функционална зависимост със следните функционални зависимости: A₁ A₂ …A_n  B_i, i = 1, 2, …, m. Това правило наричаме правило за разделяне.

Обратно, функционалните зависимости A₁ A₂ …A_n  B_i, i = 1, 2, …, m можем да заменяме с една функционална зависимост

A₁ A₂ …A_n  B₁ B₂ …B_m. Това правило наричаме правило за комбиниране.

Очевидно е, че и в двата случая полученото множество функционални зависимости е еквивалентно на изходното.

Например, множествата функционални зависимости { title year  length,

title year  type, title year  studioName } и

{ title year  length type studioName } са еквивалентни.

A₁ A₂ …A_n  B₁ B₂ …B_m е тривиална, ако { B₁, B₂, …, B_m}  { A₁, A₂, …, A_n}.

Казваме, че функционалната зависимост A₁ A₂ …A_n  B₁ B₂ …B_m е нетривиална, ако съществува i  { 1, 2, …, m}, такова че

B_i  { A₁, A₂, …, A_n}.

Казваме, че функционалната зависимост A₁ A₂ …A_n  B₁ B₂ …B_m е напълно нетривиална, ако за всяко i  { 1, 2, …, m}, имаме

B_i  { A₁, A₂, …, A_n}.

функционалната зависимост title year  year length е нетривиална,

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

Тогава можем да премахнем онези B_i, които съвпадат с някое A_j.

Получаваме нова функционална зависимост A₁ A₂ …A_n  C₁ C₂ …C_k, която очевидно е еквивалентна на изходната. Това правило наричаме правило за отстраняване на тривиалните зависимости.
Нека A₁ A₂ …A_n  B₁ B₂ …B_m и B₁ B₂ …B_m  C₁ C₂ …C_k са функционални зависимости. Тогава добавяме нова функционална зависимост

A₁ A₂ …A_n  C₁ C₂ …C_k. Това правило наричаме транзитивно правило.

Ясно е, че добавената функционална зависимост следва от изходните функционални зависимости, така че получаваме еквивалентно множество от функционални зависимости.
Например, да разгледаме релацията

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

За нея са в сила функционалните зависимости

title year  studioName, studioName  studioAddress.

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

title year  studioAddress също е в сила за тази релация.

Означаваме покритието по следния начин: { A₁, A₂, …, A_n} ⁺.

Естествено, { A₁, A₂, …, A_n }  { A₁, A₂, …, A_n} ⁺, тъй като тривиалните функционални зависимости винаги са изпълнени.
Ще опишем алгоритъм за изчисляване на покритието на { A₁, A₂, …, A_n} относно S.

1. 
   Инициализираме X = { A₁, A₂, …, A_n }.
   
2. 
   Търсим функционална зависимост B₁ B₂ …B_m  C в S, такава че B₁, B₂, …, B_m  X, но C  X. Тогава добавяме C към X.
   
3. 
   Повтаряме стъпка 2., докато вече не е възможно добавяне на атрибути в X. Този момент винаги ще настъпи, тъй като X винаги расте, а множеството от атрибути е крайно.
   
4. 
   Покритието { A₁, A₂, …, A_n} ⁺ съвпада с X.
   

Ще разгледаме пример. Нека атрибутите на релацията са A, B, C, D, E, F.

Нека S се състои от следните функционални зависимости

AB  C, BC  AD, D  E, CF  B.

Да изчислим покритието на { A, B} в S.

1. 
   X = { A, B }.
   
2. 
   X = { A, B, C}, чрез AB  C.
   
3. 
   X = { A, B, C, D}, чрез BC  AD.
   
4. 
   X = { A, B, C, D, E }, чрез D  E.
   

Покритието се използва при определяне дали дадена функционална зависимост следва от множество функционални зависимости по следната схема. Нека A₁ A₂ …A_n  B е функционална зависимост, S е множество от функционални зависимости. Тогава образуваме покритието на { A₁, A₂, …, A_n } относно S.

1. 
   Ако B  { A₁, A₂, …, A_n} ⁺, то функционалната зависимост A₁ A₂ …A_n  B следва от S.
   
2. 
   Ако B  { A₁, A₂, …, A_n} ⁺, то функционалната зависимост A₁ A₂ …A_n  B не следва от S.
   

Първо изчисляваме { D} ⁺.

1. 
   X = { D }.
   
2. 
   X = { D, E }, чрез D  E.
   

А  { D, E }, то функционалната зависимост D  A не следва от S.

1. 
   (коректност) Ако B  { A₁, A₂, …, A_n} ⁺, то функционалната зависимост A₁ A₂ …A_n  B действително следва от S.
   
2. 
   (пълнота) Ако A₁ A₂ …A_n  B следва от S, то задължително
   

База: преди да се изпълни стъпка 2. имаме X = { A₁, A₂, …, A_n}, така че функционалната зависимост A₁ A₂ …A_n  D e тривиална и следва от S.

Предположение: нека твърдението е изпълнено след k-тото изпълнение на стъпка 2.

Стъпка: нека D е добавено в X при k+1-то изпълнение на стъпка 2.

Тогава съществува функционална зависимост B₁ B₂ …B_m  D от S и

B₁ B₂ …B_m са били в X след k-тото изпълнение на стъпка 2.

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

A₁ A₂ …A_n  B_i, i = 1, 2, …, m следват от S, също B₁ B₂ …B_m  D е в S, така че A₁ A₂ …A_n  D следва от S по транзитивното правило.

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

	{ A1, A2, …, An} +				останалите атрибути (тук е B)
t:	1	1	…	1	0	0	…	0
s:	1	1	…	1	1	1	…	1

Нека C₁ C₂ …C_k  D е функционална зависимост от S. Да допуснем, че

тя не е в сила за горния екземпляр. Тъй като в него има само два кортежа, то те я нарушават, т.е. стойностите им за C₁ C₂ …C_k съвпадат, но стойностите за D не съвпадат. Ясно е, че при това положение

C₁, C₂, …, C_k  { A₁, A₂, …, A_n} ⁺, D  { A₁, A₂, …, A_n} ⁺. Но това е противоречие, тъй като D трябва да е било добавено към X чрез функционалната зависимост C₁ C₂ …C_k  D когато X е било

{ A₁, A₂, …, A_n} ⁺. И така, функционалните зависимости от S са в сила за посочения екземпляр. От друга страна, очевидно функционалната зависимост A₁ A₂ …A_n  B не е в сила за него, тъй като

А_i  { A₁, A₂, …, A_n} ⁺, i = 1, 2, …, n, но B  { A₁, A₂, …, A_n} ⁺.

Така намерихме екземпляр на релацията, който удоволетворява S, но не удоволетворява A₁ A₂ …A_n  B, така че A₁ A₂ …A_n  B не следва от S.

С това доказахме пълнотата.

Като пример да разгледаме релацията R (A, B, C) със следните функционални зависимости A  B, A  C, B  A, B  C, C  A, C  B,

AC  B, AB  C, BC  A. Тогава множествата

{ A  B, B  A, B  C, C  A } и { A  B, B  C, C  A } образуват минимални бази на релацията.