# BD 16.03.2021

## Zadanie 1

### Tomasz Orda

### Anadi Agrawal

Z wykładu wiemy, że istnieje równoważność między rrk i rrd, więc pokażemy implikację do tej drugiej.
Dowód będzie indukcyjny. Bazą indukcji będą relacje, tj. $\phi = R$. W rrd można je zapisać, jako $R(x_1, x_2, \ldots, x_k)$.

Krok indukcyjny wygląda tak, że mamy pewne dwie formuły $\phi_1$ i $\phi_2$ dla których istnieje równoważny zapis w rrd (oznaczmy przez $\Phi(\phi)$) i chcemy pokazać, że dla dowolnej operacji $\pi, \sigma_F, \rho, \times, \setminus$ istnieje odpowiednia formuła w rrd:
* Dla $\pi_{x_1, x_2, \ldots, x_k}(\phi_1)$ możemy to zapisać, jako $\{x_1, x_2, \ldots, x_k \, | \, \exists_{z_1, \ldots, z_l} \Phi(\phi_1)(x_1, x_2, \ldots, x_k, z_1, \ldots, z_l)\}$
* Dla $\rho_{x_1, \ldots, x_k}(\phi_1)$, mamy po prostu $\Phi(\phi_1)(x_1, \ldots, x_k)$
* Dla $\sigma_F(\phi_1)$, mamy po prostu $\Phi(\phi_1) \land F$ (bo $F$ z warunków jest też formułą dla rrd)
* Dla $\times$ możemy to zapisać, jako $\{ X, Y \, | \, X \in \Phi(\phi_1) \land Y \in \Phi(\phi_2) \}$
* Ostatecznie różnicę można zapisać podobnie: $\{ X \, | \, X \in \Phi(\phi_1) \land X \notin \Phi(\phi_2) \}$

## Zadanie 2

### Maciej Zientara
Relacje R(A,B,C) oraz S(X,Z)
Własność klucza obcego mówi, że nie istnieje element w kluczu obcym, który nie ma odpowiednika w kluczu głównym.

{z | (∃x : S(x,z)) ∧ ¬(∃b,c : R(z,b,c))}

### Filip Komorowski

Formuła, która pokazuje że atrybut Z z relacji A jest kluczem obcym dla atrubytu A z relacji R

