Databases · Week 2 practice: normalisation

Answer: Normalisation is a process used in data modelling/database creation where you organise data and tables so they can be added to and updated efficiently. It is done manually at design time (“no click a button and do it!”). In the Week 1 design steps it is schema refinement. It was introduced by Codd alongside the relational model in the early 1970s.

• Make the database more efficient.
• Prevent duplicates: the same data stored in more than one place.
• Ensure consistency: stop updates being applied to some copies but not others.
• Prevent data not being deleted when it should be, or lost when it shouldn't be.
• Ensure data accuracy.
• Reduce storage space.
• Optimise query execution times.

Without it, the database is likely to be slow and hard to manage, update and keep accurate. Notice these are Week 1's redundancy problems again: normalisation is the systematic way to apply Guideline 2 (“do not repeat information”).

• INSERT anomaly (you can't add something without adding unrelated data, or you add incomplete data): a new group lesson “Jazz Ensemble” can't be recorded until a pupil takes it, because lessons only exist as cells in pupil rows. A new pupil whose instrument isn't decided yet gets incomplete data (NULL Instrument and Tutor).
• UPDATE anomaly (you update a record but fail to make all the necessary changes): rename “Theory 1” to “Music Theory 1”. It appears in several rows and in different columns (Lesson 1 here, Lesson 2 elsewhere). Miss one and the data is inconsistent. Same if Ms Osei's name changes.
• DELETE anomaly (deleting one thing removes other data you wanted to keep): if Lucy Moore leaves and her row is deleted, the only record that Cello is taught by Ms Osei disappears. If Emma leaves, “Aural 1” vanishes entirely.

Answer: a DELETE anomaly: deleting one thing (a student) removes other data you wanted to keep (that those classes exist). This is the slides' own example.

Answer: Each normal form's definition starts “fulfils the requirements of the previous one”, so the sets nest: every 3NF table is in 2NF and 1NF, but not the other way round. The innermost (BCNF) is the strictest. The lecture notes add 4NF, 5NF, even 6NF, but 3NF is the one you'll most commonly see in practice.

The diagram also shows each step decomposing the relation into more, smaller relations (R → R₁₁, R₁₂ → R₂₁, R₂₂, R₂₃ …). Only 1NF–3NF are in scope here; 4NF/5NF are recognition only.

(a) (1) A single cell must not hold more than one value (atomicity). (2) There must be a primary key for identification. (3) No duplicated rows or columns. (4) Each column must have only one value for each row.

(b)

• No primary key. Pupil Name isn't unique (two pupils could share a name), and neither is any other column. As in the slides, introduce a PupilID.
• Repeating group / duplicated columns: Lesson 1, Lesson 2 are the same kind of column repeated. How many do you allow? Lucy has an empty one; a pupil with three lessons doesn't fit at all. (Cells are each atomic here, but the slide's own Class columns are written as “Biology 1 (Science)”, two facts in one cell: a lesson and its department. That would break atomicity.)

Answer: the determinant. Y is the dependent. A functional dependency says one attribute (set) determines the value of another: whenever two rows agree on X, they must agree on Y. Read StudentID → StudentName as “StudentID determines StudentName”: know the ID and there's exactly one name.

1. Yes. Determinant PupilID, dependent Pupil Name: one ID, one name.
2. No. Two pupils can share a name, so a name can map to several IDs.
3. Yes (business rule: each instrument has one tutor). Determinant Instrument, dependent Tutor.
4. No. Ms Osei teaches Violin and Cello.
5. No. A pupil attends several lessons. This is why lessons can't stay as a column of the pupil table: it's a many-to-many relationship, not a dependency.
6. Yes (each pupil learns one instrument).

Key habit: FDs come from the business rules, not from spotting patterns in today's rows. Three rows of sample data can't prove a rule holds.

Answer: A partial dependency is a non-key attribute depending on only part of the primary key. If the key is a single column, it has no “part” to depend on, so (slide 19) a table in 1NF with a single-column PK is already in 2NF.

(a)

