Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 77 ยท Databases and Data Interview Questions

DBMS Concepts: ER Model, Keys, Normal Forms and Schedules

Prepare DBMS theory interviews: ER diagrams to tables, keys, functional dependencies, BCNF, serializable schedules, two-phase locking and write-ahead logging.

Campus and early-career interviews often include a pure database-theory round. The questions are not about writing a query. They ask: "What is a candidate key?", "Why is this table not in third normal form?", "Is this schedule serializable?", "What does the log do when the server crashes?" The interviewer wants to see that you can reason from definitions and finish with a clear example.

Databases: Indexes, Normalization and Transactions already covers B-trees, ACID, isolation levels and deadlocks, so this lesson concentrates on the theory it does not: the ER model, the hierarchy of keys, functional dependencies and normal forms, schedules and serializability, and recovery. The SQL examples run in the in-browser SQLite runner; the dependency and schedule checks run in the Python runner. Server-only behaviour (locks, write-ahead log files) is described in plain text and marked read-only.

DBMS theory in one picture

ER model Entities, attributes, relationships.
Keys Which columns identify a row.
Normal forms Remove redundancy by dependency.
Schedules Safe orderings of transactions.

Every answer starts from a definition.

1 / 2

What is the ER model and how does it become tables?

Short answer: The entity-relationship model describes data as entities (things with an identity, such as Student), their attributes (properties such as name), and relationships between entities (enrolls in). A relationship has a cardinality: one-to-one, one-to-many or many-to-many. Converting an ER diagram to a relational schema follows a few mechanical rules.

  • Entity โ†’ table. Attributes become columns; a key attribute becomes the primary key.
  • One-to-many: put the key of the "one" side as a foreign key in the "many" table (a department has many employees, so employee.department_id).
  • One-to-one: put a foreign key in either table with a UNIQUE constraint (or merge the tables).
  • Many-to-many: create a junction table whose primary key is the pair of foreign keys; it also holds attributes of the relationship (a student's grade in a course).
  • Weak entity (no key of its own, such as Dependent of an Employee): its table's key is the owner's key plus a partial key, and the foreign key is part of the primary key.
  • Multivalued attribute (a person's phone numbers) becomes its own table. A derived attribute (age from birth date) is usually computed, not stored.
SQL Many-to-many as a junction table, with enforced keys

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

The last statement fails with a constraint error: the composite primary key means a student can be enrolled in a course only once. A foreign key violation (enrolling student 99) fails the same way once PRAGMA foreign_keys = ON is set, which SQLite needs explicitly.

What are the different kinds of keys?

Short answer: A super key is any set of attributes that uniquely identifies a row. A candidate key is a minimal super key: remove any attribute and it stops being unique. The primary key is the candidate key you choose; the other candidates are alternate keys. A foreign key refers to a key in another table. A composite key has more than one attribute. A surrogate key is an artificial identifier (an auto-increment id) with no business meaning.

An example: in Employee(emp_id, email, name, dept), both emp_id and email are candidate keys; so is any superset like (emp_id, name) a super key but not a candidate, since name is redundant. If we choose emp_id as primary, email is an alternate key.

Questions with functional dependencies (next section) ask you to find all candidate keys. The method: attributes that never appear on the right side of any dependency must be in every key; compute the closure of that set; add more attributes only if the closure is incomplete.

What are functional dependencies and normal forms?

Short answer: A functional dependency X โ†’ Y means that whenever two rows agree on X they agree on Y (an employee id determines the employee's name). The closure Xโบ is the set of all attributes that X determines, found by repeatedly applying the dependencies. A set X is a super key exactly when Xโบ contains every attribute.

The normal forms use dependencies to remove redundancy:

Form Rule (informal)
1NF Every cell holds one atomic value; no repeating groups
2NF 1NF and no partial dependency: a non-key attribute depends on only part of a composite key
3NF 2NF and no transitive dependency: a non-key attribute depends on another non-key attribute
BCNF For every non-trivial X โ†’ Y, X is a super key

3NF allows X โ†’ Y when Y is part of a candidate key; BCNF does not, so BCNF is stricter. Every BCNF schema is in 3NF, but a decomposition into BCNF may lose some dependencies, while a 3NF decomposition can always preserve them and stay lossless.

Python Attribute closure, candidate keys and a BCNF check

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.

Read the output as you would in an interview. Neither A nor D appears on the right side of any dependency, so both are in every key, and AD already reaches every attribute: AD is the only candidate key. Each dependency has a left side that is not a super key, so all three violate BCNF.

To decompose, take a violating dependency X -> Y and split the relation into Xโบ and the rest plus X. Start with A -> B, where Aโบ = {A, B, C}: this gives R1(A, B, C) and R2(A, D, E). In R1, B -> C still violates BCNF (B is not a key of R1), so split again into (B, C) and (A, B). R2(A, D, E) is fine, since AD is its key and AD -> E holds through A -> B -> C and CD -> E. The final schema is (A, B), (B, C), (A, D, E). It is lossless, but CD -> E can no longer be checked inside one table: BCNF decomposition can lose a dependency, which is the price of the stricter form.

When asked to normalize, say the keys first, then list which dependency breaks which form, and finish with the decomposition. Then check lossless join (the shared attributes form a key of one side) and dependency preservation.

What is a schedule, and when is it serializable?

Short answer: A schedule is an interleaving of the operations of several transactions. It is serial if the transactions run one after another. A schedule is conflict serializable if it can be turned into a serial schedule by swapping adjacent, non-conflicting operations. Two operations conflict when they belong to different transactions, touch the same item, and at least one is a write.

The test is the precedence graph: draw a node per transaction, and an edge T1 โ†’ T2 whenever an operation of T1 conflicts with a later operation of T2. The schedule is conflict serializable if and only if the graph has no cycle. A topological order of the graph gives an equivalent serial order.

Python Precedence graph and cycle detection

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.

The lost-update schedule has edges both ways between the two transactions (each reads X before the other writes it), so the graph has a cycle and the schedule is not serializable. This is the classic reason databases need concurrency control.

How do locks give serializability, and what does recovery do?

This part is read-only because the site cannot run a real database engine.

Two-phase locking (2PL): every transaction has a growing phase (it may acquire locks, never release) followed by a shrinking phase (it may release, never acquire). Any schedule produced by 2PL is conflict serializable. Strict 2PL holds all write locks until commit, which prevents cascading rollbacks. Locks can create deadlock (T1 waits for T2 and T2 waits for T1); the system finds it as a cycle in the wait-for graph and aborts a victim.

Recovery uses a write-ahead log (WAL): before a changed page may be written to disk, the log record describing the change must be on stable storage. After a crash, the engine replays the log: it redoes the changes of committed transactions that never reached disk and undoes the changes of uncommitted ones. Checkpoints limit how far back recovery must read. This is how the "D" in ACID and the "A" survive a power cut.

Schemas, views, stored procedures, triggers, cursors and logs

This second half of the DBMS chapter covers architecture and database objects. The ER model, keys, normal forms and transactions above are the theory; these are the parts you meet when you actually run a database.

What is the three-schema architecture?

Short answer: it separates how data is stored from how it is seen, in three levels:

  • Internal (physical) schema: files, pages, indexes, storage structures.
  • Conceptual (logical) schema: the whole database for the organization: tables, columns, keys and constraints.
  • External schema (views): what one user or application sees, which may hide columns or combine tables.

The point is data independence. Physical data independence means you can change the internal level (add an index, move to different storage) without changing the conceptual schema or the queries. Logical data independence means you can change the conceptual level (add a column, split a table) without breaking external views and applications. Physical independence is common; full logical independence is harder to achieve.

What is a view, and what is a materialized view?

A view is a named, stored SELECT. It stores no rows: each time you query it the database runs the underlying query. Views simplify queries, hide columns (a security layer), and keep a stable interface while the tables underneath change. A view can be updatable if it maps cleanly to one base table (no GROUP BY, DISTINCT or aggregates); WITH CHECK OPTION then rejects an insert or update through the view that would produce a row the view itself could not show.

A materialized view stores the result on disk, so reads are fast, but it becomes stale until it is refreshed. PostgreSQL has CREATE MATERIALIZED VIEW and REFRESH MATERIALIZED VIEW; Oracle has them with fast refresh; MySQL and SQLite have none, so people build a summary table and refresh it themselves.

SQL
-- Read-only: PostgreSQL syntax (the in-page runner is SQLite)
CREATE VIEW cheap_books AS
  SELECT id, title, price FROM books WHERE price < 20
  WITH CHECK OPTION;                      -- INSERT INTO cheap_books ... price = 50 fails

CREATE MATERIALIZED VIEW sales_by_month AS
  SELECT date_trunc('month', sold_at) AS month, SUM(total) AS revenue
  FROM orders GROUP BY 1;
REFRESH MATERIALIZED VIEW sales_by_month; -- recompute when the data changed

The runnable example uses SQLite: an ordinary view that is always current, and a summary table that behaves like a materialized view and goes stale until you refresh it.

SQL A view stays current; a materialized copy goes stale

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

Stored procedures, functions and triggers

A stored procedure is a named block of SQL and procedural code kept and run inside the database (CALL month_end_close()). Benefits: fewer network round trips, one place for the logic, permission control (users may run the procedure without touching the tables). Costs: logic is harder to version, test and port between database products, and it adds load to the database server. A function returns a value and can be used inside a query; a procedure is called as a statement and may change data and manage transactions. Neither exists in SQLite, so they are shown read-only.

A trigger is code the database runs automatically on INSERT, UPDATE or DELETE, BEFORE or AFTER the change, for each row or each statement. Typical uses are audit logs, maintaining a derived column and enforcing a rule too complex for a CHECK constraint. Interview warning: triggers are invisible to the application, can cascade into other triggers, and make bulk loads slower, so use them sparingly and document them.

SQL
-- Read-only: a PostgreSQL function used as a trigger
CREATE FUNCTION touch_updated_at() RETURNS trigger AS $$
BEGIN
  NEW.updated_at := now();
  RETURN NEW;
END $$ LANGUAGE plpgsql;

CREATE TRIGGER books_touch BEFORE UPDATE ON books
  FOR EACH ROW EXECUTE FUNCTION touch_updated_at();

SQLite does support triggers, so an audit trigger can run in the page.

SQL An audit trigger fires on every update

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

What is a cursor?

A cursor lets procedural code walk through a query result one row at a time (DECLARE, OPEN, FETCH, CLOSE). It exists because loops in a stored procedure or an application need row-by-row access. It is also a classic performance trap: a cursor loop does one operation per row, while a single set-based UPDATE ... FROM or INSERT ... SELECT lets the optimizer handle everything at once. The usual interview answer is "use a cursor only when the work genuinely cannot be expressed as a set operation". Application drivers expose cursors as result-set iterators, and server-side cursors let you stream a huge result without loading all of it into memory.

Locks: granularity, intention and deadlocks

The two-phase locking story is above. Add these terms: granularity (row, page, table; finer locks allow more concurrency but cost more memory to track), shared (S) and exclusive (X) locks, and intention locks (IS, IX) placed on a table to announce that a transaction holds row locks inside it, so the database can quickly tell whether a whole-table lock conflicts. Lock escalation converts many row locks into one table lock to save memory. A deadlock (two transactions each waiting for the other's lock) is detected with a wait-for graph; the database aborts one victim, and your application should be ready to retry. Under MVCC (PostgreSQL, MySQL InnoDB) readers do not block writers because they read a snapshot.

Transaction log, recovery and backups

Databases use write-ahead logging (WAL): before a changed page may be written to the data file, the log record describing the change must be on stable storage. A commit is durable once its log records are flushed. After a crash, recovery redoes committed work missing from the data files and undoes uncommitted work. A checkpoint periodically writes dirty pages to disk so recovery has less log to replay.

Backup types: a full backup copies everything; a differential backup copies everything changed since the last full one; an incremental backup copies what changed since the last backup of any kind. Restore time grows as you chain more incrementals. Point-in-time recovery restores a full backup and replays the log up to a chosen moment (for example just before an accidental DROP TABLE). A backup you have never restored is not a backup.

How is a query processed?

The pipeline is: parse (syntax check, build a tree), bind/analyze (resolve table and column names, check permissions), optimize (choose a plan: which indexes, which join order, which join algorithm, using table statistics) and execute (run the plan, often as a tree of operators that pull rows from each other). You can ask the database for the chosen plan with EXPLAIN.

SQL Ask the optimizer for its plan, before and after an index

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

The first plan scans the whole table; the second searches the index. Exact wording differs between databases (Seq Scan versus Index Scan in PostgreSQL), but the idea is the same.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How do you represent a many-to-many relationship, such as students enrolling in courses, in a relational schema?

    A many-to-many relationship needs its own table holding both foreign keys (and any attributes of the relationship), usually with a composite primary key.
  2. 2. R(A,B,C,D,E) has A->B, B->C and CD->E. What is the candidate key?

    A and D never appear on a right-hand side, so both are in every key. The closure of AD is A, B, C, D, E, so AD is the only candidate key.
  3. 3. What is the difference between 3NF and BCNF?

    BCNF demands X is a super key for every non-trivial X -> Y. 3NF relaxes this when Y is a prime attribute, so BCNF is the stricter form.
  4. 4. How do you test a schedule for conflict serializability?

    Add an edge Ti -> Tj for each conflicting pair where Ti's operation comes first. The schedule is conflict serializable if and only if the graph is acyclic.
  5. 5. What does write-ahead logging guarantee?

    WAL orders log writes before data writes. Recovery uses the log to redo committed changes and undo uncommitted ones.

Summary

  • ER to tables: entity to table, one-to-many via a foreign key on the many side, many-to-many via a junction table, weak entities borrow the owner's key.
  • Super key identifies rows; candidate key is a minimal super key; primary key is the chosen candidate; the rest are alternate keys.
  • Xโบ is the closure of X; X is a super key when Xโบ is every attribute. Attributes never on a right-hand side belong to every key.
  • 2NF removes partial dependencies, 3NF removes transitive ones, BCNF requires every determinant to be a super key.
  • A schedule is conflict serializable if its precedence graph is acyclic.
  • Strict two-phase locking gives serializability with deadlock risk; write-ahead logging with redo and undo gives crash recovery.
  • The three-schema architecture gives physical and logical data independence; a view is a stored query, a materialized view stores the result and must be refreshed.
  • Triggers, stored procedures and cursors run inside the database; prefer set-based SQL to cursors, and use triggers sparingly.
  • Write-ahead logging, checkpoints and backups (full, differential, incremental, point-in-time) provide durability; EXPLAIN shows the plan the optimizer chose.

Next: NoSQL and Caching Questions.