---
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.


**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)*.

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:
* 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:

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