order_id, product_id → quantity
order_id             → order_date, customer_name
product_id           → product_name, unit_price

(b) The last two: their determinants are each part of the composite key. Only quantity depends on the entire key (how many of this product on this order).

(c) Move each partial dependency into its own table, keyed on the part of the key it depends on:

Order    (order_id, order_date, customer_name)
Product  (product_id, product_name, unit_price)
OrderLine(order_id FK → Order, product_id FK → Product, quantity)

OrderLine is now a junction table for the M:M between Order and Product (Week 1's pattern). Changing a price now means updating one row.

(a) A transitive dependency is when A → B and B → C, so A → C holds “through” B, where B is a non-key attribute. You can find a non-key attribute using another non-key attribute. 3NF: in 2NF and no transitive dependencies; every non-key attribute must provide “a fact about the key, the whole key, and nothing but the key”.

(b) 2NF: yes, the PK is a single column so there can be no partial dependency. 3NF: no: emp_id → dept_id → dept_name, dept_floor. Department facts depend on dept_id, a non-key attribute.

Department(dept_id, dept_name, dept_floor)
Employee  (emp_id, name, dept_id FK → Department)

The pattern is the slides' Student/Postcode split: the attribute in the middle (dept_id) becomes the PK of a new table and stays behind as a FK.

It isn't consistent. A table (Postcode PK, City) stores the dependency Postcode → City: the key determines the other column. And in reality a postcode lies in one city, while a city has many postcodes, so City → Postcode is false. The correct chain is:

StudentID → Postcode → City        so  StudentID → City (transitively)

The slide's prose (“we can identify the City using Postcode”) agrees with this; only the arrow line is reversed. In the test, write it as StudentID → Postcode → City. If you rely on the slide's arrows, the “middle” attribute would be City, and the decomposition would come out differently. That's why getting the direction right matters. (I'd treat this as a typo on the slide; worth checking with the lecturer if you can.)

Method: first check for partial dependencies (only possible with composite keys), then for non-key → non-key dependencies.

