Canonical overlap

The canonical cover is a concept from the relational design theory , which deals with the design of the schemes relational databases concerned.

At the beginning of the design of a relational schema there is the information needs analysis . It supplies the set of required attributes and a set F of the functional dependencies between these attributes. Based on these dependencies, normal forms are defined for the schemas of relational databases, which are seen as a “quality criterion” for such a schema.

In general, for a set of functional dependencies, there are many different equivalent sets of functional dependencies. Two sets of functional dependencies F and G are called equivalent if and only if their attribute envelopes are equal, in symbols . If F and G are equivalent, then F is said to cover G and vice versa. ${\displaystyle F\equiv G}$ ${\displaystyle F^{+}=G^{+}}$

For a given set F of functional dependencies, there is a clear attribute envelope , which, however, usually contains many functional dependencies, which has a negative effect when the schema is implemented in a relational database at a later date, since with every change operation as part of a consistency check, compliance with all specified functional dependencies must be checked. ${\displaystyle F^{+}}$

Therefore, in the design process of relational schemes, one is interested in the smallest possible set of equivalent functional dependencies, the canonical covering of the given set of functional dependencies. A canonical coverage describes the smallest valid amount of functional dependencies for a certain relational scheme. The derivation of such a canonical coverage ensures a redundancy-free relational scheme.

For a given set F of functional dependencies, one calls a canonical cover if the following three properties are fulfilled: ${\displaystyle F_{*}}$

• ${\displaystyle F_{*}\equiv F}$, this means ${\displaystyle F_{*}^{+}=F^{+}}$
• In there are no functional dependencies , wherein and contain amounts of unnecessary attributes; that means it must apply: ${\displaystyle F_{*}}$ ${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

(a) ${\displaystyle \forall A\in \mathbf {\alpha } :(F_{*}-(\alpha \rightarrow \beta )\cup ((\alpha -A)\rightarrow \beta ))\not \equiv F_{*}}$

(b) ${\displaystyle \forall B\in \mathbf {\beta } :(F_{*}-(\alpha \rightarrow \beta )\cup (\alpha \rightarrow (\beta -B)))\not \equiv F_{*}}$

• Each left side of a functional dependency in is unique. This can be achieved by continuing to apply the union rule to functional dependencies of type and so that the two functional dependencies are replaced by. ${\displaystyle F_{*}}$ ${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle \alpha \rightarrow \gamma }$ ${\displaystyle \alpha \rightarrow \beta \gamma }$

algorithm

In order to find a canonical cover (the canonical cover is not unique) from a given set of functional dependencies , the following algorithm can be used: ${\displaystyle F}$

1. Left reduction
2. Legal reduction
3. Summarize all functional dependencies from with the same : If , then remove these two functional dependencies and add to . ${\displaystyle \alpha \rightarrow \beta }$ ${\displaystyle F}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \rightarrow \beta \in F,\alpha \rightarrow \gamma \in F}$ ${\displaystyle F}$ ${\displaystyle \alpha \rightarrow \beta \gamma }$ ${\displaystyle F}$

literature

• Alfons Kemper, André Eickler: Database systems. An introduction. 7th updated and expanded edition. Oldenbourg Verlag, Munich 2009, ISBN 978-3-486-59018-0 .