Functional dependency

Relational database
Relational database is a set of tables containing data . Each table (which
is sometimes called a relation) contains one or more data categories in
columns . the relational schema R contains a set S of attributes
(A1,A2,A3,…..,An) where attribute A is defined on domain Di for 1<=i<=n
. The relation defined on schema R is a finite set of tuples (t1,t2,….tn) .
The relation is represented by r or r(R) . Here r is the name of the
relation and R is the schema on which r is defined.
Tables are also knows as relation.
Columns are known as attribute.
A B C
x y z
a r h
v f G
w(a , b ,c)Here w is the name of relation and a , b & c
are attributes of relation w.

Relations can be represented as
relation W relation Student
A B C
x y z
a r h
v f G
id name branch
1 gg3 IT
2 gg2 CS
3 gg1 EC
W(ABC) Student(id name branch)
attributes
ABC are the attributes of relation W Id name branch are the attributes of student relation

Functional dependency
In relational database theory, a functional dependency(a->b) is a
constraint between two sets of attributes in a relation from a database.
In other words, functional dependency is a constraint that describes
the relationship between attributes in a relation.
Dependency (a->b) means that if we know value of a we can find value
of b easily.
a b
X Y
X Y
z Z
For same values of a ,values of b are
also same so dependency a->b holds
good.
r(a,b)
a b c d
X p z a
X p z b
X q t c
For same values of ab , values of c are
same so dependency ab->c holds good
R(a , b,c,d)

Functional dependency
there is a relation R(a , b) .
R={a , b}
subsets of R ={{a , b},{a},{b},{}}
a & b both are subsets of R
a ⊆ R ,b ⊆ R
If values of a in more than one tuples are same
and values of b are also same for those tuples
Then there is functional dependency a->b .
if Functional dependency (fd) a -> b exists .
t1[a]=t2[a]
then it must be true for dependency existence i.e.
t1[b]=t2[b]
NOTE :: on same values of a it is impossible to get different values of b on a->b .
Relation R(ab)
a b
t1 x y
t2 x y
t3 z v

Objective:: Check on relation R whether Functional dependency (a->b)
exists or not?
Solution---
In this problem we have two different values of b on same values of a.
t1[a]=t2[a]
But t1[b] != t2[b]
so Dependency does not exist.
Relation R(ab)
Different values of b
a b
x y
x z
z v
Same values of a

Types of dependency(x ->y)
Trivial dependency
Ab->b
In trivial dependency y(b) is a
subset of x(ab).
y⊆ x
Dependency exists but it is
not efficient because we get
insignificant information in this
dependency .
Non trivial dependency
ab->bc
In non trivial dependency y(bc)
is not subset of x(ab)
If y ⊆ x
Dependency exists also in this
case and it is more efficient
because in this dependency
we can get information more
than trivial dependency.
x y x y

Objective:: check following dependencies holds good or not on relation
R
1. a->bc
2. de->c
3. c->de
R(a,b,c,d,e)
a b c d e
T1 x 2 3 4 5
T2 2 a 3 4 5
T3 x 2 3 6 5
t4 x 2 3 6 6
dependencies

a ->bc
In functional dependency x->y ,as we know for same values of x , y should be
same.
Fd  a->bc
For same values of a , there are
same values of bc so dependency
Holds good .
As t1[x]=t3[x]=t4[x]
Then t1[y]=t3[y]=t4[y]
From given relation
For every a=x
bc=23
So a -> bc dependency exist.

de ->c
As we know , for same values of x , y should be same.
As t1[x]=t2[x]
Then t1[y]=t2[y]
So dependency holds good.
There is no problem in searching each value of y w.r.t x .
For every unique value of x there is unique value of y.
a b c d e
T1 x 2 3 4 5
T2 2 a 3 4 5
T3 x 2 3 6 5
t4 x 2 3 6 6

C->de
As we know , for same values of x , y should be same.
As t1[x]=t2[x]=t3[x]=t4[x]
Then t1[y]=t2[y]!= t3[y]!=t4[y]
For every c= 3
de is not same
So dependency
c -> de does not exist.
a b c d e
T1 x 2 3 4 5
T2 2 a 3 4 5
T3 x 2 3 6 5
t4 x 2 3 6 6

