Normalization Motivation and Anomalies

A relational schema is well-designed if every row represents one indivisible fact (or a coherent bundle of facts about a single entity) and no fact is stored more than once. When a schema violates this principle, the same real-world fact — e.g., "Professor Chen's office is Room 214" — gets copied into many tuples, one for each course Chen teaches, each student in those courses, or whatever grouping the badly designed table happens to use. This copying is called redundancy, and it is the direct cause of three classical failure modes. An update anomaly occurs when changing one instance of a fact requires finding and modifying every duplicate copy; missing even one copy leaves the database in a state that violates the intended (but unenforced) constraint that the fact is single-valued. An insertion anomaly occurs when the schema forces two logically independent facts into the same tuple, so that you cannot insert one fact without supplying a value — real or artificial null — for the other. For example, you cannot record that a new course exists until at least one student has enrolled in it, because the "course" fact and the "enrollment" fact are welded into a single row. A deletion anomaly is the mirror image: deleting the last tuple that happens to carry a fact (say, the last enrollment in a course) inadvertently erases the fact itself (that the course exists at all), even though the two facts are conceptually unrelated. The precise diagnostic tool is the Functional Dependency. Suppose relation $R$ has attributes $A, B, C$ and a functional dependency $A \to B$ where $A$ is not a candidate key of $R$. Then, whenever two tuples of $R$ agree on $A$, they are logically forced to agree on $B$ as well — yet nothing in the relational model prevents $R$ from storing many tuples with the same $A$ value (because $A$ is not a key), each carrying its own copy of $B$. This is redundancy incarnate, and every anomaly described above is a direct behavioral consequence of exactly this situation. Anomalies are therefore not a separate phenomenon from functional dependencies; they are functional dependencies made operationally visible.

The anomaly-detection procedure is less an "algorithm" in the classical sense and more a systematic audit: given a relation schema and its functional dependencies, determine whether every determinant is a superkey, and if not, trace out the concrete failure scenarios. This audit is exactly the reasoning step that precedes formal normalization (converting to First Normal Form and then applying the tests for 2NF and 3NF).

Step 1 — Identify all functional dependencies. List the FDs that hold in the relation, both the "obvious" business ones (e.g., `StudentID → StudentName`) and any transitive or multi-attribute ones (e.g., `CourseID → Department, Building`).

Step 2 — Determine the candidate keys. Compute the candidate key(s) of the relation using attribute-closure reasoning over the FD set. A relation may have one key, several keys, or (rarely, in pathological designs) none among the natural attributes.

Step 3 — Check each FD's determinant against the keys. For each FD $X \to Y$, ask: is $X$ a superkey of $R$? If yes, this FD cannot cause redundancy-based anomalies (each $X$ value appears in only one tuple, so $Y$ cannot be duplicated). If no, $X$ is a non-key determinant, and every value of $X$ can appear in multiple tuples, each dragging along its own copy of $Y$ — this is the anomaly trigger.

Step 4 — Enumerate the anomalies for each violating FD. For each non-key determinant $X \to Y$ found in Step 3, construct the three canonical scenarios:

• Update: two tuples share the same $X$ value; update $Y$ in one but not the other.
• Insert: you know a new $(X, Y)$ pair but have no value for the "other side" of the table (the part that is not functionally determined by $X$), so you cannot insert without a placeholder or null.
• Delete: deleting the sole tuple carrying a particular $X$-side fact also deletes the only surviving copy of an unrelated fact bundled into that tuple.

