Logika i bazy danych, algebra relacyjna

Zad. 1

Niech \(R,S\) będą odpowiednio \(n+m\)- i \(m\)-argumentowymi symbolami relacyjnymi z sygnatury.
Określamy nową operację \(\div\) w algebrze relacyjnej:

\([\![R\div S]\!]=\{\langle a_1,\dots,a_n\rangle|\) dla każdego \(\langle b_1,\dots,b_m\rangle\in[\![S]\!]\ (\langle a_1,\dots,a_n,b_1,\dots,b_m\rangle\in[\![R]\!])\}\).

Pokazać, że operator \(\div\) jest wyrażalny za pomocą pozostałych operatorów algebry relacyjnej. Podać wyrażenie algebry relacyjnej, które jest równe \(R\div S\).

Wskazówka metodyczna

Chodzi o pokazanie, jak wiedz o równoważności logiki pierwszego rzędu i algebry relacyjnej pomaga.
Zadanie w wersji "Podać wyrażenie" ma dwa wykrzykniki w podręczniku baz danych Ullmana i Widom.

Definicje

Niejedednostajna klasa \(AC^0\) składa się z funkcji \(f:\{0,1\}^*\to\{0,1\}^*\) takich, że istnieje wielomian \(p(n)\) i stała \(c\) takie, że dla każdego \(n\) istnieje sieć logiczna \(C\) obliczająca \(f(x)\) dla wszystkich \(x\in\{0,1\}^n\), która:

ma \(n\) bramek wejściowych i \(m\) bramek wyjściowych
jest ponadto złożona z bramek logicznych AND, OR i NOT
bramki wejściowe i bramki logiczne mogą mieć dowolnie wiele wyjść
bramki AND i OR mogą mieć dowolnie wiele wejść, a bramki NOT zawsze tylko jedno
liczba bramek w sieci nie przkracza \(p(n)\)
głębokość sieci nie prekracza \(c\)

Niejedednostajna klasa \(NC^1\) składa się z funkcji \(f:\{0,1\}^*\to\{0,1\}\) takich, że istnieje wielomian \(p(n)\) i stała \(c\) takie, że dla każdego \(n\) istnieje sieć logiczna \(C\) obliczająca \(f(x)\) dla wszystkich \(x\in\{0,1\}^n\), która:

ma \(n\) węzłów wejściowych i jeden węzeł wyjściowy
jest złożona z bramek AND, OR i NOT
węzły wejściowe i bramki mogą mieć dowolnie wiele wyjść
bramki AND i OR muszą mieć 2 wejścia, a bramki NOT zawsze tylko jedno
liczba bramek w sieci nie przkracza \(p(n)\)
głębokość sieci nie prekracza \(c\log n\)

Zad. 2

Pokazać, że po odpowiednim (naturalnym) zakodowaniu struktur skończonych \(\mathfrak{A}\) w postaci ciągów binarnych \(code(\mathfrak{A})\), dla każdego zdania \(\varphi\) logiki pierwszego rzędu funkcja
\(f_\varphi:code(\mathfrak{A})\mapsto\) if \(\mathfrak{A}\models\varphi\) then \(1\) else \(0\)
należy do niejednostajnego \(AC^0\).

Zad. 3

Pokazać, że funkcja \(f_\varphi\) z poprzedniego zadania należy do niejednostajnego \(NC^1\).

Wskazówka metodyczna

Tak naprawdę \(AC^0\subseteq NC^1\) i o to w tym zadaniu chodzi matematycznie.
Ideologicznie \(NC^1\) jest dużo bardziej realistyczna niż \(AC^0\) i chodzi o to, że SQL (z grubsza równoważny logice pierwszego rzędu) daje się sprawnie wyliczać w architekturach równoległych.

Informacja Znana w dziedzinie baz danych reguła optymalizacji zapytań wyrażonych w algebrze relacyjnej polega na tym, by rozmiar wyników pośrednich otrzymywanych trakcie ewaluacji zapytania był jak najmniejszy.

Zad. 4

