##### 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