Databases

Question 1

(a) Closure of ShipmentID: (5) Start {ShipmentID}.

• $F_1 \Rightarrow$ add TruckID, DepotID, Weight → {ShipmentID, TruckID, DepotID, Weight} (1)
• $F_2$ (TruckID→DriverName) → add DriverName (0.5)
• $F_3$ (DepotID→DepotCity) → add DepotCity (0.5)
• $F_4$ (DepotCity→RatePerKg) → add RatePerKg (0.5)
• $F_5$ (Weight,RatePerKg→Cost) → add Cost (0.5)

$\{\text{ShipmentID}\}^+ = \{$all 8 attributes$\}$ → ShipmentID is a superkey. (1) No other attribute appears on the LHS of the "top" FD generating ShipmentID; ShipmentID never appears on any RHS, so it must be in every key ⇒ it is minimal and the unique candidate key. (1)

(b) With key = ShipmentID (all non-keys are non-prime): (4)

• 2NF: since the key is a single attribute, there are no partial dependencies → no 2NF violation. (1) (Award for recognizing single-attribute key ⇒ automatically 2NF.)
• 3NF violations are transitive dependencies:
• $F_2$ TruckID→DriverName (2)
• $F_3$ DepotID→DepotCity, $F_4$ DepotCity→RatePerKg, $F_5$ Weight,RatePerKg→Cost — none of these LHS are superkeys and RHS is non-prime → all violate BCNF/3NF. (1)

Anomalies (name any correct mapping): DriverName re-stored on every shipment of a truck ⇒ update anomaly; can't record a depot's city/rate with no shipment ⇒ insert anomaly; deleting last shipment loses truck's driver/depot city ⇒ delete anomaly.

(c) BCNF decomposition (each relation: LHS of an FD becomes a key): (7)

• $R_1(\underline{\text{TruckID}}, \text{DriverName})$ — from $F_2$ (1)
• $R_2(\underline{\text{DepotID}}, \text{DepotCity})$ — from $F_3$ (1)
• $R_3(\underline{\text{DepotCity}}, \text{RatePerKg})$ — from $F_4$ (1)
• $R_4(\underline{\text{Weight, RatePerKg}}, \text{Cost})$ — from $F_5$ (1)
• $R_5(\underline{\text{ShipmentID}}, \text{TruckID}, \text{DepotID}, \text{Weight})$ — residual with the key. (1) FKs: R5.TruckID→R1, R5.DepotID→R2, R2.DepotCity→R3, (R5.Weight, R3.RatePerKg via join)→R4.

Lossless proof (1): At each binary split $R = R_a \bowtie R_b$ the common attribute is the key of one side (e.g. splitting off R1, common attr TruckID is key of R1 ⇒ $R_a\cap R_b \to R_a$ holds). By the lossless-join test, if the shared attribute set is a superkey of one fragment the join is lossless; applying this at every step ⇒ overall decomposition is lossless. (1)

(d) Dependency preservation: (4) Each of $F_2,F_3,F_4,F_5$ is fully contained inside one relation → preserved. $F_1$ (ShipmentID→TruckID,DepotID,Weight) lives entirely in R5 → preserved. (2) So this decomposition is dependency-preserving. However, note the general principle worth stating: BCNF is not guaranteed dependency-preserving (3NF is), because forcing every determinant to be a key can split an FD across relations whose join must be recomputed to check it. (2)

Question 2

(a) (6)

SELECT deptID, empID, name, salary
FROM (
  SELECT e.*,
         DENSE_RANK() OVER (PARTITION BY deptID ORDER BY salary DESC) AS rnk
  FROM Employee e
) t
WHERE rnk = 2;

Justification: DENSE_RANK assigns rank on distinct salary values, so if two employees tie for the top salary they both get rank 1 and the next distinct salary gets rank 2 — exactly "second-highest distinct salary." (3) RANK would skip to rank 3 after a two-way tie (leaving no rank 2), and ROW_NUMBER would arbitrarily pick one top earner as 1 and the other as 2 — both wrong for the requirement. (3)

(b) (6)

WITH RECURSIVE subtree AS (
    SELECT empID, name, managerID, 0 AS depth
    FROM Employee
    WHERE empID = :rootID              -- anchor member
  UNION ALL
    SELECT e.empID, e.name, e.managerID, s.depth + 1
    FROM Employee e
    JOIN subtree s ON e.managerID = s.empID   -- recursive member
)
SELECT * FROM subtree;

