Functional Dependencies

One of the main concepts associated with normalization is functional dependency, which describes the relationship between attributes.

Characteristics of Functional Dependencies

Assume, that a relational schema has attributes (A, B, C, D, ..., Z) and that the whole database is described by a single universal relation called R = (A, B, C, D, ..., Z).

Functional dependency Describes the relationship between attributes in a relation. For example, if A and B are attributes of relation R, B is functionally dependent on A (denote A->B), if each value of A is associated with exactly one value of B. (A and B may each consist of one or more attributes.)

Determinant Refers to the attribute or a set of attributes on the left-hand side of the arrow of a functional dependency.
See example.

Inference Rules for Functional Dependencies

Closure of X is the set of all functional dependencies that are implied by a given set of functional dependencies X (written X+).
A set of inference rules, called Armstrong's axioms, specifies how new functional dependencies can be inferredfrom given ones.

Name Explanation Example
Reflexivity if B is a subset of A, then A->B sName,Position->Position
Augmenttion if A->B, then A,C->B,C bAddress->branchNo => bAddress,Position->branchNo,Position
Transitivity
If  A->B , then A->C
and
B->C
staffNo->branchNo
branchNo->bAddress		  => staffNo->bAddress
Note that each of these three rules can be directly derived from the definition of functional dependency. The rules are complete in that given a set X of functional dependencies, all functional dependencies implied by X can be derived from X using these rules. In other words, the rules can be used to derived the closure of X+.
Several further rules can be derived from the three given above that simplify practical task of computing X+.
Self-determination A->A  
Decomposition
If A->B,C, then  A->B
and
A->C
staffNo->Position,Salary  =>  staffNo->Position
and
staffNo->Salary
Union
If  A->B
and
A->C		 , then A->B,C
staffNo->Position
and
staffNo->Salary		   => staffNo->Position,Salary
Composition
If  A->B
and
C->D		 , then A,C->B,D
staffNo->sName
and
branchNo->bAddress		   => staffNo,branchNo->Position,bAddress

Minimal Set of Functional Dependencies

Definition 1: A set of functional dependensies Y is covered by a set of functional dependencies X, if every functional dependency in Y is also in X+.

Definition 2: A set of functional dependencies X is set to be equivalent to a set of functional dependencies Y if X is covered by Y and Y is covered by X.

Definition 3: A set of functional dependencies X is minimal if it satisfies the following conditions:
  		• Every dependency in X has a single attribute on its right-hand side.
  		• We can not replace any dependency A->B in X with dependency C->B, where C is a proper subset of A, and still have a set of dependencies that is equivalent to X.
  		• We can not remove any dependency from X and still have a set of dependencies that is equivalent to X.


    Definition 4: Full Functional Dependency. Indicates that if A and B are attributes of a relation, B is fully functionally dependent on A if
  • B is functionally dependent on A,
  • but not on any proper subset af A.

    Definition 5: Transitive dependency. A condition where A, B, and C are attributes of a relation such that A->B and B->C, then C is tranditively dependent on A via B (provided that A is not functionally dependent on B or C).