Relational Design: Redundancy, Anomalies & Functional Dependencies

Redundancy and Anomalies

A relational schema should reflect real-world structure, avoid storing the same fact twice, and stay easy to update correctly. When a schema fails at this, two related problems show up: redundancy and anomalies.

A Bad Schema

instructor_with_department(ID, name, salary, dept_name, building, budget)

• ID, name, salary — belong purely to the instructor, no repetition
• dept_name, building, budget — belong to the department

Since a department has many instructors, building and budget get copied once per instructor in that department. That repetition is redundancy — the same data item stored in multiple places.

Here’s what that looks like with actual rows:

ID	name	salary	dept_name	building	budget
101	Srinivasan	65000	Comp. Sci.	Taylor Hall	100000
102	Wu	90000	Finance	Painter Hall	120000
103	Gold	87000	Comp. Sci.	Taylor Hall	100000
104	Katz	75000	Comp. Sci.	Taylor Hall	100000

Notice Taylor Hall and 100000 repeat for every Comp. Sci. instructor — that’s the redundancy in action.

Anomalies

Redundancy causes anomalies — inconsistencies triggered by insert, delete, or update operations. Using the same table:

Anomaly	What Goes Wrong	On This Table
Insertion	Can’t add a record without unrelated data	To add a brand-new “Physics” department with no instructors yet, we can’t — there’s no row to put it in until a physics instructor is hired
Deletion	Deleting one record erases unrelated info	If Wu (row 102) resigns and we delete that row, we lose the fact that Finance’s building is Painter Hall and its budget is 120000 — nowhere else stores that
Update	One fact change needs many row updates	If Comp. Sci.’s budget rises to 110000, we must update rows 101, 103, and 104 — miss one, and the table now claims two different budgets for the same department

Why This Happens — and the Fix

dept_name uniquely decides building and budget (a department can’t have two budgets). This dependency is exactly what forces building/budget to repeat across instructor rows:

Dependency → Redundancy → Anomaly

The fix is to decompose the table so each fact is stored exactly once — e.g., split instructor_with_department into instructor(ID, name, salary, dept_name) and department(dept_name, building, budget). (Covered in detail under Lossless Join Decomposition.)

Removing redundancy this way is what makes a schema easier to maintain: updates touch a single row, deletions don’t silently destroy unrelated facts, and inserts don’t need unrelated data just to go through. This is the core motivation behind everything else in normalization theory.

---

Functional Dependencies

Definition

A functional dependency (FD) says: knowing the value of one set of attributes is enough to pin down another.

For relation schema \(R\), with \(\alpha \subseteq R\) and \(\beta \subseteq R\):

\[\alpha \rightarrow \beta\]

holds if, for any legal instance of \(R\), two tuples that agree on \(\alpha\) must also agree on \(\beta\):

\[t_1[\alpha] = t_2[\alpha] \implies t_1[\beta] = t_2[\beta]\]

Example: in instructor_with_department, we expect:

dept_name → building
dept_name → budget

since a department has exactly one building and one budget. We would not expect dept_name → salary — a department tells you nothing about one specific instructor’s salary.

Note: An FD only “holds” if it’s true for every legal instance of the schema, not just today’s data. If the current rows happen to satisfy name → ID by coincidence (no two instructors currently share a name), that doesn’t mean the FD genuinely holds.

Keys, Redefined Using FDs

• \(K\) is a superkey for \(R\) if and only if \(K \rightarrow R\) (K determines every attribute in R)
• \(K\) is a candidate key for \(R\) if and only if \(K \rightarrow R\), and no proper subset \(\alpha \subset K\) also satisfies \(\alpha \rightarrow R\) (K is minimal)

Trivial FDs

An FD \(\alpha \rightarrow \beta\) is trivial if \(\beta \subseteq \alpha\) — it’s automatically true for any relation and tells us nothing new.

ID, name → ID     -- trivial (ID is already on the left)
name → name       -- trivial