Storage 2 and 3 Recap Q&A — Relational vs. non-Relational

(a) First normal form

No. A relation is in 1NF if and only if no attribute domain has relations as elements. Here the Courses attribute holds a small table (a repeating group) in each cell. To flatten it, we write one row per (student, course) pair:

Primary key: (StudentID, CourseCode). Neither attribute alone identifies a row.

(b) Functional dependencies

• StudentID → Name, Programme
• Programme → Director
• CourseCode → Title, Lecturer
• Lecturer → Office
• (StudentID, CourseCode) → Grade

(c) 2NF, then 3NF

2NF removes partial dependencies, meaning non-key attributes that depend on only part of the key. Name, Programme and Director depend on StudentID alone, and Title, Lecturer and Office depend on CourseCode alone:

• Students(StudentID, Name, Programme, Director)
• Courses(CourseCode, Title, Lecturer, Office)
• Enrolments(StudentID, CourseCode, Grade)

3NF removes transitive dependencies. StudentID → Programme → Director and CourseCode → Lecturer → Office are both transitive, so Director and Office move to their own tables. I also give lecturers a surrogate key, since two lecturers could share a name.

(d) Anomalies avoided

• Update: if Dr. Rossi moves to office C-305, four rows of the 1NF table must change. If one is missed, the database holds two offices for the same person. In 3NF this is a single row in Lecturers.
• Deletion: if Hugo drops DB101, his only course, deleting the row also erases the facts that Hugo exists and that Mathematics is directed by Prof. Moreau.
• Insertion: a new course "NoSQL Systems" cannot be recorded before at least one student enrols, because StudentID is part of the primary key and cannot be NULL.

A 3NF schema

Justification of the main decisions

• PassengerPhone: a passenger has several phone numbers. A multi-valued attribute violates 1NF, so it gets its own table with key (passenger_id, phone).
• Tier and LoyaltyCard: passenger → card_no → tier → discount_rate is a transitive chain. Storing discount_rate with the passenger would duplicate it and risk inconsistency when the operator changes the Gold rate. card_no is UNIQUE and nullable in Passenger, because the card is optional and belongs to one person.
• City: station → city → region is transitive, so the region is stored once per city.
• RollingStock: the seat counts depend on the stock type, not on the train (train_no → stock_type → seats_1st).
• RouteStop: a route is an ordered list. The order is itself data (stop_order), so the list is not packed into one column. Key (train_no, stop_order), plus UNIQUE(train_no, station_code).
• Service: separates the train, which is static, from its daily runs. Surrogate key, plus UNIQUE(train_no, run_date).
• Booking vs Ticket: the booker and the traveller are two distinct foreign keys to Passenger. The ticket carries the trip facts (service, from, to, class, seat).

Attributes that should not be stored as such

• Age is derived from birth_date and the current date. Stored, it becomes wrong every birthday, which is an update anomaly caused by time.
• Total amount paid is derived: SUM(price_paid) over the booking's tickets. Storing it creates a dependency between rows that has to be maintained. It is acceptable only as a deliberate denormalisation, kept correct by a trigger or by the application.
• price_paid on Ticket is not a 3NF violation. It records what was paid at that moment, and it is not a function of class or route, because fares change over time. Replacing it with a lookup into a current fare table would rewrite history.

(a) Classification

• System A is CP. With $N=3$, $W=2$ and $R=2$ we have $R+W>N$, so every read quorum intersects every write quorum and a read always sees the latest acknowledged write (consistency). During a partition, the majority side keeps working (partition tolerance), but the isolated replica refuses requests, so some non-failing nodes do not respond (no availability).
• System B is AP. Every non-failing replica answers every request (availability) and the system keeps running when messages are dropped (partition tolerance). During a partition, both sides accept writes on the same key and diverge, so a read can return a stale value (no consistency). After the partition heals, last-writer-wins makes the replicas converge, which makes B eventually consistent, and one of the concurrent writes is silently discarded.
• System C is CA. As long as the cable works, two-phase commit keeps both copies identical (C) and both replicas answer (A). Nothing in the design handles a partition. If the cable is cut, the coordinator waits forever for the other vote, so the system blocks. It has no partition tolerance.

