Databases

Download the introduction presentation

View the presentation on proofs or download it. The links refer to the slides of prof. Perelli and don't work on the website: you have to download the pdf in the same folder with the course's slides for the links to work.

Schema

An attribute is a $(\text{name},\text{domain})$ pair; we can define the $dom()$ function on a set of names, which associates to each name a specific domain (different attributes can have the same domain)

$$\begin{array}{rl}dom:\{{\text{name}}_1,...,{\text{name}}_n\}& \to \{{\text{domain}}_1,...,{\text{domain}}_k\}\\ {\text{name}}_i& \mapsto {\text{domain}}_j\end{array}$$

PDF 7 slide 2

A relation schema $R=\{A_1,A_2,...,A_n\}$ is a set of attributes

Tuples & instances

PDF 7 slide 3 Given a relation schema $R=A_1{A}_2...A_n$, a tuple $t$ on $R$ is a function such that

$$\begin{array}{rl}t:R& \to \bigcup _{i=1}^{n}dom(A_i)\\ A_i& \mapsto a\in dom(A_i)\end{array}$$

Given a relation schema $R$, a subset $X\subseteq R$ and $t$ a tuple on $R$, the reduction of $t$ on $X$ is defined as

$$t[X]=\{(A,t[A])\mid A\in X\}$$

PDF 7 slide 4 Given a relation schema $R$, a subset $X\subseteq R$ and $t_1,t_2$ tuples on $R$

$$t_1[X]=t_2[X]⟺t_1[A]=t_2[A]\forall A\in X$$

PDF 7 slide 5 Given a relation schema $R$ and $t_1,t_2,...,t_k$ tuples on $R$, a set $r=\{t_1,t_2,...,t_k\}$ is an instance of $R$

Functional dependencies

PDF 7 slide 6

Given a relation schema $R$ and $X,Y\in \mathcal{P}(R)\setminus \{\varnothing \}$ we have that $(X,Y)$ is a functional dependency on $R$ (noted as $X\to Y$)

PDF 7 slide 7

Given a relation schema $R$ and a functional dependency $X\to Y$ defined on $R$ we say that an instance $r$ of $R$ satisfies the functional dependency $X\to Y$ if

$$\forall t_1,t_2\in r{t}_1[X]=t_2[X]⟹t_1[Y]=t_2[Y]$$

Instance legality & closure

PDF 7 slide 14

Given a relation schema $R$ and a set $F$ of functional dependencies defined on $R$, an instance $r$ of $R$ is legal if it satisfies every dependency in $F$

$$\forall X\to Y\in F\forall t_1,t_2\in r{t}_1[X]=t_2[X]⟹t_1[Y]=t_2[Y]$$

PDF 7 slide 20

Given a relation schema $R$ and a set $F$ of functional dependencies defined on $R$, the closure of $F$ is the set of functional dependencies that are satisfied by every legal instance of $R$

$$F^{+}=\{V\to W\mid \forall \text{ legal }r\text{ of }R,r\text{ satisfies }V\to W\}$$

$V\to W$ doesn't necessarily have to be in $F$

$F\subseteq F^{+}$

PDF 7 slide 21

$$F\subseteq F^{+}$$

Proof

$$F^{+}=\{V\to W\mid \forall \text{ legal }r\text{ of }R,r\text{ satisfies }V\to W\}$$

By definition $r$ is legal if it satisfies every dependency $X\to Y\in F⟹$ given $X\to Y\in F$, every legal instance of $R$ satisfies $X\to Y⟹X\to Y\in F^{+}$

Keys

PDF 7 slide 22

Given a relation schema $R$ and a set $F$ of functional dependencies on $R$, $K\subseteq R$ is a key of $R$ if

• $K\to R\in F^{+}$
• $\forall K^{\prime }\subset K,K^{\prime }\to R\notin F^{+}$

$"\subset "$ means proper subset, which implies that $K\ne K^{\prime }$

Trivial dependencies

PDF 7 slide 26

Given a schema $R$ and $X,Y\in \mathcal{P}(R)\setminus \{\varnothing \}:Y\subseteq X$, we have that every instance $r$ of $R$ satisfies the dependency $X\to Y$

Proof

Given an instance $r$ of $R,\forall t_1,t_2\in r$ we have that

$t_1[X]=t_2[X]⟹$ by definition $t_1[A]=t_2[A]\forall A\in X⟹$ as $Y\subseteq X$ we have that
$t_1[A^{\prime }]=t_2[A^{\prime }]\forall A^{\prime }\in Y⟹$ by definition $t_1[Y]=t_2[Y]$

