Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Bazy danych – 6. Teoria projektowania relacyjnych baz danych – MIM UW

Zagadnienia

6. Teoria projektowania relacyjnych baz danych

6.1. Zależności funkcyjne

Zależność funkcyjna występuje wtedy, gdy po ustaleniu wartości pewnych atrybutów relacji wartości jakichś innych atrybutów tej relacji są jednoznacznie wyznaczone (unikalne).

Używa się notacji: X\rightarrow Y, gdzie X i Y są zbiorami atrybutów z relacji R.

Mówimy, że zależność funkcyjną X\rightarrow Y zachodzi w R, jeśli każde dwa wiersze mające te same wartości atrybutów z X muszą mieć te same wartości atrybutów z Y.

Formalnie mozna to wyrazić następująco

(\exists f:X\rightarrow Y)(\forall(x,\dots,y)\in R(X,\dots,Y))\, y=f(x)

choć funkcja f nie jest oczywiście znana (albo czasem nie jest łatwa do obliczenia).

6.1.1. Rozbicie zależności

Zależność funkcyjną, której prawa strona zawiera kilka atrybutów

X\rightarrow A_{1}A_{2}\dots A_{n}

można zastąpić zbiorem zależności o pojedynczych prawych stronach

X\rightarrow A_{1},X\rightarrow A_{2},\dots,X\rightarrow A_{n}

Operacja ta jest oczywiście odwracalna.

Przykład: A\rightarrow BC można zastąpić przez A\rightarrow B i A\rightarrow C.

Uwaga:Nie wolno rozbijać lewych stron zależności!

6.1.2. Przykłady zależności

Jeśli w przykładowym ZOO każdy zwierzak nazywa się inaczej, to dla relacji Zwierz(imie,gatunek,waga,wiek) zachodzi zależność: imie \rightarrow gatunek

Jeśli przyjęto (raczej naturalną) zasadę ,,Żadne dwa wykłady nie odbywają się o tej samej godzinie w tej samej sali”, to mamy zależność funkcyjną godzina sala \rightarrow wykład

Jak określa się zależności dla danej relacji? Jedynie przez odpytanie użytkowników.

Nie należy natomiast liczyć na to, że wykryjemy je na podstawie zawartości tabeli w bazie danych. W takiej tabeli może być pozornie spełniona pewna zależność, która przestanie zachodzić za pięć minut (po dodaniu do tabeli nowych wierszy)! W ten sposób można jedynie upewnić się, że podana zależność nie zachodzi.

6.1.3. Zależności trywialne

Definicja 6.1

Zależność X\rightarrow Y nazywamy trywialną, jeśli spełnione jest Y\subseteq X.

Uwaga 6.1

Zależności trywialne zachodzą zawsze i nie dostarczają żadnej informacji.

6.2. Klucze

Jednym z ważniejszych pojęć w projektowaniu relacyjnych baz danych jest pojęcie klucza relacji. Zaczniemy od pomocniczej definicji.

Definicja 6.2

Podzbiór N zbioru atrybutów relacji R(A_{1},A_{2},\dots,A_{n}) nazywamy jej nadkluczem, jeśli zachodzi zależność funkcyjna

N\rightarrow A_{1}A_{2}\dots A_{n}

Czyli zbiór wszystkich atrybutów relacji na pewno jest jej nadkluczem.

Definicja 6.3

Podzbiór K zbioru atrybutów relacji R(A_{1},A_{2},\dots,A_{n}) nazywamy jej kluczem, jeśli jest on nadkluczem i żaden jego podzbiór nie jest nadkluczem.

Inaczej mówiąc, klucze relacji to jej minimalne nadklucze. Obejrzymuy teraz przykłady kluczy.

Niech w relacji Zwierz zachodzi zależność imie \rightarrow gatunek wiek waga

  • {imie,gatunek} jest nadkluczem w relacji Zwierz

  • Nie jest jednak kluczem, bo {imie} też jest nadkluczem

  • {imie} jest kluczem i nie ma innych kluczy

6.2.1. Skąd się biorą klucze?

Skąd się biorą klucze? Na ogół są wyznaczane z zależności funkcyjnych.

Czasem jednak otrzymane w ten sposób klucze obejmują zbyt wiele kolumn, co jest w praktyce niewygodne. Wprowadza się wtedy arbitralnie tzw. klucze sztuczne), dodając do relacji R nowy atrybut KS jako klucz. Oznacza to nałożenie dodatkowej zależności funkcyjnej

KS\rightarrow A_{1}A_{2}\dots A_{n}