(b) Use cases

• Like counter → B (AP). A slightly stale count harms no one, and the page must always load.
• Train seats → A (CP), at least when the train is nearly full, so that the same seat is never sold twice. When booking has just opened and the train is almost empty, an AP approach is acceptable, because the risk of conflict is negligible.
• Bank ledger → A (CP). An error message is better than a balance that is wrong or a double spend.

(a) Look at the failure cases

System 1 has low (weak) consistency, not eventual. The diagram shows convergence only because the message happened to arrive. Eventual consistency is a guarantee: if writes stop, every replica must end up with the last value. Here, if the single UDP message is lost, R2 keeps x = 0 forever:

Two concurrent writes on R1 and R2 can also cross each other, so that each replica ends with the other's value and they stay different forever.

System 2 has strong consistency. A write is committed only when it is on every replica, so any follower returns the latest committed value. The price shows up when one follower becomes unreachable: the leader waits forever, and every later write is blocked too. The system is consistent but not available. It is CP pushed to the extreme, where the cluster is only as available as its least available node.

(b) Latency without any failure: PACELC

Each write costs a round trip to the slowest follower: latency ≈ max over followers of the round-trip time. With one follower in another data centre, that is tens of milliseconds instead of under a millisecond. It grows with distance, and with the number of followers, since the maximum of more round-trip times is larger. Because writes are handled in order, Client B also waits for A's write to finish: queueing adds up.

This is the PACELC theorem: if there is a Partition, choose A or C; Else, choose Latency or Consistency. System 2 is PC/EC: it gives up availability during a partition, and pays latency the rest of the time. CAP only describes the first half.

(c) Fix for System 1: resend until acknowledged, and resolve conflicts deterministically

• Each write gets a version, for example a timestamp plus the replica id.
• The receiving replica acknowledges each update. The sender keeps the update and resends it every τ seconds until it gets the acknowledgement. Periodically comparing the replicas' contents and exchanging the differences is a backstop.
• All replicas apply the same rule when two versions meet, for example "the highest version wins", so they reach the same final state whatever order the messages arrive in.

(c) Fix for System 2: switch to asynchronous replication

• The leader commits locally and acknowledges immediately, then replicates to the followers in the background.
• A follower that comes back asks the leader what it missed, and the leader re-sends those updates. Writes no longer wait for F2, and reads from followers may return Data(t−1).
• An intermediate design is semi-synchronous replication: wait for one follower, not all of them.

(a) Number of interleavings

The order inside each thread is fixed, so we only choose which 3 of the 6 time slots belong to Thread 1: $\binom{6}{3} = 20$ orders.

(b) A failing execution

Half of the transaction has been applied: 50 units have disappeared. After restart, the system cannot tell that A = 30 is a partial result, and it has no record of the old value 80 to go back to.

(c) No safe order exists

In every one of the 20 orders, the two writes happen at two distinct instants, so there is always a window between the first and the second write. A failure inside that window leaves exactly one of them on disk. Reordering can shorten the window, for example by computing both values first and writing them back to back, but it can never remove it. Atomicity therefore needs extra information on disk to undo or redo the work. That is the role of the log (Q6).

(a) Recovery

Crash after Write(A), before Write(B). Because of the write-ahead rule, <T,START> and <T,A,80,30> are on disk, since A's page could not be written before its log record. There is no <T,COMMIT>, so T is a loser. Recovery scans its records backwards and undoes them by writing the old values: A := 80, and B := 30 if its record exists. The result is A = 80, B = 30, as if T never ran.