Step 5 — Confirm with a concrete instance. Anomalies are best demonstrated, not merely asserted: construct an actual table instance and show the exact update/insert/delete operation that breaks it. This is the "trace" that convinces a skeptical reader (and a rigorous designer) that the flaw is real and not hypothetical. ``` ALGORITHM DetectAnomalies(R, F) // R: set of attributes; F: set of functional dependencies over R keys := ComputeCandidateKeys(R, F) // via attribute-closure search violations := empty list for each FD (X -> Y) in F: if X is not a superkey of R (i.e., closure(X, F) != R): violations.append(X -> Y) if violations is empty: return "No redundancy-based anomalies: every determinant is a key." for each (X -> Y) in violations: report: "Update anomaly risk: rows sharing X = x1 each store a copy of Y; an update to one copy but not others yields an inconsistent DB." "Insertion anomaly risk: cannot insert a fact about X (or about attributes outside X union Y) without a full tuple, possibly forcing NULLs for unrelated attributes." "Deletion anomaly risk: deleting the last tuple with a given X value destroys any fact bundled in that tuple that was conceptually independent of X -> Y." return violations ``` The key computational step, `ComputeCandidateKeys`, itself reduces to repeatedly testing attribute-set closures — the same closure algorithm used to reason about Functional Dependencies in general: start from a candidate attribute set, repeatedly apply FDs whose left side is already covered, and check whether the closure reaches all attributes of $R$. ``` FUNCTION Closure(X, F) // X: set of attributes, F: set of FDs result := X changed := true while changed: changed := false for each (A -> B) in F: if A subsetOf result and B not subsetOf result: result := result union B changed := true return result ```

Detecting anomalies (the audit). Given a relation with $n$ attributes and $m$ functional dependencies, computing the closure of a single attribute set takes $O(m \cdot n)$ time in the naive implementation shown above (each pass over the $m$ FDs can add at least one attribute, and there are at most $n$ passes, with each pass costing $O(m)$ work to scan the FD list). Determining all candidate keys requires testing subsets of attributes, which is exponential in the worst case ($O(2^n)$), because there is no known polynomial algorithm for enumerating all minimal keys of an arbitrary relation — this is a genuinely hard combinatorial problem in general, though in practice schemas have few attributes with intuitive keys, so this exponential blowup rarely bites in classroom or industrial-scale designs. Checking a given determinant against a given key, however (the actual anomaly-detection audit in Step 3), is just one closure computation, i.e., $O(m \cdot n)$ per FD, and $O(m^2 n)$ to check all FDs in $F$ — polynomial and fast in practice.

Correctness of the anomaly claim. The claim "if $X \to Y$ holds and $X$ is not a superkey, then update/insert/delete anomalies exist" is not a heuristic — it follows from the definitions themselves. Update anomaly proof sketch. If $X$ is not a superkey, then by definition there exist (or can exist) two distinct tuples $t_1 \ne t_2$ with $t_1[X] = t_2[X]$ but $t_1 \ne t_2$ (otherwise $X$ would functionally determine every attribute, making it a superkey). Since $X \to Y$ holds, $t_1[Y] = t_2[Y]$ is required by the FD. Both tuples physically store their own copy of $Y$. An update operation that modifies $t_1[Y]$ without a corresponding modification to $t_2[Y]$ produces a database instance where $t_1[X] = t_2[X]$ but $t_1[Y] \ne t_2[Y]$ — this instance violates the functional dependency $X \to Y$, meaning the "current" logical fact about $X$'s corresponding $Y$-value is now ambiguous. Since ordinary `UPDATE` statements operate on one tuple (or an explicitly matched subset) at a time, and there is no schema-level constraint forcing all matching tuples to be updated together, this inconsistent state is reachable. $\blacksquare$ Insertion anomaly proof sketch. If the relation bundles attributes belonging to two independent entity sets, $E_1$ (attributes functionally dependent on key $K_1$) and $E_2$ (attributes functionally dependent on a different, non-overlapping key $K_2$) into a single relation $R(K_1, \dots, K_2, \dots)$, then a tuple can only exist in $R$ if both a $K_1$-fact and a $K_2$-fact are simultaneously known, because a row of $R$ requires values for all its declared attributes (or explicit nulls, which most schema designs and application logic try to avoid). Hence a legitimate, independently-existing $E_1$ fact cannot be inserted unless a — possibly nonexistent — $E_2$ fact is supplied too. $\blacksquare$ Deletion anomaly proof sketch. Symmetric to insertion: if the only remaining tuple carrying a fact about $E_2$ also happens to be the only tuple carrying a particular $E_1$ fact, deleting that tuple (because the $E_2$ fact, e.g., an enrollment, is no longer true) removes the $E_1$ fact (e.g., "this course exists") as a side effect, even though $E_1$ and $E_2$ are logically independent existence claims. $\blacksquare$

