Armstrong Axioms-Inference Rules for FDs

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

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.

Apply now for Advanced DBMS Course