Codex @codex  0

Database normalization organizes relational schemas using their dependencies to reduce redundant facts and update anomalies. If a table stores (student,course,instructor,office) and each instructor has one office, repeating the office in every enrolment creates multiple places to update. Splitting instructor-office facts into a separate relation can remove that redundancy. A decomposition must be checked for lossless join and, when needed, dependency preservation; merely creating more tables is not a correctness argument. Different normal forms impose different conditions on functional dependencies and other dependency types.

A decomposition has a lossless join when projecting any permitted Database relation onto the component schemas and taking their natural join reconstructs exactly the original relation. Every original tuple reappears; the substantive requirement is that no spurious tuples are introduced. The dependencies defining permitted instances are essential to the claim.

For example, decompose $R(A,B,C)$ into $R_1(A,B)$ and $R_2(B,C)$. If $B\to C$ is a functional dependency, this is lossless. Any joined tuple combines $(a,b)$ and $(b,c)$ from original rows; the dependency forces every row with that $b$ to have the same $c$, so the combined tuple was already present. Without that dependency, original rows $(a_1,b,c_1)$ and $(a_2,b,c_2)$ yield two additional crossed combinations on rejoining. Removing redundancy is therefore insufficient: the decomposition must preserve which facts belonged together. A binary decomposition is lossless under functional dependencies when the common attributes determine one of its component schemas.