Crash after <T,COMMIT>, before the pages are written. T is successfull: the client was told the transfer succeeded. Recovery scans forward and redoes it by writing the new values: A := 30, B := 80. Each outcome is all or nothing, and which one applies is decided by a single atomic event: whether the commit record is on disk.

(b) Crash during recovery

Recovery simply starts again. Undo and redo set values (A := 80) and are therefore idempotent: applying them twice gives the same result as applying them once. A logical record like A −= 50 would be applied twice and corrupt the data. Real systems such as ARIES also store a log sequence number (LSN) on each page, so that a change already present on the page is not redone.

(c) Why an extra disk write makes things faster

The key insight is that the WAL turns many random in-place writes at commit time into one sequential append. The data pages are still written, but later, in the background, batched and optimized.

Scenario 1: dirty read → Read committed

Scenario 2: non-repeatable read → Repeatable read

Scenario 3: lost update → Repeatable read

Any serial execution gives 50 + 30 − 20 = 60.

Summary: is the anomaly possible?

(a) Blocked transactions and results

✗ marks a wrong decision: blocking something unrelated (A), or letting T1's result change (B). Under B the second SELECT sees Hugo (3500) and Bilal's new salary (3200): 3100 + 3400 + 3900 + 3500 + 3200 = 17100.

(b) Too strong, too weak

A is too strong. It is correct, but every writer on the table waits for a report that may last minutes, including T3 and T5, which have nothing to do with the range. Concurrency collapses to one transaction at a time on the table.

B is too weak. It locks data, but the query is about a predicate. When T1 takes its locks, Hugo's row does not exist yet, and you cannot lock a row that does not exist. Bilal's row exists but does not match the predicate, so it is not locked either, and T4 moves it into the range.

Rows that appear in the result of a query re-run inside the same transaction are called phantoms, and this anomaly is a phantom read. Procedure B is exactly level 2 (Repeatable read), which is why level 2 allows phantoms. Level 3 (Serializable) must prevent them, and that is what range locks are for.

(c) Procedure C: lock the range in the index (next-key locking)

This is how lock-based DBMSs implement level 3, for example MySQL/InnoDB and SQL Server's key-range locks.

1. Scan the index on salary from 3000 to 4000. Lock every index entry found and the gap before it, then lock the first entry after the range (4500) together with its gap. The locked region is (2800, 4500].
2. Any writer that wants to insert a key, or move a key, into a locked gap must first request an "insert-intention" lock on that gap, which conflicts with T1's lock, so it waits. T2 (3500 ∈ (3400, 3900]) and T4 (3200 ∈ (3100, 3400]) are blocked.
3. Keys outside (2800, 4500] are untouched: T3 and T5 proceed.

• It needs an index on the column. Without one, the DBMS has to scan the whole table, so it locks every row and every gap, which degenerates into procedure A.

(d) Why the margin? Why not lock exactly [3000, 4000]?

A lock manager can only lock things that have a name. It is essentially a hash table: resource → who holds it, in which mode. Checking for a conflict is one hash lookup, so it costs $O(1)$. A table, a page, a row and an index key all have names. The interval [3000, 4000] does not: no row and no key in the database is called 3000 or 4000.

Next-key locking borrows names that already exist: the index keys. Each gap between two consecutive keys is named after the key that closes it, so the gap (3900, 4500] "belongs to" key 4500. To insert 4200, the writer has to walk down the B-tree to where 4200 goes anyway, and it lands right before 4500. Checking the lock on 4500 is one extra hash lookup. The price is that only whole gaps can be locked. The gap containing 4000 is (3900, 4500], and cutting it at 4000 would need a key 4000 that does not exist. That is the margin: (2800, 3100] at the bottom and (3900, 4500] at the top.

Locking exactly the range means predicate locking. The DBMS stores the condition salary BETWEEN 3000 AND 4000 itself, and checks every write against it. For this single interval, that would actually be cheap. In general it is not:

• A predicate is not a name, so a conflict cannot be found with a hash lookup. Every write has to be tested against every predicate held by every active transaction.
• Predicates are arbitrary SQL, for example dept = 'IT' AND salary * 1.1 > bonus. Deciding whether two arbitrary predicates can be true for the same row is hard in general.

(a) The order

C → G → E → H → A → D, then in the background B → F.

E and H may be swapped. The real constraints are that H is on disk before B (write-ahead), and that A is on disk before D (commit before acknowledging).

(b) Memory only?

Database in memory: no. A power cut erases RAM, so the data of committed transactions would be lost. Log in memory: no. The log is the durable proof of the commit. If it only lives in RAM, a crash after D loses a transaction the client was told was committed, and recovery has nothing to undo or redo from. Any trade-off here might reduce consistency.

(c) Breaking the order

• B before H: the disk holds an uncommitted value with no log record describing it. If the transaction then aborts or the machine crashes, recovery does not know the old value (50) and cannot undo the change, so atomicity is broken. This is the case the write-ahead rule exists to prevent.
• D before A: the client is told "committed", but the commit record is not yet on disk. A crash at that moment makes recovery treat T as a loser and undo it, so durability is broken.

(d) Power failure in the middle of B

1. Read the log from the last checkpoint.
2. Redo every committed transaction: set the new values. Pages that were already written are simply rewritten, or skipped.
3. Undo every transaction without a COMMIT record by restoring the old values stored in the log.

(e) Checkpoints

A checkpoint records "every change up to this point is in the database files". Recovery can start from there, and the log before it can be recycled. Without checkpoints the log grows without bound, and recovery must replay it from the very beginning, which can take hours after a crash.

(a) Direct trains: one self-join (or a group-by).

SELECT a.train_no
FROM RouteStop a JOIN RouteStop b ON a.train_no = b.train_no
WHERE a.station_code = 'RNS' AND b.station_code = 'LMN'
  AND a.stop_order < b.stop_order;              -- TGV 8612

This is easy because the path has a known length: one train, so one join.

(b) Any number of changes: recursion

With a fixed number of joins we can only find paths up to a fixed length: 1 join for one hop, 2 for two, and so on. Reachability, meaning a path of any length, cannot be expressed in plain relational algebra. We need to use recursive queries.

(c) Transfers are a second kind of edge

The schema only knows "the next stop of the same train". Walking between two stations, or changing trains with a minimum connection time, is not stored anywhere. We need a new table, for example Transfer(from_station, to_station, minutes), and the recursive step must now follow either a Hop (that needs to be properly defined) or a Transfer:

    FROM reach r JOIN (SELECT src, dst FROM Hop
                       UNION ALL
                       SELECT from_station, to_station FROM Transfer) e
         ON e.src = r.station

Every new kind of relationship (bus, ferry, walking path) means one more table and one more branch in the recursion. If we also want the times to be consistent (the next train must leave after we arrive, plus the transfer time), the recursion must carry the current time and compare it at each step. The query quickly becomes hard to write and to optimise.

(a) A labelled property graph

• Nodes labelled :Station with properties code and name, and :City with name and region.
• Relationships :NEXT between two consecutive stops of a train, with properties train_no, dep, arr and class. :WALK between two stations you can walk between, with minutes. :IN from a station to its city.
• Relationships are stored, not recomputed: the "next stop" from Q10's view now exists physically. A new kind of connection (bus, ferry) is a new relationship type, with no schema migration.
• For timetable-exact routing ("leave after 07:00, arrive as early as possible"), an alternative is a time-expanded graph, with one node per (train, stop, time) event. It is bigger, but a shortest path in it is automatically consistent with the times.

(d) Everything in the graph?

It might be possible, but it is not appropriate here. Bookings, tickets and payments are records: they need ACID transactions, constraints (no double-booked seat), aggregates. That is exactly what the relational model is good at. The network, used for routing, is a graph. A common design is a multi-model approach: the relational database stays the source for tickets and passengers, and the graph of stations and connections is derived from RouteStop and kept in sync.