Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Schema design and SQL practice
Page 6 of 20

Normalization: decompose without losing facts

Use functional dependencies to remove repeated facts, prove a binary decomposition is lossless, and choose deliberately between BCNF and dependency preservation.

Lesson briefSchema design and SQL practice · 8 h · 3 outcomes

Required knowledge

  • Functional dependencies, closure, superkeys, and candidate keys
  • Relation grain, joins, and foreign-key constraints

Learning outcomes

  • Identify a dependency that causes an update, insertion, or deletion anomaly at a stated relation grain.
  • Decompose a relation on a violating dependency and test the binary lossless-join criterion.
  • Explain when a 3NF design may be preferred to a stricter BCNF design.

Assessment target

Given a relation and functional dependencies, identify its key, choose a decomposition, show why it is lossless or lossy, and document a dependency-preservation trade-off.

Scope boundary

  • Multivalued dependencies, 4NF/5NF, and physical denormalization performance work are deferred.

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.

Code
skinparam linetype ortho
hide circle

class "TaskAllocation [Unnormalized]" as R {
* task_id
* service_name
* cluster_id
--
node_ip
port
}

note bottom of R
FD: (service_name, cluster_id) -> (node_ip, port)
Violates BCNF because determinant is NOT a superkey!
end note

class "ServiceDeployment [BCNF]" as O {
* service_name <<PK>>
* cluster_id <<PK>>
--
node_ip
port
}

class "TaskAssignment [BCNF]" as E {
* task_id <<PK>>
* service_name <<PK, FK>>
* cluster_id <<PK, FK>>
}

R -down-> O : "Lossless Decompose"
R -down-> E : "Lossless Decompose"
O "1" -right- "many" E : "(service_name, cluster_id)"
TaskAllocation [Unnormalized]task_idservice_namecluster_idnode_ipportFD: (service_name, cluster_id) ->(node_ip, port)Violates BCNF becausedeterminant is NOT a superkey!ServiceDeployment [BCNF]service_name «PK»cluster_id «PK»node_ipportTaskAssignment [BCNF]task_id «PK»service_name «PK, FK»cluster_id «PK, FK»Lossless DecomposeLossless Decompose(service_name,cluster_id)1many

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

(service_name,cluster_id)→(node_ip,port).(service\_name, cluster\_id) \to (node\_ip, port).
task_idservice_namecluster_idnode_ipport
t-101auth-svcus-east-110.0.1.58080
t-102auth-svcus-east-110.0.1.58080
t-103billing-svcus-east-110.0.1.128443

Worked example. (task_id, service_name, cluster_id) is a candidate key under the stated rules, yet node_ip and port depend only on (service_name, cluster_id). Moving auth-svc to another node requires editing rows t-101 and t-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?

HintExpand

The relation's grain begins with a task execution, but the deployment fact is about a cluster service.

Worked solutionExpand

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

FormUseful test
1NFEach attribute value is modeled as one value in its chosen domain; repeating groups are made explicit relations when they represent repeated facts.
2NFEvery non-prime attribute is fully dependent on every candidate key; no non-prime fact depends on a proper subset of a composite candidate key.
3NFFor every nontrivial X→AX \to A either XX is a superkey or AA is prime (belongs to a candidate key).
BCNFFor every nontrivial X→YX \to Y XX 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.

StartDependency appliedClosure after the stepMissing attribute
(service_name, cluster_id)(service_name, cluster_id) → (node_ip, port)(service_name, cluster_id, node_ip, port)task_id
HintExpand

In TaskAllocation, the service deployment determinant cannot add a task identifier.

Worked solutionExpand

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.

Proposition 2.2.1Binary lossless-join criterion

For a decomposition of relation RR into R1R_1 and R2R_2 the decomposition is lossless with respect to FF when

(R1∩R2)→R1or(R1∩R2)→R2(R_1 \cap R_2) \to R_1 \quad \text{or} \quad (R_1 \cap R_2) \to R_2

