Recall
DB Design
1. Functional Dependencies
Week 9: Worksheet
CSC 343 Winter 2021 University of Toronto Mississauga
March 25/26, 2021
• How do you identify FDs?
– Domain knowledge! Note: DBMSs can’t identify (nor optimize) FDs for you!
• Trivial FDs, Splitting/Combining
• Armstrong’s Axioms (Reflexivity, Augmentation, Transitivity, Union, Decomposition) • Closure, Minimal Basis
2. Schema Decomposition
• Avoiding Anomalies
• Lossless Join Decomposition • Dependency Preservation
3. Normalization
• 1NF, 2NF, 3NF, BCNF, … and many more 🙂
• 1NF – no multi-valued attributes.
• 2NF – in 1NF and non-prime attributes depend the proper subset of any candidate key.
– Consider a non-prime attribute A, then there exists a FD X s.t. X → A, and X is a candidate key.
• 3NF – in 2NF and non-prime attributes depend only on candidate keys.
– ConsideraFDX→A,eitherXisasuperkeyorAisprime(partofakey). – Lossless Join and Dependency Preserving.
• BCNF–in3NFandforeveryFDX→A,Xisasuperkey. – Stricter version of 3NF, also know as 3.5NF.
– If X → A is a non-trivial FD that holds in a relation and X is a superkey. – Lossless Join and Anomaly Free.
1
Task I
Consider a relation R with a set of attributes α = {A, B, C, D, E, F } and the set of Functional Dependencies F = { A → BC, B → E, C → BD, D → A, E → F, F → BE}
(a) Compute the closure of each attribute.
(b) Find all candidate keys (i.e., minimal keys) of relation R.
Solution:
(a) A+ →BCEDFA B+ →EFB
C+ →BDEAFC
D+ → AD … you have A so it′s closed E+ →FBE
F+ →BEF
(b) A,C,andD.
2
Task II
Consider a relation R with a set of attributes α = {A, B, C, D, E} and the set of Functional Dependencies F = { A → B, BC → E, ED → A}
(a) Is R in 3NF? (b) Is R in BCNF?
HINT 1: Compute the keys first, then solve (a) and (b). HINT 2: Define 3NF and BCNF after HINT 1.
Solution:
(hint 1) The candidate keys are: CDE, ACD, and BCD.
(a) R is in 3NF because A, B, and E are all ‘part of’ keys.
(b) R is not in BCNF because none of {A, B, C, D, E} contain a key.
3