---
# System prepended metadata

title: BD 25.05.2021

---

# BD 25.05.2021

## z1 Maurycy Borkowski, Piotr Piesiak
### Piotr Piesiak:
Postać BCNF:
Baza danych jest w postaci BCNF, jeśli dla każdej nietrywialnej zależności $\alpha \rightarrow \beta$, $\alpha$ jest nadkluczem

Nasza baza nie jest w tej postaci, ponieważ istnieje zależność np. $Szef \rightarrow Dochód$, a Szef nie jest kluczem, ponieważ jeden Szef może mieć kilka różnych wpisów (nie mamy powiedziane, że jest kluczem)

Mafia (Miasto, Gang, Proceder)
Opłacalność (Proceder, ROI)
Zysk (Szef, Dochód) 
Organizacja (Gang, Szef) 

Ta baza jest w postaci BCNF, ponieważ wszystkie tabele (poza Mafią) wynikają z zależności, natomiast w Mafii z hisotryjki wiemy, że:
1. Miasto i proceder nie jest kluczem, gdyż w danym mieście, dany proceder może być uprawiany przez kilka gangów
2. Proceder i gang nie jest kluczem, gdyż dany proceder i dany gang może występować w kilku miastach
3. Miasto i gang nie jest kluczem, gdyż dany gang w danym mieście może uprawiać kilka procederów


**Maurycy Borkowski**

Mafia (Miasto, Gang, Proceder, Szef, Dochód, ROI) <span style="color:red">NIE BCNF</span> bo np. Gang nie jest nadkluczem

Mafia (Miasto, Gang, Proceder, Szef, Dochód) <span style="color:red">NIE BCNF</span> bo np. Gang nie jest nadkluczem
Rentowność (Proceder, ROI) <span style="color:green">BCNF</span>
    
Mafia (Miasto, Gang, Proceder, Dochód) <span style="color:red">NIE BCNF</span> bo $Gang \rightarrow Dochód$, ale Gang w różnych miastach
Rentowność (Proceder, ROI) <span style="color:green">BCNF</span>
Boss (Gang, Szef) <span style="color:green">BCNF</span>


Mafia (Miasto, Gang, Proceder) <span style="color:green">BCNF</span>
Rentowność (Proceder, ROI) <span style="color:green">BCNF</span>
Boss (Gang, Szef) <span style="color:green">BCNF</span>
WypłataBossa (Szef, Dochód) <span style="color:green">BCNF</span>
    
W Mafii nie ma nietrywialnej zależności funkcyjnej $\alpha \rightarrow \beta$, ponieważ:
* Miasto,Proceder nie definiuje jednoznacznie gangu (jeden proceder w mieście może być uprawiany przez kilka gangów)
* Miasto,Gang - Gang może uprawiać kilka procederów w danym mieście
* Gang,Proceder - Dany gang i porceder, moze wystepowac w kilku miastach 
## z2 Tomasz Orda, Filip Komorowski

### Treść
Czy mimo tego, że baza (po Twoich modyfikacjach) jest w postaci BCNF
dostrzegasz w niej jeszcze jakąś oczywistą redundancję? Jaka jest jej przyczyna?

### Filip Komorowski
Tak, nadal występuje redundancja. Z historyjki na początku treści wiemy, że mafia wykonuje wszystkie procedery, którymi w ogólności się zajmuje, w każdym z miast, w którym występuje. Zatem informacje o precederach wykonywanych w danych miastach będą niepotrzebnie dublowane.

### Tomasz Orda
*Ustalono też ponad wszelką wątpliwość, ż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.*

Dla danego gangu powtórzymy wielokrotnie (o ile gang działa w kilku miastach lub zajmuje się kilkoma procederami) informacje na temat uprawianych procederów i/lub miast w których jest obecny.
Zatem też można uprościć relację $MGP$. 

## z3 Martyna Firgolska, Krzysztof Łyskawa
Czy istnieje odwracalny rozkład pozwalający się tej redundancji pozbyć? Podaj go. Dlaczego jest on odwracalny?
### Martyna Firgolska

S(gang, szef), 
D(szef , dochód), 
**M(gang, miasto)**,
**P(gang, preceder)**,
R(preceder, roi)

Rozkład jest odwracalny, ponieważ złączenie naturalne M i P daje z powrotem Mafia(gang, miasto, preceder).

### Krzysztof Łyskawa
Możemy rozłożyć relację ***Działalność(Miasto, Gang, Proceder)*** na dwie relacje: ***Miasta(Gang, Miasto)*** i ***Procedery(Gang, Proceder)***. Proces ten jest odwracalny - wystarczy zwykłe złączenie naturalne, żeby powrócić do poprzedniego stanu a dodawanie nowych miast i procederów jest bardzo uproszczone (wystarczy jedna krotka).

## z4 Łukasz Stasiak, Jonatan Hrynko
### Treść
Napisz zapytanie algebry relacji zwracające niepustą odpowiedź wtedy i tylko wtedy gdy w relacji $\texttt{Mafia}$ naruszona jest zależność funkcyjna $\texttt{Proceder} \rightarrow \texttt{ROI}$.

### Jonatan Hrynko
Zależność funkcyjna $\texttt{Proceder} \rightarrow \texttt{ROI}$ oznacza, że dla każdych dwóch krotek $t_1, t_2 \in \texttt{Mafia}$ zachodzi:
$$
t_1.\texttt{Proceder}=t_2.\texttt{Proceder} \implies t_1.\texttt{ROI}=t_2.\texttt{ROI}
$$

