---
# System prepended metadata

title: Bazy Danych  lista3

---


---
tags: BD, lista 3
---
# Bazy Danych  lista3

## ZADANIA 7/9 : <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:gray">8</span>, <span style="color:gray">9</span>
**Zadanie 1** :rocket: Pokaż, że nie istnieje takie zapytanie koniunkcyjne używające jako formuł atomowych wyłącznie perspektyw *P3(x,y)* i *P4(x,y)*, które jest równoważne zapytaniu *P5(x,y)*. 

Podam przykład grafów *G1* i *G2*, które mają ten sam zbiór relacji *P3* i *P4* a tylko jeden z nich zawiera scieżkę długości 5. Gdyby istniało takie zapytanie koniunkcyjne to było by spełnione dla obu grafów, a tylko jeden ma cieżke długości 5. 

![](https://i.imgur.com/MV3rK2a.png)

**Zadanie 2** :memo:/:rocket: Napisz zapytanie rrd (dozwolone ∃, ∀ i wszystkie spójniki boolowskie),
które korzysta wyłącznie z perspektyw *P3(x,y)* i *P4(x,y)* i jest równoważne zapytaniu *P5(x,y)*.

![](https://i.imgur.com/rZ3xjcJ.png)
Jeśli jakaś para *x, y* spełnia to zapytanie to omiędzy nimi jest ścieżka długości 5. 


**Zadanie 3** :rocket:
1. Pokaż, że istnieje graf G, taki, że dla dowolnego grafu G′ istnieje homomorfizm z G′ w G.
* Niech *G* składa się z jedego wierzchołka i jedej pętelki **1-1**
    * dla dowolnego *G'* homomorfizm to *h(v) = 1* 
3. Udowodnij lub podaj kontrprzykład na stwierdzenie: dla dowolnych grafów G1 i G2 następujące warunki są równoważne:
    * istnieją homomorfizmy *h1 : G1 → G2* oraz *h2 : G2 → G1* (mówimy, że takie grafy są homomorficznie równoważne)
    *  istnieje izomorfizm *f : G1 → G2*
* KONTRPRZYKŁAD:
![](https://i.imgur.com/3z3M9GU.png)
    * h1(v) = 1 
    * H2(v) = 1 
    
**Zadanie 4** :rocket: W tym zadaniu rozważamy grafy symetryczne tzn. takie, że jeśli istnieje krawędź z v do w to istnieje też krawędź z w do v . Pokaż, że każde dwa takie grafy będące cyklami o parzystej długości są homomorficznie równoważne.

Załóżmy, że *G1* składa się z *2n* wierzchołków a *G2* z *2k* wierzchołków i niech *n>=k*. Wierzchołki na cyklu *G1* mogę ponumerowć kolejno *1, 2, ..., 2n* oraz analogicznie dla *G2*. Wtedy:
* h1(v) = (v mod2) +1 
* h2(v) = (v mod2) +1 
* Krawędzie zarówno w *G1* jak i w *G2* występują miedzy wierzchołkami o różnej parzystości.
    * [h(v),h(v+1)] =  [1,2] lub [2,1] <- te krawędzie należą napewno do *G1* i *G2*.    

**Zadanie 5** :memo:/:rocket: Pokaż, że problem 3SAT można wyrazić jako problem istnienia homomorfizmu pomiędzy bazami danych, tzn. pokaż, że jesli potrafisz rozwiązywać problem istnienia homomorfizmu to potrfisz także rozwiązywać problem 3SAT. Twoja konstrukcja powinna działać w czasie wielomianowym.

Baza danych *D1* zawiera *8+4+2 = 14* tabel/relacji. Tabele podzielone są na 3 grupy: pierwsza grupa będzie odpowiadała klauzulom 3 elementowym, drguga grupa klauzulom 2 argumentowym, a trzecia grupa 1 argumentowym. Każda klauzula 3 argumentowa (składająca się z 3 literałów) może mieć jedną z *8* postaci, na niektórych pozycjach zmienną zadaniową a na pozostałych zanegowaną zmienną zdaniową. Relacja *K 3, 0* będzie zawierać krotkę *<p,q,r>* gdy w formule wystęuje klazula *p v q v r*. Drugi parametr określa, które zmienne zdaniowe mają być zanegowane. 

Baza danych *D2* zawiera relacje o tych samych nazwach co *D1*, krotki zawarte w danej relacji to wartościowania, które spełniają klauzulę tego typu*. 

**Zadanie 6** :rocket:/:memo: Zaproponuj algorytm obliczania dla danej bazy z nullami D zbioru ```{I|I ∈ rep(D)}```, tzn. zbioru krotek obecnych w każdej bazie w rep(D), zbiór ten oznaczmy certain(D).

Iteruję się po wszystkich możliweych krotkach jakie potencjalnie mogą się znajdować w *D* (korzystając z dziedzin poszczególnych kolumn). Nastepnie decyduje czy dana krotka *k* należy do *rep(D)*. Musi spełniać warunek:
* nie da się stworzyć tablei *D'* bez tej krotki
Przeglądam wszystkie krotki w *D* (z nullami) i analizuje te krotki, które dopasowują się do *k*, tzn. zgadzają się na odpowiadających polach lub mają na danm polu null. 

WYDAJE MI SIĘ, ŻE: zamieniam nulle tam gdzie dziedzina 1 argumentowa i wszystkie krotki bez nulli wrzucam do wyniku. 

Wszystko co nie jest nullem będzie w wyniku + jeśli kolumna/relacja ma dziedzinę jedno argumentową -> wtedy w wyniku dziedzina tez ( jeśli w kolumna/relacja zawera null).

**Zadanie 7** :rocket:
![](https://i.imgur.com/d0JBODp.jpg)

## MATERIAŁY
* kalkulator algebry relacji: https://dbis-uibk.github.io/relax/help#relalg-reference 


