Projektowanie relacyjnych baz danych

BAD 420 Projektowanie relacyjnych baz danych

str.1

Projektowanie relacyjnych baz danych ZALEŻNOŚCI FUNKCYJNE Mówimy, że w relacji R typu U spełniona jest zależność funkcyjna XY, gdzie X,YU, jeśli dla każdych dwóch krotek r, sR r[X]=s[X]  r[Y]=s[Y]. Oznaczenia: F{XY: X, YU} – zbiór zależności funkcyjnych F+ - najmniejszy zbiór zależności funkcyjnych domknięty ze względu na następujące reguły wyprowadzania: Aksjomaty Armstronga Niech X, Y, Z  U A1. YX  XYF+ (zwrotność) A2. XYF+  XZYZF+ (poszerzalność) A3. XYF+  YZF+  XZF+ (przechodniość) Jeżeli chcemy stwierdzić, które atrybuty są funkcjonalnie zależne od zbioru X to wyznaczamy domknięcie tranzytywne tego zbioru. Domknięciem tranzytywnym zbioru XU względem zbioru zależności funkcyjnych F nazywamy zbiór atrybutów X+ = {AU: XAF+ } Konstrukcja zbioru X+ pozwala stwierdzić, czy dana zależność XY wynika logicznie ze zbioru F, XYF+  YX+ Algorytm wyznaczania domknięcia tranzytywnego K1. X0 = X, i = 0 K2. Xi+1 = Xi  {A: YZF+  AZ  YXi } (dołączamy prawe strony tych zależności funkcyjnych, których lewa strona jest podzbiorem Xi) K3. Czy Xi = Xi+1? Jeśli tak to koniec (X+ = Xi), jeśli nie to i:=i+1, przejdź do kroku K2

Postacie normalne. Anomalie: redundancja, anomalia modyfikacji, anomalia wstawiania, anomalia usuwania 1PN (1NF): Relacja R jest w pierwszej postaci normalnej, jeśli dziedziną każdego atrybutu są wartości elementarne (nierozkładalne). Kluczem relacji R(U), o zbiorze zależności F nazywamy dowolny zbiór atrybutów KU taki, że (1) KUF+ (jednoznaczna identyfikowalność) (2)  YK, YK, YUF+ (minimalność) Zbiór atrybutów XU spełniających warunek (1) nazywamy nadkluczem. A jest atrybutem głównym (kluczowym), jeżeli istnieje klucz K taki, że AK. W przeciwnym wypadku mówimy, że A jest atrybutem niekluczowym. XY jest pełną zależnością funkcyjną, jeśli nie istnieje zbiór ZX taki, że ZYF+. 2PN (2NF): Schemat R = (U, F) jest w drugiej postaci normalnej, jeśli każdy niekluczowy atrybut AU jest w pełni funkcyjnie zależny od każdego klucza tego schematu.

BAD 420 Projektowanie relacyjnych baz danych

str.2

