---
# System prepended metadata

title: Bazy Danych  lista4

---


---
tags: BD, lista 4
---
# Bazy Danych  lista4

## ZADANIA 9/10 : <span style="color:green">1</span>, <span style="color:green">2</span>, <span style="color:green">3</span>, <span style="color:green">4</span>, <span style="color:green">5</span>, <span style="color:green">6</span>, <span style="color:green">7</span>, <span style="color:green">8</span>, <span style="color:green">9</span>
**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 


