Functional Dependencies (Fds)

Functional Dependencies (FDs)

1. Definition of FD

2. Definition of FFD

3. Attribute closure

4. Key(Candidate & Primary)

5. Prime and Non prime attribute

6. Trivial Dependencies

7.Inference Rules for FDs

8.Equivalence of Sets of FDs

9.Minimal Sets of FDs

Functional Dependency (FD)

A set of attributes X functionally determines a set of attributes Y if each value of X determines a unique value for Y.

X  Y holds if whenever two tuples have the same value for X, they must have the same value for Y

For any two tuples t1 and t2 in any relation instance r(R): If t1[X] = t2[X], then t1[Y]=t2[Y].

Example

Consider the following relation R(A, B, C):

ABC

111

110

232

The FDs A  B and B  A hold in R. However, the FDs A  C, B  C, AB  C do not hold in R.

Consider the following relation R(A, B, C, D):

ABCD

A1B1C1D1

A1B2C1D2

A2B2C2D2

A2B3C2D3

A3B3C2D4

The FD A  C holds in R, but not C  A. The following FDs also hold in R –

D  B, AB  C, AB  D, AB  CD etc.

Note that

a)If X  Y holds in R, it does not necessarily imply that Y  X also holds in R.

b)If X is a candidate key of R, then X  Y holds for any subset of attributes Y of R.

Full Functional Dependency (FFD)

Given a relation R(r), Y is fully functionally dependent on X (X and Y are subsets of the schema r) iff,

(i) Y is functionally dependent on X.

(ii) Y is not functionally dependent on any proper subset of X.

In other words, X  Y is a FFD if removal of any attribute (say A) from X means that the dependency does not hold. That is, (X – A)  Y does not hold in R.

Attribute closure

Closureof a set F of FDs is the set F+ of all FDs that can beinferred from F.

A systematic way to determine the FDs in F+ is first to determine each set of attributes X that appear in the left-hand side of some FD in F, and then to determine the set of all attributes that are dependent on X. Thus for each such set of attributes X, we determine the set X+ of attributes that are functionally determined by X based on F. X+ is called the closure of X under F.

Algorithm to determine X+, the closure of X under F

X+ = X;

Repeat

oldX+ = X+;

for each FD Y  Z in F do

If X+ Y then X+ = X+ Z;

Until (X+ = old X+);

Examples:

i) Let F consist of the following eight dependencies:

AB  CD  EG

C  ABE  C

BC  DCG  BD

ACD  BCE  AG

Find the attribute closure of BD.

Ans: Let X = BD. We have to compute X+.

Initially, X+ = BD

(a) oldX+ = X+ = BD

Now we look for FDs that have a left side B or D or BD. The only FD is D  EG.

So, we adjoin EG to X+, and X+ = BDEG.

(b) oldX+ = X+ = BDEG

The FDs are D  EG and BE  C. So X+ = BCDEG.

The FDs are C  A, BC  D, D  EG, BE  C, CG  BD and CE  AG.

So X+ = ABCDEG

(d) oldX+ = X+ = ABCDEG

The FDs are AB  C, C  A, BC  D, ACD  B

D  EG, BE  C, CG  BD and CE  AG.

So X+ = ABCDEG.

Thus (BD)+ = ABCDEG.

ii)Consider the relation schema R (A, B, C, G, H, I) with the following set of FDs –

F = { A  B, A  C, CG  H, CG  I, B  H }

Find the attribute closure of AG.

Ans: The attribute closure of AG with respect to F is: (AG)+ = ABCGHI

Key

If X is a minimal set of attributes in R and X+ contains all the attributes in relation R then X is the candidate key of R.

Example:

i) Consider the relational schema R(A, B, C, D) with following set of FDs

F={A B, B CD}

Ans: (A)+ =ABCD [ All the attributes in R]

So A is the candidate key in relation R

ii) Find the Candidate key for a relation R(A,B,C,D,E,F,G,H,I,J) with the following FDs

F={ AB  C, A  DE, B  F, F  GH, D  IJ}

Ans: (AB)+ =(ABCDEFGHIJ)

Therefore the key is AB

Prime and non prime attribute

The attributes which are participate to form primary key are called prime attribute and remaining attributes in relation R called non prime attribute.

Trivial Dependencies

A fd X  Y is called:

Trivial if the Yis a subset of the X.
Nontrivial if at least one attribute of the Y is not among the X.
Completely nontrivial if no attribute of the Y is also one of the X.

Examples:

TITLE, YEAR TITLE is a trivial fd.

TITLE, YEAR YEAR, LENGTH is a nontrivial fd but it is not completelynontrivial.

TITLE,YEAR LENGTH is a completely nontrivial fd.

Inference Rules for FDs

Armstrong's inference rules:

IR1 (Reflexive rule): If X  Y, then X  Y.

IR2 (Augmentation rule): If X  Y, then XZ  YZ and ZX  ZY.

IR3 (Transitive rule): If X  Y and Y  Z, then X  Z.

IR1, IR2, IR3 form a sound and complete set of inferencerules

Some additional inference rules that are useful:

IR4 (Union rule): If X  Y and X  Z, then X  YZ.

IR5 (Decomposition rule): If X  YZ, then X  Y and X  Z.

IR6 (Pseudotransitive rule): If X  Y and WY  Z, then WX  Z.

The last three inference rules, as well as any other inferencerules, can be deduced from IR1, IR2, and IR3 (completenessproperty)

Example: From the following FDs derive AB  CD

FD = { AB  E, -- FD1

E  C, -- FD2

BE  I-- FD3

CI  D-- FD4

}

Solution:

AB  C -- Transitive: FD1, FD2
AB  AB -- Reflexive
AB  B-- Decompose
AB  BE-- Union: FD1 and c.
AB  I-- Transitive: d and FD3
AB  CI-- Union: a. and e.
AB  D-- Transitive: FD4 and f.
AB  CD-- Union a and g.

Equivalence of Sets of FDs

Two sets of FDs F and G are equivalent if:

Every FD in F can be inferred from G, and
Every FD in G can be inferred from F.

Hence, F and G are equivalent if F+=G+.

Example:

Let F = { A  C, AC  D, E  AD, E  H} and

G = { A  CD, E  AH }

Show that F and G are equivalent.

Solution:

Set F / Derivation steps from G
AC / A  CDAC
AC  D / A  CDAD  AC  D
E  AD / E  AHE  AE CDE D
E  AD
E  H / E  AHE H
Set G / Derivation steps from F
A  CD / [A  C, AC  D] A D
[A  C, A D]c A  CD
E  AH / E  ADE  A
[E  A, E  H] E  AH

Minimal Sets of FDs

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

E.g.: A C is redundant in: {A B, B C, A C}

Parts of a functional dependency may be redundant

E.g. on RHS: {A B, B C, A CD} can be simplified to{A B, B C, A D}

E.g. on LHS: {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 functionaldependencies which is equivalent to F, minimal in the sense that there are no redundant dependencies and nodependency has any redundant parts

A set of FDs isminimal if it satisfies the followingconditions:

(1) Every dependency in F has a single attribute for its RHS.

(2) We cannot remove any dependency from F and have a setof dependencies that is equivalent to F.

(3) We cannot replace any dependency X  A in F with adependency Y  A, where Y proper-subset-of X(Y X) and still have a set of dependencies that is equivalentto F.

- Every set of FDs has an equivalent minimal set

- There can be several equivalent minimal sets

- There is no simple algorithm for computing a minimal set ofFDs that is equivalent to a set F of FDs

Example:

a) Given relation R(W, X, Y, Z) and set of functional dependencies F = {X W,WZ XY, Y WXZ}

Compute the minimal cover for F.

Answer.

Step 1: X W,WZ X,WZ Y, Y W, Y X, Y Z

Step 2: Don’t need WZ X, since WZ Y and Y X

Don’t need Y W, since Y X and X W

This leaves {X W, WZ Y, Y X, Y Z}

Step 3: Only need to consider WZ Y can’t eliminate W or Z. So nothing is eliminated.

Step 4: {X W, WZ Y, Y XZ} is the minimal cover

b) Given relation R(W, X, Y, Z) and set of functional dependencies G = {Z W, Y XZ,XW Y }

where G is a minimal cover:

c) Example of Computing a Canonical Cover(minimal set)

R = (A, B, C)

F = {ABC,B C,A B,AB C}

Step1: don’t need A BC since A B and B C

This leaves {B C, A B, AB C}

Step2: don’t need AB C since A C[A B and B C]

The canonical cover is: {A B,B C}

******************************************************************************

Question 3 Suppose you are given a relation R=(A,B,C,D,E) with the following functional dependencies:

BD ! E,A ! C.

a. Show that the decomposition into R1=(A,B,C) and R2=(D,E) is lossy. You can show using any

method. My suggestion is to show how spurious tuples result from this decomposition with respect

to the table below:

A B C D E

1 2 3 4 5

1 8 3 4 4

b. Find a single dependency from a single attribute X to another attribute Y such that when you

add the dependency X ! Y to the above dependencies, the decomposition in part a is no longer

lossy.

Answer.

a. If we were to decompose the relations into:

A B C

1 2 3

1 8 3

D E

4 5

4 4

and then join the two (in this case with a cartesian product), we would get:

A B C D E

1 2 3 4 5

1 8 3 4 5

1 2 3 4 4

1 8 3 4 4

Tuples 2 and 3 are not in the original relation. Hence, this decomposition is lossy.

b. This decomposition cannot be made lossless. The problem is there is no longer a way to make

sure BD ! E holds across two relations since they do not share any attributes. However, a lossy

decomposition of the form (A,B,C), (C,D,E) can be made lossless by adding an FD B ! C.

Question 9 Consider relation R(X, Y, Z). Relation R currently has three tuples: (6, 4, 2), (6, 6,

8) and (6, 4, 8). Which of the following three functional dependencies can you infer do not hold

for relation R? Explain your answer.

Y ! X

Z ! Y

XY ! Z

Answer. The first functional dependency holds, but the rest do not hold. The second and third

tuples both have 8 for Z but di_erent values of Y. The first and third tuples both have 6 and 4 for

X and Y but di_erent values for Z.

Question 10 Consider the relation R(V, W, X, Y, Z) with functional dependencies {Z ! Y, Y !

Z,X ! Y,X ! V, VW ! X}.

a) List the possible keys for relation R based on the functional dependencies above.

b) Show the closure for attribute X given the functional dependencies above.

c) Suppose that relation R is decomposed into two relations, R1(V, W, X) and R2(X, Y, Z). Is this

decomposition a lossless decomposition? Explain your answer.

Answer.

a. {V,W}, {X,W} b. X+ = {X, V, Y,Z} c. Yes it is lossless. To be lossless the attributes in common between the two relations must

functionally determine all the attributes in one of the two relations. The only attribute in common

is X and it functionally determines all the attributes in R2.

a) Decompose R into a set of relations in Third Normal Form.

b)Is your decomposition in part a) also in Boyce Codd Normal Form? Explain your answer.

Answer.

a. Possible keys: {Y }, {X,Z}, {W,X} R1=(Z, W), R2=(X, Y, Z), R3=(X, Y, W)

b.Yes. In each of the three relations, the left side of the funcational dependencies that apply are

superkeys for the relation. Hence, all three relations satisfy the definition of BCNF.