is implied by F+F^+ 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 of ServiceDeployment by the deployment dependency (service_name, cluster_id) -> (node_ip, port), so joining TaskAssignment back to ServiceDeployment does not invent extra task/deployment combinations. The decomposition is lossless under the stated rule.

Counterexample. Let R(A,B,C)R(A,B,C) contain (a1,b1,c1) and (a2,b1,c2). Decompose it into R1(A,B)R_1(A,B) and R2(B,C)R_2(B,C) without any dependency that makes B determine 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 R1R_1 R2R_2 their intersection, and the dependency that satisfies the criterion.

Verify the Lossless-Join Criterion

0 / 4 answered

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.

1
The lossless-join criterion is unconditionally satisfied provided the shared attribute contains no NULL values.
2
If the intersection fails to determine either component, the natural join may produce invalid spurious tuples.
3
A lossless decomposition strictly requires R1 and R2 to contain an identical number of stored tuples.
4
The decomposition is lossless if and only if the shared attribute set determines either R1 or R2 under F+.
HintExpand

Put the service-deployment relation on the side determined by the shared pair.

Worked solutionExpand

Take R1=ServiceDeployment(service_name,cluster_id,node_ip,port)R_1 = ServiceDeployment(service\_name, cluster\_id, node\_ip, port) and R2=TaskAssignment(task_id,service_name,cluster_id)R_2 = TaskAssignment(task\_id, service\_name, cluster\_id) Their intersection is (service_name,cluster_id)(service\_name, cluster\_id) and (service_name,cluster_id)→R1(service\_name, cluster\_id) \to R_1 follows from (service_name,cluster_id)→(node_ip,port)(service\_name, cluster\_id) \to (node\_ip, port) plus reflexivity. The criterion therefore proves the binary decomposition lossless.

BCNF is not the only goal

To decompose a schema SS on a BCNF-violating dependency X→YX \to Y form:

S1=X∪Y,S2=S−(Y−X).S_1 = X \cup Y, \qquad S_2 = S - (Y - X).

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 R(A,B,C)R(A,B,C) have F={AB→C,C→B}F = \{AB \to C, C \to B\} Candidate keys are AB and AC; all attributes are prime, so C→BC \to B satisfies 3NF but violates BCNF because C is not a superkey. Decomposing on C→BC \to B yields CB and AC. The original dependency AB→CAB \to C 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:

HintExpand

There is no automatic winner: name the anomaly risk and the cost of enforcement.

Worked solutionExpand

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.

Section Exercises

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

Verificationapplication

A relation schema TaskAllocation(task_id,service_name,cluster_id,node_ip,port)TaskAllocation(task\_id, service\_name, cluster\_id, node\_ip, port) is decomposed into ServiceDeployment(service_name,cluster_id,node_ip,port)ServiceDeployment(service\_name, cluster\_id, node\_ip, port) and TaskAssignment(task_id,service_name,cluster_id)TaskAssignment(task\_id, service\_name, cluster\_id) Using Proposition 2.2.1, verify whether this decomposition is lossless under functional dependency (service_name,cluster_id)→(node_ip,port)(service\_name, cluster\_id) \to (node\_ip, port)

HintExpand

Find the shared attributes between ServiceDeployment and TaskAssignment, then compute their attribute closure.

Worked solutionExpand

The intersection of attributes is ServiceDeployment∩TaskAssignment={service_name,cluster_id}ServiceDeployment \cap TaskAssignment = \{service\_name, cluster\_id\} Under the given functional dependency, {service_name,cluster_id}+={service_name,cluster_id,node_ip,port}\{service\_name, cluster\_id\}^+ = \{service\_name, cluster\_id, node\_ip, port\} which equals the entire attribute set of ServiceDeploymentServiceDeployment 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

Constructionapplication

Let R(A,B,C)R(A, B, C) be decomposed into R1(A,B)R_1(A, B) and R2(B,C)R_2(B, C) under empty dependency set F=∅F = \emptyset Construct a concrete 2-tuple instance of RR whose natural join R1⋈R2R_1 \bowtie R_2 produces spurious tuples, and identify the spurious combinations.