gdzie A_{1},A_{2},\dots,A_{n} są atrybutami relacji R

6.2.2. Wyprowadzanie zależności

Pewne zależności można wyprowadzić z innych. Przykład: jeśli zachodzi

A\rightarrow B

i zachodzi

B\rightarrow C

to musi zachodzić

A\rightarrow C

Można to sprawdzić z definicji. Inny sposób to skorzystać z reguł wnioskowania Armstronga.

6.2.3. Domknięcie zbioru atrybutów

Definicja 6.4

Domknięciem zbioru atrybutówY (względem danego zbioru zależności) nazywamy taki zbiór atrybutów Y^{+}, że

  1. Y\subseteq Y^{+}

  2. Dla dowolnej zależności U\rightarrow W, jeśli U\subseteq Y^{+}, to W\subseteq Y^{+}

Jeśli U\subseteq V^{+}, to zachodzi zależność funkcyjna V\rightarrow U. Klucz jest to więc taki minimalny zbiór atrybutów, że jego domknięcie jest zbiorem wszystkich atrybutów relacji.

Dla przykładu policzymy domknięcie atrybutu A z naszego przykładu

  1. Krok bazowy: A^{+} := A

  2. Indukcja: ponieważ A\rightarrow B i A\subseteq A^{+}, to A^{+} := A^{+}\cup B = AB

  3. Indukcja: ponieważ B\rightarrow C i B\subseteq A^{+}, to A^{+} := A^{+}\cup C = ABC

Wniosek: ponieważ C\subseteq A^{+}, więc zachodzi A\rightarrow C.

Spróbujmy innego przykładu. Dla zbioru zależności

AB\rightarrow C,BC\rightarrow AD,D\rightarrow E,CF\rightarrow B

domknięciem \{ A,B\}^{+} jest \{ A,B,C,D,E\}, ponieważ

AB\rightarrow C C\in\{ A,B\}^{+}
BC\rightarrow AD D\in\{ A,B\}^{+}
D\rightarrow E E\in\{ A,B\}^{+}

6.2.4. Domknięcie zbioru zależności

Definicja 6.5

Domknięcie zbioru zależnościZ (oznaczane Z^{+}) jest to zbiór wszystkich zależności, które można wyprowadzić z Z.

Definicja 6.6 (Równoważność zbiorów zależności)

Dwa zbiory zależności Z_{1} i Z_{2} są równoważne, jeśli ich domkniecia są równe: Z_{1}\equiv Z_{2} wtw Z_{1}^{+}=Z_{2}^{+}.

Definicja 6.7 (Minimalny zbiór zależności)

Minimalny zbiór zależności jest to taki zbiór zależności, który nie jest równoważny żadnemu swojemu podzbiorowi.

  • Uwaga: to jest uproszczona definicja, pełna jest bardziej skomplikowana.

  • Minimalny zbiór zależności dla danego wyjściowego zbioru zależności nie jest wyznaczony jednoznacznie.

6.2.5. Reguły wnioskowania Armstronga

Reguły wnioskowania Armstronga służą do wyprowadzania zależności z innych zależności.

\begin{array}[]{lrl}\mbox{Zwrotność}&Y\subseteq X&\vdash X\rightarrow Y\\
\\
\mbox{Rozszerzanie}&X\rightarrow Y&\vdash XZ\rightarrow YZ\\
\\
\mbox{Przechodniość}&X\rightarrow Y,Y\rightarrow Z&\vdash X\rightarrow Z\end{array}

6.3. Projektowanie schematu

6.3.1. Redundancja

Jeden z celów, który staramy się osiągnąć podczas projektowania schematu bazy danych to unikanie redundancji (nadmiarowości). Redundancja oznacza, że niektóre informacje są zapisane w bazie danych wielokrotnie. Prowadzi to do anomalii podczas modyfikacji i usuwania

  • Anomalia modyfikacji: informacja zostaje uaktualniona tylko w niektórych miejscach

    • Przykład: zmiana adresu studenta na nowy, jeśli informacja o studencie i jego adresie trzymana jest w kilku miejscach.

  • Anomalia usuwania: wraz z usunięciem ostatniego wiersza szczegółowego znika informacja ogólna

    • Gdyby informacje o adresie studenta trzymać przy przedmiotach, na które jest zarejestrowany, to po zakończeniu sesji (a przed nową rejestracją) adres ten by zniknął.

6.3.2. Przykład złego projektu

Obejrzyjmy przykład złego projektu i jego konsekwencje. Przypuśćmy, że mamy relację Zwierzaki(gatunek,imie,waga,kontynent) z następującymi zależnościami