3PN (3NF): Schemat R = (U, F) jest w trzeciej postaci normalnej, jeśli dla każdej zależności XAF+, (XU, AU) zachodzi: (1) AX (zależność trywialna), albo (2) X jest nadkluczem, albo (3) A jest atrybutem głównym (kluczowym). WNIOSEK: Schemat R = (U, F) jest w 3PN, jeśli jest w 2PN oraz nie zawiera zależności przechodnich (zależność XA nazywa się zależnością przechodnią, jeśli X nie jest ani podzbiorem, ani nadzbiorem żadnego klucza ; K XA – A atrybut niekluczowy). BCNF: Schemat R = (U, F) jest w postaci normalnej Boyce’a-Codda, jeśli dla każdej zależności XAF+, (XU, AU) zachodzi: (1) AX (zależność trywialna), albo (2) X jest nadkluczem. Oprócz zależności funkcyjnych rozważa się też zależności wielowartościowe (ozn. XY, czyt. X wyznacza wieloznacznie Y), które służą do zdefiniowania czwartej postaci normalnej. Zależność XY można interpretować jako regułę: jeśli krotki oraz  R to y = y’. Podobnie zależność XY można interpretować jako regułę: jeśli krotki oraz  R to również krotki oraz  R Schemat relacyjny R = (U, F) jest rozkładalny na składowe niezależne S = (X, G) i T = (Y, H) w.i t.w. gdy: (1) XY = U (2) F+= (G+H)+ (3) Dla każdej relacji RINST(R), R = R[X]  R[Y] (rozkład bez straty danych i zależności) Twierdzenie. Niech dany będzie schemat R = (U, F) oraz X, Y takie, że XY=U i XY. Projekcje R[X] = (X, G) oraz R[Y] = (Y, H) są niezależnymi składowymi schematu R w.i.t.w. gdy: (1) F+=(GH)+ (2) XYX  F+ lub XYY  F+ [Dla R(U) jeśli XY to rozkład R1(X+) i R2(U-X+X) jest rozkładem bez straty danych] Algorytm Bernsteina (wersja uproszczona) – generuje schemat relacji w 3PN wykorzystując rozkład bez straty danych i zależności. (K1) Eliminowanie zbędnych atrybutów (z lewej strony zależności funkcyjnych w F). Atrybut AX nazywamy zbędnym w zależności XYF+, jeżeli (X-A)YF+. Wynik – zbiór F’. (K2) Znajdowanie minimalnego generatora F0 zbioru F’. Ponieważ XYF+  YX+ zatem, kolejno dla każdej zależności za zbioru F’, badamy ten warunek korzystając z algorytmu wyznaczania domknięcia tranzytywnego. (K3) Podział. Elementy zbioru F0 dzielimy na grupy F1, ..., Fm w taki sposób, że wszystkie zależności jednej grupy mają identyczne lewe strony. (K4) Grupowanie. Każdą parę Fi, Fj z lewymi stronami odpowiednio X i Y łączymy w jedną grupę, jeżeli XYF0+ i YXF0+ (K5) Dla każdej grupy Fi tworzymy zbiór Ui złożony z atrybutów tej grupy. Wynik – docelowy schemat relacyjny TD = {Ri = (Ui, Fi), i=1, 2, ..., n}

BAD 420 Projektowanie relacyjnych baz danych

str.3

ZADANIA 1. Korzystając z aksjomatów Armstronga wyprowadzić następujące reguły: a) XYF+  YWZF+  XWZF+ (pseudo-przechodniość) b) XYF+  XZF+  XYZF+ (addytywność) c) XYZF+  XYF+  XZF+ (dekompozycyjność) d) XYF+  XZYF+ 2. Dany jest schemat relacyjny R = (U, F), gdzie U = {A, B, C, D, E, G}, F = {ABC, DEG, CA, BEC, BCD, CGBD, ACDB, CEAG}. Wyznaczyć domknięcia tranzytywne zbiorów: a) X1 = {B, D} b) X2 = {B} c) X3 = {D} 3. Udowodnić, ze jeżeli XY to X+Y+ (domknięcia oblicza się według tego samego zbioru atrybutów). 4. W której postaci normalnej są następujące schematy relacyjne: a) R = (U, F), gdzie U = {M, U, K}, F = {MUK, KM} b) R = (U, F), gdzie U = {A, B, C, D}, F = {ABC, BD, BCA} c) R = (U, F), gdzie U = {S, T, D, K}, F = {TSD, SDK} 5. Dany jest schemat relacyjny R = (U, F), gdzie U = {NrInd, Nazwisko_studenta, Wydział_nazwa, Wydział_adres}, F = {Nr_IndNazwisko_studenta,Wydział_nazwa, Wydział_nazwaWydział_adres}. Uzasadnij dlaczego schemat ten nie jest w 3PN i podaj rozkład na składowe niezależne w 3PN. 6. Dany jest schemat relacyjny R = (U, F), gdzie U = {P, G, S, I, E, O}, F = {PGS, GSP, PIO, PGSE, GIP, GIS, GSIO}. Stosując algorytm Bernsteina znaleźć rozkład tego schematu na składowe niezależne w 3PN.