As $t_1[X]=t_2[X]⟹t_1[Y]=t_2[Y]$ we have that $r$ satisfies $X\to Y$

Decomposition

PDF 7 slide 27

Given a schema $R$ and a set of functional dependencies $F$ on $R$, we have that

$$X\to Y\in F^{+}⟺X\to A\in F^{+}\forall A\in Y$$

Proof

$X\to Y\in F^{+}⟹\forall \text{ legal }r\text{ of }R\forall t_1,t_2\in r{t}_1[X]=t_2[X]⟹t_1[Y]=t_2[Y]⟹t_1[A]=t_2[A]\forall A\in Y⟹X\to A\in F^{+}\forall A\in Y$

$$\begin{gathered} X\to A\in F^{+}\forall A\in Y⟹\forall \text{ legal }r\text{ of }R\forall t_1,t_2\in R{t}_1[X]=t_2[X]⟹ \\ {t}_1[A]=t_2[A]\forall A\in Y⟹t_1[Y]=t_2[Y]⟹X\to Y\in F^{+} \end{gathered}$$

$F^A$

PDF 8 slide 3 $F^A$ is a set of functional dependencies on $R$ such that

• $X\to Y\in F⟹X\to Y\in F^A$
• $Y\subseteq X\in R⟹X\to Y\in F^A$ (refelxivity)
• $\forall Z\in R,X\to Y\in F^A⟹ZX\to ZY\in F^A$ (augmentation)
• $X\to Y,Y\to Z\in F^A⟹X\to Z\in F^A$ (transitivity)

PDF 8 slide 6 derivates

• $X\to Y,X\to Z\in F^A⟹X\to YZ\in F^A$ (union)
• $X\to Y\in F^A\wedge Z\subseteq Y⟹X\to Z\in F^A$ (decomposition)
• $X\to Y,WY\to Z\in F^A⟹WX\to Z\in F^A$ (pseudotransitivity)

PDF 8 slide 8 $X\to A_1{A}_2...A_n\in F^A⟺\forall i=1,...,nX\to A_i\in F^A$

Derivates (Proofs)

Union

$(X{)}_F^{+}$ LaTeX

$X\to Y,X\to Z\in F^A⟹$ by augmentation $X\to XY,XY\to YZ\in F^A⟹$ by transitivity $X\to YZ\in F^A$

Decomposition

$X\to Y\in F^A\wedge Z\subseteq Y⟹Y\to Z\in F^A⟹$ by transitivity $X\to Z\in F^A$

Pseudotransitivity

$X\to Y,WY\to Z\in F^A⟹$ by augmentation $WX\to WY\in F^A⟹$ by transitivity $WX\to Z\in F^A$

$(X{)}_F^{+}$