Honest tradeoffs. Eliminating anomalies by decomposing into smaller relations (the path toward First Normal Form and 2NF and 3NF) is not free: queries that used to read one row now require a join across multiple relations, costing extra I/O and CPU at query time. Over-normalization can also fragment data so finely that even simple reporting queries require many joins, hurting read-heavy analytical workloads. This is precisely why real systems sometimes deliberately denormalize after confirming the design is anomaly-free "on paper," accepting controlled, application-managed redundancy for performance, especially in read-mostly OLAP systems.

Consider a company schema: ``` Assignment(EmpID, EmpName, ProjID, ProjBudget, HoursWorked) ``` Business rules (functional dependencies):

• `EmpID → EmpName`
• `ProjID → ProjBudget`
• `{EmpID, ProjID} → HoursWorked`

Step 1 — Candidate key. Closure of `{EmpID, ProjID}` under these FDs reaches `EmpName` (via `EmpID → EmpName`), `ProjBudget` (via `ProjID → ProjBudget`), and `HoursWorked` directly — so `{EmpID, ProjID}` is a candidate key (its closure is the full attribute set, and no proper subset works, since `EmpID` alone can't derive `ProjBudget` and `ProjID` alone can't derive `EmpName`).

Step 2 — Check each FD's determinant. `EmpID → EmpName`: is `EmpID` a superkey? No — the key is `{EmpID, ProjID}`, and `EmpID` alone does not determine `HoursWorked` or `ProjBudget`. Violation. Likewise `ProjID → ProjBudget`: `ProjID` alone is not a superkey. Violation.

Step 3 — Instance and concrete anomalies.

• Update anomaly. Priya (`E1`) gets a legal name correction to "Priyanka." The application must find both rows with `EmpID = E1` and update `EmpName` in each. If it updates only the `P1` row, the table now claims `E1`'s name is simultaneously "Priyanka" and "Priya," violating `EmpID → EmpName` — the database is internally contradictory even though every individual `UPDATE` statement executed successfully.
• Insertion anomaly. HR wants to record a new employee, `E4`, "Sana," who has been hired but not yet assigned to any project. There is no `ProjID`/`ProjBudget`/`HoursWorked` to put in the row (this is not a foreign-key issue; the schema requires a project pairing to have a row at all), so either the insert is impossible without inventing a placeholder project, or `ProjID` must be null — which is often disallowed if `{EmpID, ProjID}` is the primary key and primary-key attributes cannot be null.
• Deletion anomaly. Project `P3` has exactly one worker, `Wei`, logging `0` hours so far. If Wei is reassigned and that row is deleted, the fact "Project P3 exists, with budget 30000" disappears entirely from the database, even though the project itself has not been cancelled — it simply has no current workers.

Step 4 — What the fix looks like (foreshadowing). Decomposing into `Employee(EmpID, EmpName)`, `Project(ProjID, ProjBudget)`, and `WorksOn(EmpID, ProjID, HoursWorked)` makes every determinant (`EmpID`, `ProjID`, `{EmpID, ProjID}`) a key of its own relation. Priya's name is now stored exactly once; a new employee can be inserted into `Employee` with no project row required; and deleting the last `WorksOn` tuple for `P3` leaves the `Project` row intact. This decomposition is exactly the mechanical procedure formalized by 2NF and 3NF.

The systematic study of anomalies emerged directly from Edgar F. Codd's foundational work on the relational model, where he first argued that update irregularities were a design defect, not an application bug, and that formal normal forms could eliminate them by construction.

Every production relational database — from a small SaaS billing system to a bank's core ledger — is designed by first identifying functional dependencies and then checking for exactly the anomalies described here, whether or not the designer names them explicitly. Schema migration tools, ORMs' auto-generated tables, and data-warehouse staging layers are all judged by whether they reintroduce update/insert/delete anomalies when engineers add convenience columns for performance. Database courses use this anomaly framework as the entire rationale for teaching 2NF and 3NF; without it, normal forms would look like arbitrary syntactic rules rather than principled fixes for observable operational bugs. Data-quality and master-data-management systems in industry — customer records, product catalogs, employee HR systems — exist specifically to combat the update-anomaly problem at scale, because uncontrolled redundancy across dozens of microservices reproduces exactly the single-table anomaly problem across an entire distributed system.

Ask the tutor: Can you show me how the decomposition into Employee/Project/WorksOn formally satisfies 2NF and 3NF, step by step?