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 – 2. Algebra relacji – MIM UW

Zagadnienia

2. Algebra relacji

Algebra relacji jest modelem teoretycznym do opisywania semantyki relacyjnych baz danych, zaproponowanym przez T. Codda, twórcę koncepcji relacyjnych baz danych. Jest to algebra, w której dziedzinę stanowią relacje. Zmienne występujące w wyrażeniach tej algebry odpowiadają pojedynczym relacjom.

Operatory algebry relacji zostały dobrane tak, aby odpowiadały typowym operacjom występującym w zapytaniach podczas wyszukiwania informacji z tabel w bazie danych.

Tak określona algebra miała być językiem zapytań (query language) dla relacyjnych baz danych.

2.1. Relacje

Relacje w algebrze relacji reprezentujemy ich nazwami. Z nazwą każdej relacji jest związany jej schemat — ciąg nazw atrybutów (odpowiadających kolumnom modelowanej tabeli), np.

  • R(A,B,C)

  • Student(indeks,imię,nazwisko)

Nazwy atrybutów w schemacie relacji muszą być różne, dlatego w literaturze schemat jest czasem definiowany jako zbiór nazw atrybutów, a nie ciąg.

Ponieważ relacje miały być abstrakcyjnym modelem tabel, ich elementy nazywa się często krotkami — odpowiadają one wierszom tabel z bazy danych.

2.2. Operacje

Zestaw operacji jest spory. Obejmuje po pierwsze typowe operacje teoriomnogościowe: sumę zbiorów (\cup), iloczyn zbiorów (\cap) i różnicę zbiorów (-). Wymaga się, aby oba argumenty miały ten sam schemat atrybutów. Jeśli nazwy atrybutów różnią się, to należy użyć operacji przemianowania (o czym za chwilę).

Iloczyn kartezjański (R\times S) także jest zdefiniowany klasycznie. Ponieważ jednak argumenty mogą mieć atrybuty o tych samych nazwach, nazwy kolumn w schemacie wynikowym trzeba czasem poprzedzać nazwami relacji, z których pochodzą, np. dla relacji R(A,B) i S(B,C) schematem ich iloczynu kartezjańskiego będzie R\times S(A,R.B,S.B,C), tak jak w poniższym przykładzie

R1 = A B
1 2
3 4
R2 =
B C
5 6
7 8
9 10

R1 \times R2 = A R1.B R2.B C
1 2 5 6
1 2 7 8
1 2 9 10
3 4 5 6
3 4 7 8
3 4 9 10

Lepiej jednak w takiej sytuacji użyć przemianowania.

2.2.1. Selekcja

Oprócz operacji teoriomnogościowych w algebrze relacji określono kilka operacji (a właściwie rodzin operacji) specyficznych dla niej. Pierwsza z nich to selekcja (wybór) \sigma _{{warunek}}(R). Zgodnie z nazwą wybiera ona z relacji tylko te krotki, dla których jest spełniony podany warunek.

Przypuśćmy, że w mamy relację Zwierzaki o następującej postaci:

gatunek imię waga
Papuga Kropka 3,50
Papuga Lulu 5,35
Papuga Hipek 3,50
Lis Fufu 6,35
Krokodyl Czako 75,00

Wartością wyrażenia \sigma _{{gatunek=^{{\prime}}Papuga^{{\prime}}}}\texttt{Zwierzaki} jest:

gatunek imię waga
Papuga Kropka 3,50
Papuga Lulu 5,35
Papuga Hipek 3,50

2.2.2. Rzutowanie

Podobna do selekcji jest operacja rzutowania (projekcji) \pi _{{kolumna_{1},...,kolumna_{n}}}(R): z relacji wybieramy tylko podane kolumny. Zwróćmy uwagę, że mogłoby to prowadzić do utworzenia relacji, w której niektóre wiersze byłyby takie same. Ponieważ jednak relacje są zbiorami, więc takie duplikaty są automatycznie eliminowane, tak jak w poniższym przykładzie dla wyrażenia \pi _{{gatunek,waga}}\texttt{Zwierzaki}:

gatunek waga
Papuga 3,50
Papuga 5,35
Lis 6,35
Krokodyl 75,00

Ze względów praktycznych warto zdefiniować uogólnione rzutowanie, w którym oprócz nazw kolumn dozwolone są dowolne wyrażenia oparte na kolumnach, np. arytmetyczne. Trzeba je tylko wtedy nazwać: A+B\rightarrow C