Zatem jeśli ta zależność funkcyjna zostaje złamana, to oznacza, że istnieją dwie krotki $t_1, t_2 \in \texttt{Mafia}$ dla których zachodzi:
$$
t_1.\texttt{Proceder}=t_2.\texttt{Proceder} \land t_1.\texttt{ROI} \neq t_2.\texttt{ROI}
$$

Zatem zapytanie będzie wyszukiwało par krotek dla których zachodzi powyższy warunek

$$
\sigma_{(m.\texttt{Proceder}=m_1.\texttt{Proceder}) \land (m.\texttt{ROI} \neq m_1.\texttt{ROI})}(\rho_{m}(\texttt{Mafia}) \times \rho_{m_1}(\texttt{Mafia}))
$$

### Łukasz Stasiak

![](https://i.imgur.com/x8kvvkQ.jpg)
Mówimy, że zależność funkcyjną X → Y zachodzi w R, jeśli każde dwa wiersze mające te same wartości atrybutów z X muszą mieć te same wartości atrybutów z Y.
Mamy zwrócić wyniki tylko wtedy kidy naruszona jest zależność Proceder → ROI. Oznacza to, że zwrócić wyniki trzeba tylko wtedy kiedy dwa wiersze mają różne wartości atrybutów z Proceder muszą mieć różne wartości atrybutów z ROI.

## z5 Michał Hetnar, Maciej Zientara

### Michał Hetnar
przykład:
1, leroylovesusa, USA, "God. Country. Family. #InGodWeTrust", 2016-11-09,
"RT @w0tn0t: #ElectionDay #NeverHillary @TwitterMoments Voting Issues:
Some Trump Voters Reporting Ballots Switching To Clinton. https://t.col5",
2, ["ElectionDay","NeverHillary"], ["w0tn0t","twittermoments"], 3, 4


[author_id,author_name,author_location,author_description,created_at,text,tweet_id,hastags,mentions,reweted_tweet_id,inreply_to_tweet_id]

zależności funkcyjne:
author_id -> author_name
author_id -> author_location
author_id -> author_description
tweet_id -> created_at
tweet_id -> text
tweet_id -> retweeted_tweet_id
tweet_id -> inreply_to_tweet_id

Tweety:
[tweet_id,created_at,reweted_tweet_id,inreply_to_tweet_id,author_id]


Użytkownicy:
[author_id,author_name,author_location,author_description]

Hashtags:
[tweet_id,hashatgs]

Wzmianki:
[tweet_id,mentions]

ewentualnie:
możemy dodać tabele rekurencyjną:
[tweet_id,inreply_to_tweet_id]
i usunąć inreply_to_tweet_id z tabeli Tweety.



### Maciej Zientara
Tabele:
Author(author_id, author_name, author_location, author_description)
Tweet(author_id, created_at, text,tweet_id, hashtags, mentions, retweeted_tweet_id, in_reply_to_tweet_id)

1. dodanie tabeli Author eliminuje potencjalne redundancje w kolejnych tweetach 
(dane autora zmieniamy tylko w tablicy Author, a nie w każdym jego tweet)
2. author_id pojawia się w obu tablicach, aby podział był odwracalny (JOIN tablic)

hashtags i mentions są w postaci wektora text [ '', '', '', ...]
co jest niezgodne z 1FN, niestety nie mamy lepszej alternatywy

Tweet(author_id, created_at, text, tweet_id, retweeted_tweet_id, in_reply_to_tweet_id)
Hashtags (tweetID, hashtag)
Mentions (tweetID, mention)

Próba rozdzielenia dwóch wektorów na oddzielne tablice spowoduje, że przy łączeniu Hashtags i Mentions
otrzymamy iloczyn kartezjański każdego hashtagu i każdego mention ale nie uda nam się odtworzyć oryginalnych
dwóch wektorów.

Pomysł zrobienia tablic Hashtags i Mentions z wieloma kolumnami, aby zasymulować wektory również nie jest wskazany
(zawsze znajdzie się ktoś, kto będzie chciał użyć wiecej niż maksymalna przewidziana ilość hashtagów).

3. dodanie Hashtags i Mentions w celu zachowania 1NF 
(tylko typy proste danych np text zamiast jakiś wektorów text ["", "", ...])
niestety psuje to odwracalność podziału.

[A,B], [1,2]

A 1
A 2
B 1
B 2


## z6 Anadi Agrawal, Karol Machoś

### Karol Machoś

1) Kontrprzykład

    |    |F|M|R|
    |----|-|-|-|
    |t_1 |a|b|d|
    |t_2 |a|c|d|
Możemy zauważyć, że oba warunki na zależność wielowartościową $F\twoheadrightarrow M$ zostały spełnione, jednakże nie zachodzi $F\rightarrow M$ ponieważ nie możemy jednoznacznie wyznaczyć wartości w kolumnie $M$ dla pewnej wartości w kolumnie $F$.

2) Dowód

Załóżmy, że $F\rightarrow M$. Zatem w relacji $S$ każdej wartości w kolumnie $F$ będzie "przypisana" wartość w kolumnie $M$. Zatem w przypadku $t_1,t_2$ takich że, $\pi_F(t_1) = \pi_F(t_2)$, będzie również zachodzić $\pi_{FM}(t_2) = \pi_{FM}(t_1)$, oraz $\pi_{FR}(t_2)=\pi_{FR}(t_2)$.