# Ćwiczenia bazy danych - RFE- 27.05

## Zadanie 2
T(Gang, Miasto, Proceder)
`n*m`

T1(Gang, Proceder), T2(Gang, Miasto)
`n+m`

## Zadanie 3

### Rozwiązanie

---

**Proponowany rozkład bazy**
$(Gang,\ Szef)$
$(Gang,\ Dochód)$
$(Proceder,\ ROI)$
$(Gang,\ Miasto)$
$(Gang,\ Proceder)$

---

**Dlaczego rozkład jest odwracalny**

#### Lemat nr 1 z wykładu
Niech $R$ będzie relacją i $F$ jej zbiorem zależności funkcyjnych. Jeżeli zależność $(\alpha → \beta) \in F^{+}$ jest nietrywialna, to rozkład $R$ na $R_{1} = \alpha\beta$ i $R_{2} = R\setminus\beta$ jest odwracalny.

#### Lemat nr 2 z wykładu
Rozkład $R$ na $R_{1},\ ...\ ,\ R_{k}$ jest odwracalny, jeśli dla każdego poprawnego stanu $r$ zachodzi:
$r=r_{1}⋈r_{2}⋈···⋈r_{k}$
gdzie $r_{i}$ to stan kolumn relacji $R_{i}$

#### Rozkład bazy na podstawie lematu nr 1
$(Miasto,\ Gang,\ Proceder,\ Szef,\ Dochod,\ ROI)$

--- rozkład przez $(Gang→Szef)$ ---

$(Gang,\ Szef)$ i $(Miasto,\ Gang,\ Proceder,\ Dochod,\ ROI)$

--- rozkład przez $(Gang→Dochod)$ ---

$(Gang,\ Szef)$, $(Gang,\ Dochod)$ i $(Miasto,\ Gang,\ Proceder,\ ROI)$

--- rozkład przez $(Proceder→ROI)$ ---

$(Gang,\ Szef)$, $(Gang,\ Dochod)$, $(Proceder,\ ROI)$ i $(Miasto,\ Gang,\ Proceder)$

Teraz zastanówmy się nad relacją $(Miasto,\ Gang,\ Proceder)$. Ponieważ wiemy, że "jeśli gang uprawia jakiś proceder to uprawia go we wszystkich miastach, w których jest obecny, a jeśli jest obecny w jakimś mieście to uprawia w nim wszystkie procedery, które uprawia gdziekolwiek", to na mocy lematu nr 2 $(Miasto,\ Gang,\ Proceder)$ można rozłożyć na $(Miasto,\ Gang)$ oraz $(Proceder,\ Gang)$, bowiem $(Miasto,\ Gang,\ Proceder) = (Miasto,\ Gang) ⋈ (Proceder,\ Gang)$, niezależnie od stanu relacji.

Zatem zaproponowany rozkład jest odwracalny.

---

**Czy w proponowanym rozkładzie jest redundancja?**

Zależy, jaka jest interpretacja atrybutów.

Jeśli atrybuty Gang oraz Proceder reprezentują niezmienne ID, proponowany rozkład nie ma redundancji.

Jeśli natomiast atrybuty te reprezentują nazwy gangów/procederów, nie ma takiego rozkładu, bo potrzebowalibyśmy jeszcze niezmiennych ID dla gangów i procederów.

## Zadanie 4

**Napisz zapytanie algebry relacji zwracające niepustą odpowiedź wtedy i
tylko wtedy gdy w relacji Mafia naruszona jest zależność funkcyjna Proceder → ROI.**

$$A = \pi_{Proceder,ROI}(Mafia)$$

$$\sigma_{ROI\neq{ROI2}}\biggl(A\bowtie \rho_{Proceder, ROI2}\bigl(A\bigl)\biggl)$$

## Zadanie 5

1.
`Tweet(id, author_id, creation_date, text, retweeted_tweet_id, in_reply_to_tweet_id)`
`User(Id, name, location, description)`
`Hashtag(tag, tweet_id)`
`Mention(tweet_id, mentioned_user_id)`

2.
`Users(id, name, location, description)`
`Tweets(id, author_id, created_at, text)`
`Hashtags(tweet_id, hashtag)`
`Mentions(tweet_id, user_id)`
`Retweets(tweet_id, retweeted_tweet_id)`
`Replies(tweet_id, in_reply_to_tweet_id)`

3.
Authors:

| *author_id* | author_name | author_description |
| -------- | -------- | -------- |
| int | text | text |

Tweets:

| *tweet_id* | author_id | created_at | text | author_location |
| ---------- | --------- | ---------- | ---- | --------------- |
| int | int | timestamp | text | text |

Replies:

| *tweet_id* | in_reply_to_tweet_id |
| -------- | -------- |
| int | int |

Retweets:

| *tweet_id* | retweeted_tweet_id |
| -------- | -------- |
| int | int |

Mentioned:

| *tweet_id* | *mentioned* |
| -------- | -------- |
| int | text |

Hashtags:
| *tweet_id* | *hashtag* |
| -------- | -------- |
| int | text |

Zależność funkcyjna: {author_id} -> {author_name, author_description}

Kluczem jest tweet_id zatem podana baza jest w BCNF-ie. Jednak jest kilka rzeczy, które należałoby zmienić. Informacje o autorach przenosimy do osobnej tabeli, żeby nie trzymać ich niepotrzebnie po kilka razy(i wynika to też zależności funkcyjnej). Zakładam, że author_location może być różne dla różnych postów tego samego autora.Tworzymy tabele Replies i Retweets - nie każdy post musi nimi być - tym samym unikamy Nulli. Hashtagi i wspominki są przechowywane w formie tabeli - na takich wartościach atrybutów nie pracuje się szybko i wygodnie. Możemy te informacje przechowywać w tablicach tak jak teraz lub (co chyba jest lepszą opcją)- rozbić do wartości atomowych - zgodne z 1NF, powinniśmy stworzyć trigery, które będą pilnowały przechowywanych tam wartości. Wtedy kluczami będą odpowiednio {tweet_id, mentioned} i {tweet_id, hashtag} (zakładam że nikt nie dodaje kilkukrotnie takiego samego hashtagu i nie wspomina jednej kilka razy w tym samym poście).

# Zadanie 6 #
**6.1**
S(F,M,R)

Założenie: $F→→M$

W tabeli S, która spełnia $F→→M$ są:
$(x,m,r)$
$(x,m',r')$
$(x, m, r')$
$(x, m', r)$

Kontrprzykład :+1: :+1:
$T_{1}$: $F_{1}$, M$_{1}$, R
$T_2$ : $F_{1}$, M$_{2}$, R

T : $F_{1}$, $M_{1}$, R

**6.2**

Założenie : $F → M$

Weźmy dwie dowolne krotki T$_{1}$ i T$_{2}$ które zgadzają się na F. Zgodnie z założeniem będą się też zgadzały na M. Zatem nasze T$_{1}$ będzie wyglądać tak:
T$_{1}$ : F$_{1}$, M$_{1}$, R$_{1}$ natomiast T$_{2}$ : F$_{1}$,M$_{1}$, R$_{2}$. Teraz widzimy że naszą krotką T która będzie spełniała zadanie jest po prostu T$_{2}$. c