Functional Dependency
Functional
Dependency
1
Functional Dependency
A “good” database schema should not lead to update anomalies.
• update anomalies,
• functional dependencies,
• Armstrong Axioms,
• closures.
2
Update Anomalies
Redundancy in a database means storing a piece of data more than once.
Redundancy is often useful for efficiency and semantic reasons, but
creates the potential for consistency problems.
A poor redundancy control may cause update anomalies.
Consider the example relation below (adapted from “An Introduction to
Database Systems” by Desai):
3
Modification anomalies: e.g. Jones’s phone number appears 3 times. When a
phone number is changed, it must be changed in all 3 places, or the data will be
inconsistent.
4
STUDENTS
Name Course Phone_no Major Prof Grade
Jones 353 237-4539 Comp Sci Smith A
Ng 329 427-7390 Chemistry Turner B
Jones 328 237-4539 Comp Sci Clark B
Martin 456 388-5183 Physics James A
Dulles 293 371-6259 Decision Sci Cook C
Duke 491 823-7293 Mathematics Lamb B
Duke 356 823-7293 Mathematics Bond UN
Jones 492 237- 4539 Comp Sci Cross UN
Baxter 379 839-0827 English Broes C
Insertion anomalies:
• If Jones enrolls in another course, and a different phone number is
entered, again the data will be inconsistent.
• Also, if the only way that the association between course and
professor is stored in this relation, we can only enter the association when
someone enrolls in the course.
Deletion anomalies: If the last student in a course is deleted, the
association between professor and course is lost.
5
Update Anomalies
Functional dependencies
A function f from S1 to S2 has the property
A generalization of keys to avoid design flaws violating the above rule.
Let X and Y be sets of attributes in R.
X (functionally) determines Y , X → Y , iff t1[X] = t2[X] implies t1[Y ] = t2[Y ].
i.e., f (t(X)) = t [Y]
We also say X →Y is a functional dependency, and that Y is functionally dependent on X.
X is called the left side, Y the right side of the dependency.
6
𝑖𝑓 𝑥, 𝑦 ∈ 𝑆1 and 𝑥 = 𝑦, then 𝑓(𝑥) = 𝑓(𝑦) .
• For every Name, there is a unique Phone_no and Major, assume Name is
unique;
• For every Course, there is a unique Prof;
• For every Name and Course, there is a unique
Grade.
7
Examples
8
In this example:
{Name} →{Phone_no , Major}
{Course} → {Prof}
{Name , Course} → {Grade}
We can also show these in a diagram like this one:
Notice that other FD’s follow from these:
{Name} → {Major}
{Course , Grade} → {Prof , Grade}
8
Name Course Phone_no Major Prof Grade
Let F be a set of FD’s.
Definition 1: X → Y is inferred from F (or that F infers X → Y ), written in
F |= X→ Y
if any relation instance satisfying F must also satisfy X → Y .
Impossible to list every relation to verify if X → Y is inferred from F.
A set ρ of derivation rules are required, such that:
a X → Y is inferred from F according to Definition 1 iff it can be
derived using ρ.
9
Functional dependencies
Armstrong’s axioms (1974)
Notation: If X and Y are sets of attributes, we write XY for their union.
e.g. X = {A, B}, Y = {B, C}, XY = {A, B, C}
F1 (Reflexivity) If X ⊇ Y then X →Y .
F2 (Augmentation) {X → Y } |= XZ → Y Z.
F3 (Transitivity) {X → Y , Y → Z} |= X → Z.
F4 (Additivity) {X→ Y , X → Z} |= X → Y Z.
F5 (Projectivity) {X → Y Z} |= X → Y .
F6 (Pseudotransitivity) {X → Y , Y Z → W} |= XZ → W.
10
11
Example: Given F = {A → B,A → C,BC → D}, derive A → D:
1. A → B (given)
2. A → C (given)
3. A → BC (by F4, from 1 and 2)
4. BC → D (given)
5. A → D (by F3, from 3 and 4)
12
F4 (Additivity) {X→ Y , X → Z} |= X → Y Z.
F5 (Projectivity) {X → Y Z} |= X → Y .
F6 (Pseudotransitivity) {X → Y , Y Z → W} |= XZ → W.
In fact, F4, F5, and F6 can be derived from F1-F3.
Example: Prove {X→ Y , X → Z} |= X → Y Z.
1) X→ Y is given.
2) XX → XY (by F2); that is, X → XY
3) X → Z is given.
4) X Y → Y Z (by F2)
5) X → Y Z (by F3, 2) and 4))
We can prove that Armstrong’s axioms are sound and complete:
Sound: if F derives A →B by using Armstrong’s axioms, then F |= A →
B by Definition 1.
Complete: if F |= M → N by Definition 1, then F derives M → N by
using Armstrong’s axioms.
13
Armstrong’s axioms
Algorithm to Check a FD
Given F, how do we check if X →Y is in F+?
F+ denotes the smallest set of FD’s that
• contains F, and
• is closed under Armstrong’s axioms.
F+ is the closure of F.
14
15
F = { A → B, B → C, A → C }
F+ = {AB -> A, AB -> B, AB -> C, AC -> A, AC -> B,
AC -> C, ABC -> A, ABC -> B, ABC -> C, AB -> AB,
AB -> BC, AB -> AC, …….}
F+ always has an exponential size regarding |F|.
16
Too expensive to compute F+ to verify a membership.
Instead we can compute the closure X+ of X under F, X+ is the largest set of
attributes functionally determined by X.
It can be proven (using additivity) that
S1:
S2:
17
F = { A → B, BC → D, A → C }, compute {A}+
1st scan of F:
X+ := {A}
X+ := {A, B}
X+ := {A, B, C}
2nd scan of F:
X+ := {A, B, C, D }
3rd scan of F: no change, therefore the algorithm terminates.
{A}+ := {A, B, C, D }
Example:
X+ := X;
change := true;
while change do
begin
change := false;
for each FD W → Z in F do
begin
if (W ⊆ X+) and (Z X+) then do
begin
X+ := X+∪ Z;
change := true;
end
end
end
18
Algorithm to compute X+
Algorithm to Compute a Candidate Key
Given a relational schema R and a set F of functional dependencies on R.
A key X of R must have the property that X+ = R.
Algorithm to compute a candidate key
Step 1: Assign X a superkey in F.
Step 2: Iteratively remove attributes from X while retaining the property X+ =
R till no reduction on X.
The remaining X is a key.
19
20
R = {A, B, C, D} and F = { A → B, BC → D, A → C }
X = {A, B, C} if the left hand side of F is a super key.
A cannot be removed because {BC}+ = {B, C, D} ≠ R
B can be removed because {AC}+ = {A, B, C, D} = R
X = { A, C}
C can be further removed because {A}+ = {A, B, C, D}
X = {A}
Example: