Lab 12

back

Algebra relacji

Zakładamy jakiś schemat danych składający się z pewnych relacji.

• Wyrażenia atomowe: $\{(a_1, a_2, \ldots, a_n\}$, $R$, gdzie $R$ jest relacją w schemacie
• Selection:
  • $\sigma_{i=j}(S) = \{(a_1, \ldots, a_n)\,|\, (a_1, \ldots, a_n) \in S, a_i=a_j\}$
  • $\sigma_{i=c}(S) = \{(a_1, \ldots, a_n)\,|\, (a_1, \ldots, a_n) \in S, a_i=c\}$ dla pewnej wartości (stałej) $c$
• Projection: $\pi_{i_1, \ldots, i_k}(S) = \{(a_{i_1}, \ldots, a_{i_k})\, |\, (a_1, \ldots, a_n) \in S\}$
• Cartesian product: $S \times T = \{(a_1, \ldots, a_n, b_1, \ldots, b_m)\,|\, (a_1, \ldots, a_n) \in S, (b_1, \ldots, b_m) \in T\}$
• Union: $S \cup T = \{(a_1, \ldots, a_n)\,|\,(a_1, \ldots, a_n) \in S\,\lor\, (a_1, \ldots, a_n) \in T\}$
• Difference:
  $S \setminus T = \{(a_1, \ldots, a_n)\,|\,(a_1, \ldots, a_n) \in S\,\lor\, (a_1, \ldots, a_n) \in T\}$

Zadanie 1

Schemat bazy:

• Film(Tytuł, Reżyser, Aktor)
• Kino(Nazwa, Adres)
• Seans(Kino, Film, Godzina)

Napisz zapytania w FOL i w algebrze relacji:

1. Wypisz nazwy i adresy kin wyświetlających filmy Bergmana
   $$\varphi(k, adr) = \exists_{f, g, akt} \,Seans(k, f, g) \land Film(f, \texttt{'Bergman'}, akt) \land Kino(k, adr)$$
   $$\pi_{1, 8}\, \sigma_{1=7,2=4, 5=\texttt{'Bergman'}}\, (Seans \times Film \times Kino)$$
2. Czy grają gdzieś Bergmana?
   $$\varphi = \exists_{k,f,g,akt, adr}\,Seans(k, f, g) \land Film(f, \texttt{'Bergman'}, akt) \land Kino(k, adr)$$
   $$\pi_1\,\sigma_{5=\texttt{'Bergman'}}\, (Seans \times Film \times Kino)$$
3. Wypisz takie pary osób, że pierwsza reżyserowała drugą i odwrotnie.
   $$\varphi(r_1, r_2) = \exists_{t_1, t_2}\,Film(t_1, r_1, r_2) \land Film(t_2, r_2, r_1)$$
   $$\pi_{2, 3} \,\sigma_{2=6}\,\sigma_{3=5}\,(Film \times Film)$$
4. Wypisz reżyserów, którzy grali w swoim filmie.
   $$\varphi(r) = \exists_f\,Film(f, r, r)$$
   $$\pi_{2}\,\sigma_{2=3}\,Film$$
5. Wypisz krotkę $(\texttt{'Czas apokalipsy'}, \texttt{'Copolla'})$.
   $$\varphi(f, r) = (\texttt{'Czas apokalipsy'}, \texttt{'Copolla'})$$
   $$\sigma_{1=\texttt{'Czas apokalipsy'}} \sigma_{2 =\texttt{'Copolla'} } \{ (f, r) \}$$

Zadanie 2

Napisz wyrażenie algebry relacji wykorzystujące tylko selekcję, rzutowanie i produkt (SPC), które wylicza przecięcie dwóch relacji.

Rozwiązanie

$$\pi_{1, \ldots n}\,\sigma_{1=n+1,\,2=n+2,\,\ldots,\,n=2n} (R \times S)$$

Zadanie 3

Udowodnij, że różnicy dwóch relacji nie daje się wyliczyć wyrażeniem algebry relacji używającym jedynie selekcji, rzutowania, produktu i sumy (algebra SPCU).

Rozwiązanie

Możemy udowodnić nawet więcej: każdy z operatorów algebry relacji jest niezależny od pozostałych.

Lemat 1: Jedyne operacje zwiększające kardynalność wyniku to suma i produkt kartezjański.
Lemat 2: Jedyna operacja zmniejszająca arność krotek wynikowych to projekcja.
Lemat 3: Jedyna operacja zwiększająca arność krotek wynikowych to produkt kartezjański.
Lemat 4: Jedyne operacje pomniejszające kardynalność wyniku to selekcja i różnica, poza trywialnym przypadkiem $R \times \emptyset$.

Suma jest niezależna na mocy Lematu 1, bo tylko ona pozwala uzyskać większą kardynalność bez zmiany arności.
Projekcja jest niezależna na mocy Lematu 2.
Produkt kartezjański jest niezależny na mocy Lematu 3.

Różnica
Wszystkie operatory za wyjątkiem różnicy mają są monotoniczne, t.j. dodając krotki do źródłowych relacji możemy jedynie zwiększyć rozmiar wyniku.

Innymi słowy, jeśli mamy schemat z $S$ i $T$ oraz zapytanie algebry relacji $E$ składające się jedynie z operacji SPCU to
$$S \subseteq S' \land T \subseteq T' \implies E(S, T) \subseteq E(S', T')$$
To oczywiście nie zachodzi dla różnicy: przy $S \setminus T$ możemy zmniejszyć wynik dodając krotki do $T$.

Selekcja jest niezależna, bo tylko ona zmniejsza kardynalność wyniku jednocześnie będąc monotoniczna.

Zadanie 3.1

Zdefiniuj operator
$$S \bowtie_{i_1=j_1,\ldots,i_k=j_k} T = \{(a_1, \ldots, a_n, b_1, \ldots, b_m)\,|\,(a_1, \ldots, a_n) \in S, (b_1, \ldots, b_m) \in T, a_{i_1} = b_{j_1}, \ldots, a_{i_k} = b_{j_k}\}$$

Rozwiązanie

$$S \bowtie_{i_1=j_1,\ldots,i_k=j_k} T = \sigma_{i_1=n+j_1,i_2=n+j_2,\ldots,i_k=n+j_k} (S \times T)$$

Zadanie 4

Mikrozadanie.
Napisz wyrażenie algebry relacji (selekcja, rzut, produkt, suma, różnica) wyliczające wynik operacji
$$R:S = \{t\,|\,\{t\} \times S \subseteq R\}$$

Zadanie 5

Udowodnij, że każde wyrażenie algebry SPC (tj. używające tylko operacji selekcji, rzutu i produktu) można równoważnie napisać w następującej postaci normalnej:
$$\pi_{k_1, \ldots, k_n} \sigma_\theta (R_1 \times \ldots \times R_m)$$
gdzie $\theta$ to zbiór równości między kolumnami oraz między kolumnami a stałymi.

Rozwiązanie

Rozpatrzmy drzewo zapytania, w którym każdy wierzchołek jest jednym z operatorów a dzieci to jego operandy. A więc wierzchołek produktu ma dwoje dzieci, selekcji jedno i projekcji też jedno.

Dowód przebiega przez indukcję po budowie drzewa. Wykazujemy, że możemy zmodyfikować drzewo tak, że selekcja nie ma w poddrzewie projekcji, a produkt ani selekcji ani projekcji.

Węzeł postaci $(\pi_{i_1, \ldots, i_n} A) \times B$ jest oczywiście równoważny $\pi_{i_1, \ldots, i_n} (A \times B)$. Podobnie $A \times (\pi_{i_1, \ldots, i_n} B)$ jest równoważne $\pi_{i_1 + |A|, \ldots, i_n + |A|} (A \times B)$.

Analogicznie dla $(\sigma_t A) \times B$ oraz $A \times (\sigma_t B)$.

Zrzuciliśmy wszystkie produkty poniżej selekcji i projekcji. Teraz łatwo zauważyć, że $\sigma_{j=k} (\pi_{i_1, \ldots, i_n} A)$ da się przerobić na projekcję selekcji $A$. Wymaga to przenumerowania $j$ i $k$ tak, żeby odnosiło się do tych samych kolumn przed projekcją.

Zadanie 6

Udowodnij, że operator sumy nie daje się wyrazić wyrażeniem algebry SPC (czyli używającym tylko selekcji, rzutowania i produktu).

Rozwiązanie

Patrz Zadanie 3.

back