Inference Rules for Functional Dependencies

1.Definitions

Definition. Functional dependency, denoted by X → Y, between two sets of attributes X and Y that are subsets of R specifies a constraint on the possible tuples that can form a relation state r of R. The constraint is that, for any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also have t1[Y] = t2[Y].

This means that the values of the Y component of a tuple in r depend on, or are determined by, the values of the X component; alternatively, the values of the X component of a tuple uniquely (or functionally) determine the values of the Y component. We also say that there is a functional dependency from X to Y, or that Y is functionally dependent on X. The abbreviation for functional dependency is FD or f.d. The set of attributes X is called the left-hand side of the FD, and Y is called the right-hand side.

Thus, X functionally determines Y in a relation schema R if, and only if, whenever two tuples of r(R) agree on their X-value, they must necessarily agree on their Y value. Note the following:

• If a constraint on R states that there cannot be more than one tuple with a given X-value in any relation instance r(R)—that is, X is a candidate key of R—this implies that X → Y for any subset of attributes Y of R (because the key constraint implies that no two tuples in any legal state r(R) will have the same value of X). If X is a candidate key of R, then X→R.
• If X→Y in R, this does not say whether or not Y→X in R.

Definition of closure. Formally, the set of all dependencies that include F as well as all dependencies that can be inferred from F is called the closure of F; it is denoted by F⁺.

Definition of closure of X under F. For each such set of attributes X, we determine the set X_F⁺ of attributes that are functionally determined by X based on F; X_F⁺ is called the closure of X under F.

Definition covered by F. A set of functional dependencies F is said to cover another set of functional dependencies E if every FD in E is also in F⁺; that is, if every dependency in E can be inferred from F; alternatively, we can say that E is covered by F.

Definition of equivalence . Two sets of functional dependencies E and F are equivalent if E⁺ = F⁺. Therefore, equivalence means that every FD in E can be inferred from F, and every FD in F can be inferred from E; that is, E is equivalent to F if both the conditions—E covers F and F covers E—hold.

Definition of minimal cover . A minimal cover of a set of functional dependencies E is a minimal set of dependencies (in the standard canonical form and without redundancy) that is equivalent to E.We can always find at least one minimal cover F for any set of dependencies E

2.Inference Rules for Functional Dependencies

We denote by F the set of functional dependencies that are specified on relation schema R. Typically, the schema designer specifies the functional dependencies that are semantically obvious; usually, however, numerous other functional dependencies hold in all legal relation instances among sets of attributes that can be derived from and satisfy the dependencies in F. Those other dependencies can be inferred or deduced from the FDs in F.

We use the notation F |=X → Y to denote that the functional dependency X→Y is inferred from the set of functional dependencies F.The following six rules IR1 through IR6 are well-known inference rules for functional dependencies:

• IR1 (reflexive rule): If X ⊇ Y, then X→Y.
• IR2 (augmentation rule): {X→Y} |=XZ→YZ.
• IR3 (transitive rule): {X→Y, Y→Z} |=X→Z.
• IR4 (decomposition, or projective, rule): {X→YZ} |=X→Y.
• IR5 (union, or additive, rule): {X→Y, X→Z} |=X→YZ.
• IR6 (pseudotransitive rule): {X→Y,WY→Z} |=WX→Z.

The reflexive rule (IR1) states that a set of attributes always determines itself or any of its subsets, which is obvious. Because IR1 generates dependencies that are always true, such dependencies are called trivial. Formally, a functional dependency X→Y is trivial if X ⊇ Y; otherwise, it is nontrivial.

Proof of IR1:

Suppose that X ⊇ Y and that two tuples t1 and t2 exist in some relation instance r of R such that t1 [X] = t2 [X]. Then t1[Y] = t2[Y] because X ⊇ Y; hence, X→Y must hold in r.

Proof of IR2:

Assume that X→Y holds in a relation instance r of R but that XZ→YZ does not hold. Then there must exist two tuples t1 and t2 in r such that

• (1) t1 [X] = t2 [X],
• (2) t1 [Y] = t2 [Y],
• (3) t1 [XZ] = t2 [XZ],
• (4) t1 [YZ] ≠ t2 [YZ].

This is not possible because from (1) and (3) we deduce (5) t1 [Z] = t2 [Z], and from (2) and (5) we deduce (6) t1 [YZ] = t2 [YZ], contradicting (4).

Proof of IR3:

Assume that (1) X → Y and (2) Y → Z both hold in a relation r. Then for any two tuples t1 and t2 in r such that t1 [X] = t2 [X], we must have (3) t1 [Y] = t2 [Y], from assumption (1); hence we must also have (4) t1 [Z] = t2 [Z] from (3) and assumption (2); thus X→Z must hold in r.

Proof of IR4:

• 1. X→YZ (given).
• 2. YZ→Y (using IR1 and knowing that YZ ⊇ Y).
• 3. X→Y (using IR3 on 1 and 2).

Proof of IR5:

• 1. X→Y (given).
• 2. X→Z (given).
• 3. X→XY (using IR2 on 1 by augmenting with X; notice that XX = X).
• 4. XY→YZ (using IR2 on 2 by augmenting with Y).
• 5. X→YZ (using IR3 on 3 and 4).

Proof of IR6 :

• 1. X→Y (given).
• 2. WY→Z (given).
• 3. WX→WY (using IR2 on 1 by augmenting with W).
• 4. WX→Z (using IR3 on 3 and 2).

Inference rules IR1 through IR3 are known as Armstrong’s inference rules.

Algorithm. DeterminingX_F⁺ , the Closure of X under F

• Input: A set F of FDs on a relation schema R, and a set of attributes X, which is a subset of R.
• X+ := X;
• repeat
• oldX+ := X+;
• for each functional dependency Y→Z in F do
• if X+ ⊇ Y then X+ := X+ ∪ Z;
• until (X+ = oldX+);

The Implementation above Algorithm:Link(For given X and FDs to get X_F⁺)

Algorithm Finding a Minimal Cover F for a Set of Functional Dependencies E

• Input: A set of functional dependencies E.
• 1. Set F := E.
• 2. Replace each functional dependency X→{A1, A2, ..., An} in F by the n functional
• dependencies X→A1, X→A2, ..., X→An.
• 3. For each functional dependency X→A in F
• for each attribute B that is an element of X
• if { {F – {X→A} } ∪ { (X – {B} ) →A} } is equivalent to F
• then replace X→A with (X – {B} ) →A in F.
• 4. For each remaining functional dependency X→A in F
• if {F – {X→A} } is equivalent to F,
• then remove X→A from F.