Ponadto dopuszcza się, aby pewne kolumny wystąpiły wielokrotnie, wymagane jest jednak przemianowanie jak powyżej.

A oto przykład: dane jest relacja R

R =
A B
1 2
3 4

Wartością wyrażenia \pi _{{A+B\rightarrow C,A,A\rightarrow A1}}R będzie

C A A1
3 1 1
7 3 3

Wspominaliśmy wcześniej o operacji przemianowania \rho _{S}(R): nie powoduje ona żadnych zmian w zawartości relacji, lecz służy jedynie

  • do zmiany nazwy relacji: \rho _{S}(R)

  • lub zmiany nazw jej atrybutów \rho _{{R(X,Y,Z)}}R,

  • a czasem jednego i drugiego: \rho _{{S(X,Y,ZX)}}R.

Złączenie R\underset{\theta}{\Join}S: podobne do iloczynu kartezjańskiego, ale łączy się ze sobą tylko pary wierszy spełniające podany warunek

  • R\underset{\theta}{\Join}S=\sigma _{{\theta}}(R\times S)

  • \theta oznacza dowolny warunek na kolumny łączonych relacji, np. A<C.

  • Złączenie theta, w którym warunek jest prostą równością pary atrybutów, nazywa się złączeniem równościowym.

  • Pojęcie porzuconej krotki (dangling tuple): wiersza z jednej z relacji, do którego nie pasuje żaden wiersz z drugiej relacji.

  • Zwierzaki
    gatunek imię waga
    Papuga Kropka 3,50
    Papuga Lulu 5,35
    Papuga Hipek 3,50
    Lis Fufu 6,35
    Krokodyl Czako 75,00
    Gatunki
    nazwa kontynent
    Papuga Ameryka
    Lis Europa
    Krokodyl Afryka
  • Zwierzaki \underset{gatunek=nazwa}{\Join} Gatunki
    gatunek imię waga nazwa kontynent
    Papuga Kropka 3,50 Papuga Ameryka
    Papuga Lulu 5,35 Papuga Ameryka
    Papuga Hipek 3,50 Papuga Ameryka
    Lis Fufu 6,35 Lis Europa
    Krokodyl Czako 75,00 Krokodyl Afryka

  • Notacja: R\Join S.

  • Łączone relacje muszą mieć co najmniej jedną wspólną kolumnę o tej samej nazwie.

  • Warunkiem złączenia jest równość dla wszystkich par atrybutów o tych samych nazwach.

  • W wyniku zostaje tylko jedna kolumna z pary kolumn o tych samych nazwach.

  • Zwierzaki
    gatunek imię waga
    Papuga Kropka 3,50
    Papuga Lulu 5,35
    Papuga Hipek 3,50
    Lis Fufu 6,35
    Krokodyl Czako 75,00
    Gatunki
    gatunek kontynent
    Papuga Ameryka
    Lis Europa
    Krokodyl Afryka
  • Zwierzaki \Join Gatunki
    gatunek imię waga kontynent
    Papuga Kropka 3,50 Ameryka
    Papuga Lulu 5,35 Ameryka
    Papuga Hipek 3,50 Ameryka
    Lis Fufu 6,35 Europa
    Krokodyl Czako 75,00 Afryka

  • Pozwala na nazywanie relacji wynikowych: \rho _{{RS(A,B,X,C,D,E)}}(R\times S).

  • Uproszczone notacja: R1(A1,B,X,C,D,E):=(R\times S).

2.3. Wyrażenia

  • Ponieważ jest to algebra, więc operacje można składać otrzymując wyrażenia złożone.

  • Równoważność wyrażeń można wykorzystać przy optymalizacji, zastępując dane wyrażenie równoważnym mu, lecz bardziej efektywnym.

  • Zwierzaki
    gatunek imię waga
    Papuga Kropka 3,50
    Papuga Lulu 5,35
    Papuga Hipek 3,50
    Lis Fufu 6,35
    Krokodyl Czako 75,00
  • Znajdź pary zwierzaków (imiona) tego samego gatunku

