Skip to content
Tutorials Center
My learning

Topics

Lesson 77 of 79 ยท Practice and Review

Exercises with Solutions

Practice DBMS with nine solved exercises: ER mapping, relational algebra, SQL division, closure and keys, serializability, B+ trees and crash recovery.

Reading about databases is not the same as solving problems about them. This lesson collects nine exercises, covering every major area of the course, each with a worked solution. Every solution is also a live example, so you can run it, change the inputs and watch the answer move.

The method that works best: read the problem, close the page, and try it on paper for a few minutes. Only then look at the live code and the explanation. Getting a problem wrong and seeing why teaches more than reading a correct answer.

Nine exercises, four themes

Modelling ER to tables, then algebra and SQL.
Design theory Closure, keys and normal forms.
Concurrency Serializability by precedence graph.
Storage and recovery B+ trees, then redo and undo.
1 / 2

Part 1: modelling

Exercise 1: from ER to tables

A clinic keeps patients (id, name, birth date) and doctors (id, name, specialty). A patient can see many doctors, a doctor sees many patients, and each visit has a date and an optional diagnosis. The same patient may see the same doctor on several different days. Map this to tables, choosing the keys.

Solution. patient and doctor are strong entities, so each becomes a table with its own key. The relationship "sees" is many-to-many, so it becomes a table of its own holding the two foreign keys plus the relationship attribute (the diagnosis). The subtle part is the key. (patient_id, doctor_id) alone would forbid a second visit, which the problem allows. Adding visit_date makes the key (patient_id, doctor_id, visit_date). This follows the mapping rules from Mapping ER Diagrams to Tables. If the clinic could book two visits on one day, you would need an artificial appointment_id instead.

SQL Exercise 1: the clinic schema

Press Run (or Ctrl + Enter) to see the result here.

The query shows the three valid visits. The last statement is rejected on purpose, because it repeats a full key, so the runner ends with a constraint error: that failure proves the key does its job.

Exercise 2 to 5: algebra and SQL on one dataset

Use the tables student(sid, name), course(cid, title) and enrolled(sid, cid, grade). Write each query in relational algebra first, then in SQL:

  1. The names of students enrolled in DB.
  2. The students with no enrollment at all.
  3. The students enrolled in every course.
  4. The number of courses per student, including students with zero.

Solutions.

  1. Algebra: ฯ€ name (ฯƒ cid='DB' (student โ‹ˆ enrolled)). Select first or join first gives the same result, and an optimizer would push the selection down (Algebraic Equivalence and Heuristic Optimization).
  2. Algebra: ฯ€ sid (student) โˆ’ ฯ€ sid (enrolled) followed by a join back to get names. In SQL that difference is an antijoin, written with NOT EXISTS.
  3. This is division: ฯ€ sid, cid (enrolled) รท ฯ€ cid (course). SQL has no division operator, so it is written as "there is no course for which the student has no enrollment", a double NOT EXISTS. See Division, Aggregation and Extended Operators.
  4. A plain join would lose students with no row in enrolled, so use a LEFT JOIN. The trap is COUNT(*), which would count the one null-extended row as 1; COUNT(e.cid) ignores nulls and gives 0.
SQL Exercises 2 to 5: four queries

Press Run (or Ctrl + Enter) to see the result here.

The four result sets are: Ana, Bo and Cy for exercise 2; Di for exercise 3; Ana only for exercise 4 (she is the only one with all three courses); and the counts 3, 2, 1 and 0 for exercise 5. Change 'DB' in the first query, or delete one of Ana's enrollments, and predict the new answers before running.

Part 2: design theory

Exercise 6: closure, keys and normal form

Let R(A, B, C, D, E) have the dependencies AB -> C, C -> D, D -> A, E -> B.

  • (a) Compute the closures of AB and EC.
  • (b) Find all candidate keys.
  • (c) What is the highest normal form of R? Justify it.

Solution. (a) Starting with AB: AB -> C adds C, then C -> D adds D, then D -> A adds nothing new. The closure is ABCD, which lacks E. For EC: E -> B adds B; C -> D adds D; D -> A adds A; now AB is present, so AB -> C holds, and the closure is all five attributes.

(b) E never appears on a right side, so it belongs to every key. The cycle A -> ... -> D -> A (via AB -> C -> D -> A) lets different attributes complete the key: AE, CE and DE all work (try AE: E gives B, then AB -> C, then D). BE does not work because nothing derives A. So the candidate keys are AE, CE and DE.

(c) The prime attributes are A, C, D, E; the only non-prime one is B. The dependency E -> B has the determinant E, a proper part of every key, and a non-prime right side: that is a partial dependency, so R is not even in 2NF. It is in 1NF only. The method comes from Attribute Closure, Keys and Minimal Cover and 1NF, 2NF and 3NF.

Python Exercise 6: check the answer in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

To fix the design, run 3NF synthesis on the minimal cover (it is already minimal): one relation per dependency gives ABC, CD, DA and BE, and because none of them contains a candidate key, a fifth relation AE is added. The result is lossless and keeps every dependency. Check it with the chase from the normalization toolkit project.

Part 3: transactions and concurrency

