Canonical cover

Extraneous attribute

Some attributes in a given relational schema do not affect the closure of functional dependency of the schema.

An attribute of functional dependency in $F$ is said to be extraneous if it can be removed without changing its closure $F^{+}$.

When removing an attribute from a functional dependency:

• Removing an attribute from the left side of a functional dependency could make it a stronger constraint.
• Removing an attribute from the right side of a functional dependency could make it a weaker constraint.

Consider a set $F$ of functional dependencies and a functional dependency $\alpha \to \beta \in F$. Then attribute $A$ is extraneous if:

• $A\in \alpha$:
  $F$ logically implies $\left(F\setminus \{\alpha \to \beta \}\right)\cup \{(\alpha \setminus A)\to \beta \}$
• $A\in \beta$:
  $\left(F\setminus \{\alpha \to \beta \}\right)\cup \{\alpha \to (\beta \setminus A)\}$ logically implies $F$.

Note that a stronger functional dependency always implies a weaker one.

Testing if an attribute is extraneous

Let $R$ be a relation schema, and let $F$ be a set of functional dependencies that hold on $R$.

Consider an attribute $A$ in the functional dependency $\alpha \to \beta \in F$.

• Testing if $A\in \alpha$ is extraneous in $\alpha$:
  1. Let $\gamma =\alpha \setminus A$.
  2. Compute ${\gamma }^{+}$ under $F$.
  3. If $\beta \subseteq {\gamma }^{+}$, $A$ is extraneous in $\alpha$.
• Testing if $A\in \beta$ is extraneous in $beta$:
  1. Let $F^{\prime }=(F\setminus \{\alpha \to \beta \})\cup \{\alpha \to (\beta \setminus A)\}$
  2. Compute ${\alpha }^{+}$ under $F^{\prime }$.
  3. If $A\in {\alpha }^{+}$, $A$ is extraneous in $\beta$.

Canonical cover

A canonical cover for $F$ is a set of dependencies $F_c$ that satisfies all of the followings:

• $F$ logically implies all dependencies in $F_c$.
• $F_c$ logically implies all dependencies in $F$.
• None of the attributes in $F_c$ is extraneous.
• Each left side of all functional dependencies in $F_c$ is unique.
  • i.e., $\forall {\alpha }_1\to {\beta }_1,{\alpha }_2\to {\beta }_2\in F_c:{\alpha }_1\ne {\alpha }_2$

Purpose of canonical covers

Whenever a user performs an update on a relation, the database system must ensure that the update does not violate any functional dependencies.

The effort spent in checking for violations in functional dependencies can be reduced by testing on only a simplified set of functional dependencies that has the same closure as the given set. This is the canonical cover of the functional dependencies.

Algorithm for computing canonical covers

F_c = F
REPEAT
  FOR EACH alpha -> beta1, alpha -> beta2 IN F_c
    APPLY union rule
    /* alpha -> beta1, beta2 */
    REPLACE TO F
  FOR EACH f in F_c
    IF EXISTS (extraneous attribute A) IN f
    REMOVE A FROM f
UNTIL (F_c CONVERGE)

Note that the union rule may become applicable after some extraneous attributes have been deleted, so it has to be re-applied.