Normalization is not a ritual of splitting tables. It asks whether one tuple stores several facts whose values can change independently. If it does, a dependency tells us where the repetition comes from and a lossless decomposition tells us whether we can separate the facts safely.
See the repeated fact before naming a normal form
Suppose one relation records both scheduled tasks and cluster deployment facts:
TaskAllocation(task_id, service_name, cluster_id, node_ip, port)
The grain is one task execution assigned to a deployed service on a cluster. The infrastructure scheduling rule says
task_id | service_name | cluster_id | node_ip | port |
|---|---|---|---|---|
| t-101 | auth-svc | us-east-1 | 10.0.1.5 | 8080 |
| t-102 | auth-svc | us-east-1 | 10.0.1.5 | 8080 |
| t-103 | billing-svc | us-east-1 | 10.0.1.12 | 8443 |
Worked example.
(task_id, service_name, cluster_id)is a candidate key under the stated rules, yetnode_ipandportdepend only on(service_name, cluster_id). Movingauth-svcto another node requires editing rowst-101andt-102. A missed edit creates an inconsistent state about the same service deployment.
Predict the anomaly
auth-svc migrates to node 10.0.1.9 before any task is scheduled. Which operation is awkward in this relation, and what data could be lost if the last billing-svc task finishes and its row is deleted?
HintExpandCollapse
The relation's grain begins with a task execution, but the deployment fact is about a cluster service.
Worked solutionExpandCollapse
Inserting the service deployment is awkward because there is no task_id to form a legal tuple. Deleting the last billing-svc task also deletes the only record of its assigned node and port. These are insertion and deletion anomalies; they reveal that a service deployment fact has been forced into a task-grain relation.
Use the normal forms as tests
| Form | Useful test |
|---|---|
| 1NF | Each attribute value is modeled as one value in its chosen domain; repeating groups are made explicit relations when they represent repeated facts. |
| 2NF | Every non-prime attribute is fully dependent on every candidate key; no non-prime fact depends on a proper subset of a composite candidate key. |
| 3NF | For every nontrivial either is a superkey or is prime (belongs to a candidate key). |
| BCNF | For every nontrivial is a superkey. |
In TaskAllocation, (service_name, cluster_id) is not a superkey because it does not determine task_id. Its dependency to node_ip, port therefore violates BCNF. Because those attributes are non-prime and depend on a proper subset of the composite key, it also violates 2NF.
Recheck the determinant
Trace the dependency inside the actual normalization example rather than changing fixtures.
| Start | Dependency applied | Closure after the step | Missing attribute |
|---|---|---|---|
(service_name, cluster_id) | (service_name, cluster_id) → (node_ip, port) | (service_name, cluster_id, node_ip, port) | task_id |
HintExpandCollapse
In TaskAllocation, the service deployment determinant cannot add a task identifier.
Worked solutionExpandCollapse
For TaskAllocation, (service_name, cluster_id)^+ adds node_ip and port, not task_id; it is not a superkey. That is exactly the BCNF failure. The functional-dependencies lesson’s explorer is the place to practice the general closure algorithm; this table keeps the proof tied to the relation being decomposed.
Decompose, then prove the join is lossless
Split the relation on the violating dependency:
ServiceDeployment(service_name, cluster_id, node_ip, port)
TaskAssignment(task_id, service_name, cluster_id)
ServiceDeployment has one tuple per service deployed to a cluster. TaskAssignment has one tuple per task scheduled on that deployment. A foreign key from (service_name, cluster_id) in TaskAssignment to the key of ServiceDeployment records the intended connection.
For a decomposition of relation into and the decomposition is lossless with respect to when
is implied by In words: the shared attributes determine one whole side.
For a decomposition of relation into and the decomposition is lossless with respect to when
is implied by In words: the shared attributes determine one whole side.
For every proposed split, verify a three-part evidence record: the two projected relations, their natural join on the shared attributes, and either (a) equality with the original legal instance under the stated dependencies or (b) a concrete spurious tuple. A lossless claim without the shared-attribute closure and this counterexample test is incomplete. The join test is a finite witness for the supplied instance; the criterion above is the dependency-level argument that generalizes it.
Worked example. The shared attributes are
(service_name, cluster_id). They determine all ofServiceDeploymentby the deployment dependency(service_name, cluster_id) -> (node_ip, port), so joiningTaskAssignmentback toServiceDeploymentdoes not invent extra task/deployment combinations. The decomposition is lossless under the stated rule.
Counterexample. Let contain
(a1,b1,c1)and(a2,b1,c2). Decompose it into and without any dependency that makesBdetermine either side. Joining the projections produces four tuples, including spurious(a1,b1,c2)and(a2,b1,c1). Splitting columns alone is not a proof.
Work the criterion
For the TaskAllocation split, name their intersection, and the dependency that satisfies the criterion.
Verify the Lossless-Join Criterion
For a relation R(A, B, C) decomposed into R1(A, B) and R2(B, C), evaluate which statements regarding join losslessness and functional dependencies are correct:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
HintExpandCollapse
Put the service-deployment relation on the side determined by the shared pair.
Worked solutionExpandCollapse
Take and Their intersection is and follows from plus reflexivity. The criterion therefore proves the binary decomposition lossless.
BCNF is not the only goal
To decompose a schema on a BCNF-violating dependency form:
BCNF removes every dependency whose determinant is not a superkey. It can sacrifice local enforcement of another dependency. 3NF is often chosen when lossless decomposition and dependency preservation matter more than removing every BCNF anomaly.
Worked example. Let have Candidate keys are
ABandAC; all attributes are prime, so satisfies 3NF but violates BCNF becauseCis not a superkey. Decomposing on yieldsCBandAC. The original dependency is not contained in either relation, so enforcing it may require a join or another design decision.
Choose the trade-off
Your team can enforce dependencies with single-relation checks during every write, but a BCNF decomposition would require checking one dependency across a join. What design question should be documented before choosing 3NF or BCNF?
The BCNF vs 3NF Architecture Decision
Consider schema Address(Street, City, Zip) with FDs: { (Street, City) -> Zip, Zip -> City }. Candidate keys are (Street, City) and (Street, Zip). Notice Zip -> City violates BCNF because Zip is not a superkey, but satisfies 3NF because City is prime. Decomposing into R1(Zip, City) and R2(Street, Zip) achieves BCNF.
Evaluate the trade-offs of decomposing Address into BCNF versus retaining 3NF:
HintExpandCollapse
There is no automatic winner: name the anomaly risk and the cost of enforcement.
Worked solutionExpandCollapse
Document the business cost of inconsistent redundant facts, the dependency that would no longer be locally enforceable under BCNF, the write path that must enforce it, and the expected query/join cost. Choose 3NF when preserving that dependency locally is important and its residual redundancy is understood; choose BCNF when the stronger anomaly protection outweighs that enforcement cost.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.2.1: Binary Decomposition Losslessness Verification
A relation schema is decomposed into and Using Proposition 2.2.1
HintExpandCollapse
Find the shared attributes between ServiceDeployment and TaskAssignment, then compute their attribute closure.
Worked solutionExpandCollapse
The intersection of attributes is Under the given functional dependency, which equals the entire attribute set of By the binary lossless-join criterion, because the intersection functionally determines one of the decomposed relations, the decomposition is guaranteed to be lossless.
Exercise 2.2.2: Spurious Tuple Construction on Arbitrary Split
Let be decomposed into and under empty dependency set Construct a concrete 2-tuple instance of whose natural join produces spurious tuples, and identify the spurious combinations.
HintExpandCollapse
Choose two tuples that share a B value but have distinct A and C values.
Worked solutionExpandCollapse
Let The projections are and Computing yields four tuples: The tuples and are spurious tuples not present in
Exercise 2.2.3: BCNF vs. 3NF Architectural Trade-Off Analysis
Explain why schema with dependencies and is in 3NF but not BCNF. What engineering trade-off is made when deciding whether to decompose to BCNF?
HintExpandCollapse
Check candidate keys and whether every determinant is a superkey or every determined attribute is prime.
Worked solutionExpandCollapse
Candidate keys are and In is not a superkey, violating BCNF. However, is part of candidate key (i.e. prime), so it satisfies 3NF. Decomposing to BCNF produces and eliminating redundancy but destroying dependency preservation: enforcing now requires an expensive join assertion across both tables.
Exercise 2.2.4: Lossless Normalization of Multi-Region Service Deployments
A microservice deployment schema is given by with dependencies and Propose a BCNF decomposition into three relations with stated grains, candidate keys, and lossless join justifications.
HintExpandCollapse
Separate service placement facts, regional routing endpoint facts, and task executions iteratively.
Worked solutionExpandCollapse
Decompose into three relations:
- with key and grain ‘one node assignment for a service cluster’.
- with key and grain ‘one regional ingress port for a cluster service’.
- with key and grain ‘one task execution allocated to a regional service’. Each step is lossless: intersects the remainder on which determines intersects on which is a candidate key of