imie \rightarrow gatunek waga kontynent
gatunek \rightarrow kontynent

Przykładowa zawartość takiej relacji

gatunek imie waga kontynent
Papuga Kropka 3,50 ???
Papuga Lulu 5,35 Ameryka
Papuga Hipek 3,50 ???
Lis Fufu 6,35 Europa
Krokodyl Czako 75,00 Afryka

Występuje redundancja, ponieważ wartości dla ??? można łatwo odgadnąć (czy jak kto woli wyznaczyć) na podstawie zależności.

6.4. Normalizacja

Normalizacja to proces, służący do przekształcenia schematu zawierającego redundancję w schemat, który jej nie zawiera. Zależnie od potrzeb określa się różne poziomy normalizacji — zakresy usuwania redundancji, nazywane postaciami normalnymi.

6.4.1. Postacie normalne

Dotychczas formalnie zdefiniowano pięć (poziomów) postaci normalnych, choć tylko trzy pierwsze są powszechnie używane podczas projektowania baz danych.

Postacie normalne są ponumerowane kolejno, ale istnieje postać pośrednia BCNF między 3 i 4 poziomem. Postacie o wyższych numerach automatycznie (z definicji) spełniają warunki dla niższych postaci, dlatego relacja w drugiej postaci normalnej jest automatycznie w pierwszej postaci normalnej.

Odwrotne wynikanie oczywiście nie zachodzi; drugą postać normalną otrzymujemy z pierwszej po nałożeniu dodatkowego warunku.

Proces normalizacji polega na dekompozycji tabel aż do otrzymania pożądanej postaci.

6.4.2. Pierwsza postać normalna (1NF)

Warunkiem pierwszej postaci normalnej jest to, by każdy atrybut w relacji przyjmował tylko wartości niepodzielne. Przez wartości niepodzielne rozumiemy takie pojedyncze wartości, jak używane w atrybutach ,,numer klienta” czy ,,nazwisko klienta”.

Relacja w pierwszej postaci normalnej nie może zawierać atrybutu, w którym można upakować kilka wartości, np. odddzielając je przecinkami.

Daty można traktować jako wartości niepodzielne lub tworzyć oddzielne atrybuty dla dnia, miesiąca i roku.

6.4.3. Druga postać normalna (2NF)

Aby stwierdzić, czy relacja będąca w pierwszej postaci normalnej jest także w drugiej, należy określić klucze relacji.

Każdej wartości klucza powinien jednoznacznie odpowiadać pojedynczy wiersz w tabeli. Na przykład dla relacji Zamówienie_klienta kluczem może być numer_zamówienia.

Warunkiem na drugą postać normalną jest to, aby każdy niekluczowy atrybut zależał funkcyjnie od całego klucza. Niedozwolone są więc tzw. zależności częściowe.

Uwaga: przypominamy, że kluczy może być kilka!

6.4.4. Trzecia postać normalna (3NF)

Dla sprawdzenia, czy relacja będąca w drugiej postaci normalnej jest także w trzeciej, bada się zależności między atrybutami niekluczowymi.

Atrybuty niekluczowe powinny zależeć funkcyjnie wyłącznie od klucza i niczego więcej. Wykluczamy w ten sposób zależności przechodnie.

6.4.5. Postać normalna Boyce-Codda (BCNF)

Bardziej restrykcyjna niż trzecia postać normalna jest postać normalna Boyce-Codda, lecz jest ona rzadziej wykorzystywana w aplikacjach komercyjnych.

Relacja R jest w tej postaci, jeśli jest w 1NF oraz dla każdej nietrywialnej zależności X\rightarrow Y zachodzącej w R, lewa strona zależności X jest nadkluczem.

W odróżnieniu od 3NF sprowadzenie do BCNF nie gwarantuje zachowania zależności funkcyjnych przy rozkładzie.

Popatrzmy na inną definicję 3NF, lepiej pokazującą różnicę między nią a BCNF.

Definicja 6.8 (3NF)

Relacja jest w 3NF jeśli jest w 1NF oraz dla każdej nietrywialnej zależności X\rightarrow Y:

  • lewa strona zależności X jest nadkluczem

  • lub

  • prawa strona zależności Y zawiera tylko atrybuty z kluczy (bo kluczy może być kilka)

6.4.6. Dekompozycja do BCNF