HintExpand

Choose two tuples that share a B value but have distinct A and C values.

Worked solutionExpand

Let R={(a1,b1,c1),(a2,b1,c2)}R = \{(a_1, b_1, c_1), (a_2, b_1, c_2)\} The projections are R1={(a1,b1),(a2,b1)}R_1 = \{(a_1, b_1), (a_2, b_1)\} and R2={(b1,c1),(b1,c2)}R_2 = \{(b_1, c_1), (b_1, c_2)\} Computing R1⋈R2R_1 \bowtie R_2 yields four tuples: {(a1,b1,c1),(a1,b1,c2),(a2,b1,c1),(a2,b1,c2)}\{(a_1, b_1, c_1), (a_1, b_1, c_2), (a_2, b_1, c_1), (a_2, b_1, c_2)\} The tuples (a1,b1,c2)(a_1, b_1, c_2) and (a2,b1,c1)(a_2, b_1, c_1) are spurious tuples not present in RR

Exercise 2.2.3: BCNF vs. 3NF Architectural Trade-Off Analysis

Descriptionrecall

Explain why schema Address(Street,City,Zip)Address(Street, City, Zip) with dependencies (Street,City)→Zip(Street, City) \to Zip and Zip→CityZip \to City is in 3NF but not BCNF. What engineering trade-off is made when deciding whether to decompose to BCNF?

HintExpand

Check candidate keys and whether every determinant is a superkey or every determined attribute is prime.

Worked solutionExpand

Candidate keys are (Street,City)(Street, City) and (Street,Zip)(Street, Zip) In Zip→CityZip \to City ZipZip is not a superkey, violating BCNF. However, CityCity is part of candidate key (Street,City)(Street, City) (i.e. prime), so it satisfies 3NF. Decomposing to BCNF produces (Zip,City)(Zip, City) and (Street,Zip)(Street, Zip) eliminating redundancy but destroying dependency preservation: enforcing (Street,City)→Zip(Street, City) \to Zip now requires an expensive join assertion across both tables.

Exercise 2.2.4: Lossless Normalization of Multi-Region Service Deployments

Generalisationtransfer

A microservice deployment schema is given by RegionalDeployment(task_id,service_name,cluster_id,region,endpoint_port,node_ip)RegionalDeployment(task\_id, service\_name, cluster\_id, region, endpoint\_port, node\_ip) with dependencies (service_name,cluster_id)→node_ip(service\_name, cluster\_id) \to node\_ip and (service_name,cluster_id,region)→endpoint_port(service\_name, cluster\_id, region) \to endpoint\_port Propose a BCNF decomposition into three relations with stated grains, candidate keys, and lossless join justifications.

HintExpand

Separate service placement facts, regional routing endpoint facts, and task executions iteratively.

Worked solutionExpand

Decompose into three relations:

  1. ServiceHost(service_name,cluster_id,node_ip)ServiceHost(service\_name, cluster\_id, node\_ip) with key (service_name,cluster_id)(service\_name, cluster\_id) and grain ‘one node assignment for a service cluster’.
  2. RegionalIngress(service_name,cluster_id,region,endpoint_port)RegionalIngress(service\_name, cluster\_id, region, endpoint\_port) with key (service_name,cluster_id,region)(service\_name, cluster\_id, region) and grain ‘one regional ingress port for a cluster service’.
  3. TaskExecution(task_id,service_name,cluster_id,region)TaskExecution(task\_id, service\_name, cluster\_id, region) with key (task_id,service_name,cluster_id,region)(task\_id, service\_name, cluster\_id, region) and grain ‘one task execution allocated to a regional service’. Each step is lossless: ServiceHostServiceHost intersects the remainder on (service_name,cluster_id)(service\_name, cluster\_id) which determines ServiceHostServiceHost RegionalIngressRegionalIngress intersects TaskExecutionTaskExecution on (service_name,cluster_id,region)(service\_name, cluster\_id, region) which is a candidate key of RegionalIngressRegionalIngress

References & Further Reading