$\{{p^{[Z]}\ |\ ((\exists s)(\ s \in S \wedge p.Z=s.Z) \implies (\exists r)(r \in R \wedge r.A=s.Z)}\}$

$\Downarrow$ negujemy

:::success
$\{{p^{[Z]}\ |\ ((\exists s)(\ s \in S \wedge p.Z=s.Z) \wedge \neg(\exists r)(r \in R \wedge r.A=s.Z)}\}$
:::

## Zadanie 3

### Krzysztof Wiśniewski
Relacje R = AB, S = B1B2, T = BC
Inna interpretacja

R: Miasto B leży na wysokości A
B - Miasto
A - Wysokość na której leży miasto
S: Połączenie komunikacyjne pomiędzy dwoma miastami
B1 - Miasto
B2 - Miasto
T: Miasto B o poziomie zanieczyszczenia powietrza C
B - Miasto
C - Poziom zanieczyszczenia powietrza

1. Najwyższa wysokość na jakiej leży miasto (Dlaczego da się zapisać w AR, nie dostajemy nieskończonego zbioru, jako że mamy nałożone zabezpieczenie w postaci tego, że wszystkie rzeczy, które w tym zapytaniu rozpatrujemy muszą istnieć w konkretnej relacji, już niezależnie od dziedziny)

$\pi_A(R) \setminus \pi_A(\sigma_{A < A_1}(R \times \rho_{R_1(A_1, B_1)}(R)))$

3. Takie dwa poziomy zanieczyszczeń, że w każdym mieście, miasto ma poziom zanieczyszczenia a lub poziom zanieczyszczenia b lub nie istnieją takie poziomy zanieczyszczeń.

Jeśli C byłaby pusta

dziedzina poziomów zanieczyszczeń to liczby naturalne
| Miasto | Poziom zanieczyszczeń |
| -------- | -------- |
| Warszawa | |
| Wrocław | |
| Oleśnica | |

Wtedy otrzymamy zbiór nieskończony ponieważ 3 warunek alternatywy nam wszystko zepsuje
### Adam Turowski


Interpretacja:
- $R$: W punkcie $B$ ma swoj srodek kolo o kolorze $A$
- $A$: kolor
- $B$: punkt
- $S$: krawędź pomiędzy $B_1$ i $B_2$
- $B_1$: punkt
- $B_2$: punkt
- $T$: Koło o środku w punkcie $B$ ma promień długości $C$
- $B$: punkt
- $C$: promień

1. Najjaśniejszy kolor kół

$\pi_A(R) \setminus \pi_A(\sigma_{A < A'}(R \times \rho_{R'(A', B')}(R)))$

2. Takie dwa promienie, że w każdym punkcie (rysunku/grafu) koła mają albo promien $a$ albo promien $b$ albo nie istnieją (nie mają promienia)

Jeżeli relacja $T$ byłaby pusta, to trzeci warunek alternatywy byłby zawsze spełniony, zatem wynikiem tego zapytania byłyby wszystkie pary a, b z uniwersum, w szczególności mógłby to być zbiór nieskończony.

## Zadanie 4
**Treść:** Wypisz osoby bywające tylko w tych barach, w których podaje się (przynajmniej) jeden z ich ulubionych soków.
1. $\{o \| (∃b)(B(o, b)) ∧ ¬(∃b)(B(o, b) ∧ (∀s)(P (s, b) ⇒ ¬L(o, s)))\}$
2. $\{o \| (∃b)(B(o, b)) ∧ ¬(∃b)(B(o, b) ∧ (∀s)(P (s, b) ⇒ L(o, s)))\}$
3. $\{o \| (∃b)(B(o, b)) ∧ (∀b)(B(o, b) ⇒ (∃s)(P (s, b) ∧ L(o, s)))\}$
4. $\{o \| (∃b)(B(o, b)) ∧ (∀b)(B(o, b) ∧ (∃s)(P (s, b) ∧ L(o, s)))\}$

### Jonatan Hrynko
1. TAK - nie istnieje bar, gdzie bywa *o*, a wszystkie soki, które tam podają nie są lubiane przez *o*
2. NIE - nie istnieje bar w którym bywa *o*, gdzie podają tylko soki lubiane przez *o*, więc jeśli *o* bywa w barze w którym podają tylko soki, które lubi, to zapytanie odrzuci ten bar
3. TAK (NIE?) - z jednej strony bar, gdzie nie podaje się żadnego soku nie przechodzi - dla każdego *b* w którym bywa *o*, istnieje *s*, który podają w *b* i zarazem *o* go lubi, ale z drugiej strony wychodzi równoważność z punktem 1 (zapewne błąd w przekształceniach, ale nie umiem go znaleźć).
(∀b)(B(o, b) ⇒ (∃s)(P (s, b) ∧ L(o, s))) =
(∀b)(¬B(o, b) ∨ (∃s)(P(s,b) ∧ L(o, s))) =
¬(∃b)(B(o, b) ∧ ¬(∃s)(P(s,b) ∧ L(o, s))) =
¬(∃b)(B(o, b) ∧ (∀s)(¬P(s,b) ∨ ¬L(o, s))) =
¬(∃b)(B(o, b) ∧ (∀s)(P(s,b) ⇒ ¬L(o, s)))
4. NIE - *o* bywa w każdym barze i w każdym barze podają sok, który lubi *o* - jeśli *o* bywa w tylko jednym barze i tylko w nim podają sok, który *o* lubi, to zapytanie odrzuci taką osobę

### Martyna Firgolska

1. NIE - Wszystkie osoby, które bywają w barach i dla których nie ma baru w którym nie lubią wszystkiego co podają (jeśli w jakimś barze nie podają żadnego soku i będzie osoba która np. bywa tylko w nim to będzie przyjęta przez to zapytanie)
2. NIE - Osoby bywające w barach, i dla których nie ma baru w którym lubią wszystko
3. TAK - Wszystkie osoby bywające w barach, i takie że dla każdego baru w którym dana osoba bywa znajdziemy sok który lubi ta osoba i który podają w tym barze
4. NIE - Osoby bywające we wszystkich barach oraz które w każdym z tych barów lubią pewien sok

## Zadanie 5

### Piotr Piesiak
1. Nie
- Istnieje bar, w którym ta osoba bywa oraz nie istnieje bar w którym ta osoba bywa (zawsze fałsz)
2. Nie
- osoby, które bywają w przynajmniej jednym barze
3. Tak
- istnieje bar, w którym ta osoba bywa oraz nie istnieje inny bar, w którym ta osoba bywa
4. Tak
- istnieje bar, w którym ta osoba bywa oraz nie istnieje inny bar, w którym ta osoba bywa
### Krzysztof Łyskawa
1. Istnieje bar $b$, do którego osoba chodzi i nie istnieje bar $b'$ do którego osoba chodzi - FAŁSZ
2. Istnieje bar do którego chodzi osoba - FAŁSZ
3. Istnieje bar, do którego chodzi osoba i nie istnieje INNY bar, do którego osoba chodzi - PRAWDA
4. To samo co 3., tylko dłuższe - PRAWDA

## Zadanie 6
## a)
### Maurycy Borkowski
$\{{a | a\in A \wedge (\exists r)(r \in R \wedge r.pseudo=a.pseudo \wedge (\exists f)(f \in F \wedge f.idf = r.idf \wedge }$
${(\forall r')(r' \in R \wedge r'.pseudo=r.pseudo \implies (\forall f')(f' \in F \wedge f'.idf = r'.idf\implies f'.rokProd = f.rokProd))))}\}$
### Łukasz Stasiak

