Functional Dependencies (Chase Algorithm)

Functional Dependency

Formal Definition: Attribute B is functionally dependent upon attribute A (or a collection of attributes) if a value of A determines a single value of attribute B at any one time.

Formal Notation:A→Bor it should be read as'A determines B'or 'B determines A'or'B is functionally dependent on A'. A is called the determinant and B is called the object of the determinant.

Mathematical Definition: Let R be a relation schema, α ⊆ R and β ⊆ R. The functional dependency α →β holds on R if and only if for any legal relations r(R), whenever any two tuples t₁and t₂ of r agree on the attributesα, they also agree on the attributesβ. That is,

t₁[α ] = t₂ [α ] ⇒t₁[β ] = t₂ [β ]

Example: Consider r(A,B) with the following instance of r.

On this instance, A→ B does NOThold, but B →A does hold.

Example:

• Loan_Number →Amount
• CRN→ F_Name
• (Degree, Experience)→Salary.

A functional dependency is trivial if,the consequent is a subset of the determinant. In other words, it is impossible for it to not to be satisfied. In general, A functional dependency of the formα →β is trivial if β ⊆α.

Example:

• AB →A
• A →A
• customer_name, loan_number →customer_name
• customer_name →customer_name

A functional dependency isnon-trivial, if dependency is not trivial.

Example:

• A →B
• (Degree, Experience) →Salary

Compound determinants: If there is an essence of more than one attribute to determine another attribute in an entity, then such a determinant is termed as compound determinant.

Full Functional Dependency: It is only of relevance with composite determinants. Full functional dependency can be taken as a situation when it is necessary to use all the attributes of the composite determinant to identify its object uniquely.

Partial Functional Dependency: This dependency s the situation that exists if it is necessary to only use a subset of the attributes of the composite determinant to identify its object uniquely.

Example:

Example:

Closure of a Set of Functional Dependencies

The set of all Functional dependencies implied by a set of functional dependencies F is called the closure of F. For a given set F of functional dependencies, there are certain other functional dependencies that are logically implied by F. For example: If A → B and B → C, then we can infer that A → C. The set of all functional dependencies logically implied by F is the closure of F. The closure of F is denoted by F⁺ where F⁺ is a superset of F. By applying Armstrong’s Axioms, we find all of F⁺ in following ways:

• If β ⊆α, then α → β. This phenomenon is also called Reflexivity.
• If α → β, then γ α → γ β. This phenomenon is also called Augmentation.
• If α → β, and β → γ, then α → γ. This phenomenon is also called Transitivity.

Additional rules are

• if α → β holds and α → γ holds, then α → β γ holds. This phenomenon is called Union.
• if α → β γ holds, thenα → β holds and α → γ holds. This process is called Augmentation.
• if α → β holds andγ β→δ holds, then α γ → δ holds.This process is called Pseudo transitivity.

It is noted that the above rules can be inferred from Armstrong’s axions.

Example: For given FD, find all possible F⁺.

R = (A, B, C, G, H, I)

F = {A → B, A → C, CG → H, G → I, B → H, CG → I}

Some members of F⁺ are:

• A → H by transitivity from A → B and B → H
• AG → I by augmenting A → C with G, to get AG → CG and then transitivity with CG → I
• CG → HI by augmenting CG → I to infer CG → CGI, and augmenting of CG → H to infer CGI → HI, and then transitivity.

Problem 1: For given FD,

R = (A, B, C, D, E, G, H, I, J)

F = { AB→ E, AG→J, BE→ I, E→ G, GI→ H}

1. List all possible F⁺
2. Does AB→ GH?

Problem 2: For given FD,

R = (A, B, C, D, E, G)

F = { A → B, ABCD →E, EF → G}

1. List all possible F⁺
2. Does ACDF → G, implied by the set of FD's?

Problem 3: For given two set of F1 and F2 for a relation,

F1 = {A → B, AB → C, D → AC, D → E}

F2 = {A → BC, D → AE}

F1 and F2 are equivalent or not?

Problem 4: Let R =(A, B, C, D, E, F)

F = {A → BC, B → E, CD → EF}

1. List all possible F⁺
2. Does AD→ F, implied by the set of FD's?

Closure of Attribute Sets

Given a set of attributes A, define the closure of A under F (denoted by A⁺) as the set of attributes that are functionally determined by under F. Algorithm to compute A⁺, the closure of under F

result := A;

while (changes to result) do

for each β → γ in F do

begin

if β ⊆ result then result := result∪γ

end

Uses of Attribute Closure

Testing for super key- To test, if α is a super key, we compute a⁺, and check if a⁺ contains all attributes of R. Thenα is a super key of R.

Testing functional dependencies- To check if a functional dependencyα → β holds (or. in other words, is in F⁺), just check ifβ⊆α⁺.

Example: For given FD, find closure of (AG)⁺

R = (A, B, C, G, H, I)

F = {A → B, A → C, CG → H, G → I, B → H, CG → I}

• Solution:

1. result = AG
2. result = ABCG (A → C, A → B)
3. result = ABCGH (CG → H and CG⊆ AGBC)
4. result = ABCGHI (CG → I and CG⊆ AGBCH)

• Here AG is the candidate key because closure of AG contains all attributes of R.

Problem1: Let R =(A, B, C, D, E)

F = {B → CD, B → A, E → C, AD → B, D → E}

Is B→ E in F⁺?

Canonical Cover

Sets of functional dependencies may have redundant dependencies that can be inferred from the others

• For example: A→ C is redundant in: {A → B, B → C, A → C}
• Parts of a functional dependency may be redundant
• E.g: On R.H.S: {A → B, B → C, A → CD} can be simplified to {A → B, B → C, A → D}
• E.g: On L.H.S: {A → B, B → C, AC → D} can be simplified to {A → B, B → C, A → D}

Intuitively, a canonical cover of F is a "minimal" set of functional dependencies equivalent to F, having no redundant dependencies or redundant parts of dependencies.

Extraneous Attributes

Consider a set F of functional dependencies and the functional dependency α → β in F.

• Attribute A is extraneous in α if A ∈ α and F logically implies
  (F - {α → β})∪ {(α - A)→β}.
• Attribute A is extraneous in β if A ∈ β and the set of functional dependencies
  (F - {α → β}) ∪ {α →(β - A)} logically implies F.

Example 1: Given F = { A→ C, AB→ C}

B is extraneous in AB→ C because { A→ C AB→ C} logically implies A→ C (i.e the result of dropping B from AB→ C).

Example 2: Given F = { A→ C, AB→ CD}

C is extraneous in AB→ CD since AB→ C can be inferred even after deleting C.

Example 3: Computing a Canonical Cover

R = (A, B, C)

F = {A→ BC, B→ C,A→ B, AB→ C}

• Combine A→ BC and A→ B into A→ BC
  Set is now {A→ BC, B → C, AB → C}
• A is extraneous in AB → C
  Check if the result of deleting A from AB → C is implied by the other dependencies. The answer will be Yes: in fact, B → C is already present
  Set is now {A→ BC, B → C}
• C is extraneous in A→ BC
  Check if A→ C is logically implied by A→ B and the other dependencies. The answer will be Yes: using transitivity on A→ B and B → C
• The canonical cover is: A→ B, B→ C

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhattacharaya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.

.

.

.