Lukas' Notes

Search titles, aliases and note text. Use # for tags.

Closure (Relational Algebra)

3 min read

relational-algebra

Definition

Closure (Relational Algebra)

The set of all functional dependencies which can be derived by inference from a set of functional dependencies is called the closure of . 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 is a canonical representation of a set of functional dependencies and has the properties:

  1. (see set equivalence of functional dependencies).
  2. There is no functional dependency , where or contains redundant attributes, thus:

is called left-reduced and is called right-reduced.

  1. Every left side of a functional dependency in is unique. By applying composition, is replaced by .

To test efficiently that in is redundant:

  1. is redundant if (attribute closure) - left reduction
  2. is redundant if (attribute closure) - right reduction

Example:

Given the following set of functional dependencies:

We first set :

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

  2. Left reduction: Replace by . This is possible due to transitivity: . The updated is:

  1. Right reduction: Replace by since can already be reached by . The updated is:
  1. Again, compose the left side to be unique. We have two ‘s, using composition:

Backlinks