Dekomponując relację R do BCNF pozbywamy się kolejno zależności naruszających ją. Przedtem należy zminimalizować zbiór zależności, ale pominiemy ten etap.

  1. Dla relacji R wybierz ze zbioru zależności F zależność X\rightarrow Y naruszającą BCNF (jeśli nie ma takiej, to relacja jest już w BCNF).

  2. Oblicz X^{+}

    • Będzie zawierać tylko część atrybutów R, bo inaczej X byłoby nadkluczem.

  3. Zastąp R dwoma relacjami o schematach

    • R_{1}=X^{+}

    • R_{2}=R-(X^{+}-X)

  4. Zrzutuj zbiór zależności F na nowe relacje.

  5. Powtarzaj dopóki relacje nie będą w BCNF.

6.4.7. Zachowanie zależności

Czasem zależności powodują kłopoty przy przejściu do BCNF. Weźmy tabelę Gdzie(adres,miasto,kod-pocztowy) i dwie zależności

adres miasto \rightarrow kod-pocztowy
kod-pocztowy \rightarrow miasto

Mamy tu dwa klucze: {adres,miasto} oraz {adres,kod-pocztowy}. Ale zależność kod-pocztowy \rightarrow miasto narusza postać BCNF, czyli musimy dokonać dekompozycji na dwie tabele

Gdzie1(adres,kod-pocztowy)
Gdzie2(miasto,kod-pocztowy)

Popatrzmy jednak na poniższy (ciut złośliwy) przykład

Gdzie2
adres kod
Banacha 2 01-234
Banacha 2 01-235
Gdzie1
miasto kod
Warszawa 01-234
Warszawa 01-235

Pozornie wszystko jest w porządku (żadna zależność nie jest naruszona), ale po złączeniu będzie już inaczej

Gdzie
adres miasto kod
Banacha 2 Warszawa 01-234
Banacha 2 Warszawa 01-235

Naruszona jest zależność adres miasto \rightarrow kod-pocztowy.

Takie kłopotliwe układy zależności nie są rzadkie, popatrzmy na inny przykład zależności dla fikcyjnej sieci kin

kino \rightarrow miasto
film miasto \rightarrow kino

Pierwsza z nich jest oczywista: każde kino znajduje się tylko w jednym mieście. Druga może wynikać z prowadzonej ,,polityki” wyświetlania, aby kina w tym samym mieście nie konkurowały ze sobą filmami. Skutek jest taki sam jak poprzednio.

6.5. Zależności wielowartościowe

6.5.1. Czwarta postać normalna (4NF)

W większości baz danych wystarcza dekompozycja do trzeciej postaci normalnej. Mogą jednak czasem występować anomalie wstawiania, powodowane zależnością wielowartościową.

Będzie tak między innymi wtedy, gdy pewne dwa niekluczowe atrybuty przyjmują dla każdej wartości innego atrybutu tylko po kilka wybranych wartości, niezależnie od innych atrybutów.

Na przykład na seminariach korzysta się z kilku książek. Każde seminarium ma tylko jedną nazwę, ale może mieć kilku prowadzących. Należy wówczas dokonać dekompozycji na dwie osobne relacje: prowadzący seminaria oraz teksty do seminariów, w przeciwnym razie wypadałoby umieścić w relacji dla danego seminarium wszystkie kombinacje prowadzących i książek.

Przykład zależności wielowartościowej

  • Tabela

    Aktorzy(nazwisko,ulica,miasto,film,rok)

    podaje adresy aktorów (mogą mieć kilka) i filmy, w których grali.

  • Każdy aktor mógł grać w wielu filmach i może mieć kilka adresów.

  • Ale w pojedynczym wierszu możemy zapisać tylko jeden film i jeden adres.

  • Trudno będzie wtedy znajdować wszystkie filmy aktorów mieszkających w Warszawie.

  • W zasadzie powinniśmy zapisać wszystkie kombinacje adresów z filmami.

Definicja zależności wielowartościowej

Definicja 6.9 (Zależność wielowartościowa)

Zależność wielowartościowa

A_{1}\dots A_{k}\twoheadrightarrow B_{1}\dots B_{l}

dla relacji R(A_{1},\dots,A_{k},B_{1},\dots,B_{l},C_{1},\dots,C_{m}) oznacza, że jeśli dwie krotki są zgodne na składowych A_{i}, to można w nich zamienić składowe B_{i} i otrzymane krotki będą także w relacji R.

  • Inaczej mówiąc, lewa strona każdej takiej zależności nie wyznacza pojedynczej wartości, lecz zbiór wartości, np.

    nazwisko \twoheadrightarrow ulica,miasto
    nazwisko \twoheadrightarrow film,rok

Reguły dla zależności wielowartościowych

