Redundancy and update, insert, delete anomalies

An enrolment sheet that copies each instructor’s office into every enrolment row stores Iyer’s office in five rows, so one move to a new room has to change five rows. Storing a fact more than once is redundancyredundancy: Storing the same fact more than once, in several rows or tables, so that every copy has to change whenever the fact changes., and it causes three kinds of trouble, called anomalies: an update that leaves copies disagreeing, a fact that cannot be stored until an unrelated one exists, and a delete that takes an unrelated fact with it.

The cure is to split the table so that each fact is stored once, and the split needs care too: a careless one joins back into rows that never existed. This lesson runs all three anomalies on a real SQLite table, joins a careless split back into 13 rows from 8 and a careful one into exactly 8, and ends with the three goals that the rest of this module turns into rules.

One sheet stores the same office five times

Many college offices keep one big sheet of enrolments: a row for each student in each course, with everything about the course and its instructor copied into the row. Here it is as an SQLite table. Its key is the pair (roll_no, course), because a student takes a course once. The second query counts how many rows repeat each instructor’s office:

-- One table for students, courses, instructors and grades: the enrolment sheet.
CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

SELECT * FROM sheet ORDER BY roll_no, course;

-- How many rows repeat each fact about an instructor's office?
SELECT instructor, office, count(*) AS copies
FROM sheet GROUP BY instructor, office ORDER BY copies DESC;

┌─────────┬─────────┬────────┬───────────┬────────────┬────────┬───────┐
│ roll_no │ student │ course │   title   │ instructor │ office │ grade │
├─────────┼─────────┼────────┼───────────┼────────────┼────────┼───────┤
│ 101     │ Aarav   │ CS301  │ Databases │ Iyer       │ B-204  │ A     │
│ 101     │ Aarav   │ CS302  │ Systems   │ Sen        │ C-110  │ B     │
│ 102     │ Diya    │ CS301  │ Databases │ Iyer       │ B-204  │ A     │
│ 102     │ Diya    │ CS303  │ Networks  │ Iyer       │ B-204  │ B     │
│ 103     │ Kabir   │ CS301  │ Databases │ Iyer       │ B-204  │ B     │
│ 103     │ Kabir   │ CS302  │ Systems   │ Sen        │ C-110  │ C     │
│ 104     │ Meera   │ CS303  │ Networks  │ Iyer       │ B-204  │ A     │
│ 104     │ Meera   │ CS304  │ Compilers │ Khan       │ A-015  │ A     │
└─────────┴─────────┴────────┴───────────┴────────────┴────────┴───────┘
┌────────────┬────────┬────────┐
│ instructor │ office │ copies │
├────────────┼────────┼────────┤
│ Iyer       │ B-204  │ 5      │
│ Sen        │ C-110  │ 2      │
│ Khan       │ A-015  │ 1      │
└────────────┴────────┴────────┘

Count the copies. Iyer’s office, B-204, is written in five rows, because Iyer teaches two of the courses those rows mention. The title of CS301 is written three times, once for each student in it. Each row holds four kinds of fact: who the student is, what the course is called and who teaches it, where that instructor sits, and the student’s grade. Only the grade is a fact about the whole key. The student’s name depends on roll_no alone and the title on course alone, while the office depends on the instructor, who is not part of the key at all. Every one of those facts is repeated in each row that mentions its subject.

An update that changes three of five copies

Iyer moves to room B-310. The college office updates the rows it is looking at, those of CS301, and stops there. Step through what the update does to the five rows that name Iyer:

The program runs the same update on the whole sheet and then asks where Iyer sits:

CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

-- Iyer moves to room B-310. The update names one course, so it changes
-- only the rows of that course.
UPDATE sheet SET office = 'B-310' WHERE course = 'CS301';

-- One instructor, two offices: the copies now disagree.
SELECT instructor, office, count(*) AS rows_saying_so
FROM sheet WHERE instructor = 'Iyer'
GROUP BY instructor, office ORDER BY office;