\pi _{{Z1.imie,Z2.imie}}(\rho _{{Z1}}Zwierzaki\underset{\begin{array}[]{l}\scriptstyle Z1.gatunek=Z2.gatunek\land\\
\scriptstyle Z1.imie<Z2.imie\end{array}}{\Join}\rho _{{Z2}}Zwierzaki)

  • Zgodnie z matematyczną definicją relacji jako zbioru utożsamia się jednakowe krotki (powstające np. podczas rzutowania).

  • Można rozszerzyć tę algebrę na wielozbiory, dopuszczając powtórzenia.

  • Powstaje jednak problem odpowiedniej semantyki dla operacji iloczynu i różnicy teoriomnogościowej.

  • Intuicyjnie zdefiniowane rozszerzenia operacji na wielozbiory zastosowane do relacji dają relacje z wyjątkiem sumy, która dla dwóch relacji może dać wielozbiór.

  • Przestają zachodzić niektóre prawa algebry relacji, np.

    (R\cup S)-T=(R-T)\cup(S-T)
  • Operator eliminacji powtórzeń \delta(R).

  • Operator grupowania z ewentualną agregacją

    \gamma _{{A,MIN(B)\rightarrow MinB}}(R)
  • Zauważmy, że

    \gamma _{{A_{1},...,A_{n}}}(R)=\sigma(R)

    jeśli A_{i} to wszystkie atrybuty R.

  • Operator sortowania \tau _{{C,B}}(R).

  • Nie jest to operator algebry relacji ani wielozbiorów, lecz ewentualnej algebry list, dlatego powinien być zewnętrznym operatorem wyrażenia!

  • naturalne: R\stackrel{\circ}{\Join}S

    • jako wypełniaczy brakujących wartości w dołączonych kolumnach używa się \bot;

  • lewostronne: R\stackrel{\circ}{\Join}_{L}S

    • brane są tylko porzucone krotki z pierwszego argumentu;

  • prawostronne: R\stackrel{\circ}{\Join}_{R}S;

  • wersje theta powyższych (z warunkiem u dołu).

  • Zwierzaki
    gatunek imię waga
    Papuga Kropka 3,50
    Papuga Lulu 5,35
    Papuga Hipek 3,50
    Lis Fufu 6,35
    Krokodyl Czako 75,00
    Gatunki
    gatunek kontynent
    Papuga Ameryka
    Lis Europa
    Krokodyl Afryka
    Krowa Europa
  • Zwierzaki \Join Gatunki
    gatunek imię waga kontynent
    Papuga Kropka 3,50 Ameryka
    Papuga Lulu 5,35 Ameryka
    Papuga Hipek 3,50 Ameryka
    Lis Fufu 6,35 Europa
    Krokodyl Czako 75,00 Afryka
    Krowa \bot \bot Europa

2.4. Zastosowania algebry relacji

  • Zapisywanie zapytań (np. modelowanie semantyki)

  • Nakładanie ograniczeń na poprawność bazy danych (więzy). Przykłady:

    \begin{array}[]{ll}R\cap S=\emptyset&\mbox{(styl równościowy)}\\
R\cap S\subseteq\emptyset&\mbox{(styl teoriomnogościowy)}\end{array}
  • Integralność referencyjna

    \begin{array}[]{l}\pi _{{\mbox{\footnotesize\textit{klucz-zewnętrzny}}}}(R)\subseteq\pi _{{klucz}}(S)\\
\pi _{{\mbox{\footnotesize\textit{klucz-zewnętrzny}}}}(R)-\pi _{{klucz}}(S)=\emptyset\end{array}
  • Zależności funkcyjne

    A\rightarrow B:\qquad\sigma _{{R.A=R1.A\land R.b\ne R1.B}}(R\times\rho _{{R1}}(R))=\emptyset

2.5. Zadania

Ćwiczenie 2.1

Dane są dowolne relacje R(x), S(x), T(x) algebry relacji oraz wyrażenia (zapytania)

Q_{1}: (R\cup S)-T
Q_{2}: (R-T)\cup(S-T)

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

  1. Q_{1} i Q_{2} dają ten sam wynik

  2. Odpowiedź na Q_{1} może mieć mniej elementów niż odpowiedź na Q_{2}

  3. Q_{1} i Q_{2} mogą dać inne wyniki.

Rozwiązanie: 

Pierwsze.

Ćwiczenie 2.2

Dane są relacje R i Q, każda zawierająca n krotek. Relacja R\bowtie Q ma

  1. co najmniej n krotek

  2. co najwyżej n^{2} krotek

  3. zawsze 2n krotek

Rozwiązanie: 
  1. nie

  2. tak

  3. nie

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.