Functional dependencies are a generally useful concept
data storage – compression
reasoning about queries – optimization

Example: College application info
Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)
Apply(SSN, cName, state, date, major)

suppose priority iss determined by GPA
if GPA > 3.8 priority = 1
3.3 < GPA <= 3.8 priority = 2 GPA <= 3.3 priority = 3 Any two tuples that have the same priority have the same GPA GPA -> priority

Functional Dependency
based on knowledge of real world
all instances of relation must adhere
A -> B

Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)

SSN -> sName
SSN -> address
HScode -> HSname, HScity
HSname, HScity -> HScode
SSN -> GPA
GPA -> priority
SSN -> priority

Apply(SSN, cName, state, date, major)
REAL WORLD CONSTRAINTS, below are stretches
cName -> date
SSN, cName -> major
SSN -> state

Functional Dependencies and Keys
relation with no duplicates
suppose that set of attributes A -> set of attributes B
cannot have two tuples with set of attributes A

Trivial Functional Dependency
A -> B if B is a subset of A

NonTrivial Functional Dependency
A -> B if B is not a subset of A

Completely nontrivial Functional Dependency
A -> B where A and B have no intersection

Rules for Functional Dependencies

Splitting Rule
If set of attributes A -> set of attributes B, then A -> B1 etc. If A values are the same, then B values must be the same
Cannot Split the Left-Hand Side
If set of attributes A -> set of attributes B
then A1 does not determine set of attributes B

Combining Rule
If set of attributes A -> B1, B2, Bn then set of attributes A -> set of attributes B

Trivial Dependency Rule
If A -> B then A -> A union B
If A -> B then A -> A intersect B

Transitive Rule
If A -> B and B -> C then A -> C

Closure of Attributes

Given relations, Functional Dependencies, set of attributes A
Find all B such that set of attributes A -> B
{A1, …, An}+

start with {A1, …, An }
repeat until no change:
if A -> B and and A in set
add B to set

Closure Example

Student(SSN, sName, address, HScode, HSname, HScity, GPA, priority)

SSN -> sName, address, GPA
HScode -> HSname, HScity
GPA -> priority

{SSN, HScode}+
{SSN, HScode, sName, address, GPA, priority, HSname, HScity}

functionally determines all attributes
therefore, A KEY

Closure and Keys

is set of attributes A a key for R?

compute the closure of A and if = all attributes then A is a key

How can we find all keys given a set of functional dependencies?

consider every subset of attributes

Specifying Functional Dependencies for a relation

given S1 and S2 sets of functional dependencies
S2 “follows from” S1 if every relation instance satisfying S1 also satisfies S2

S2 {SSN -> priority}
S1 {SSN -> GPA, GPA -> priority}

How to test?
Does A -> B follow from S?

1) compute closure of A based on S and check if B is in the set

2) Armstrong’s Axioms (not explained)

Specifying Functional Dependencies for a relation
Want: Minimal set of completely nontrivial FDs such that all FDs that hold on the relation follow from the dependencies in this set.