Bazy Danych lista4

--- tags: BD, lista 4 --- # Bazy Danych lista4 ## ZADANIA 9/10 : 1, 2, 3, 4, 5, 6, 7, 8, 9 **Zadanie 1** :rocket: Rozważmy następujące zapytanie w Datalogu. ``` T(X, Y) :- E(X,Y). T(X, Y) :- T(X,Z), T(Z,Y). ``` 1. Przypomnij definicję semantyki dla Datalogu, a następnie pokaż, że dla każdego ``i ∈ N+`` zachodzi ```T_i = {(a, b)| istnieje ścieżka z a do b o długości ≤ 2^(i−1) }``` * datalog - "deklaratywny", "bazodanowy" jęyk zapytań rozszerzający język zapytań koniunkcyjnych o rekurencję. * program datalogowy skłąda się z głowy i ciała * głowa - relacja, którą definiujemy * ciało - zbiór reguł (symboli relacyjnych), które wyrażają jakieś koniunkcyjne zapytanie, każda zmienna występująca w głowie musi pojawić się także w ciele i dopuszczamy, że definowany w głowie symbol relacyjny występuje też w ciele (rekurencja) * SEMANTYKA datalogu: * **procedularna** [określa procedurę jak wyliczyć wynik danego programu w datalogu] * 1. Początkowo wszystkie relacje, które definujemy w programie, są puste. * 2. ?Zaaplikuj wszystkie reguły dla każdej relacji relacji, równocześnie.? * 3. Powtarzaj dopóki conajmniej jedna relacja zyskuje nowy element. * deklaratywna Dowdód indukcyjny : * Teza indukcyjna: dla ``n`` zachodzi ``T_n = {(a, b)| istnieje ścieżka z a do b o długości ≤ 2^(n−1)}`` * dla ``n = 0`` ``T_0 = {}`` * załóżmy, że teza indukcyjna zachodzi dla ``n`` * Aplikuję reguły aby wyliczyć ``T_(n+1)``: * ``T_(n+1) = {(a,b)| E(a,b) lub istnieje z t.że T_n(a,z) i T_n(z,b)}`` = * ``{(a,b)| E(a,b) lub istnieje ścieżka z a do b dł <= 2^(n−1) + 2^(n−1) = 2^n}`` = * ``{(a,b)| istnieje ścieżka z a do b dł <= 2^n}`` **Zadanie 2** :rocket: Zwróci wierzchołki, do których można dojść ścieżką z n lub ścieżką z m. ``` T(X) :- E(n,X). T(X) :- E(m,X). T(X) :- T(Z), T(Z,X). ``` **Zadanie 3** :rocket: Zwróci wierzchołki, do których można dojść ścieżką z n i ścieżką z m. **ŹLE** ZNaleźć wszystkie ścieżki najpierw potem wierzchołki które mają scieżkę do m i n ``` T(X) :- E(n,X), E(m,X). T(X) :- T(Z), T(Z,X). ``` **Zadanie 4** :rocket: Zwróci pary wierzchołków, do których można dojść z wierzchołka n ścieżkami o tej samej długości. ``` T(X,Y) :- E(n,X), E(n,Y). T(X,Y) :- T(a,b), E(a,X), E(b,Y). ``` **Zadanie 5** :rocket: Zwróci pary wierzchołków x, y , takie, że z wierzchołka n do x oraz do y można dojść ścieżkami, które mają różną długość. T(X,Y) - jest ścieżka równej długości z x do y (z poprzedniego zadania) T'(x,y) - jest jaka kolwiek ścieżka z x do y T''(x,y) - jest ścieżka równej długości z n do a oraz z n do y, oraz jest dowolna ścieżka z a do x ``` T'(x,y) :- E(x,y) T'(x,y) :- T'(x,z), E(z,y) T''(x,y) :- T(a,y), T'(a,x) T''(x,y) :- T(x,b), T'(b,y) ``` **Zadanie 6** :rocket: Zwróć pary wierzchołków x, y takie, że nie istnieje ścieżka z x do y. Nie da się napisać takie zapytania w datalogu, bo: * im większa baza danych, im więcej wpisów tym mniejsza może być odpowiedź (wszystkie występujące wcześniej krawędzie nadal występują i dodajemy nowe). Wynik zapytania powinien pozostać taki sam lub się zmniejszyć. A zapytania w datalogu są monotoniczne im większa baza tym większy więkzy lub nie mniejszy wynik. (CZY TO Z WYKŁADU??). **Zadanie 7** :rocket: Zwróć pary wierzchołków x, y , takie, że z x do y można przejść jednokolorową ścieżką. T'(x,y,c) - jest ścieżka z x do y koloru c. T(x,y) - jest ścieżka w jednym kolorze z x do y. ``` T'(x,y,c) :- E(x,y,c) T'(x,y,c) :- T'(x,z,c), E(z,y,c) T(x,y) :- T'(x,y,c) ``` **Zadanie 8** :rocket: Zwróć pary wierzchołków x, y takie, że każda ścieżka z x do y składa się z krawędzi co najmniej dwóch kolorów. Nie da się bo po zwiększeniu się bazy może zmienjszyć się wynik zapytania, a zapytania w datalogu są monotoniczne. **Zadanie 9** :rocket: Zwróć pary wierzchołków x, y , takie, że z x do y można przejść ścieżką składającą się z krawędzi nie więcej niż dwóch kolorów. T'(x,y,c) - jest ścieżka z x do y koloru c. T''(x,y,c,c') - jest ścieżka tylko z kolorami c i c' na krawędziach z x do y T(x,y) - jest ścieżka w jednym lub 2 kolorach z x do y ``` T'(x,y,c) :- E(x,y,c) T'(x,y,c) :- T'(x,z,c), E(z,y,c) T''(x,y,c,c') :- T'(x,z,c), T'(z,y,c') T''(x,y,c,c') :- T'(x,z,c'), T'(z,y,c) T''(x,y,c,c') :- T''(x,z,c,c'), T''(z,y,c,c') T(x,y) :- T'(x,y,c) T(x,y) :- T''(x,z,c,c') ``` ## MATERIAŁY * kalkulator algebry relacji: https://dbis-uibk.github.io/relax/help#relalg-reference