apohllo.pl
więcej niż strona domowa...
 

Normalizacja

Normalizacja schematu bazy danych polega na jego przekształceniu, do postaci, w której nie będą występowały następujące anomalie:
  1. redundancja – powtarzające się dane
  2. a. modyfikacji – zmodyfikowanie wartości atrybutu jednej krotki może wymagać zmodyfikowania wartości atrybutów innych krotek
  3. a. usunięć – usunięcie zbędnej informacji może prowadzić do usunięcia informacji przydatnych
Ad. 1,2
Zamówienie
Nazwa towaru Pozycja Cena
Gogle 1 70 PLN
Narty 2 260 PLN
Gogle 3 70 PLN

Informacja o cenie gogli niepotrzebnie powtarza się w kilku miejscach (przy założeniu, że nazwa towaru jest kluczem). Jeśli chcielibyśmy zmodyfikować ten atrybut, w pierwszej krotce, musielibyśmy dodatkowo zmodyfikować go w krotce trzeciej.

Ad.3
Magazyn
Nazwa towaru Cena Nr zamówienia
Gogle 70 PLN #1
Gogle 70 PLN #2
Narty 260 PLN #1

Zakładając, że informacja o towarze znajduje się tylko w relacji Magazyn, usunięcie (zbędnej) informacji o zamówieniu #1, powodowałoby usunięcie (przydatnej) informacji o cenie nart.

Dekompozycja

Normalizacja schematu bazy danych polega na dekompozycji relacji, w których występują anomalie. Dekompozycja relacji, to rozbicie jednej relacji na dwie lub więcej relacji. Kiedy dekomponujemy relację R (A1, A2, A3 , ..., An) na relacje T (B1 , B2, B3, ..., Bm) i S (C1, C2, C3, ..., Cr), muszą być zachowane następujące warunki:
  1. (A1, A2, A3 , ..., An) = (B1 , B2, B3, ..., Bm) + (C1, C2, C3, ..., Cr) (+ oznacza sumę teoriomnogościową)
  2. Krotki w relacji T to krotki powstałe przez rzutowanie krotek relacji R na zestaw atrybutów (B1 , B2, B3, ..., Bm)
  3. Krotki w relacji S to krotki powstałe przez rzutowanie krotek relacji R na zestaw atrybutów (C1, C2, C3, ..., Cr)

Rzutowanie krotki na zestaw atrybutów polega na zawężeniu zbioru jej wartości, tylko do tych, które odpowiadają atrybutom, na które krotka jest rzutowana. W wyniku tej operacji mogą powstać krotki, które nie różnią się wartością żadnego atrybutu. Ponieważ instancja danej relacji zawsze jest zbiorem, krotki takie są utożsamiane.

Przykład

Relację Magazyn, z poprzedniego punktu, możemy zdekomponować na dwie relacje: Towary(Nazwa towaru, Cena) i Zamówienia(Nazwa towaru, Nr zamówienia).
Instancja relacji Towary będzie zawierać następujące krotki:
Nazwa towaru Cena
Gogle 70 PLN
Narty 260 PLN
Instacja relacji Zamówienia będzie zawierać zaś krotki:
Nazwa towaru Nr zamówienia
Gogle #1
Gogle #2
Narty #1

Odzyskiwanie danych po dekompozycji

Aby odzyskać instancję relacji, która została zdekomponowana, należy każdą krotkę występującą w jednej relacji powstałej po dekompozycji, połączyć z wszystkimi krotkami występującymi w drugiej relacji, których atrybuty wspólne z daną krotką, są identyczne.

Przykład

