BD 25.05.2021 - HackMD

# 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) NIE BCNF bo np. Gang nie jest nadkluczem Mafia (Miasto, Gang, Proceder, Szef, Dochód) NIE BCNF bo np. Gang nie jest nadkluczem Rentowność (Proceder, ROI) BCNF Mafia (Miasto, Gang, Proceder, Dochód) NIE BCNF bo $Gang \rightarrow Dochód$, ale Gang w różnych miastach Rentowność (Proceder, ROI) BCNF Boss (Gang, Szef) BCNF Mafia (Miasto, Gang, Proceder) BCNF Rentowność (Proceder, ROI) BCNF Boss (Gang, Szef) BCNF WypłataBossa (Szef, Dochód) BCNF 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)$.