Databases

Lecture 6: Functional Dependencies and Normal Forms

• Lecture notes: chapter 5
• Book: chapter 3

Functional Dependencies

Definition

• Consider a relational schema R(a,b,c,d,e).
• What does a functional dependency a b → c d mean?
  • If two rows agree on the values of a and b, they should also agree on the values of c and d.
  • The values of a and b determine the values of c and d.

Functional Dependencies

Example 2 (from last time)

• Countries

  country	currency	value
  Finland	EUR	1.09
  Estonia	EUR	1.09
  Sweden	SEK	0.12

  Schema: Countries(country,currency,value)
• Functional Dependencies:
  • country→currency
    currency→value
• If country is the primary key then country→currency will be trivially satisfied.
• But how do we ensure that currency→value is satisfied?
  • The functional dependencies help us identify a problematic schema.

Functional Dependencies

Notation

• a → b c

  is the same as

  a → b a → c

  (a determines both b and c)

• but
• a b → c

  is not the same as

  a → c b → c

• a b → c means that a and b together determine c.

Properties of Functional Dependencies

Transitivity

• a → b b → c

  implies

  a → c

• A more complex example:
• a → c b → d c d → e

  implies

  a b → e

Properties of Functional Dependencies

Augmentation

a b → d

implies

a b c → d

Properties of Functional Dependencies

Reflexivity and trivial dependencies

• a → a

  an attribute always determines itself

• a b → a

  two or more attributes determine a subset of the attributes (reflexivity + augmentation)

Properties of Functional Dependencies

F^- Minimal basis (minimal cover)

• If F is a set of functional dependencies,
• then minimal basis F^- is a simplified but equivalent set of dependencies
  • no trivial dependencies
  • no dependencies that are implied by transitivity
  • no dependencies that are augmentations of other dependencies

Properties of Functional Dependencies

• Closure
  • X⁺: the set of attributes determined (directly or indirectly) by X.
• Superkey
  • X is a superkey if X⁺ includes all attributes in the relation.
• Key
  • A minimal superkey.
  • Candidates for primary keys.

Functional Dependencies

• Example 2 (continuing from last time)

  • Countries

    country	currency	value
    Finland	EUR	1.09
    Estonia	EUR	1.09
    Sweden	SEK	0.12

    Schema: Countries(country,currency,value)
• Functional Dependencies:
  • country→currency
    currency→value
    country→value (implied by transitivity)
• Closures:
  • country+ = {country,currency,value}
    currency+ = {currency,value}
    value+ = {value}
• Superkeys: {country}, {country,currency}, {country,value}, {country,currency,value}
• Key: {country}
• Non-trivial FD that is not a superkey: currency→value

Functional Dependencies

Split tables to avoid redundancy

• JustCountries country currency Finland EUR Estonia EUR Sweden SEK

  Currencies currency value EUR 1.09 SEK 0.12

• Countries = JustCountries ⨝ Currencies
• We can insert new info about which currency is used in a country without knowing the exchange rate.
• We can insert the exchange rate for a new currency without knowing which country it is used in.

Another Example (1)

• Consider a database to keep track of room bookings:

  Bookings

  code	name	day	timeslot	room	seats
  TDA357	Databaser	Tuesday	0	GD	236
  TDA357	Databaser	Tuesday	1	GD	236
  ERE033	Reglerteknik	Tuesday	0	HB4	224
  ERE033	Reglerteknik	Friday	0	GD	236

• Problems?

Another Example (2)

• Consider a database to keep track of room bookings:

  Bookings

  code	name	day	timeslot	room	seats
  TDA357	Databaser	Tuesday	0	GD	236
  TDA357	Databaser	Tuesday	1	GD	236
  ERE033	Reglerteknik	Tuesday	0	HB4	224
  ERE033	Reglerteknik	Friday	0	GD	236

• There is some redundancy
  • For example, the number of seats in GD is mentioned 3 times.
• Problems:
  • Insert anomaly: we can't insert the number of seats in a room if there is no booking in that room
  • Update anomaly: we get an inconsistency if the number of seats in GD is changed in only one of the rows.
  • Delete anomaly: the number of seats in a room is lost of all bookings in that room are removed.