Stwierdzenie 6.1 (Promocja)

Każda zależność funkcyjna jest zależnością wielowartościową, czyli jeśli zachodzi X\rightarrow Y

to zachodzi także X\twoheadrightarrow Y

  • Niestety odwrotna implikacja nie jest prawdziwa!

Stwierdzenie 6.2 (Uzupełnianie)

Jeśli dla relacji R(X,Y,Z) zachodzi X\twoheadrightarrow Y

to zachodzi także X\twoheadrightarrow Z

Stwierdzenie 6.3 (Przechodniość)

Jeśli dla relacji R(X,Y,Z,V) zachodzą X\twoheadrightarrow Y
Y\twoheadrightarrow Z

to zachodzi także X\twoheadrightarrow Z

Dodatkowe uwagi

  • Podobnie jak dla zależności funkcyjnych, nie wolno rozbijać lewej strony zależności.

  • Ale dla zależności wielowartościowych nie wolno również rozbijać prawej strony!

Czwarta postać normalna — definicja

Definicja 6.10 (Nietrywialna zależność wielowartościowa)

Zależność wielowartościowa X\twoheadrightarrow Y dla relacji R jest nietrywialna, jeśli

  • Y\not\subseteq X oraz

  • X\cup Y nie są wszystkimi atrybutami R

Definicja 6.11 (4NF)

Relacja R jest w czwartej postaci normalnej (4NF), jeśli dla każdej nietrywialnej zależności X\twoheadrightarrow Y w R, X jest nadkluczem R.

Wnioski

  • Jeśli relacja jest w 4NF, to jest też w BCNF.

  • Odwrotne zawieranie nie zachodzi.

Rozkład do 4NF

  • Podobnie jak dla BCNF, szukamy zależności X\twoheadrightarrow Y naruszającej 4NF.

  • Rozbijamy relację R(X,Y,Z) na dwie relacje:

    R_{2}(X,Y)
    R_{1}(X,Z)
  • Kończymy, gdy już nie ma takich zależności.

Przykład rozkładu do 4NF

  • Zaczynamy od relacji Aktorzy(nazwisko,ulica,miasto,film,rok)

    i zależności
    nazwisko \twoheadrightarrow ulica,miasto
    nazwisko \twoheadrightarrow film,rok

  • W skład klucza wchodzą wszystkie kolumny tabeli.

  • Obie zależności naruszają więc 4NF (bo nie są trywialne).

  • Wybieramy do rozkładu pierwszą z nich.

  • Otrzymujemy dwie tabele
    Aktorzy1(nazwisko,ulica,miasto)
    Aktorzy2(nazwisko,film,rok)

    z tymi samymi zależnościami.

  • Ponieważ obie zależności stały się trywialne, kończymy.

6.6. Zadania

Ćwiczenie 6.1

Czy któraś z podanych zależności funkcyjnych jest zależnością trywialną?

  1. A\rightarrow A

  2. AB\rightarrow BC

  3. BC\rightarrow C

Rozwiązanie: 

Pierwsza i trzecia.

Ćwiczenie 6.2

Dla relacji R(A,B,C,D) nie określono żadnych zależności funkcyjnych. Relacja R:

  • nie ma żadnego klucza

  • ma jeden klucz

  • ma 4 klucze.

Rozwiązanie: 

Ma jeden klucz, składający się z wszystkich atrybutów relacji.

Ćwiczenie 6.3
Rozwiązanie: 
Ćwiczenie 6.4

Które z poniższych stwierdzeń są prawdziwe:

  1. Każda relacja w 3NF jest także w BCNF.

  2. Każda relacja w BCNF jest także w 3NF.

  3. Każda relacja dwuargumentowa jest w BCNF.

Rozwiązanie: 

Drugie i trzecie.

Ćwiczenie 6.5

Dana jest tabela R(A,B,C,D,E) z jedynymi zależnościami funkcyjnymi

A\rightarrow B,AB\rightarrow CD,D\rightarrow ABCE

Który z poniższych zbiorów atrybutów jest kluczem R?

  1. A

  2. AB

  3. CD

Rozwiązanie: 

Tylko A.

Ćwiczenie 6.6

Dana jest tabela R(A,B,C,D) z jedynymi zależnościami funkcyjnymi

A\rightarrow B,B\rightarrow C,C\rightarrow A

będąca w pierwszej postaci normalnej (1NF).

W jakich jeszcze postaciach jest ta tabela?

  1. 2NF

  2. 3NF

  3. BCNF

Rozwiązanie: 

2NF i 3NF.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.