$([PDF8slide9](08Givenarelationschema$R$,aset$F$ofdependencieson$R$and$X \subseteq R$.The\ast \ast closure\ast \ast of$X$withrespectto$F$,denoted$(X)^+_F$isdefinedas$$(X{)}_F^{+}=\{A\in R\mid X\to A\in F^A\}$$Wehavethat$X \subseteq (X)^+_F

Proof

\forall A \in X$byreflexivity$X \to A \in F^A \implies$bydefinition$A \in (X)^+_F \implies X \subseteq (X)^+_F$>WecanuseArmstron{g}^{\prime }saxiomsas$(X)^+_F$isdefinedof$F^A$>NOTE:$(X)^+_F$is\ast \ast NOT\ast \ast definedon$F^+

Lemma of closure

PDF 8 slide 10

Let R$beaschemaand$F$asetoffunctionaldependencieson$R$X\to Y\in F^A⟺Y\subseteq (X{)}_F^{+}$

Proof

X \to Y \in F^A \implies$bydecomposition$X \to A \in F^A ; \forall A \in Y \implies$bydefinition$A \in (X)^+_F ; \forall A \in Y \implies Y \subseteq (X)^+_F$>$Y \subseteq (X)^+_F \implies A \in (X)^+_F ; \forall A \in Y \implies$bydefinition$X \to A \in F^A ; \forall A \in Y \implies$byunion$X \to Y \in F^A

F^+ = F^A$[PDF8slide11](08Let$R$bearelationschemaand$F$asetoffunctionaldependencieson$R$then$F^+ = F^A

Proof

Let F_i$bethevalueof$F$afterthe$i$-thapplicationofanArmstron{g}^{\prime }saxiom,with$F_0 = F

F^A \subseteq F^+

Base case

F_0 = F \subseteq F^+ \implies F_0 \subseteq F^+

Inductive step

F_i \subseteq F^+ \implies F_{i + 1} \subseteq F^+$Let$X \to Y \in F_{i + 1}$,either-$X \to Y \in F_i \implies$byHP$X \to Y \in F^+$-$X \to Y \in F_{i + 1} \setminus F_i$,whichmeansthat$X \to Y has been optained through one of the axioms

F^A \subseteq F^+

Reflexivity

Y \subseteq X \implies$giventhat$X \to Y$issatisfiedbyeveryinstance$X \to Y \in F^+

Augmentation

Z \subseteq R, X = ZV, Y = ZW \land V \to W \in F_i$given$t_1, t_2 \in r$legalinstanceof$R$wehavethat$t_1[X] = t_2[X] \implies (t_1[V] = t_2[V] \implies$byHP$t_1[W] = t_2[W]) \land t_1[Z] = t_2[Z] \implies t_1[Y] = t_2[Y]

Transitivity

X \to Z, Z \to Y \in F_i \implies$byHP$\forall \text{ legal } r \text{ of } R, \forall t_1, t_2 \in r, t_1[X] = t_2[X] \implies t_1[Z] = t_2[Z] \implies t_1[Y] = t_2[Y]$wehavethat$t_1[X] = t_2[X] \implies t_1[Y] = t_2[Y] \implies X \to Y \in F^+

F^+ \subseteq F^A${}_{(}legalinstance{)}_{G}iven$X \subseteq R$wecanbuildaninstance$r = \set{t_1, t_2}$on$R$suchthat<table><thead><tr><th>$r$</th><thcolspan="5">$(X)^+_F$</th><thcolspan="5">$R \setminus (X)^+_F$</th></tr></thead><tbody><tr><td>$t_1$</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td></tr><tr><td>$t_2$</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td><td>0</td><td>0</td><td>0</td><td>...</td><td>0</td></tr></tbody></table>Le{t}^{\prime }sverifythat$r$isalegalinstance.Given$V \to W \in F$,as$V, W \neq \varnothing$bydefinition,wecouldhave-$V \nsubseteq (X)^+_F \implies \exists A \in V : A \in R \setminus (X)^+_F \implies t_1[V] \neq t_2[V] \implies r$satisfies$V \to W$-$V \subseteq (X)^+_F$,wecouldhavethat-$W \subseteq (X)^+_F \implies t_1[V] = t_2[V] \land t_1[W] = t_2[W] \implies r$satisfies$V \to W$-$W \nsubseteq (X)^+_F \implies \exists A \in W : A \in R \setminus (X)^+_F \implies t_1[V] = t_2[V] \land t_1[W] \neq t_2[W]

F^+ \subseteq F^A${}_{(}legalinstance{)}_{I}nthelastcase$r$does{n}^{\prime }tsatisfy$V \to W$,sowehavetoshowthatitca{n}^{\prime }thappen.Le{t}^{\prime }ssupposethat$\exists V \to W \in F$suchthat$r$does{n}^{\prime }tsatisfy$V \to W$;byconstructionwehavethat$$V\subseteq (X{)}_F^{+}\wedge \exists A\in W:A\in R\setminus (X{)}_F^{+}⟹A\notin (X{)}_F^{+}$$Wehavethat-$V \subseteq (X)^+_F \implies$bythelemmaofclosure$X \to V \in F^A$-$A \in W \implies$bydecomposition$V \to A \in F^A$Bytransitivity$X \to A \in F^A \implies$bythelemmaofclosure$A \in (X)^+_F which is a contraddiction

Legality

In the first 2 cases r$satisfies$V \to W \in F$,case3ca{n}^{\prime }thappen$\implies r$isalegalinstanceof$R

F^+ \subseteq F^A$Le{t}^{\prime }sconsider$X \to Y \in F^+$Bydefinitionwehavethat$X \subseteq (X)^+_F \implies$byconstruction$t_1[X] = t_2[X] \implies$byhypotesisandgiventhat$r$isalegalinstance$t_1[Y] = t_2[Y] \implies$bythelemma$Y \subseteq (X)^+_F \implies X \to Y \in F^A

F^+ = F^A$Giventhat$F_i \subseteq F^+ : \forall i \in \mathbb{N}$and$F^+ \subseteq F^A$wehavethat$F^+ = F^A

3NF

PDF 9 slide 14

Given a relation schema R$andasetoffunctionaldependencies$F$on$R$.$R$isin\ast \ast 3NF\ast \ast if$\forall X \to A \in F^+ : A \notin X$either-$A$isprim{e}_{(}belongstoakey{)}_{-}$X is superkey

3NF pt.2

PDF 10 slide 4

Let R$bearelationschemaand$F$asetoffunctionaldependencieson$R$Anattribute$A \in R$\ast \ast partially\ast \ast dependsonakey$K$if<!--TODOcheckifsubseteq?NOTneededbecauseXisapropersubsetofK-->-$\exists X \subset R : A \notin X \land X \to A \in F \land X \subset K$-$A$is{n}^{\prime }tprimeAnattribute$A \in R$\ast \ast transitively\ast \ast dependsonakey$K$if-$\exists X \subset R : A \notin X \land X \to A \in F \land K \to X \in F$-$X$is{n}^{\prime }takey-$A$is{n}^{\prime }tprime>$X \subset R$meansthat$X \neq R$,otherwiseXwouldbeasuperkey,as$R \to R \in F^A = F^+

3NF pt.3

PDF 10 slide 5

Given a schema R$andasetoffunctionaldependencies$F$on$R$,\ast \ast TFAE\ast \ast -$R$isin3NF-thereare\ast \ast noattributesthatpartiallyortransitivelydependonakey\ast \ast -$\forall X \to A \in F^+ : A \notin X$either:-$A$isprim{e}_{(}belongstoakey{)}_{-}$X is superkey

Proof

TODO: I have it, I just have to write it out in \LaTeX$---<!--PDF10slide6--><!--Let$R$bearelationschemaand$F$asetoffunctionaldependencieson$R$.Aschema$R$isin3NFifandonlyifneitherpartialdependenciesnortransitivedependenciesexistin$F -->

BCNF (Boyce-Codd)

PDF 10 slide 20

A relation schema R$isin\ast \ast Boyce-CoddNormalForm\ast \ast (BCNF)wheneverydeterminantin$F is a superkey. A relation that respects Boyce-Codd Normal Form is also in 3NF, but the opposite is not true.

(X)^+_F

PDF 11 slie 5

def clousure(R, F, X):
	Z = X
	S = { A ∈ R | Y → V ∈ F ∧ Y ⊆ Z ∧ A ∈ V }

	if S ⊆ Z:
		return Z

	return closure(R, F, Z ∪ S)

(X)^+_F$[PDF11slide8](11Thealgorithm‘closure()‘correctlycomputestheclosureofasetofattributes$X$respectivelytoaset$F$offunctionaldependencieson$R

Proof

Let's consider Z_i, S_i$thevaluesof$Z$and$S$atthe$i$-thcallofthefunctionand$Z_f, S_f \mid S_f \subseteq Z_f$thevaluesof$Z, S$atthelastcallofthefunction.Le{t}^{\prime }sprovebyinductionthat$Z_i \subseteq (X)^+_F

Z_i \subseteq (X)^+_F

Base case

Inductive step Z_i \subseteq (X)^+F \implies Z{i + 1} \subseteq (X)^+F$<!--Wehavetoprovethat$Z_i \subseteq (X)^+F \implies Z{i + 1} \subseteq (X)^+F$--><!--and$S_i = \set{A \in R \mid Y \to V \in F \land Y \subseteq Z_i \land A \in V}$-->Giventhat$Z{i + 1} = Z_i \cup S_i$thenif$A \in Z{i + 1}$either-$A \in Z_i \implies$byHP$A \in (X)^+_F$-$A \in S_i \implies$byconstruction$\exists Y \to V \in F \mid Y \subseteq Z_i \land A \in V \implies$byHP$Y \subseteq (X)^+_F \implies$bythelemmaofclosure$X \to Y \in F^A$andbydecomposition$Y \to A \in F^A \implies$bytransitivity$X \to A \in F^A \implies$bydefinition$A \in (X)^+_F

(X)^+_F \subseteq Z_f${}_{(}legalinstance{)}_{G}iven$Z_f$wecanbuildaninstance$r = \set{t_1, t_2}$on$R$suchthat<table><thead><tr><th>$r$</th><thcolspan="5">$Z_f$</th><thcolspan="5">$R \setminus Z_f$</th></tr></thead><tbody><tr><td>$t_1$</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td></tr><tr><td>$t_2$</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td><td>0</td><td>0</td><td>0</td><td>...</td><td>0</td></tr></tbody></table>Le{t}^{\prime }sverifythat$r$isalegalinstance.Given$V \to W \in F$as$V, W \neq \varnothing$wecouldhaveeither-$V \nsubseteq Z_f \implies \exists A \in V : A \in R \setminus Z_f \implies t_1[V] \neq t_2[V] \implies r$satisfies$V \to W$-$V \subseteq Z_f$-$W \subseteq Z_f \implies$byconstruction$t_1[V] = t_2[V] \land t_1[W] = t_1[W] \impliesr$satisfies$V \to W$-$W \nsubseteq Z_f \implies$byconstruction$t_1[V] = t_2[V] \land t_1[W] \neq t_2[W]

(X)^+_F \subseteq Z_f${}_{(}legalinstance{)}_{L}e{t}^{\prime }ssupposethat$\exists V \to W \in F : r$does{n}^{\prime }tsatisfy$V \to W \implies$byconstruction$$V\subseteq Z_f\wedge \exists A\in W:A\in R\setminus Z_f⟹A\notin Z_f$$Giventhat$V \subseteq Z_f \land V \to W \in F \land A \in W \implies$byconstructionof$S_f, : A \in Z_f which is a contraddiction

Legality

In the first 2 cases r$satisfies$V \to W \in F$case3ca{n}^{\prime }thappen$\implies r$isalegalinstanceof$R

(X)^+_F \subseteq Z_f$Le{t}^{\prime }sconsider$A \in (X)^+_F$Giventhat$X \to A \in F^A = F^+$and$r$isalegalinstance$\implies r$satisfies$X \to Y$,andgiventhatbyconstruction$X \subseteq Z_f \implies t_1[X] = t_2[X] \implies$bydefinition$t_1[A] = t_2[A] \implies$byconstruction$A \in Z_f

Z_f = (X)^+_F$Giventhat$Z_i \subseteq (X)^+_F ; \forall i \in \mathbb{N}$and$(X)^+_F \subseteq Z_f$,wehavethat$Z_f = (X)^+_F

Intersection Rule

PDF 12 slide 19

Given a relation scheme R$andasetoffunctionaldependencies$F$on$R$X:=\bigcap _{V\to W\in F}R-(W-V)$$<!--Iftheintersectionofthesesetsdetermines$R$,thentheintersectionistheonlykeyto$R$elsetherearemultiplekeys,andALLofthemmustbeidentifiedforchecking3NF-->If$X \to R \in F^+$thentheintersectionistheonlykeyto$R$otherwisetherearemultiplekeys,and\ast \ast ALL\ast \ast ofthemmustbeidentifiedtocheckif$R is in 3NF

Decomposition

PDF 13 slide 8

Let R$bearelationscheme,adecomposition$\rho$of$R$issuchthat$$\rho =\{R_1,R_2,...,R_k\}\subseteq \mathcal{P}(R):\bigcup _{i=1}^k{R}_i=R$

Equivalence

PDF 13 slide 12

Let F$and$G$betwosetsoffunctionaldependencies,wecandefineanequivalencerelation$$F\equiv G⟺F^{+}=G^{+}$$-reflexivity$F \implies F^+ = F^+ \implies F \equiv F$-simmetry$F \equiv G \implies F^+ = G^+ \implies G^+ = F^+ \implies G \equiv F$-transitivity$F \equiv G \land G \equiv H \implies F^+ = G^+ \land G^+ = H^+ \implies F^+ = H^+ \implies F \equiv H$[PDF13slide14](13Let$F$and$G$betwosetsoffunctionaldependencies$$F\subseteq G^{+}⟹F^{+}\subseteq G^{+}$

F \subseteq G^+ \implies F^+ \subseteq G^+

Base case

F_0 = F \subseteq G^+ \implies F_0 \subseteq G^+

Inductive Step

F_i \subseteq G^+ \implies F_{i + 1} \subseteq G^+X \to Y \in F_{i + 1} \implies X \to Y$hasbeenoptainedthrough-reflexivity$Y \subseteq X \implies$giventhat$X \to Y$issatisfiedbyeveryinstance$X \to Y \in G^+$-augmentation$\exists Z \subseteq R, V \to W \in F_i \mid X = ZV, Y = ZW

• transitivity

TODO

Preserving F

PDF 13 slide 15

Let R$bearelationscheme,$F$asetoffunctionaldependencieson$R$and$\rho = \set{R_1, R_2, ..., R_k}$adecompositionof$R$,wesaythat$\rho$preseves$F$if$$F\equiv G=\bigcup _{i=1}^k{\pi }_{R_i}(F)$$Where$${\pi }_{R_i}(F)=\{X\to Y\in F^{+}\mid XY\subseteq R_i\}$$[PDF13slide16](13Giventhedefinitionof$G$,itwillalwaysbethat$G \subseteq F^+ \implies G^+ \subseteq F^+$soitisenoughtoverifythat$F \subseteq G^+

Dependency preservation

PDF 13 slide 17

def preserves_dependencies(R, F, ρ):
	for X → Y ∈ F:
		if Y ⊈ closure_G(R, F, ρ, X):
			return false

	return true

This algorithm is enough as we just have to check wether F \subseteq G^+$Given$X \to Y \in F$wehavethat$X \to Y \in G^+ = G^A \iff$bythelemmaofclosure$Y \subseteq (X)^+_G

(X)^+_G$‘‘‘pythondefclousur{e}_G(R,F,X,\rho ):Z=XS=\varnothing forP\in \rho :S=S\cup (closure(R,F,Z\cap P)\cap P)ifS\subseteq ZreturnZreturnclosur{e}_G(R,F,Z\cup S)‘‘‘<!--returnXifS\subseteq Xelseclosur{e}_G(R,F,X\cup S)-->[PDF13slide23](13$R$bearelationschema,$F$asetoffunctionaldependencieson$R$and$\rho = \set{R_1, R_2, ..., R_k}$adecompositionof$R$and$X \subseteq R$thealgorithm‘closur{e}_G()‘correctlycomputes$(X)^+_G

Z_f \subseteq (X)^+_G$Let$Z_i, S_i$thevaluesof$Z$and$S$atthe$i$-thcallofthefunction,with$Z_0 = X$,and$S_f \subseteq Z_f$<!--thefinalvaluesof$Z$and$S -->

Base case

Z_0 = X \subseteq (X)^+_G \implies Z_0 \subseteq (X)^+_G by HP

Inductive step

Z_i \subseteq (X)^+G \implies Z{i+1} \subseteq (X)^+G$,giventhat$S_i = \bigcup\limits{j = 1}^k (Z_i \cap R_j)^+F \cap R_j$Let$A \in Z{i + 1} = Z_i \cup S_i \implies \exists j : A \in (Z_i \cap R_j) \cap R_j \implies Z_i \cap R_j \to A \in G^A$ByHPwehavethat$Z_i \subseteq (X)^+_G \implies X \to Z_i \in G^A$,let$Z_i = (Z_i \cap R_j) \cup V$bydecompositionwehavethat$X \to Z_i \cap R_j \in G^A \implies$bytransitivity$X \to A \in G^A

X \subseteq Y \implies (X)^+_F \subseteq (Y)^+_FX \subseteq Y \implies Y \to X \in F^A$byreflexivityGiven$A \in (X)^+_F \implies$bythelemmaofclosure$X \to A \in F^A \implies$bytransitivity$Y \to A \in F^A \ \implies$bythelemmaofclosure$A \in (Y)^+_F

(X)^+_G \subseteq Z_fX \subseteq Z_f \implies (X)^+_G \subseteq (Z_f)^+_G$,wehavetoprovethat$Z_f = (Z_f)^+_G$Le{t}^{\prime }sconsider$A \in S' = \set{A \in R \mid V \to W \in G \land V \subseteq Z_f \land A \in W} \implies \exists V \to W \in G : V \subseteq Z_f \land A \in W \implies \exists R_j \in \rho : VW \subseteq R_j \implies V \subseteq Z_f \cap R_j \land A \in R_j \implies A \in (Z_f \cap R_j)^+_F \cap R_j \implies A \in S_f \implies A \in Z_f

Loseless join

r \subseteq m_{\rho}(r)t \in r \implies t[R_i] \in \pi_{R_i}(r) ; \forall R_i \in \rho$bydefinition$\mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r) = \set {\bigcup\limits_{i = 1}^k p_i[R_i] \mid p_i[R_i] \in \pi_{R_i}(r) \land \bigcup\limits_{i = 1}^k p_i[R_i] \text{ is a function}}\forall t \in r, ; t = \bigcup\limits_{i = 1}^k t[R_i]$asbydefinitionof$\rho$wehavethat$R = \bigcup\limits_{i = 1}^k R_it \in r \implies t$isafunctionbydefinition$t = \bigcup\limits_{i = 1}^k t[R_i] \in \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r) = m_{\rho}(r) \implies t \in m_{\rho}(r)$<!--$\forall t \in r, ; t = \bigcup\limits_{i = 1}^k t[R_i] = \mathop{\bowtie}\limits_{i = 1}^k \set{ t[R_i] }$--><!--$t \in r \implies$bydefinition$t[R_i] \in \pi_{R_i}(r) ; \forall R_i \in \rho \implies \set{ t[R_i] } \subseteq \pi_{R_i}(r) ; \forall R_i \in \rho$--><!--$t = \mathop{\bowtie}\limits_{i = 1}^k \set{ t[R_i] } \subseteq \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r) = m_{\rho}(r) \implies t \in m_{\rho}(r)$--><!--$\forall t \in r$weconsider$t[R_i], : R_i \in \rho$,wehavethat$t \in \set{ t[R_1] } \bowtie ... \bowtie \set{ t[R_k] } \subseteq \pi_{R_1}(r) \bowtie ... \bowtie \pi_{R_k}(r) = m_{\rho}(r) -->

\pi_{R_i}(m_{\rho}(r)) = \pi_{R_i}(r)$<!--Le{t}^{\prime }sconsider$t_{R_i} \in \pi_{R_i}(m_{\rho}(r))$,wehavetoprovethat$t_{R_i} \in \pi_{R_i}(r)$-->$t \in r \implies$bydefinition$t[R_i] \in \pi_{R_i}(r) ; \forall R_i \in \rho\pi_{R_i}(m_{\rho}(r)) = \set{q[R_i] \mid q \in \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r)}

\pi_{R_i}(r) \subseteq \pi_{R_i}(m_{\rho}(r))t \in r \implies t \in m_{\rho}(r) \implies t[R_i] \in \pi_{R_i}(m_{\rho}(r))

\pi_{R_i}(m_{\rho}(r)) \subseteq \pi_{R_i}(r)q \in \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r) \implies$bydefinitionofjoin$q = \mathop{\bowtie}\limits_{i = 1}^k \set{ p_i[R_i] } \mid p_i \in r \implies$giventhat$q$isafunction$q[R_i] = p_i[R_i]$and$p_i \in r \implies p_i[R_i] \in \pi_{R_i}(r)$wehavethat$q[R_i] \in \pi_{R_i}(r)$<!--$\exists p_1, p_2, ..., p_k \in r \mid p_i[R_i] \in \pi_{R_i}(r) ; \forall i = 1,..., k$--><!--$t_{R_i} \in \pi_{R_i}(m_{\rho}(r)) \iff \exists t' \in m_{\rho}(r) : t'[R_i] = t_{R_i} \iff\iff \exists t_1, ..., t_k \in r : t'[R_j] = t_j[R_j] \quad \forall R_j \in \rho$but$t_{R_i} = t[R_i] \in \pi_{R_i}(r) -->

m_{\rho}(m_{\rho}(r)) = m_{\rho}(r)m_{\rho}(m_{\rho}(r)) = \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(m_{\rho}(r)) = \mathop{\bowtie}\limits_{i = 1}^k \pi_{R_i}(r) = m_{\rho}(r)$<!--$m_{\rho}(m_{\rho}(r)) = \pi_{R_1}(m_{\rho}(r)) \bowtie ... \bowtie \pi_{R_k}(m_{\rho}(r)) = \pi_{R_1}(r) \bowtie ... \bowtie \pi_{R_k}(r) = m_{\rho}(r)$--><!--$m_{\rho}(m_{\rho}(r)) = \pi_{R_1}(m_{\rho}(r)) \bowtie ... \bowtie \pi_{R_k}(m_{\rho}(r)) = \pi_{R_1}(r) \bowtie ... \bowtie \pi_{R_k}(r) = m_{\rho}(r)$--><!--Le{t}^{\prime }sconsider$t_{R_i} \in \pi_{R_i}(r)$,wehavetoprovethat$t_{R_i} \in \pi_{R_i}(m_{\rho}(r))$--><!--Le{t}^{\prime }sconsider$t_{R_i} \in \pi_{R_i}(r) \land t' \in r$with$t'[R_i]$,wehavethat$t'[R_i] \in t_{R_i} -->

Loseless join pt.2

PDF 15 slide 15 Given \rho = \set{R_1, R_2, ..., R_k}$,buildatable$r$with$|R|$columnsand$k$rows.Atthe$i$-throwand$j$-thcolumnput$a_j$if$A \in R_{i}$else$b_{ij}

def has_looseless_join(R, F, ρ):
	while !(∃ t ∈ r | ∀ A ∈ R, t[A] = a) and r changed:
		for X → Y ∈ F:
			for t1 ∈ r:
				for t2 ∈ r:
					if t1[X] = t2[X] and t1[Y] != t2[Y]:
						for A ∈ Y:
							if t1[A] = a:
								t2[A] = t1[A]
							else:
								t1[A] = t2[A]

	return ∃ t ∈ r | ∀ A ∈ R, t[A] = a

Correctness

PDF 15 slide 19

Let R$bearelationscheme,$F$asetoffunctionaldependencieson$R$andlet$\rho = \set{R_1, R_2, ..., R_k}$beadecompositionof$R$;thealgorithmcorrectlydecideswhether$\rho$hasalosslessjoin$r = m_{\rho}(r) \iff r$hasatuplewithall$a$whenthealgorithmtermintes>TODO:Icanprove$r = m_{\rho}(r) \implies r$hasatuplewithall$a$whenthealgorithmterminates,Ijusthavetowriteitin$\LaTeX

Minimal cover

PDF 17 slide 7

Let R$beaschemaand$F$beasetoffunctionaldependencieson$R$.A\ast \ast minimalcover\ast \ast of$F$isasetoffunctionaldependencies$G \equiv F$suchthat:-$\forall X \to Y \in G, |Y| = 1$-$\forall X \to A \in G, \nexists X' \subset X \mid G \equiv (G - \set{X \to A}) \cup \set{X' \to A}$-$\nexists X \to A \in G \mid G \equiv G - \set{X \to A}

Minimal cover (step 1)

F_1 = \set{X \to A \mid X \to Y \in F \land A \in Y}F \overset{A}{\to} F_1$bydecomposition$F_1 \overset{A}{\to} F_1^A \implies F \subseteq F_1^AF_1 \overset{A}{\to} F$byunion$F \overset{A}{\to} F^A \implies F_1 \subseteq F^AF \equiv F_1

Minimal cover (step 2)

Given X \to A \in F_1, X' \subset X \land X' \to A \in F_1^+ \implies F_2 = (F_1 \setminus \set{X \to A}) \cup \set{X' \to A}X' \subseteq X \implies X \to X' \in F_1^+ \land X \to X' \in F_2^+$byreflexivity$X \to A \in F_1$-$X \to A \in F_2 \implies X \to A \in F_2^+$-$X \to A \notin F_2 \implies X \to X' \in F_2^+ \land X' \to A \in F_2^+ \implies X \to A \in F_2^+$bytransitivity$X \to A \in F_2$-$X \to A \in F_1 \implies X \to A \in F_1^+$-$X \to A \notin F_1 \implies X \to A \in F_1^+$byHP$F_2 \equiv F_1 \implies F \equiv F_2$bytransitivityofthe$\equiv relationship

Minimal cover (step 3)

X \to A \in F_2, ; A \in (X)^+{F_2 \setminus \set{X \to A}} \implies F_3 = F_2 \setminus \set{X \to A}X \to A \in F_2$-$X \to A \in F_3 \implies X \to A \in F_3^+$-$X \to A \notin F_3 \implies X \to A \in F_3^+$byHPas$A \in (X)^+{F_3}X \to A \in F_3$-$X \to A \in F_2 \implies X \to A \in F_2^+$-$X \to A \notin F_2$isacontraddictionas$F_3 = F_2 \setminus \set{X \to A}$bydefinition$F_2 \equiv F_3 \implies F \equiv F_3

Decomposition

def decomposition(R, F: minimal cover):
	S = ∅
	ρ = ∅

	for A ∈ R | ∄ X → Y ∈ F : A ∈ XY:
		S = S ∪ {A}

	if S != ∅:
		R = R - S
		ρ = ρ ∪ {S}

	if ∃ X → Y ∈ F | XY = R:
		ρ = ρ ∪ {R}
	else:
		for X → A ∈ F:
			ρ = ρ ∪ {XA}

Decomposition pt.2

PDF 19 slide 5

Let R$bearelationalschemaand$F$asetoffunctionaldependencieson$R$,whichisaminimalcover;thealgorithm‘decomposition()‘compute{s}_{(}inpolynomialtime{)}_{a}decomposition$\rho$of$R$suchthat:-eachrelationalschemain$\rho$isin3NF-$\rho$preserves$F