Another Example (2)

A better design

• Courses code name TDA357 Databases ERE033 Reglerteknik	Rooms room seats GD 236 HB4 224
  Bookings code day timeslot room TDA357 Tuesday 0 GD TDA357 Tuesday 1 GD ERE033 Tuesday 0 HB4 ERE033 Friday 0 GD

• Courses ⨝ Bookings ⨝ Rooms gives us the original table
• This is probably what we would get if we started from an Entity-Relationship model
  • What would the E-R diagram look like?
  • What are the primary keys in these tables?

Database design using FDs

Another way detect and fix the problems with the original table

• Consider the functional dependencies between the attributes.
• This will reveal that the table is not in a normal form.
• Split it into smaller tables that are in a normal form.

Normal Forms

• 1NF: First Normal Form (1970)
• 2NF: Second Normal Form (1971)
• 3NF: Third Normal Form (1971)
• BCNF (3½NF): Boyce-Codd Normal Form (1974)
• 4NF: Fourth Normal Form (1977)
• …

1NF: First Normal Form

• Requirement: Only atomic values in the tables
• 1NF id name phone program 1 Alice 1234, 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

  ⟹

  1NF id name phone program 1 Alice 1234 TKDAT 1 Alice 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

1NF: First Normal Form

• Another way to convert to 1NF
• 1NF id name phone program 1 Alice 1234, 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

  ⟹

  1NF id name phone1 phone2 program 1 Alice 1234 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

Purpose of Normal Forms (beyond 1NF)

• To free the collection of relations from undesirable insertion, update and deletion dependencies.
• To reduce the need for restructuring the collection of relations, as new types of data are introduced, and thus increase the life span of application programs.
• To make the relational model more informative to users.
• To make the collection of relations neutral to the query statistics, where these statistics are liable to change as time goes by.
  • 
    (Codd, E.F.: "Further Normalization of the Data Base Relational Model")

2NF: Second Normal Form

• Requirement: 1NF + No Partial Dependencies
• Example: CompletedCourses(student,course,grade,credits)
• CompletedCourses (2NF)

  student	course	grade	credits
  1	C1	G	5.0
  2	C2	VG	7.5
  1	C4	G	9.0
  4	C3	G	5.0
  4	C1	VG	5.0
  2	C5	G	9.0

• Functional Dependencies:
  • student,course→grade
    course→credits (partial dependency!)

2NF: Second Normal Form

Convert to 2NF by splitting the table

• Grades(student,course,grade)
Credits(cource,credits)
• Grades (2NF) student course grade 1 C1 G 2 C2 VG 1 C4 G 4 C3 G 4 C1 VG 2 C5 G

  Credits (2NF) course credits C1 5.0 C2 7.5 C3 5.0 C4 9.0 C5 9.0

• CompletedCourses = Grades ⨝ Credits

3NF: Third Normal Form

• Requirement: 2NF + no transitive dependencies from the primary key to non-key attributes
• HomeAddress (3NF)

  id	name	postcode	city
  1	Alice	41279	Göteborg
  2	Bob	43168	Mölndal
  3	Carl	41279	Göteborg

• Functional dependencies:
  • id→name,postcode,city
    postcode→city
• Transitive dependency: id→postcode→city

3NF: Third Normal Form

Convert to 3NF by splitting the table

• HomeCodes (3NF) id name postcode 1 Alice 41296 2 Bob 43168 3 Carl 41296

  PostcodeCities (3NF) postcode city 41279 Göteborg 43168 Mölndal

• HomeAddress = HomeCodes ⨝ PostcodeCities

About 3NF…

Does it avoid all problems with redundancies?

• Consider the following schema and functional dependencies:
• Postcodes(city,street,postcode)
  • city street → postcode
    postcode → city
  • {city,street} is a key, since {city,street}⁺ = {city,street,postcode}
• Is it in 2NF? Is it free from partial dependencies? Yes!
• Is it in 3NF? Is it free from transitive dependencies from the key to non-key attributes? Yes!

About 3NF…

Example

• Postcodes (3NF)

  city	street	postcode
  Göteborg	Framnäsgatan	41264
  Göteborg	Rännvägen	41258
  Göteborg	Hörsalsvägen	41258
  Göteborg	Barnhusgatan	41102
  Stockholm	Barnhusgatan	11123

• The same city,postcode pair can appear many times.
• But postcode → city, so there is some redundancy.

BCNF: Boyce-Codd Normal Form

• Requirement: for each non-trivial functional dependency X→Y, X is a superkey
• BNFC ⇒ 2NF, 3NF

BCNF Normalisation Algorithm

To normalise a relation R(S)

• Find a non-trivial FD X→y such that X⁺ ≠ S (X⁺ is not a superkey)
• If there is no such FD, R is already in BCNF, so we are done.
• Otherwise, split R into R₁(X⁺) and R₂(X ∪ (S – X⁺)).
• Repeat the procedure for R₁ and R₂.

BCNF Normalisation Algorithm

Example

• Postcodes(city,street,postcode)
  • city street → postcode
    postcode → city
• Pick postcode → city:
  • postcode⁺ = {postcode,city} ≠ {city,street,postcode}
  • A BNFC violation
    • Split into {postcode,city} and {postcode,street}
    • These have no BNFC violations.

BCNF Normalisation Algorithm → Example

• Streets (BCNF) street postcode Framnäsgatan 41264 Rännvägen 41258 Hörsalsvägen 41258 Barnhusgatan 41102 Barnhusgatan 11123

  Cities (BCNF) city postcode Göteborg 41264 Göteborg 41258 Göteborg 41102 Stockholm 11123

• Postcodes = Streets ⨝ Cities
• The city,postcode duplications are avoided, but there are other problems…

Another BCNF Normalisation example

• Bookings(code,name,day,timeslot,room,seats)
  • code → name
    room → seats
    day timesslot room → code
    day timeslot code → room
• …

Multivalued Dependencies (MVDs)

• Returning to the 1NF example:
• 1NF id name phone program 1 Alice 1234, 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

  ⟹

  1NF id name phone program 1 Alice 1234 TKDAT 1 Alice 1235 TKDAT 2 Bob 4567 TKITE 3 Carl 9870 MPSC

• In some sense, id still determines the phone numbers, even if there is more than one.
• This is called a multivalued dependency: id↠phone

Multivalued Dependencies (MVDs)

Another Example

• Courses

  course	book	author	teacher
  Databases	DTCB	Ullman	Jonas
  Databases	DTCB	Ullman	Thomas
  Reglerteknik	RTB 1	Author1	Lennart
  Reglerteknik	RTB 2	Author2	Lennart

  • course↠teacher
  • course↠book author

Properties of Multivalued Dependencies

• Every FD is also a MVD.
• MVDs do not have the same properties as normal FDs.
  • X↠Y Z can not be split into X↠Y and X↠Z
  • Complement: if X↠Y, then X↠S–Y
  • Transitivity: if X↠Y and if Y↠Z then X↠Z–Y
  • …

4NF: Fourth Normal Form

• Requirement: BCNF + for all non-trivial MVDs X↠Y, X is a superkey

4NF Normalisation algorithm

To normalise a relation R(S)

• Find a non-trivial MVD X↠Y such that X⁺ is not a superkey.
• If there is no such MVD, R is already in 4NF, so we are done.
• Otherwise, split R into R₁(X ∪ Y) and R₂(S–Y).
• Repeat the procedure for R₁ and R₂.

Good to know

• A relational schema obtained from an E-R diagram is in 3NF.
  • And if there are no additional functional dependencies, it is also in BCNF.
• Sometimes BCNF normalisation causes problems, so using 3NF can be the better choice.
• The lecture notes describe a 3NF synthesis algorithm that starts from a the minimal basis of a set FDs.

Database Design workflow

• Start by creating an E-R model.
• Obtain a relational schema from the E-R model.
• Identify additional functional dependencies.
  • Use them to add UNIQUE constraints.
  • Apply BNCF decomposition when appropriate.

Further reading

• Jonas Duregård's slides
• Normal Forms in DBMS (geeksforgeeks.org)
• Database normalization (Wikipedia)
• Multivalued dependency (Wikipedia)