
Quick Contact
DBMS Tutorial
- DBMS Tutorial
- What is Database Management System (DBMS)?
- Components of DBMS
- Applications of DBMS
- Three Schema DBMS Architecture
- Difference between DBMS and RDBMS?
- Difference between File Oriented System and DBMS
- Types of Data Models
- DBMS Schema and Instances
- Data Independence and Data Abstraction
- Database Users and Administrator
- DBMS Languages and Interfaces
DBMS ER Model
DBMS Relational Data Model
DBMS Normalization
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
- A→BC (Given)
- A→C (Rule4)
- AD→CD (Rule2 on step2)
- CD→EF (Given)
- AD→EF (Rule3 on step 3 and step4)
- 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.
- {A,B}+ = {A,B}
- 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}.
- 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.
- For the FD,B → E, we add E to {A,B}+ which now has the value {A,B,C,E}.
- For the FD, CD → EF, {A,B}+ It remains unchanged.
- 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.
- 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