┌────────────┬────────┬────────────────┐
│ instructor │ office │ rows_saying_so │
├────────────┼────────┼────────────────┤
│ Iyer       │ B-204  │ 2              │
│ Iyer       │ B-310  │ 3              │
└────────────┴────────┴────────────────┘

The database did exactly what it was told. It changed the three rows that name CS301 and left the two rows of CS303 alone, so the sheet now says that Iyer sits in two rooms at once. No constraint was broken, because the table has no rule that ties an instructor to a single office, and it cannot have one while the office is copied into every enrolment. This is an update anomalyupdate anomaly: A fact copied into many rows has to be changed in all of them; changing only some leaves copies that disagree.. Every program and every person who changes an office must remember to change all the copies, and the cost of forgetting is a table that contradicts itself, whose reports disagree depending on which row they read.

You can look for this damage with a query that groups the rows by instructor and counts the different offices in each group. The exercise at the end of the lesson asks you to write it.

A new course has nowhere to go

The department adds a course for the next term, CS405 Machine Learning, to be taught by Rao in room D-002. Nobody has enrolled yet. The sheet has no place for a course without a student, because every row needs a roll number:

CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

-- A new course, CS405 Machine Learning, will be taught by Rao in D-002.
-- Nobody has enrolled yet, so there is no roll number to give.
INSERT INTO sheet (course, title, instructor, office)
VALUES ('CS405', 'Machine Learning', 'Rao', 'D-002');

SELECT count(*) AS rows_about_cs405 FROM sheet WHERE course = 'CS405';

┌──────────────────┐
│ rows_about_cs405 │
├──────────────────┤
│ 0                │
└──────────────────┘

Runtime error near line 16: NOT NULL constraint failed: sheet.roll_no

SQLite refuses the row because roll_no is part of the primary key and is declared NOT NULL. That declaration matters in SQLite. The SQL standard says that a primary key column can never be NULL, but SQLite, to stay compatible with early versions, accepts NULL in most primary key columns unless they are declared NOT NULL (SQLite: CREATE TABLE). PostgreSQL follows the standard: the values of a primary key must be unique and not null (PostgreSQL 18: constraints). Without the NOT NULL, SQLite would have stored the course next to an empty roll number, a fake enrolment that every count of students would then have to skip. Either way the design forces a bad choice, an insertion anomalyinsertion anomaly: A fact that cannot be stored until an unrelated fact exists to share its row, such as a new course with no student enrolled yet.: leave the fact out, or record it next to an invented one.

Deleting one enrolment deletes a course

Meera drops Compilers. Hers was the only enrolment in CS304, so deleting it deletes more than an enrolment:

CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

-- Meera drops Compilers. Hers was the only row for CS304.
DELETE FROM sheet WHERE roll_no = 104 AND course = 'CS304';

-- The course's title, its instructor and Khan's office went with it.
SELECT count(*) AS rows_about_cs304 FROM sheet WHERE course = 'CS304';
SELECT count(*) AS rows_about_khan FROM sheet WHERE instructor = 'Khan';

┌──────────────────┐
│ rows_about_cs304 │
├──────────────────┤
│ 0                │
└──────────────────┘
┌─────────────────┐
│ rows_about_khan │
├─────────────────┤
│ 0               │
└─────────────────┘

After the delete, the database no longer knows that CS304 exists, what it is called, who teaches it or where Khan sits, although the statement mentioned none of that: a deletion anomalydeletion anomaly: Deleting one fact also removes another that was stored only in the same rows, such as a course lost with its last enrolment.. It and the insertion anomaly are two sides of one fault. Step through both, the refused insert on the left and the delete on the right:

Facts about courses and instructors live only inside enrolment rows, so they exist only while some enrolment carries them. These faults are as old as the relational model. E. F. Codd’s paper that introduced it, A Relational Model of Data for Large Shared Data Banks, already treats redundancy and the consistency of stored data as central problems, and William Kent’s A Simple Guide to Five Normal Forms in Relational Database Theory shows the same faults with a warehouse address kept in records about parts.

A careless split joins back into 13 rows

The fix is to give each fact a table of its own, keyed by whatever determines it. Before doing that properly, look at a split that seems reasonable and is not. It keeps each enrolment with its instructor, and moves the office and the course title into a table of staff, looked up by instructor:

CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

-- A tempting split: keep each enrolment with its instructor, and look up
-- the office and the course title by instructor.
CREATE TABLE enrolled AS SELECT roll_no, student, course, instructor, grade FROM sheet;
CREATE TABLE staff AS SELECT DISTINCT instructor, office, title FROM sheet;

-- Join them back on the only shared column, instructor.
CREATE TABLE rejoined AS SELECT * FROM enrolled NATURAL JOIN staff;

SELECT (SELECT count(*) FROM sheet) AS original_rows,
       (SELECT count(*) FROM rejoined) AS rows_after_join;

-- Rows the join invented: courses paired with a title they never had.
SELECT roll_no, course, title FROM rejoined
EXCEPT
SELECT roll_no, course, title FROM sheet
ORDER BY roll_no, course;

┌───────────────┬─────────────────┐
│ original_rows │ rows_after_join │
├───────────────┼─────────────────┤
│ 8             │ 13              │
└───────────────┴─────────────────┘
┌─────────┬────────┬───────────┐
│ roll_no │ course │   title   │
├─────────┼────────┼───────────┤
│ 101     │ CS301  │ Networks  │
│ 102     │ CS301  │ Networks  │
│ 102     │ CS303  │ Databases │
│ 103     │ CS301  │ Networks  │
│ 104     │ CS303  │ Databases │
└─────────┴────────┴───────────┘

The join returns 13 rows from 8. All 8 original rows are among them, and 5 more pair an enrolment with the wrong title. Step through the join for the five enrolments in Iyer’s courses to see where the extra rows come from:

Rows that a join produces but the original table never had are called spurious tuplesspurious tuple: A row that the join of a split's pieces returns although the original table never held it., and a split that produces them is a lossy decompositionlossy decomposition: A split whose pieces join back into rows the original table never had, so the true rows can no longer be told apart.. The name sounds odd for a split that gains rows, but what it loses is information: from the two smaller tables, nobody can tell which of the 13 rows are true.

The cause is the column the two tables share. SQLite’s NATURAL JOIN matches rows on every column that appears in both inputs (SQLite: SELECT), which here is instructor, and the instructor does not determine the title, because Iyer teaches two courses. Spreadsheets and data tools behave the same way: joining two exported files on a column that is not unique in either file multiplies rows.

Four tables join back into the same 8 rows

Now the careful split. Each fact goes into a table keyed by what determines it: a student’s name by roll number, a course’s title and instructor by course, an instructor’s office by instructor, and a grade by the pair (roll_no, course). The figure shows the four tables and the key that each join follows:

The program builds the four tables from the sheet, joins them back, and moves Iyer once more:

CREATE TABLE sheet (
  roll_no INTEGER NOT NULL, student TEXT, course TEXT NOT NULL, title TEXT,
  instructor TEXT, office TEXT, grade TEXT, PRIMARY KEY (roll_no, course));
