Closure (Relational Algebra)

relational-algebra

Definition

Closure (Relational Algebra)

The set of all functional dependencies $F^{+}$ which can be derived by inference from a set of functional dependencies $F$ is called the closure of $F$. The derivation is based Armstrong’s axioms

This remembers me of the linear span from linear algebra, which is the set of all vector that can be constructed from a set of basis vectors.

Minimal Cover

A minimal cover $F_c$ is a canonical representation of a set $F$ of functional dependencies and has the properties:

1. $F_c\equiv F$ (see set equivalence of functional dependencies).
2. There is no functional dependency $\alpha \to \beta$, where $\alpha$ or $\beta$ contains redundant attributes, thus:

$$\begin{array}{r}(a)\forall \alpha \to \beta \in F_c:\forall A\in \alpha :(F_c-(\alpha \to \beta ))\cup \{(\alpha -A)\to \beta \}\cancel{\equiv }{F}_c\\ (b)\forall \alpha \to \beta \in F_c:\forall B\in \alpha :(F_c-(\alpha \to \beta ))\cup \{\alpha \to (\beta -B)\}\cancel{\equiv }{F}_c\end{array}$$

$(a)$ is called left-reduced and $(b)$ is called right-reduced.

3. Every left side of a functional dependency in $F_c$ is unique. By applying composition, $\alpha \to \beta \wedge \alpha \to \gamma$ is replaced by $\alpha \to \beta \gamma$.

To test efficiently that $A\in \alpha$ in $\alpha \to \beta$ is redundant:

1. $A\in \alpha$ is redundant if $\beta \subseteq (\alpha -A{)}_F^{+}$ (attribute closure) - left reduction
2. $B\in \beta$ is redundant if $B\in {\alpha }_{(F-\{\alpha \to \beta \})\cup \{\alpha \to (\beta -B)\}}^{+}$ (attribute closure) - right reduction

Example:

Given the following set of functional dependencies:

$$F=\{A\to B,B\to C,AB\to C\}$$

We first set $F_c\leftarrow F$:

$$F_c=F=\{A\to B,B\to C,AB\to C\}$$

1. Compose the left side to be unique. Since there are no duplicate left sides in $F_c$, nothing needs to be done.

2. Left reduction: Replace $AB\to C$ by $A\to C$. This is possible due to transitivity: $\underset{\in F_c}{\underbrace{A\to B}}\to C$. The updated $F_c$ is:

$$F_c=\{A\to B,B\to C,A\to C\}$$

3. Right reduction: Replace $A\to C$ by $A\to \varnothing$ since $C$ can already be reached by $A\to B\to C$. The updated $F_c$ is:

$$F_c=\{A\to B,B\to C,A\to \varnothing \}$$

4. Again, compose the left side to be unique. We have two $A$‘s, using composition:

$$F_c=\{A\to B\cup \varnothing ,B\to C\}=\{A\to B,B\to C\}$$