Minimal FD Lists

• Definitions

• Example

Definitions

• Minimal FD Lists
• Minimal FD Sets

[Top]

Minimal FD Lists

A list of FDs is minimal if:

• There are no trivial FDs; and

• There are no wasteful FDs; and

• There are no derivable FDs; and

• The right-hand side (RHS) of every FD contains only one attribute.

An FD is trivial if its RHS is a subset of its left-hand side (LHS).

An FD is wasteful if

• it is not trivial; and
• its RHS is fully functionally determined by a subset of its LHS.

An FD is derivable if

• it is not wasteful; and
• it can be derived from other FDs in the list.

Edmondson

[Top]

Minimal FD Sets

Informally, a minimal cover of a set of functional dependencies E is a set of functional dependencies F that satisfies the property that every dependency in E is in the closure F+ of F. In addition, this property is lost if any dependency from the set F is removed; F must have no redundancies in it, and the dependencies in E [sic] are in a standard form. To satisfy these properties, we can formally define a set of functional dependencies F to be minimal if it satisfies the following conditions:

1. Every dependency in F has a single attribute for its right-hand side.
2. We cannot replace ant dependency X → A in F with a dependency y → A, where y is a proper subset of X, and still have a set of dependencies that is equivalent to F.
3. We cannot remove and dependency from F and still have a set of dependencies which is equivalent to F.

We can think of a minimal set of dependencies as being a set of dependencies in a standard or canonical form and with no redundancies. Condition 1 just represent every dependency in a canonical form with a single attribute on the right-hand side. Conditions 2 and 3 ensure that there are no redundancies in the dependencies either by having redundant attributes on the left-hand side of a dependency (Condition 2) or by having a dependency that can be inferred from the remaining FDs in F (Condition 3). A minimal cover of a set of functional dependencies E is a minimal set of dependencies F that is equivalent to E. There can be several minimal cover sets for a set of functional dependencies.

(Elmasri & Navathe 2004:311)

[Top]

Example

HTH (H, A, N, D)

A minimal FD list (F) for HTH:

     H -> A
     A -> H
     H -> N
     A -> D

A minimal FD list (G) for HTH:

     H -> A
     A -> H
     H -> D
     A -> N

A minimal FD list (H) for HTH:

     H -> A
     A -> H
     A -> D
     A -> N

A minimal FD list (I) for HTH:

     H -> A
     A -> H
     H -> D
     H -> N

A minimal set of FDs for HTH:

  F = {H -> A,
       A -> H,
       H -> D,
       H -> N}

[Top]