Content

1. Overview
2. Functional Dependency
3. Attribute Set Closure
4. FD Closure
5. Decomposition
   1. Loss-less Join Decomposition
   2. Dependency Preserving
6. DB Normalization

Overview

• No information loss
• No redundancy
• Preserve functional dependencies in individual relations

Functional Dependency

Constraints between 2 sets of attributes in a relation from a database. Help check legality of DB.

X (determine attribute set) -> Y (dependent attribute set)
=> t1[X] = t2[X] => t1[Y] = t2[Y]

If t1 and t2 have the same value in X, then they also have the same value in Y.

Given a relationship R, a set of attributes X in R functionally determine another set of attributes Y also in R iff each X value maps with a single Y value.

• Cannot derive tighter FDs from looser ones

Attribute Set Closure

Closure of A (A+): set of attributes that can be functionally determined by A

• Only consider single attribute
• Use of A+
  • Super key testing: A is a superkey of R iff A+ contains all attributes of R
  • Check decomposition of relation is dependency preserving or not
  • Calculate FD closure F+ for database normalization

FD Closure

Closure of F (F+): set of all functional dependencies that can be implied by F

Decomposition

Loss-less Join Decomposition

Avoid information loss after decomposition.

• Decomposition of R into R1 & R2
  • R = R1 ∪ R2
• Loss-less join: R1 ⋈ R2 = R
  • R1 ∩ R2 -> R1 OR
  • R1 ∩ R2 -> R2
• Making loss-less join decompositions
  • Choose 1 FD A -> B, add R1(A, B)
  • Add R2(A, rest of R...)

Dependency Preserving

Avoid need to join the decomposed relations back to check functional dependencies when new tuples are inserted.

• Decomposition of R into Ri
  • R = R1 ∪ R2 ∪ ... ∪ Rn
• Dependency preserved:
  • (F1 ∪ F2 ∪ ... ∪ Fn)+ = F+, where Fi is the set of FDs in F+ that includes only attributes in Ri

DB Normalization

Reduce redundancy by ensuring the relations in Boyce-Codd Normal Form (BCNF).

• All FDs in F must form a key to aviod redundancy
• BCNF:
  • For all FDs in F+ of the form A -> B, where A ⊆ R and B ⊆ R, at least one of the following holds:
    • A -> B is trivial (B ⊆ A)
    • A is a superkey for R (A+ contains all attr of R)
• BCNF doesn't imply dependency preserving