Functional Dependencies and Boyce-Codd Normal Form
A functional dependency says one set of attributes determines another. Attribute closures identify superkeys; minimality identifies candidate keys. Boyce-Codd normal form requires a superkey on the left of every nontrivial functional dependency.
What a learner can do afterwards
- State functional dependencies from given rules and compute an attribute-set closure
- Find all candidate keys from a set of dependencies
- Decompose a table that violates Boyce-Codd form and check the join still recovers it
1 · Read
A functional dependency X -> Y says that any two allowed tuples agreeing on all attributes in X must agree on all attributes in Y. ID -> email permits different IDs to share an email, but one ID cannot have different emails. These are rules for every allowed state. Unique values in today's rows do not prove a dependency.
To compute X+, the closure of X, start with X. When every attribute on a dependency's left side is present, add its right-side attributes. Repeat until nothing changes. A set reaching the entire schema is a superkey. For a rule P,Q -> T, having P alone is insufficient: both P and Q must be present.
A candidate key is a minimal superkey: no proper subset is a superkey. Minimal does not mean shortest among all keys. To find all candidate keys, enumerate attribute subsets in increasing size and compute their closures. Record each superkey with no previously found key inside it. Skip supersets of recorded keys. Continue until all remaining subsets have been tested.
In R(P,Q,S,T), suppose the only given rules are P -> Q, Q -> P and Q -> S. No rule adds T, so every key needs T. T alone reaches nothing else. Adding P or Q reaches everything, giving candidate keys {P,T} and {Q,T}. Adding S alone cannot reach P or Q. Any larger set either lacks P and Q or contains one of the two keys.
X -> Y is trivial when every attribute in Y is already in X. Boyce-Codd normal form, or BCNF, requires X to be a superkey for every nontrivial dependency implied by the rules. The determinant need not be a minimal candidate key. Trivial dependencies do not violate BCNF. This is a stricter condition than third normal form.
For R(ID,email,dorm), suppose the only given rules are ID -> email and email -> dorm. ID+ reaches everything. Email+ reaches only email and dorm. Thus email -> dorm is nontrivial and starts from a non-superkey, violating BCNF. Even if email values are unique in today's rows, what follows from the rules stays the same.
For a violating X -> Y, make one relation containing X and Y. The other keeps X and every original attribute outside Y. Project the original relation onto each schema. Shared X determines the first piece, so joining the projections is lossless: exactly the original tuples return, with none missing or added. Here use R1(ID,email) and R2(email,dorm), joined on email. Recheck each piece for further BCNF violations.
Closure finds superkeys; minimality identifies candidate keys. BCNF requires superkeys for nontrivial dependencies. A lossless split rejoins to exactly the original relation.
This functional-dependency and BCNF lesson, question bank and flashcards were written for this dataset.
This reading about functional dependencies and lossless decomposition was independently written for this dataset.
More to read
Check the dependency and the reconstruction
Assignments(Locker,Zone,Supervisor) obeys Locker -> Zone and Zone -> Supervisor. Treat these as the only given rules, together with their consequences.
Locker reaches Zone and then Supervisor, so it is a superkey. Its only proper subset is empty, which reaches none of the attributes under these rules. Locker is therefore a candidate key.
Zone reaches Supervisor but cannot reach Locker. The nontrivial dependency Zone -> Supervisor violates BCNF because Zone is not a superkey. Distinct Zone values in one displayed sample would not establish a new dependency.
Project Assignments into LockerZones(Locker,Zone) and ZoneSupervisors(Zone,Supervisor). Join the projections on Zone. Every original tuple returns. No additional locker/supervisor combination can appear because each zone determines its supervisor. This decomposition is lossless for every state obeying the rules.
Successful reconstruction of one sample alone would not prove that guarantee. Here the dependency supplies the reason.
BCNF tests nontrivial dependencies and allows any superkey determinant. It does not require determinants to be minimal. After splitting, check the dependencies in each resulting relation. Losslessness and dependency preservation are separate properties: a lossless BCNF decomposition need not leave every original dependency checkable within one piece.
2 · Watch
En anglaisTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.