note – in functional dependency x->y
If all the values of x are different then dependency always exist.
If all values of y are same then dependency always exist.
for normalization functional dependency is used as tool .
a b C
s j P
R e P
q W q
Dependency ab->c
always exist in this
relation.
a b C
s j P
R e P
q W p
Dependency ab->c
always exist in this
relation.

Closure of set of functional dependencies
Let F is set of all functional dependencies.
Then closure of set of functional dependencies is the set of all
functional dependencies that can be inferred(guessed) from F.
Objective :: F={(a->b),(ab->c)}
check functional dependency( bd->cd )exist or not.
Solution-
a ->b
ab ->c
b ->c
bd->cd (augmentation rule)
Dependency bd -> cd exist.

Inference rules
There are 6 inference rules for functional dependencies.
IR1-{reflexive rule}
IR2-{augmentation rule}
IR3-{transitivity rule}
IR4-{union rule}
IR5-{decomposition rule}
IR6-{pseudo transitivity rule}
RAT axioms or
ARMSTRONG’s axiom

axioms
An axiom is a statement that is taken to be true,
to serve as starting point for further reasoning
and arguments.

Reflexivity rule-IR1
If x is a set of attributes and y⊆ x , then x->y holds i.e. if y is a subset of
x then x->y holds. A functional dependency is said to be trivial if y⊆ x .
Augmentation rule-IR2
If x->y holds then xz->y and xz->yz also holds i.e. if we augment a set of
attributes z to the left side or to both side of fd x->y , then resultant fd
also hold.
If x->y is holds and z is a set of attributes , then z x->z y holds.
Transitivity rule- IR3
If x->y holds and y->z holds , then x->z also holds.
These three rules are known as Armstrong axioms and these are sound ,
because they do not generate any incorrect functional dependency.

Union rule-IR4
If x->y holds and x->z holds , then x->yz holds.
Decomposition rule-IR5
If x->yz holds , then x->y holds , x->z holds.
Pseudo transitivity rule-IR6
If x->y holds and zy->q holds ,then zx->q holds.

Objective- given relation R(a,b,c,d,e,f,g) and a set of FD {a->b ,
abcd->e , ef->g } IS acdf->g, implied by the set of given fd’s?
Solution-
given a->b
abcd->e
ef->g
Abcd->e
Aacd->e
implies acd->e(by pseudotransitivity rule)
acdf->ef(by augmentation rule)
acdf->g( by transitivity rule)
hence acdf->g
Hence acdf->g by the set of fd.

Closure set of attributes
Given R(a,b,c)
Fd’s a-> b
b->c
with the help of a we can get b
From b we can find c
So all the attributes can be derived from given dependencies so closure
of a+ ={abc} .
let F= total set of dependency.
F=f1+f2
Dependencies
which are
directly
visible
Dependencies
that are not
directly visible
F1=A->b
F2= A->c
F=A->bc

a+ = { abc}
b+ ={bc}
C+ ={c}
Closure is represented by attribute + symbol.

1. Objective : given R(a,b,c,d,e,f,g)
dependencies
a->b
bc->de
aeg->g
Find (ac)+ .
solution –
let x={ac}
X1={abc} (by 1 dependency)
X2={abcde} (by 2 dependency)
We can not use 3 dependency because we do not have g .
(ac)+ =x2
hence (ac)+ ={abcde}

2. Objective :given R(a,b,c,d,e)
fd { a->bc , cd->e, b->d, e->a}
find b+ .
let x={b}
X1={bd} (by 3 dependency)
b+=x1
So (b)+ = {bd}.
note ---------Cd is not used because it is not possible
Ab->c
A->b
A->c

Objective: R(abcdef)
Fd ’ s ab->c
bc->ad
d->e
cf->b
Find (ab)+.
Solution-
let x={ab}
X1={abc} (by 1 dependency)
X2={abcd} (by 2 dependency)
X3={abcde} (by 3 dependency)
(ab)+ =x3= {abcde}

