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.