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