Objective: given R(abcdefgh)
A->bc
Cd->e
E->c
D->aeh
Abh->bd
Dh->bc
Check bcd->h is this dependency is valid or not??
Solution-
(bcd)+ = {bcdaeh}
closure of bcd contains h so bcd->h dependency is valid.

Canonical form/irreducible form
In canonical form we check that there is any redundant element exist
or not , if there is any redundant element exist then remove it .
Redundant –
If presence or absence of element do not effect capability of given
functional dependency , then we have to eliminate that dependency, it
is considered as minimization.
R(w,x,y,z)
x->w
wz->xy
y->wxz
Irreducible form –
A set F of FDs is non redundant (irreducible)if there is no proper
subset F’ of F with F' ≡ F. If such an F' exists, F is
redundant(redundant).
In this problem functional dependency{ wz->x ,x->w }are
redundant.

Note-
If there is any dependency from P->Q
1.Then it may be redundancy on left side
2.It may be redundancy on right side
3.It may be redundancy on both side.

Steps-
1.Apply decomposition
2.Find closure set of attribute for each dependency one by one.
3.Then reduce dependency and find closure set for perticular
attribute one by one .
If closure set of attributes computed from 2 is equal to closure
set of attribute from 3 .then dependency can be reduce .now
remove that dependency at that time.
4.Continue step 2&3 for each. If closure from step 2 is not equal
to closure from 3 then dependency is compulsory.
5. After computing all the closure apply composition rule.

Objective : given R(wxyz)
x->w
wz->xy
y->wxz
Find canonical form.

1) Apply decomposition rule:
1. X->w
2. Wz->x
3. Wz->y
4. Y->w
5. Y->x
6. Y->z
Now redundancy on right side removed.

Find closure->
1. X->w(compulsory)
2. Wz->x
3. Wz->y
4. Y->w
5. Y->x
6. Y->z
For first
Step 2)X+ = {x,w}
If presence or absence of any dependency is not affect on system then
that dependency is redundant.
ignore dependency x->w
3) X+ = {x}
After ignoring 1 dependency power of x is not same so x->w
dependency is compulsory.

1. X->w(compulsory)
2. Wz->x(redundant)
3. Wz->y
4. Y->w
5. Y->x
6. Y->z
for second dependency
2).(wz)+ ={wzxy}
After ignoring wz->x
3).(wz)+ = {wzyx}
In this case after ignoring dependency power of wz is not reduced so it
is redundent .

1. X->w(compulsory)
2. Wz->x(redundant)
3. Wz->y(compulsory)
4. Y->w
5. Y->x
6. Y->z
For third dependency
2).(wz)+ ={wzxy}
After ignoring wz->y
3).(Wz)+ ={wzx}
In this case after ignoring dependency power of wz is reduced
so it is not redundent .

1. X->w(compulsory)
2. Wz->x(redundant)
4. Y->w(redundant)
5. Y->x
6. Y->z
For fourth dependency
Y->w
2).Y+ ={ywxz}
After ignoring
3).Y+ ={yxzw}
Dependency y->w is redundant.

1. X->w(compulsory)
2. Wz->x(redundant)
4. Y->w(redundant)
5. Y->x(compulsory)
6. Y->z
For fifth dependency
Y->x
2).Y+ ={wzxy}
After ignoring
3).Y+ ={yz}
Dependency is not redundant .it is compulsory.

1. X->w(compulsory)
2. Wz->x(redundant)
4. Y-> w(redundant)
5. Y->x(compulsory)
6. Y->z(compulsory)
For sixth dependency
Y->z
2).Y+ = {yzwx}
After ignoring
3).y+ = {xyz}
So this is compulsory .

X->w
Wz->y
Y->z
Y->x
Now for checking redundancy on left side
Compute (wz)+ ={wzyx}
Now reduce attribute one by one and get closure
W+ ={w}
z+ = {z}
Now in this case
Neither w+ nor z+ is equal to (wz)+ so neither w nor z is
redundant.
Both are compulsory.

Final Solution
X->w
Wz->y
Y->xz(on applying composition rule)
This is irreducible canonical form of given problem.

Functional dependency

Recommended

More Related Content

What's hot (20)

Similar to Functional dependency (20)

Recently uploaded (20)

Functional dependency