Pokazać, że następujący problem jest nierozstrzygalny:

Dane: wyrażenie \(E\) algebry relacyjnej nad sygnaturą składającą się z symbolu relacyjnego \(R\) i być może innych symboli.
Pytanie: Czy dla każdej struktury moc \(|[\![E]\!]|<|[\![R]\!]|^2\)?

Wskazówka metodyczna

To już będzie po twierdzeniu Trachtenbrota o nierostrzygalności logiki pierwszego rzędu nad skończonymi strukturami. Użyć go wraz z tw. Codda o równoważności logiki pierwszego rzędu i algebry relacyjnej.
Chodzi o wykazanie nierozstrzygalności pewnych pytań związanych z optymalizacją zapytań w bazach danych.
Zadanie jest lekko (ale tylko lekko) oszukańcze, bo ta "reszta" symboli może generować bardzo duże wyniki pośrednie, a my pytamy tylko o efekt końcowy.
Można się ratować tym, że z wiedzy o strukturze bazy może wynikać, że rozmiar \(R\) jest zdecydowanie dominujący (powiedzmy, wykładniczy) w stosunku do rozmiarów pozostałych relacji.

Zad. 5

Algebrę relacyjną z liniowym porządkiem na danych można skonstruować na dwa sposoby. Załóżmy, że \(\leq\) jest relacją liniowego porządku na wszystkich elementach, które mogą się pojawić w krotkach, a w sygnaturze nie ma stałych.

Pierwszy sposób polega na tym, że do każdej bazy danych wprowadzamy dodatkową tabelę (dkoładniej perspektywę) \(LEQ\) o dwóch kolumnach, która zawiera wszystkie krotki \(\langle a,b\rangle\) dla \(a,b\) należacych do aktywnej dziedziny i takich, że \(a\leq b\). Wówczas zwykłe wyrażenia algebry relacyjnej mogą wykorzystać \(LEQ\) jak każdą inną tabelę. Jednak \(LEQ\) uważamy za część składni zapytań, a nie zwykłą tabelę w bazie.

Drugi sposób polega na tym, że nie zwiększamy liczby tabel, ale poszerzamy składnię i w warunku \(\theta\) selekcji \(\sigma_\theta(E)\) dopuszczamy także nierówności postaci \(i\leq j\) dla \(i,j\) nie większych niż liczba kolumn w \(E\). Semantyka jest oczywista, np. \([\![\sigma_{i\leq j}(E)]\!]=\{\vec{a}\in [\![E]\!]:a_i\leq a_j\}.\)

Pokazać, że zbiory zapytań wyrażalnych w obu formalizmach są takie same.

Rozwiązanie

Każde wyrażenie \(\sigma_{\theta}(E)\), gdzie \(\theta\) zawiera nierówności mozna zastąpić równoważnie przez \(\sigma_{\theta_1}(\sigma_{\theta_2}(\ldots\sigma_{\theta_k}(E)\ldots))\), gdzie \(\theta_i\) to pojedyncze równości albo nierówności. Jeśli więc wyrazimy pojedynczą selekcję \(\sigma_{i\leq j}(E)\) za pomocą \(LEQ\), to osiągniemy cel.
Robimy to następująco: \(\pi_{1,2,\ldots,n}(\sigma_{i=n+1,j=n+2}(E\times LEQ))\), gdzie \(n\) to liczba kolumn w \(LEQ\).

W drugą stronę, niech \(AD\) to wyrażenie definiujące aktywną dziedzinę (jest w skrypcie). Wówczas \(LEQ=\sigma_{1\leq 2}(AD\times AD)\).

Definicja

Operator półzłączenia (ang. semijoin) \(\gg\) w algebrze relacyjnej ma następującą semantykę (uwaga: symbol tutaj użyty jest niestandardowy, bo standardowego nie udało mi się wyprodukować używając tutejszego języka znaczników):

