Attribute Sets

A set of attributes.

Closure

Suppose $X$ is an attribute set and $F$ is a set of functional dependencies.

Closure of $X$ under a set of functional dependencies $F$, is the set of all attributes functionally determined by $X$ using the dependencies in $F$. Denoted as $X^+$,

Algorithm

$X^+$ can be computed by:

1. Start with $X^+ = X$.
2. For each dependency $Y \rightarrow Z$ in $F$:
   If $Y \subseteq X^+$, then add $Z$ to $X^+$.
3. Repeat until no new attributes can be added.

If $X^+$ includes all attributes of $R$, then $X$ is a superkey of $R$.

Can be used to test if a given functional dependency holds.

def attribute_closure(attributes, fds):
    """
    Compute the closure of a set of attributes with respect to a set of functional dependencies.

    :param attributes: set of attribute strings, e.g. {'A', 'B'}
    :param fds: list of tuples (lhs, rhs), where lhs and rhs are sets of attributes
                e.g. [({'A'}, {'B'}), ({'B'}, {'C'})]
    :return: set of attributes in the closure
    """
    closure = set(attributes)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs.issubset(closure) and not rhs.issubset(closure):
                closure.update(rhs)
                changed = True
    return closure

Extraneous Attributes

Unnecessary attributes in a functional dependency (FD) that can be removed without affecting the closure. Can either be in LHS or RHS.

Removing extraneous attributes:

• Simplifies functional dependency sets
• Helps compute minimal covers
• Avoids redundant checks during normalization

Testing

Consider a set of functional dependencies $F$, and $\alpha \rightarrow \beta \in F$.

The attribute $A \in \alpha$ is extraneous in $\alpha$ if $(\alpha - A)^+$ contains $\beta$.

The attribute $A \in \beta$ is extraneous in $\beta$ if:

• Compute $\alpha^+$ using only the dependencies in $F' = (F - \set{\alpha \rightarrow \beta}) \cup (\alpha \rightarrow (\beta - A))$
• Check if $\alpha^+$ contains $A$. If it does, $A$ is extraneous in $\beta$

Examples

Attribute in the LHS.

Given $F = \set{A \rightarrow C, AB \rightarrow C}$. Test $B$ in $AB \rightarrow C$.

Attribute in the RHS.

Given $F = \set{A \rightarrow B, B \rightarrow C, A \rightarrow BC}$. Test $C$ in $A \rightarrow BC$.