Quick Contact

    Armstrong Axioms-Inference Rules for FDs

    Let F be the collection of functional dependencies that are stated on a relation schema R and P and Q: a subset of R.S rationally means an FD P→Q, indicated by S|=P→Q, if every relation occurrence of R that satisfies all functional dependencies in S also meets P→Q. The closure of S, denoted by S^+, is the set of all functional dependencies that are logically indicated by S. In other words, it is a collection of all functional dependencies that may be logically obtained from S.

    To determine S^+, Armstrong proposed a complete set of rules in 1974 for deriving all possible functional dependency that is implied by 〖S.〗^ These rules are as follows.

    Rules of Functional Dependencies

    Following are the rules of functional dependencies

    Armstrong Axioms-Inference Rules for FDs
    Axioms or Primary Rules
    Axiom of Reflexivity

    If P is a set of attributes and Q is a subset of R, then R contains Q. If Q⊆P then, P→Q. This feature is called a trivial property.

    Axiom of Augmentation

    P→Q|=PY→QY

    We can conclude that if a dependency can hold, then it can quickly increase its left-hand size.

    It should be noted here that the notation PY is used to denote the collection of all attributes in P and Y and write PY rather than the more conventional (P,Y) for convenience.

    Axiom of Transitivity

    If X→Y and Y→Z, then X→Z.

    It is the ‘most powerful’ inference rule, which is useful in multi-step derivations.

    These rules are called Armstrong’s Axioms. Each of these rules can be proved from the definition of FD.

    Armstrong’s inference rules are sound and complete. Sound defines that given set of functional dependencies S stated on a relation design R, any dependency that we can infer from S using Armstrong’s inference rules influence in each relation state R that satisfies the dependencies in S.

    These rules are said to be complete in the sense that given a set of functional dependencies, all functional dependencies implied by S can be deducted from the given set using these rules.

    Secondary Rules

    These rules can be obtained from the raised axioms.

    Union

    If P→Q contains and P→R contains, then P→QR contains.

    If X→Y and X→Z, then X→YZ.

    Proof

    Step1: P→Q (Given)

    Step2: P→R (Given)

    Step3: P→PQ (using rule 2 on step 1, since PP=P.)

    Step4: PQ→QR (Using rule 2 on step2)

    Step5: P→QR (Using rule 3 on step3 and step4)

    Composition

    If P→Q and X→Y hold, then PX→QY holds.

    Decomposition

    If P→QR holds, then P→Q and P→R hold.

    If X→YZ, then X→Y and X→Z.

    Proof

    Step1: P→QR (Given)

    Step2: QR→Q (Using rule 1, since Q⊆QR)

    Step3: P→Q (Using rule3, on step 1 and step2)

    Pseudo Transitivity

    If P→Q holds and QR→S holds, then PR→S holds.

    If X→Y and YZ→W, then XZ→W.

    Proof

    Step1: P→Q (Given)

    Step2: QR→S (Given)

    Step3: PR→QR (Rule2 on step1)

    Step4: PR→S (Rule3 on step3 and step2)

    Example

    Suppose that we are a given relation R with attributes A,B,C,D,F, and the FDs.

    A→BC

    B→E

    CD→EF

    Prove that FD and AD→F also holds in R.

    Proof
    1. A→BC (Given)
    2. A→C (Rule4)
    3. AD→CD (Rule2 on step2)
    4. CD→EF (Given)
    5. AD→EF (Rule3 on step 3 and step4)
    6. AD→F (Rule4 on step5)
    Closure of a Set

    Let S is the set of functional dependencies on the relation R. Let X is set of attributes that appear on a left-hand side of some FD is S. We want to define the set of all attributes that are dependent on X. Thus for each such set of the attribute X, we determine the set X+ of attributes that are functionally determined by X based on S, X+ is called the closure of X under S.

    Algorithm

    Determine X+, the closure of X under S.

    X+ ≔ X;

    Repeat

    old X^+ ≔ X+

    For each FD Y→Z in S do

    If Y is a subset of X+ then

    X+= X+ U Z;

    Until (X+= old X+) // If X+did not change then leave the loop

    Example

    Suppose we are a given relation R with attributes A,B,C,D,E,F and the FDs.

    A → BC

    E → CF

    B → E

    CD → EF

    We now compute the closure {A,〖 B}〗^+on the set of attributes {A,〖 B}〗^ under this set of FDs.

    1. {A,B}+ = {A,B}
    2. For the FD, A → BC we find that the left-hand side is a subset of {A,B}+, so we add attributes (B and C) to the result. So, {A,B}+ = {A,B,C}.
    3. For the FD, E → CF, we find that the left-hand side is not a subset of the result as computed so far, which thus remains unchanged.
    4. For the FD,B → E, we add E to {A,B}+ which now has the value {A,B,C,E}.
    5. For the FD, CD → EF, {A,B}+ It remains unchanged.
    6. Then we go round the inner loop four times again. On the first FD, the result does not change; on the second, it expands to {A,B,C,E,F}; on the third and fourth, it does not change.
    7. And now we go round the inner loop four-time again. {A,B}^+ does not modify, and so the entire step terminates, with {A,B}+={ A,B,C,E,F}.
    Equivalence set of Functional Dependencies

    Two sets of functional dependencies E and F are similar if E+ = F+. Hence, equivalence defines that each FD in E can be inferred from F, and each FD in F can be inferred from E.

    Enroll Yourself in Live Training: DBMS Training

    Copyright 1999- Ducat Creative, All rights reserved.