1NF. Introduce a primary key PupilID (names aren't unique). Remove the repeating group Lesson 1/Lesson 2 by giving each pupil–lesson pair its own row:

PupilLessons(PupilID, Lesson, PupilName, FeesPaid, DOB, Instrument, Tutor)

The key is now (PupilID, Lesson), since a pupil appears once per lesson. (The slides' own example keeps Class 1–4 at 1NF and removes them at 2NF. Either way you end up in the same place.)

2NF. Partial dependencies on that composite key: PupilID → PupilName, FeesPaid, DOB, Instrument, Tutor. Nothing depends on the whole key; lessons themselves become their own table so a lesson can exist with no pupils (fixing the insert anomaly):

Pupil      (PupilID, PupilName, FeesPaid, DOB, Instrument, Tutor)
Lesson     (LessonID, LessonName)
PupilLesson(PupilID FK, LessonID FK)          -- M:M junction table

3NF. In Pupil, PupilID → Instrument → Tutor is transitive (Tutor is a fact about the instrument, not the pupil). Split it out, and give tutors their own table so a tutor's name is stored once:

Tutor      (TutorID, TutorName)
Instrument (InstrumentID, InstrumentName, TutorID FK → Tutor)
Pupil      (PupilID, PupilName, FeesPaid, DOB, InstrumentID FK → Instrument)
Lesson     (LessonID, LessonName)
PupilLesson(PupilID FK → Pupil, LessonID FK → Lesson)

Check the anomalies from Q3: a new lesson is just a row in Lesson; renaming “Theory 1” changes one row; deleting Lucy leaves “Cello → Ms Osei” intact. (Slide 21 says “program name is not dependent on the student”. Strictly, StudentID → Program does hold, as each student has one program, which is exactly why the slides keep Program ID in Student as a FK. What gets split out are the facts about the program, just as Instrument's tutor is here.)

DROP TABLE IF EXISTS pupil_lesson, lesson, pupil, instrument, tutor CASCADE;

CREATE TABLE tutor (
    tutor_id integer NOT NULL,
    name     text    NOT NULL,
    PRIMARY KEY (tutor_id)
);
CREATE TABLE instrument (
    instrument_id integer NOT NULL,
    name          text    NOT NULL,
    tutor_id      integer REFERENCES tutor(tutor_id),
    PRIMARY KEY (instrument_id)
);
CREATE TABLE pupil (
    pupil_id      integer NOT NULL,
    name          text    NOT NULL,
    fees_paid     integer,
    date_of_birth date,
    instrument_id integer REFERENCES instrument(instrument_id),
    PRIMARY KEY (pupil_id)
);
CREATE TABLE lesson (
    lesson_id integer NOT NULL,
    name      text    NOT NULL,
    PRIMARY KEY (lesson_id)
);
CREATE TABLE pupil_lesson (
    pupil_id  integer REFERENCES pupil(pupil_id),
    lesson_id integer REFERENCES lesson(lesson_id),
    PRIMARY KEY (pupil_id, lesson_id)
);

INSERT INTO tutor VALUES (1, 'Mr Hale'), (2, 'Ms Osei');
INSERT INTO instrument VALUES (1, 'Piano', 1), (2, 'Violin', 2), (3, 'Cello', 2);
INSERT INTO pupil VALUES
    (101, 'Emma Clarke', 300, '2008-03-12', 1),
    (102, 'Raj Patel',   450, '2009-07-01', 2),
    (103, 'Lucy Moore',  450, '2008-11-23', 3);
INSERT INTO lesson VALUES (1, 'Theory 1'), (2, 'Aural 1'), (3, 'Orchestra');
INSERT INTO pupil_lesson VALUES (101, 1), (101, 2), (102, 1), (102, 3), (103, 3);

-- Rebuild the original "one row per pupil per lesson" view of the data
SELECT p.name AS pupil, i.name AS instrument, t.name AS tutor, l.name AS lesson
FROM pupil p
JOIN instrument   i  ON i.instrument_id = p.instrument_id
JOIN tutor        t  ON t.tutor_id      = i.tutor_id
JOIN pupil_lesson pl ON pl.pupil_id     = p.pupil_id
JOIN lesson       l  ON l.lesson_id     = pl.lesson_id
ORDER BY p.pupil_id, l.lesson_id;

    pupil    | instrument |  tutor  |  lesson
-------------+------------+---------+-----------
 Emma Clarke | Piano      | Mr Hale | Theory 1
 Emma Clarke | Piano      | Mr Hale | Aural 1
 Raj Patel   | Violin     | Ms Osei | Theory 1
 Raj Patel   | Violin     | Ms Osei | Orchestra
 Lucy Moore  | Cello      | Ms Osei | Orchestra
(5 rows)

Table order matters: a table must exist before another can REFERENCES it, so tutor → instrument → pupil, and the drops go in reverse. JOIN … ON combines rows where the FK equals the PK (joins are on the SQL page). This is the “how do we connect all the data?” question from slide 22: the decomposition is only useful because FKs let you join the pieces back without spurious tuples, Week 1's Guideline 4.

Answer: foreign keys (slide 23): e.g. Program ID in Student, Teacher ID in Program, and the (Student ID, Class ID) link table. A FK also enforces referential integrity: you can't point at a program that doesn't exist.

Many-to-many. A Teacher ID column in Class can hold only one teacher per class (one value per cell is 1NF), so a co-taught class wouldn't fit. Use a junction table:

ClassTeacher(ClassID FK → Class, TeacherID FK → Teacher)

Exactly Week 1's rule: M:M needs an associative/junction table; 1:M puts the FK on the many side. If the school's rule were “one teacher per class”, Class.TeacherID would be correct. The business rule decides.

BCNF (Boyce–Codd Normal Form) requires that every determinant is a candidate key, with no exceptions. 3NF allows one exception: a dependency X → A where A is itself part of a key. Example: Tutoring(student, module, tutor) with tutor → module and {student, module} → tutor is in 3NF but not BCNF, because tutor is a determinant but not a key. The slides say this module only examines up to 3NF, so treat this as background.