Krotki relacji Towary i Zamówienia mają jedne wspólny atrybut Nazwa towaru. Dlatego też dla pierwszą krotkę relacji Towary łączymy z pierwszą i drugą krotką relacji Zamówienia, otrzymując krotki (Gogle, 70 PLN, #1) i (Gogle, 70 PLN, #2). Drugą krotkę relacji Towary łączymy z trzecią krotką relacji Zamówienia, otrzymując krotkę (Narty, 260 PLN, #1). W ten sposób otrzymujemy wszystkie krotki występujące w instancji relacji Magazyn przed dekompozycją.

Zależności funkcyjne

Mówimy, że F postaci A1 A2 ... An → B jest zależnością funkcyjną relacji R, jeżeli wszystkie krotki zgodne co do wartości na atrybutach A1 A2 ... An posiadają tę samą wartość atrybutu B. Innymi słowy: istnieje funkcja przeprowadzająca zbiór wektorów wartości atrybutów A1 A2 ... An w wartości atrybutu B.

Jeżeli zbiór atrybutów A1 A2 ... An określa funkcyjnie więcej niż jeden atrybut B:
  • A1 A2 ... An → B1
  • A1 A2 ... An → B2
  • ...
  • A1 A2 ... An → Bm

to możemy zastosować zapis skrótowy:
A1 A2 ... An → B1 B2 ... Bm

Zależności funkcyjne są własnością schematu bazy danych, a nie konkretnej jej instancji, dlatego też ich wykrycie nie polega na badaniu zawartości bazy danych, lecz badaniu zależności występujących w schemacie.

Występują trzy typy zależności funkcyjnych postaci A1 A2 ... An → B1 B2 ... Bm:
  • trywialne – jeśli zbiór atrybutów B1 B2 ... Bm jest podzbiorem zbioru atrybutów A1 A2 ... An
  • nietrywialne – jeśli co najmniej jeden atrybut Bi nie należy do zbioru atrybutów A1 A2 ... An
  • całkowicie nietrywialne – jeśli żaden z atrybutów Bi nie należy do zbioru atrybutów A1 A2 ... An

Domknięcie zbioru atrybutów

Ważą operacją związaną z zależnościami funkcyjnymi jest obliczanie domknięcia zbioru atrybutów relacji nad zbiorem zależności funkcyjnych. Domknięcie zbioru A oznaczamy A+.

Niech dany będzie zbiór atrybutów A = (A1, A2, ... An) oraz zbiór zależności funkcyjnych F = (F1, F2 ... Fn). Domknięciem zbioru atrybutów A nad zbiorem zależności F nazywamy taki zbiór atrybutów B, w którym dla każdego atrybutu Bi, należącego do pewnej relacji R spełniającej zależności F, spełniona jest zależność A1 A2 ... An → Bi.

Innymi słowy: zbiór B zawiera wszystkie atrybuty zależne funkcyjnie od zbioru atrybutów A.

Algorytm obliczania domknięcia:
  1. Niech oznacza zbiór domknięcia. Na początku X = A.
  2. Dla każdej zależności Fi ze zbioru F sprawdzamy, czy wszystkie atrybuty stojące po lewej stronie tej zależności należą do zbioru X. Jeśli tak, to do zbioru tego dodajemy wszystkie atrybuty stojące po prawej stronie zależności Fi (o ile wcześniej nie występowały w tym zbiorze).
  3. Poprzedni krok powtarzamy tak długo, aż zbiór X przestanie się powiększać.
  4. Zbiór X stanowi domknięci zbioru A nad zbiorem zależności F.

Przykład

Niech dana będzie relacja R (A, B, C, D, E, F) oraz zbiór zależności funkcyjnych F spełnianych przez tę relację: A C → E, B → C, A E → D, F → A (pomijamy zależności trywialne). Należy obliczyć domknięcie zbioru atrybutów (A, B) nad zbiorem zależności F:
  1. X0 = (A, B)
  2. W pierwszej iteracji do zbioru X możemy dołączyć atrybut C, ponieważ B należy do X0 oraz B → C należy do F. X1 = (A, B, C)
  3. W drugiej iteracji do zbioru D możemy dołączyć atrybut E, ponieważ A i C należą do X1 oraz A C → E należy do F. X2 = (A, B, C, E)
  4. W trzeciej iteracji do zbioru X możemy dołączyć atrybut D, ponieważ A i E należą do X2 oraz A E → D należą do F. X3 = (A, B, C, E, D).
  5. Widzimy, że do zbioru X nie można dodać już żadnego atrybutu, zatem algorytm kończy działanie.

 (A, B) + = (A, B, C, E, D)

Odtwarzanie zależności funkcyjnych po dekompozycji

Niech dane będą: relacja R, relacja S, która powstała w wyniku dekompozycji relacji R i zbiór zależności funkcyjnych F, spełnianych w relacji R. Żeby określi zbiór zależności funkcyjnych spełnianych w S należy:
  1. Rozważyć wszystkie podzbiory X zbioru atrybutów relacji S. Dla każdego z nich określić domknięcie X+ nad zbiorem zależności F.
  2. Jeśli jakiś atrybut B należący do S spełnia następujące warunki:
    1. należy do X+
    2. nie należy do X
  3. to zależność funkcyjna X → B jest spełniona w S

Klucze relacji

Mówimy, że atrybut lub zbiór atrybutów A1 A2 ... An tworzy klucz relacji R, jeżeli spełnione są warunki:
  • wszystkie atrybuty relacji R zależą funkcyjnie od tego atrybutu (zbioru atrybutów)
  • (w przypadku gdy klucz jest zbiorem atrybutów) nie istnieje żaden podzbiór właściwy zbioru atrybutów A1 A2 ... An, od którego wszystkie atrybuty relacji R zależą funkcyjnie

Jeśli chcemy sprawdzić czy dany zbiór atrybutów jest kluczem, musimy najpierw zbadać, czy wszystkie atrybuty danej relacji zależą funkcyjnie od tego zbioru atrybutów (obliczając domknięcie danego zbioru atrybutów, nad zależnościami funkcyjnymi występującymi w tej relacji), a następnie sprawdzić, czy usunięcie któregokolwiek atrybutu ze zbioru, prowadzi do niespełnienia tej własności.

Nadklucz relacji

Mówimy, że zbiór atrybutów A1 A2 ... An relacji R jest nadkluczem tej relacji, jeżeli zawiera klucz (lub co najmniej jeden z kluczy) tej relacji.

Postać normalna Boyce’a-Codda (BCNF)

Mówimy, że relacja R jest w postaci normalnej Boyce’a-Codda, jeśli we wszystkich występujących w niej nietrywialnych zależnościach funkcyjnych po lewej stronie występuje nadklucz tej relacji.

Aby przekształcić relację nie spełniając warunku BCNF należy dokonać jej dekompozycji na szereg relacji R1, R2 ... Rn, z których każda spełnia warunek BCNF. Poszczególne etapy dekomponowania polegają na:
  1. Sprawdzeniu, czy w zbiorze otrzymanych relacji nie występuje relacja łamiąca warunek BCNF. Jeśli nie, to algorytm kończy działanie.
  2. Dla każdej relacji łamiącej warunek BCNF należy zidentyfikować zależność funkcyjną, która powoduje niespełnienie tego warunku (tzn. nietrywialnej zależność postaci: A1 A2 ... An → B1 B2 ... Bm, w której A1 A2 ... An nie jest nadkluczem tej relacji)
  3. Zdekomponować wszystkie relacje łamiące warunek BCNF do dwóch relacji zawierających:
    1. atrybuty A1 A2 ... An B1 B2 ... Bm
    2. atrybuty A1 A2 ... An oraz atrybuty nie należące do zbioru B1 B2 ... Bm
  4. Powrocie do pierwszego punktu algorytmu.

Przykład

Niech R(A, B, C, D, E) będzie relacją, w której spełnione są zależności funkcyjne A B C → D, A → E. Kluczem relacji jest zbiór atrybutów (A, B, C). Zależność A → E łamie warunek BCNF. Relacja R powinna zostać zdekomponowana na relacje S(A, B, C, D) oraz T(A, E).

W relacji S zachodzi zależność funkcyjna A B C → D, ponieważ (A, B, C)+ = (A, B, C, D) i D nie należy do (A, B, C).

W relacji T zachodzi zależność funkcyjna A → E, ponieważ (A)+ = (A, E) i E nie należy do (A).

Trzecia postać normalna (3NF)

Warunek trzeciej postaci normalnej (3NF) jest nieznacznym osłabienie warunku BCNF.

Mówimy, że relacja R jest w trzeciej postaci normalnej, jeśli we wszystkich występujących w niej nietrywialnych zależnościach funkcyjnych po lewej występuje nadklucz tej relacji lub po prawej stronie występuje atrybut, który jest elementem pewnego klucza.

Zależności wielowartościowe

Zależności wielowartościowerozszerzeniem pojęcia zależności funkcyjnych, tzn. każda zależność funkcyjna jest również zależnością wielowartościową, ale nie każda zależność wielowartościowa jest zależnością funkcyjną.

Zbadanie występowania zależności wielowartościowych pozwala na wykrycie redundancji, które mogą pojawić się w bazie danych, która jednak spełnia warunek BCNF.

Niech R będzie relacją składającą się z trzech grup atrybutów:
  1. A1 A2 ... An
  2. B1 B2 ... Bm
  3. C1 C2 ... Cl
Mówimy, że A1 A2 ... An →→ B1 B2 ... Bm jest zależnością wielowartościową występującą w relacji R, jeśli dla każdej pary różnych krotek i , które mają takie same wartości atrybutów Ai można znaleźć krotkę , której składowe mają wartości równe:
  1. wartościom atrybutów Ai w krotkach i
  2. wartościom atrybutów Bi krotki
  3. wartościom atrybutów Ci krotki
Zależność wielowartościową A1 A2 ... An →→ B1 B2 ... Bm występującą w relacji R nazywamy nietrywialną, gdy:
  1. żaden atrybut Bi nie występuje po lewej stronie zależności
  2. atrybuty Ai, Bj nie obejmują wszystkich atrybutów występujących w relacji R

Przykład

Przypuśćmy, że w relacji Osoby poza imieniem i nazwiskiem poszczególnych osób, przechowywane są informacje o posiadanych przez nie samochodach i mieszkaniach. Jedna osoba może mieć zarówno wiele mieszkań, jak i wiele samochodów.

Instancja tej relacji mogłaby wyglądać następująco:
Imię Nazwisko Miasto Adres Marka samochodu
Jan Kowalski Gdańsk Mroźna 1 Ford KA
Jan Kowalski Gdańsk Mroźna 1 Opel Astra III
Jan Kowalski Łódź Prosta 4 Ford KA
Jan Kowalski Łódź Prosta 4 Opel Astra III
Redundancja widoczna jest na pierwszy rzut oka, tym niemniej relacja ta spełnia warunek BCNF (kluczem jest pełny zestaw atrybutów – należy wziąć pod uwagę, że w jednym mieście jedna osoba może posiadać wiele mieszkań), ponieważ nie występuje w niej żadna nietrywialna zależność funkcyjna. W relacji tej występują jednak dwie nietrywialne zależności wielowartościowe:
  1. Imię Nazwisko →→ Miasto Adres
  2. Imię Nazwisko →→ Marka samochodu

Czwarta postać normalna (4NF)

Mówimy, że relacja R jest w czwartej postaci normalnej (4NF), gdy dla każdej, nietrywialnej zależności wielowartościowej postaci A1 A2 ... An →→ B1 B2 ... Bm, lewa strona jest nadkluczem w R.

Normalizacja relacji do postaci 4NF polega na wykryci zależności wielowartościowej, która łamie warunek 4NF i zdekomponowaniu jej podobnie jak ma to miejsce w przypadku postaci BCNF.

Przykład

W przykładzie z poprzedniego punktu zbiór atrybutów (Imię, Nazwisko) nie stanowi nadklucza relacji Osoby, a występuje w dwóch zależnościach wielowartościowych. Konieczne jest zatem zdekomponowanie tej relacji do dwóch relacji:
  1. Adresy(Imię, Nazwisko, Miasto, Adres)
  2. Samochody(Imię, Nazwisko, Marka samochodu)
3NF | 4NF | BCNF | db | dydaktyka | rdb | Opublikowano 09:20 26-02-2007. Ostatnia modyfikacja 04:33 05-05-2008 |
comments powered by Disqus