INSERT INTO sheet VALUES
  (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
  (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
  (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
  (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
  (103, 'Kabir', 'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
  (104, 'Meera', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
  (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');

-- Each fact in a table of its own, keyed by what determines it.
CREATE TABLE students AS SELECT DISTINCT roll_no, student FROM sheet;
CREATE TABLE courses AS SELECT DISTINCT course, title, instructor FROM sheet;
CREATE TABLE offices AS SELECT DISTINCT instructor, office FROM sheet;
CREATE TABLE enrolments AS SELECT roll_no, course, grade FROM sheet;

CREATE TABLE rejoined AS
SELECT roll_no, student, course, title, instructor, office, grade
FROM enrolments NATURAL JOIN students NATURAL JOIN courses NATURAL JOIN offices;

SELECT (SELECT count(*) FROM sheet) AS original_rows,
       (SELECT count(*) FROM rejoined) AS rows_after_join,
       (SELECT count(*) FROM (SELECT * FROM rejoined EXCEPT SELECT * FROM sheet)) AS invented,
       (SELECT count(*) FROM (SELECT * FROM sheet EXCEPT SELECT * FROM rejoined)) AS lost;

-- Iyer's move is now one change to one row.
UPDATE offices SET office = 'B-310' WHERE instructor = 'Iyer';
SELECT changes() AS rows_changed;

┌───────────────┬─────────────────┬──────────┬──────┐
│ original_rows │ rows_after_join │ invented │ lost │
├───────────────┼─────────────────┼──────────┼──────┤
│ 8             │ 8               │ 0        │ 0    │
└───────────────┴─────────────────┴──────────┴──────┘
┌──────────────┐
│ rows_changed │
├──────────────┤
│ 1            │
└──────────────┘

The join returns exactly the 8 original rows, with none invented and none lost. Each step of the join matches on a column that is the key of the table it brings in, roll_no for students, course for courses and instructor for offices, so every enrolment finds exactly one partner in each table. The anomalies are gone too. Iyer’s move changes one row, a course without students is simply a row in courses, and dropping the last enrolment in CS304 leaves CS304 in courses and Khan’s room in offices.

For a split of a table into two pieces there is a simple test: the split is a lossless decompositionlossless decomposition: A split whose pieces always join back into exactly the rows of the original table, none invented and none lost. when the columns the pieces share determine every column of one of the pieces, which means the shared columns are a key of that piece. The careless split fails it, because instructor is a key of neither enrolled nor staff. A later lesson of this track proves the test and gives the general one for any number of pieces, which comes from the theory of joins of Aho, Beeri and Ullman (The Theory of Joins in Relational Databases).

Schema refinement has three goals

Splitting tables to remove redundancy is called normalisationnormalisation: Refining a schema by splitting tables so that each fact is stored once, keyed by what determines it, without losing rows or rules., and the next lessons of this module make it precise. A good refinement aims for three things at once, and this lesson has already met each of them:

A fact stored once is changed in one place, recorded without an unrelated fact and deleted only on purpose, so the first goal removes all three anomalies. The first goal says what to remove; the other two say what a split must not break, and later lessons show a case where they pull against each other. Dependency preservationdependency preservation: A split preserves dependencies when every functional dependency of the original table can still be checked within the pieces, without a join. More in “Lossless joins and dependency preservation” matters because a rule that spans two tables needs a join, or a trigger, on every insert to stay true. The rules that say which attribute determines which are called functional dependenciesfunctional dependency: A rule X -> Y on a relation: any two rows that have the same values for the attributes X also have the same values for Y. More in “Functional dependencies and Armstrong's axioms”, the subject of the next lesson.

Normalisation is a tool, not a goal in itself: some systems keep copies on purpose, for speed or to record history, and accept the work of keeping them in step. What matters is that the copy is a decision, never an accident.

Practise: find the copies that disagree

The exercise gives you a sheet after a careless update and asks for every instructor whose rows name more than one office. Its sample tests run your query on three small sheets in your browser:

-- Every instructor whose rows name more than one office, and how many.
SELECT instructor, count(*) AS offices
FROM sheet;

# Sample tests: each one builds a small sheet, runs your query on it and compares the rows it returns.
tests:
  - name: finds the instructor whose office was updated in only some rows
    setup: |
      CREATE TABLE sheet (roll_no INTEGER, student TEXT, course TEXT, title TEXT, instructor TEXT, office TEXT, grade TEXT);
      INSERT INTO sheet VALUES
        (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-310', 'A'),
        (101, 'Aarav', 'CS302', 'Systems',   'Sen',  'C-110', 'B'),
        (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-310', 'A'),
        (102, 'Diya',  'CS303', 'Networks',  'Iyer', 'B-204', 'B'),
        (103, 'Kabir', 'CS302', 'Systems',   'Sen',  'C-110', 'C'),
        (104, 'Meera', 'CS303', 'Networks',  'Iyer', 'B-204', 'A');
    expected:
      columns: [instructor, offices]
      rows:
        - [Iyer, 2]
  - name: returns no rows when every instructor's copies agree
    setup: |
      CREATE TABLE sheet (roll_no INTEGER, student TEXT, course TEXT, title TEXT, instructor TEXT, office TEXT, grade TEXT);
      INSERT INTO sheet VALUES
        (101, 'Aarav', 'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
        (102, 'Diya',  'CS301', 'Databases', 'Iyer', 'B-204', 'B'),
        (103, 'Kabir', 'CS304', 'Compilers', 'Khan', 'A-015', 'A');
    expected:
      columns: [instructor, offices]
      rows: []
  - name: counts three offices, and does not count a missing office as a different one
    setup: |
      CREATE TABLE sheet (roll_no INTEGER, student TEXT, course TEXT, title TEXT, instructor TEXT, office TEXT, grade TEXT);
      INSERT INTO sheet VALUES
        (101, 'Aarav', 'CS304', 'Compilers', 'Khan', 'A-015', 'A'),
        (102, 'Diya',  'CS304', 'Compilers', 'Khan', 'A-016', 'B'),
        (103, 'Kabir', 'CS305', 'Graphics',  'Khan', 'A-017', 'B'),
        (104, 'Meera', 'CS302', 'Systems',   'Sen',  'C-110', 'A'),
        (105, 'Vikram', 'CS302', 'Systems',  'Sen',  NULL,    'C'),
        (106, 'Zoya',  'CS301', 'Databases', 'Iyer', 'B-204', 'A'),
        (107, 'Rohan', 'CS303', 'Networks',  'Iyer', 'B-310', 'B');
    expected:
      columns: [instructor, offices]
      rows:
        - [Khan, 3]
        - [Iyer, 2]

The self-check below draws on fourteen questions, from Iyer’s five copies to the three goals. It begins with the idea you have answered worst and raises the level after each right answer:

Interview questions

Fresher · What are update, insertion and deletion anomalies? Give an example of each.

They are the three problems of a table that stores one fact in many rows. An update anomaly: an enrolment sheet copies each instructor’s office into every enrolment, so a change of office must update every copy, and updating only some leaves the table contradicting itself. An insertion anomaly: a new course cannot be recorded until a student enrols, because every row needs a roll number. A deletion anomaly: when the last student drops a course, deleting that enrolment also deletes the course’s title and its instructor’s office. All three come from mixing facts about different things in one table; storing each fact in a table keyed by what determines it removes them.

Interviewers tend to push on two points of this answer. Choose a reply to each; every choice explains what it gets right or misses:

Two design questions of this module start from this lesson:

Key takeaways

• Redundancy is one fact stored in many rows: the sheet kept Iyer’s office in five rows, and nothing in the table made the copies agree.
• An update anomaly leaves copies that disagree, as the update by course that changed three of Iyer’s five rows did.
• An insertion anomaly needs an unrelated fact to store a new one, and a deletion anomaly removes a fact along with another; both come from facts that live only inside enrolment rows.
• A split into two tables is lossless when the shared columns are a key of one of the pieces; otherwise the join invents spurious rows, 5 of 13 in the careless split.
• Schema refinement aims for no redundancy, lossless joins and preserved dependencies, and keeps a copy only as a decision.