[go: up one dir, main page]
Scribd
Upload
22 views17 pages

Functional Dependency

Database functional dependency understanding slide show

Uploaded by

mhrafe420
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views17 pages

Functional Dependency

Database functional dependency understanding slide show

Uploaded by

mhrafe420
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Database Management System

Lecture 4: Functional Dependency


Chapter: 7
Outline
• Functional dependency (FD)
• Keys
• Closure set of attributes
• Canonical form
• Equivalence
• Finding Candidate key, Prime and Non
Prime attributes
Functional Dependency (FD)
• The functional dependency is a relationship that exists
between two attributes. It typically exists between the
primary key and non-key attribute within a table.
•X → Y
• The left side of FD is known as a determinant, the right
side of the production is known as a dependent.
• Functional dependency is used as a tool for
normalization
• Data is dependent on FD, FD is not dependent on Data.
students
Id Name Roll Phone Address gpa
1 Kabir 121 0178 Dhaka 3.5
2 Khan 122 019088 Barishal 3.45
3 Alice 123 0192320 Barishal 2.86
4 Bob 124 088889 Dhaka 4
5 Campher 125 09898089 New york 4
6 Alice 126 979009 Khulna 3.75
Functional Dependencies 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 t1
and t2 of r agree on the attributes , they also agree on the attributes . That
is,

t1[] = t2 []  t1[ ] = t2 [ ]

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


1 4
1 5
3 7

• On this instance, B  A hold; A  B does NOT hold,


Examples
• ABC
• DEC
• CDE
• BCD
Types of FD
• Trivial
– A → B has trivial functional dependency if B is a
subset of A.
– Examples: A → A, B → B, ABA
• Non Trivial
– A → B has a non-trivial functional dependency if B is
not a subset of A.
– When A intersection B is NULL, then A → B is called as
complete non-trivial.
– Examples: AB, ABABC
Closure of a Set of Functional Dependencies

• It is the complete set of all possible attributes that can


be functionally derived from given functional
dependency using the inference rules known as
Armstrong's Rules.
• Given a set F set of functional dependencies, there are
certain other functional dependencies that are logically
implied by F.
– 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.
• We denote the closure of F by F+.
Armstrong’s axioms or
Inference Rules
• Reflexivity Rule: If β  α then: α → β
• Augmentation Rule: If α → β then: αγ → βγ
• Transitivity rule. If α → β holds and β → γ holds,
then α → γ holds

• Union rule. If α → β holds and α → γ holds,


then α → βγ holds.
• Decomposition rule. If α → βγ holds, then α → β
holds and α → γ holds
How to Find Closure set of Attributes
• R(ABC)
• F:
– AB
– BC
• A+{A,B,C}
• B+{B,C}
• C+{C}
Exercises

R (ABCDEFG) R (ABCDE) R (ABCDEFGH)


FD: FD: FD:
 AB  ABC  ABC
 BCDE  CDE  CDE
 AEGG  BD  EC , DAEH
(AC)+=?  EA  ABHBD, DHBC
(B)+=? And (AB)+=? BCDH?
Equivalence of FD
• R(ABCDEH)
• F1:
– AC
– ACD
– EAD
– EH
• F2:
– ACD
– EAH
Irreducible set of FD (Canonical Cover)
• A canonical cover is a simplified and reduced version
of the given set of functional dependencies.

• R(ABCD)
• FD:
– BA
– ADBC
– CABD
• Canonical Cover (Fc):
– BA
– ADC
– CBD
Keys SK, CK, PK
• R(ABCD)
– FD1: ABC
– FD2: ABC D, ABCD, ABCD
– FD3: BACD, ACDB
• Super key is the key that can uniquely identify any
record in a database
• Candidate Keys are super keys with the least
number of attributes. Any CK can not be proper
sub set of any other super keys.
– ABCD
– ABCD [here A is the subset of the super key AB]
Finding Candidate Keys
• R(ABCD)
– AB, BC, CA
• A(ABCD)
– ABCD, DA
• R(ABCDEF)
– ABC, CD, BAE
• R(ABCDE)
– ABCD, DA, BCDE
Prime and Non-Prime Attribute
• Prime Attribute: Member of candidate key
• Non-Prime Attribute: Attributes those are not
member of candidate key
Chapter 7: Functional Dependency

END OF LECTURE

You might also like