• Anchor (2): selects the root at depth 0.
• Recursive member (2): joins Employee to the working table on managerID = parent.empID, incrementing depth.
• Termination (2): recursion stops when the recursive member returns no new rows (a leaf has no children satisfying the join), i.e. the UNION ALL fixpoint is reached. Assumes an acyclic hierarchy.

(c)(i) (4) The result touches only the top-2 salary rows per department. With the ordered composite index, the engine can walk each department's leaf range and stop after the second distinct salary: roughly $O(D \cdot \log N + k)$ where $k$ = rows returned (a few per dept), i.e. $\approx 500\log_2(10^6) \approx 500\cdot 20 = 10^4$ leaf touches vs a full sort of all $10^6$ rows at $O(N\log N)\approx 10^6\cdot20 = 2\times10^7$ comparisons. (Index plan asymptotically far cheaper.) (4)

(c)(ii) (6) $C = c_{io}P + c_{cpu}T$.

• Full scan: $C_{full} = 1.0\cdot 12500 + 0.01\cdot 10^6 = 12500 + 10000 = 22500$. (2)
• Index-only: $C_{idx} = 1.0\cdot 4000 + 0.01\cdot 10^6 = 4000 + 10000 = 14000$. (2) Since $14000 < 22500$, the optimizer chooses the index-only plan. (2)

Question 3

(a) (6) Definitions (3, 1 each):

• Dirty read: reading a row modified by another uncommitted transaction.
• Non-repeatable read: re-reading the same row yields a different value because another committed txn updated it.
• Phantom read: re-running the same range query returns a different set of rows because another committed txn inserted/deleted matching rows.

Permitted-anomalies table (3):

(b) (5) Under READ COMMITTED each statement takes a fresh snapshot at statement start.

• First SELECT (before T1 commits): sees old row version (xmax from T1 not yet committed / not visible) → 100. (1.5)
• T1 commits (its new version balance=50 becomes visible). (1)
• Second SELECT: new snapshot sees the committed version → 50. (1.5) The two reads differ → non-repeatable read occurs (permitted at READ COMMITTED). (1)

(c) (7) Under REPEATABLE READ, PostgreSQL takes one snapshot at the first statement of the transaction and reuses it for the whole txn. (1)

• Both SELECTs see the version whose commit was visible at snapshot time → 100 and 100 — consistent, no non-repeatable read; xmin/xmax visibility rules hide T1's later-committed version. (2)

Write skew example (4): SERIALIZABLE-only anomaly; RR does not prevent it. Constraint: "at least one doctor must remain on call." Two on-call doctors A, B.

T1: SELECT COUNT(*) WHERE on_call=true;  -- sees 2
    UPDATE Doctor SET on_call=false WHERE name='A';
T2: SELECT COUNT(*) WHERE on_call=true;  -- sees 2 (own snapshot)
    UPDATE Doctor SET on_call=false WHERE name='B';
Both COMMIT.

Each read a snapshot of 2, each updated a different row (no write-write conflict, so RR/snapshot isolation lets both commit), but the final state has 0 on call — the invariant is violated. Only SERIALIZABLE (SSI) detects the read/write dependency cycle and aborts one. (4)

[
  {"claim":"ShipmentID closure yields all 8 attributes and cost is derivable last","code":"attrs={'ShipmentID'}\nfds=[({'ShipmentID'},{'TruckID','DepotID','Weight'}),({'TruckID'},{'DriverName'}),({'DepotID'},{'DepotCity'}),({'DepotCity'},{'RatePerKg'}),({'Weight','RatePerKg'},{'Cost'})]\nchanged=True\nwhile changed:\n    changed=False\n    for l,r in fds:\n        if l<=attrs and not r<=attrs:\n            attrs|=r; changed=True\nresult = attrs=={'ShipmentID','TruckID','DepotID','Weight','DriverName','DepotCity','RatePerKg','Cost'}"},
  {"claim":"Full scan cost = 22500","code":"C=1.0*12500+0.01*10**6\nresult = C==22500"},
  {"claim":"Index-only cost = 14000 and is cheaper","code":"Cf=1.0*12500+0.01*10**6\nCi=1.0*4000+0.01*10**6\nresult = (Ci==14000) and (Ci<Cf)"},
  {"claim":"Index leaf touches ~1e4 << full sort comparisons ~2e7","code":"import math\nidx=500*math.log2(10**6)\nfull=10**6*math.log2(10**6)\nresult = idx<11000 and full>1.9*10**7 and idx<full"}
]