Synthesis algorithm

The synthesis algorithm describes how a relational database schema becomes a relation schema of the third normal form . The special thing about this algorithm is that, in contrast to the intuitive decomposition of the schema into the third normal form, it guarantees the maintenance of dependency in every case.

An alternative algorithm is the decomposition algorithm , which transfers into Boyce-Codd normal form (BCNF). However, dependencies can be lost (not true to dependency ). It is an alternative insofar as every relational schema that is transformed in BCNF is then automatically available in the third normal form.

requirement

All functional dependencies of the relation to be decomposed under the attributes must be known. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle R}$

Example:

• ${\displaystyle R=\operatorname {Relation} (A,B,C,D,E,F)}$
• ${\displaystyle {\mathcal {F}}=\left\{\left\{A\right\}\to \left\{B,E\right\},\left\{A,E\right\}\to \left\{B,D\right\},\left\{F\right\}\to \left\{C,D\right\},\left\{C,D\right\}\to \left\{B,E,F\right\},\left\{C,F\right\}\to \left\{B\right\}\right\}}$

The synthesis algorithm then consists of four steps:

1. Reduction of , d. H. the determination of the canonical coverage. ${\displaystyle {\mathcal {F}}}$
2. Creation of the new relation schemes from the canonical cover.
3. Possibly. the addition of a relation that only contains the original key.
4. Elimination of the schemes that are contained in another scheme.

reduction

This is also called the calculation of the canonical coverage .

1st step: Left reduction

For all replace by , if is already determined by . ${\displaystyle \psi \in \Psi }$ ${\displaystyle \Psi \rightarrow \Gamma }$ ${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma }$ ${\displaystyle \Gamma }$ ${\displaystyle \Psi \setminus \{\psi \}\rightarrow \Gamma }$

The above condition can be tested by checking whether is, where F denotes the set of functional dependencies. If so, can made be removed. ${\displaystyle \Gamma \subseteq \mathop {\mathrm {AttributH{\ddot {u}}lle} } (F,\Psi \setminus \{\psi \})}$ ${\displaystyle \psi }$ ${\displaystyle \Psi }$

Example: ${\displaystyle \mathop {\mathrm {Relation} } \left(A,B,C,D,E,F\right)}$

• ${\displaystyle A\rightarrow B,E}$
• ${\displaystyle A{\underline {E}}\rightarrow B,D}$
• ${\displaystyle F\rightarrow C,D}$
• ${\displaystyle CD\rightarrow B,E,F}$
• ${\displaystyle {\underline {C}}F\rightarrow B}$

In the second relation, E is omitted because B and D are in the attribute envelope of A ( ). In the last relation, C is omitted because of . You can also put it this way: E is not needed in to achieve. ${\displaystyle A^{+}=\{A,{\underline {B,D}},E\}}$ ${\displaystyle F^{+}=\{{\underline {B}},C,D,E,F\}}$ ${\displaystyle AE\rightarrow B,D}$ ${\displaystyle B,D}$

Solution:

• ${\displaystyle A\rightarrow B,E}$
• ${\displaystyle A\rightarrow B,D}$
• ${\displaystyle F\rightarrow C,D}$
• ${\displaystyle CD\rightarrow B,E,F}$
• ${\displaystyle F\rightarrow B}$

2nd step: legal reduction

For all replace by , if is already determined transitive by . ${\displaystyle \gamma \in \Gamma }$ ${\displaystyle \Psi \rightarrow \Gamma }$ ${\displaystyle \Psi \rightarrow \Gamma \setminus \{\gamma \}}$ ${\displaystyle \gamma }$ ${\displaystyle \Psi }$

The above condition can be checked by testing for each whether is. If so, can made be removed. ${\displaystyle \gamma \in \Gamma }$ ${\displaystyle \gamma \in {\text{AttributHuelle}}((F\setminus (\Psi \rightarrow \Gamma ))\cup (\Psi \rightarrow (\Gamma \setminus \gamma )),\Psi )}$ ${\displaystyle \gamma }$ ${\displaystyle \Gamma }$

In the example above:

• ${\displaystyle A\rightarrow {\underline {B}},E}$
• ${\displaystyle A\rightarrow B,D}$
• ${\displaystyle F\rightarrow C,D}$
• ${\displaystyle CD\rightarrow {\underline {B}},E,F}$
• ${\displaystyle F\rightarrow B}$

In the first relation B is omitted because = {A, B , D, E}. In the fourth relation the B is also omitted because of = { B , C, D, E, F}. ${\displaystyle A_{F'}^{+}}$ ${\displaystyle CD_{F'}^{+}}$

• ${\displaystyle A\rightarrow E}$
• ${\displaystyle A\rightarrow B,D}$
• ${\displaystyle F\rightarrow C,D}$
• ${\displaystyle CD\rightarrow E,F}$
• ${\displaystyle F\rightarrow B}$

3rd step: Empty clauses

Eliminate form clauses ${\displaystyle \Psi \rightarrow \varnothing }$

In the example from step 2, there are no dependencies with an empty, right-hand side. So in this case there is nothing to do here.

4th step: summarize

Fasse formulas to together. ${\displaystyle a\rightarrow b_{0},a\rightarrow b_{1}\dots }$ ${\displaystyle a\rightarrow b_{0}\cup b_{1}\dots }$

In the example we now summarize expressions with the same left side:

• ${\displaystyle A\rightarrow E,B,D}$
• ${\displaystyle F\rightarrow C,D,B}$
• ${\displaystyle CD\rightarrow E,F}$

New relation scheme

All Ψ Γ become R (Ψ, Γ). ${\displaystyle \to }$

In addition, a new key must be found. If necessary, a new relation must be created. Unnecessary relations can be deleted if they are contained in others.

Exemplary:

• ${\displaystyle R_{1}}$( A , B, D, E) # A is the primary key
• ${\displaystyle R_{2}}$(B, C, D, F ) # F is the primary key
• ${\displaystyle R_{3}}$( C, D , E, F) # CD is the primary key (the elements of this relation are already through and given, but to preserve the dependency they must still be listed, it should only be removed if one relation were completely contained in another. However, this is not possible because these cases were removed beforehand by the left and right reduction.) ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$

Adding a relation

Now, by adding a relation, a relationship between , and must be established. This is made possible by a relation that only contains the source key (note that is). We get a scheme in the 3rd normal form as follows: ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{3}}$ ${\displaystyle R_{4}}$ ${\displaystyle AF}$ ${\displaystyle AF^{+}=\{A,B,C,D,E,F\}}$

• ${\displaystyle R_{1}({\underline {A}},B,D,E)}$
• ${\displaystyle R_{2}(B,C,D,{\underline {F}})}$
• ${\displaystyle R_{3}({\underline {C}},{\underline {D}},E,F)}$
• ${\displaystyle R_{4}({\underline {A}},{\underline {F}})}$, where and respectively represent foreign keys and together generate the primary key of . ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle R_{4}}$

Formal algorithm

Input: universal scheme Output: 3. Normal form of ${\displaystyle R=(U,F)}$
${\displaystyle D}$ ${\displaystyle R}$

${\displaystyle B:=\operatorname {reduction} (F)}$

${\displaystyle R:=\emptyset }$

${\displaystyle i:=0}$

${\displaystyle \mathbf {for\,each} \;Y\subseteq U\;\mathbf {where} \;\exists A\in U.(Y\rightarrow A)\in B}$

${\displaystyle i:=i+1}$

${\displaystyle X_{i}:=Y\cup \{\,A\in U\,|\,(Y\rightarrow A)\in B\,\}}$

${\displaystyle R_{i}:=(X_{i},\Pi _{X_{i}}(B))}$

${\displaystyle R:=R\cup \{R_{i}\}}$

${\displaystyle \mathbf {if} \;\forall R_{i}\in R.(X_{i}\rightarrow U)\notin B^{+}}$

${\displaystyle i:=i+1}$

${\displaystyle R:=R\cup \{R_{i}\}}$

${\displaystyle D:=(R,\emptyset )}$

Individual evidence

1. ^ A. Kemper, A. Eickler: Database systems , ISBN 3486576909 .