Modelling

The three-schema architecture

EXTERNAL (view) level     what each user or app sees
                            e.g. a payroll view exposing no home addresses
        ↕ logical data independence
CONCEPTUAL (logical) level the whole schema: tables, columns, constraints
        ↕ physical data independence
INTERNAL (physical) level  files, pages, indexes, compression

The two independences are the payoff, and are worth naming precisely:
· PHYSICAL data independence — add an index, change the storage engine,
  repartition a table, and no query has to change.
· LOGICAL data independence — split a table in two, and existing views
  can be redefined so applications querying them still work.
Physical independence is nearly complete in practice; logical
independence is only partial, which is why schema migrations are
still real work.

Integrity constraints

• Entity integrity — the primary key is unique and not null.
• Referential integrity — a foreign key must either be NULL or match an existing primary key. No orphan rows.
• Domain integrity — values fall in the column's type and CHECK constraints.
• Key/unique constraints — enforce alternate keys.

-- Referential actions: what happens to children when a parent goes away
FOREIGN KEY (customer_id) REFERENCES customers(id)
    ON DELETE RESTRICT     -- refuse the delete (the safe default)
    ON DELETE CASCADE      -- delete the children too — powerful and dangerous
    ON DELETE SET NULL     -- orphan them deliberately (column must be nullable)
    ON DELETE SET DEFAULT  -- point them at a placeholder row
    ON DELETE NO ACTION    -- like RESTRICT, but checked at end of statement

-- CASCADE is the one to be careful with: deleting one customer can
-- silently remove millions of rows across many tables, and it happens
-- inside your transaction, holding locks the whole time.

The vocabulary

Mapping cardinality to tables — the mechanical rules

1 : 1   Put the FK on either side — preferably the side with TOTAL
        participation — and add UNIQUE to it.
        e.g. employee ─ has ─ parking_space
        parking_space(id, employee_id UNIQUE REFERENCES employee)

1 : N   Put the FK on the N side. Always. No join table needed.
        e.g. customer ─ places ─ order   (one customer, many orders)
        orders(id, customer_id REFERENCES customers)

M : N   You must create a junction / associative table whose primary
        key is the pair of foreign keys.
        e.g. student ─ enrols ─ course
        enrolments(student_id, course_id, grade, enrolled_at,
                   PRIMARY KEY (student_id, course_id))
        -- and note the junction table is the natural home for
        -- attributes OF THE RELATIONSHIP, like grade and enrolled_at

Weak entity
        order_lines(order_id, line_no, product_id, qty,
                    PRIMARY KEY (order_id, line_no))
        -- line_no alone means nothing; identity comes from the owner

Ternary relationships map to a table with three FKs — but check whether
        it's genuinely ternary or really two binary relationships.

-- "Names of students enrolled in CS101"
πname( σcourse_id = 'CS101'( students ⋈ enrolments ) )

-- The optimiser's favourite rewrite: PREDICATE PUSHDOWN.
-- These are equivalent, but the second joins far fewer rows:
   σcourse='CS101'( students ⋈ enrolments )        -- join everything, then filter
=  students ⋈ σcourse='CS101'( enrolments )         -- filter first, then join ✓

-- DIVISION is the one that trips people up. "Students who take EVERY
-- course offered" — the SQL idiom is double negation:
SELECT s.name FROM students s
WHERE NOT EXISTS (
  SELECT 1 FROM courses c
  WHERE NOT EXISTS (
    SELECT 1 FROM enrolments e
    WHERE e.student_id = s.id AND e.course_id = c.id))
-- reads as: "no course exists that this student is not enrolled in"

Armstrong's axioms

Reflexivity     if Y ⊆ X then X → Y
Augmentation    if X → Y then XZ → YZ
Transitivity    if X → Y and Y → Z then X → Z
-- derived, and the ones you actually use:
Union           if X → Y and X → Z then X → YZ
Decomposition   if X → YZ then X → Y and X → Z
Pseudotransitivity  if X → Y and WY → Z then WX → Z

Attribute closure — and finding candidate keys

R(A, B, C, D, E)
FDs:  A → BC        CD → E        B → D        E → A

Closure of A:  start {A}
  A → BC   → {A,B,C}
  B → D    → {A,B,C,D}
  CD → E   → {A,B,C,D,E}
  A⁺ = {A,B,C,D,E} = all attributes  →  A is a candidate key

Closure of E:  {E}  →  E → A  →  {E,A}  →  then as above
  E⁺ = all  →  E is a candidate key

Closure of B:  {B} → B → D → {B,D}. Nothing else applies.
  B⁺ = {B,D}  ≠ all  →  B is NOT a key

Closure of CD: {C,D} → CD → E → {C,D,E} → E → A → {C,D,E,A}
                → A → BC → {A,B,C,D,E}
  CD⁺ = all  →  CD is a candidate key

Candidate keys: A, E, CD
PRIME attributes (in some candidate key): A, C, D, E
NON-PRIME: B          ← this distinction is what 2NF/3NF are defined on

The exam shortcut: an attribute that appears ONLY on the right-hand side
of every FD can never be part of a candidate key. An attribute that never
appears on any right-hand side must be in EVERY candidate key.

The three anomalies — always name these first

The forms, worked on one example

Start — unnormalised
student_courses(student_id, student_name, course_id, course_name,
                instructor, instructor_office, grades)
   grades = "A,B,A"        ← multiple values in one cell
   PK = (student_id, course_id)

══ 1NF ══ atomic values, no repeating groups ══════════════════════
Split the multivalued attribute out.
   student_courses(student_id, student_name, course_id, course_name,
                   instructor, instructor_office, grade)
   -- one grade per row now. 1NF achieved.

══ 2NF ══ 1NF + no PARTIAL dependencies ══════════════════════════
   (only relevant when the PK is composite)
FDs present:
   student_id            → student_name          ← depends on PART of PK ✗
   course_id             → course_name, instructor ← PART of PK ✗
   (student_id, course_id) → grade               ← full PK ✓

Decompose:
   students(student_id, student_name)
   courses(course_id, course_name, instructor, instructor_office)
   enrolments(student_id, course_id, grade)

══ 3NF ══ 2NF + no TRANSITIVE dependencies ═══════════════════════
   (no non-prime attribute depends on another non-prime attribute)
In courses:  course_id → instructor → instructor_office
             instructor_office depends on course_id only TRANSITIVELY ✗
             -- symptom: an instructor's office is repeated on every
             -- course they teach, so moving office = many updates
Decompose:
   courses(course_id, course_name, instructor)
   instructors(instructor, instructor_office)

══ BCNF ══ every determinant is a superkey ═══════════════════════
The classic case 3NF misses. Suppose:
   enrolments(student_id, course_id, instructor)
   · each course is taught by many instructors
   · a student takes a course from exactly one instructor
   · each instructor teaches only ONE course
FDs:  (student_id, course_id) → instructor      ✓ superkey
      instructor → course_id                   ✗ NOT a superkey!

This IS in 3NF — course_id is prime, and 3NF permits a non-superkey
determinant when the dependent attribute is prime. But it still has
redundancy. BCNF has no such exception:
   teaches(instructor, course_id)
   enrolments(student_id, instructor)