Exercise 7: serializability

Decide whether each schedule is conflict serializable. If it is, give an equivalent serial order. Ri(X) and Wi(X) mean transaction i reads or writes item X.

  • S1: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B)
  • S2: R1(A) R2(A) W1(A) W2(A)
  • S3: R1(A) W2(A) R3(A) W1(B) R3(B) W3(B) R2(B)

Solution. Draw an edge Ti -> Tj whenever an operation of Ti conflicts with a later operation of Tj on the same item (different transactions, at least one write). A cycle means the schedule is not conflict serializable (Schedules, Serializability and Precedence Graphs).

  • S1 has only edges T1 -> T2 (on A). No cycle, so it is equivalent to T1 then T2. Interleaving R1(B) W1(B) after T2 finishes with A is harmless because T2 never touches B.
  • S2 has R1(A) ... W2(A) giving T1 -> T2, and R2(A) ... W1(A) giving T2 -> T1. That is a cycle: both read the old value, so each overwrites the other's update (a lost update).
  • S3 has T1 -> T2, T2 -> T3, T1 -> T3, but also W3(B) before R2(B), giving T3 -> T2. The pair T2 <-> T3 is a cycle.
Python Exercise 7: precedence graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 4: storage and recovery

Exercise 8: B+ tree insertion

Insert the keys 10, 20, 5, 6, 12, 30, 7, 17 in this order into an empty B+ tree where a node may hold at most 3 keys. A node that gets a fourth key splits: a leaf keeps the left half and copies the first key of the right half up; an inner node pushes its middle key up. Draw the final tree.

Solution. The first three keys fill the root leaf as [5 10 20]. Inserting 6 overflows it to [5 6 10 20], which splits into [5 6] and [10 20] with 10 copied up into a new root: the tree grows to height two. Keys 12 and 30 fit into the right leaf, and 30 overflows it: [10 12 20 30] splits into [10 12] and [20 30] with 20 copied up, so the root is [10 20]. The keys 7 and 17 land in the left and middle leaves without any further split. The final tree has root [10 20] and leaves [5 6 7], [10 12 17], [20 30]. The mechanics are in B-Trees and B+ Trees. The tree grew taller only once, when the single root leaf split and a new root was created above it; that is why all leaves of a B+ tree always sit at the same depth.

Python Exercise 8: watch the splits happen

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Exercise 9: redo and undo

The log below was found after a crash. T1 committed; T2 and T3 had not. The disk shows A=100, B=250, C=300. Using a repeat-history approach (redo everything, then undo the losers), what are the final values?

Solution. The committed set is , so T2 and T3 are losers. The redo pass applies every update in log order regardless of who made it: afterwards A=40, B=250 and C=330. This restores the exact state at the crash even for updates that never reached the disk. The undo pass then walks the log backwards and restores before-images for the losers: C goes back to 310 (undoing T2), A to 90 (undoing T3), B to 200 (undoing T2). The final state is A=90, B=200, C=310, which contains only T1's effects. Notice that the undo order matters: T3 wrote A after T1, so we must restore T1's value of 90, not the original 100. See Checkpoints, ARIES and Backups for how real systems do this with LSNs.

Python Exercise 9: redo then undo

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where to practice next

If an exercise was hard, return to its lesson and rewrite the solution in your own words. Then invent a variant: change a dependency in exercise 6, reorder two operations in exercise 7, or insert the keys of exercise 8 in descending order and see how the tree differs. Variation is the quickest route to real understanding, and the projects (Project: Build a Mini Database Engine and Project: A Normalization Toolkit) let you apply these skills to bigger tasks.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is (patient_id, doctor_id, visit_date) used as the key of the appointment table instead of (patient_id, doctor_id)?

    A two-column key would allow only one visit per patient-doctor pair. Adding the date allows repeated visits on different days while still rejecting exact duplicates.
  2. 2. Which SQL pattern expresses the relational division 'students enrolled in every course'?

    Division is a 'for all' query. SQL has no division operator, so 'for all' is written as 'there is no counterexample' with two nested NOT EXISTS.
  3. 3. In exercise 7, why is S2 not conflict serializable?

    R1(A) before W2(A) gives T1 -> T2, and R2(A) before W1(A) gives T2 -> T1. A cycle means no serial order is equivalent.
  4. 4. In the redo/undo exercise, why does recovery redo updates of uncommitted transactions before undoing them?

    Repeating history makes the disk match the log at the crash moment. Then rolling back the losers in reverse order restores the right before-images.

Summary

  • Many-to-many relationships become tables whose key combines the foreign keys, plus whatever else makes a row unique (like the visit date).
  • "For all" queries are division, written in SQL with a double NOT EXISTS; use COUNT(column) after a LEFT JOIN so missing rows count as zero.
  • Closure gives keys; keys give prime attributes; prime attributes decide 2NF, 3NF and BCNF violations.
  • A schedule is conflict serializable exactly when its precedence graph has no cycle.
  • A B+ tree grows only by splitting, and the root splits last, so all leaves stay at the same depth.
  • Repeat-history recovery redoes everything in log order and then undoes the losers in reverse.

Next: DBMS Interview Questions.