\([\![R\gg_\theta S]\!]=\{\vec{a}\in [\![R]\!]~:~\exists \vec{b}\in[\![S]\!] \theta(\vec{a},\vec{b})\}\),
gdzie \(\theta\) to zbiór równości pomiędzy kolumnami \(R\) i \(S\), numerowanymi łącznie.

Na przykład dla binarnych \(R\) i \(S\)
\([\![R\gg_{1=3, 2=4} S]\!]=\{\langle a_1,a_2\rangle\in [\![R]\!]~:~\exists \langle b_1,b_2\rangle\in[\![S]\!]a_1=b_1\land a_2=b_2\}.\)

Zad. 6

Wykaż, że półzłączenie jest wyrażalne w algebrze relacyjnej i podaj jego definicję za pomocą pozostałych operatorów.

Zad. 7

Wykaż, że wyrażenia zbudowane z relacji przy użyciu selekcji, projekcji, sumy, różnicy i półzłączenia nie wyrażają wszystkich zapytań definiowalnych w zwykłej algebrze relacyjnej.

Rozwiazanie

Zad. 8

Wykaż, że każde wyrażenie zbudowane z relacji przy użyciu selekcji, projekcji, sumy, różnicy i półzłączenia w bazie danych, w której elementami są liczby naturalne, można obliczyć algorytmem o złożoności czasowej \(O(n\log n),\) gdzie \(n\) to maksymalna liczba krotek w relacjach.

Zad. 9

Wykaż, że wyrażenia zbudowane z relacji przy użyciu projekcji, produktu, sumy, różnicy i półzłączenia wyrażają wszystkie zapytania definiowalne w zwykłej algebrze relacyjnej, o ile w sygnaturze nie ma stałych.

Zad. 10

Wykaż, że istnieje wyrażenie zbudowane z relacji przy użyciu selekcji, projekcji, sumy, różnicy i półzłączenia, które wyraża przecięcie relacji.

Zad. 11

Pokazać, że poszczególne operatory algebry relacyjnej nie są wyrażalne za pomocą pozostałych:

Suma się nie wyraża za pomocą selekcji, rzutowania, produktu i różnicy.
Różnica się nie wyraża za pomocą selekcji, rzutowania, produktu i sumy.
Pozostałe przypadki są banalne.

Zad. 12

Dane są dwie tabele \(A\) i \(B\) o dwóch kolumnach każda. Ta pierwsza składa się z \(n_A\) wierszy.

Zaprojektować algorytm wyliczenia wartości wyrażenia algebry relacyjnej

\(A-\pi_{1,2}(\sigma_{1=3}(A\times B)).\)

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są dwukolumnowe tablice, których wiersze indeksowane są nieujemnymi liczbami całkowitymi i zawierają takież liczby.

W algorytmie należy użyć dokładnie jednej takiej tablicy o rozmiarze \(n_A\) wierszy i kilku dodatkowych zmiennych typu integer. Oznacza to, że wykorzystujemy dokładnie tyle pamięci, ile zajmie wynik. Proszę nie używać wskaźników, rekursji i innych metod ukrytego alokowania dodatkowej pamięci.

Tabele \(A\) i \(B\) są tylko do odczytu, przy czym można założyć, że są one posortowane. Jeśli rozwiązanie będzie z tego korzystać, proszę o tym założeniu wspomnieć.

Zad. 13

Niech \(k\in\mathbb{N}\) będzie stałą. Wykazać, że jeśli \(E\) jest wyrażeniem algebry relacyjnej i maksymalna liczba kolumn w podwyrażeniach \(E\) wynosi \(k\), to istnieje algorytm obliczający wartość \([\![E]\!]\) w każdej strukturze \(\mathfrak{A}\) i działający w czasie \(O(n^{k}\log n),\) gdzie \(n\) to liczność dziedziny aktywnej \(\mathfrak{A}\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z \(\mathfrak{A}\) są przekazywane do algorytmu właśnie w takich tablicach: relacja o \(l\) kolumnach jest reprezentowana przez \(l\) tablic, a dane zajmują początkowe indeksy. Wynik obliczenia zwraca się analogicznie.

Informatyka MIMUW