$\{p,i,n,r,n | A(p,i,n,r,n) \wedge \exists_{idf,postac,gaza}(R(pseudo, idf, postac, gaza)\wedge\exists_{tytul,rezyser,rokProd,czas}$
$F(idf,tytul,rezyser,rokProd,czas) \wedge \forall_{idf2, postac2, gaza2}$
$(R(pseudo,idf2,postac2,gaza2)=>$
$\exists_{tytul2, rezyser2, rokProd2, czas2}$
$(F(idf2,tytul2,rezyser2,rokProd2,czas2) => rokProd=rokProd2)))\}$
## b)
### Maurycy Borkowski
${\{f | f \in F \wedge \neg(\exists f')(f' \in F \wedge f.idf \neq f'.idf \wedge f.rezyser=f'.rezyser \wedge f.rokProd<f'.rokProd)}\}$

### Łukasz Stasiak
$\{f|f \in F \wedge \forall_{f_2 \in F}(f_2.rezyser=f.rezyser =>f2_2.rokProd\leq f.rokProd)\}$
## c)
### Michał Dymowski
$\{pseudo, idf, gaża | \\
\exists ps1 \forall pseudoA, ps2, gaża2 \\
R(pseudo, idf, ps1, gaża) \wedge \\
\left( R(pseudoA, idf, ps2, gaża2) \Rightarrow \\
gaża \ge gaża2 \right)\}$
### Michał Hetnar
Dla każdego flmu znajdz aktora, który dostaa najwyższ¡ gażę w tym filmie (zostaa najlepiej opaacony z obsady flmu). W relacji wynikowej podaj
pseudonim aktora, idf oraz gaża.

$\{{pse,idf,gaza|(\exists_{postac})(R(pse,idf,postac,gaza)\wedge \neg((\exists_{pse2,gaz2,postac2})(R(pse2,idf,postac2,gaza2) \wedge pse \neq pse2 \wedge gaza2>gaza)))}
\}$

## d)
### Michał Dymowski
$\{pseudo, imie, nazwisko, narodowosc, rokUr | \\
\forall rok1, rok2, minGaża1, minGaża2 \\
A(pseudo, imie, nazwisko, narodowosc, rokUr) \wedge \\
\left( \left(M(pseudo,rok,minGaża1) \wedge
M(pseudo,rok2,minGaża2) \wedge \\
rok1 \ge rok2\right) \Rightarrow \\
minGaża1 \ge minGaża2 \right)
\}$
### Michał Hetnar

Podaj pełne krotki aktorów, którzy nigdy nie obniżyli swojej minimalnej
gaży (w póżniejszych latach mogła ona najwyżej rosnąć). Na wynik nie
wpaywają lata, w których aktor nie posiada minimalnej gaży.

$\{{pse,imie,naz,nar,rokU|(\forall_{idf,tytul,rez,rok,czas,postac,gaza})(F(idf,tytul,rez,rok,czas)\wedge R(pse,idf,postac,gaza)\wedge \neg(\exists_{ idf2,tytul2,rez2,rok2,czas2,postac2,gaza2})(F(idf2,tytul2,rez2,rok2,czas2)\wedge R(pse,idf2,postac2,gaza2)\wedge rok2>rok \wedge gaza<gaza2))}
\}$

## Zadanie 7

### Karol Machoś


| Miasto | Ludność |
| -------- | -------- |
| Warszawa | 1000 |
| Wrocław | 2000 |
| Kraków | $x$ |
| Opole | 1500 |

Zapytanie $\sigma_{ludność>1400}(D)$ będzie skutkowało odrzuceniem wartości $x$ (jako że to NULL to nie wejdzie ona do wynikowych krotek), natomiast $Q(rep(D))$ będzie skutkowało wpierw przypisaniu $x$ wszystkich możliwych wartościowań a następnie wybraniu tych wartościowań które spełniają warunek $\sigma_{ludność>1400}$. Zatem nie możemy zagwarantować, że będzie zachodził warunek $rep(Q_D)=Q(rep(D))$. Zatem nie możemy używać selekcji w takich przypadkach.

### Krzysztof Wiśniewski

Przyjmujemy konkretną iterpretacje wartości NULL. Mianowicie NULL od tej pory mówi nam że danym wpisie w tabeli znajduje się wartość, która istnieje na naszej dziedzinie, ale nie wiemy jaka.
Np. (Józek, x), oznacza, że Józek ma jakieś zarobki, którą można wyrazić pewną wartością typu Int, ale nie wiemy jaką.

D relacja ze zmiennymi
Np.
Osoba

| Imie | Wiek |
| -------- | -------- |
| Krzysztof | 20 |
| Marcin | NULL |

rep(D) - relacja zwartościowana
tzn jeśli mieliśmy (Józek, x) to zrobi nam się (Józek, n) n będzie Int-em.

Q wyrażenie algebry relacji
Q_D wynik zapytania Q na D

Mamy mieć
rep(Q_D) = Q(rep(D))

Q_D nam zwróci nie wiadomo co, D może już wtedy zawierać NULL-a w sobie.