GATE-style DBMS Problems Explained

By the end of this lesson you will have solved ten exam-style problems that cover the most frequently tested DBMS topics, and you will have a short method for each type. Every problem here is original. Try each one yourself before reading the solution; the method matters more than the answer.

How to use this lesson

GATE DBMS questions reward a fixed method more than clever insight. For each problem type below you get: the problem, a numbered method, and a worked solution. If a step feels unfamiliar, the linked lesson explains it fully. A good plan is to cover the solution with your hand, solve the problem on paper, then check.

Problem 1: counting super keys

R(A, B, C, D, E) has exactly two candidate keys: {A, B} and {B, C}. How many super keys does R have?

Method (from Keys): count supersets of each key and subtract the overlap.

Supersets of {A, B}:        the other 3 attributes are free → 2^3 = 8
Supersets of {B, C}:        2^3 = 8
Supersets of {A, B, C}:     counted twice → 2^2 = 4
Super keys = 8 + 8 − 4 = 12

Answer: 12.

Problem 2: finding candidate keys

R(P, Q, R, S, T, U) with F = { P → Q, QR → S, S → P, T → U }. Find all candidate keys.

Method (from Attribute Closure & Canonical Cover):

1. Attributes never on a right side must be in every key: R and T.
2. (RT)⁺ = {R, T, U}. Not a key, so add one more attribute at a time.

(PRT)⁺: P → Q, QR → S, T → U         = {P, Q, R, S, T, U}   key
(QRT)⁺: QR → S, S → P, T → U         = all                   key
(SRT)⁺: S → P, P → Q, T → U          = all                   key
(URT)⁺: = {R, T, U}                                           not a key

Answer: PRT, QRT and RST. P, Q and S form a cycle (P → Q, QR → S, S → P), so each can play the same role.

Problem 3: highest normal form

Continue with R and F from Problem 2. What is the highest normal form?

Method (from Normal Forms: 1NF, 2NF & 3NF): list prime attributes, then look for a partial dependency of a non-prime attribute.

Prime: P, Q, R, S, T       Non-prime: U
T → U: T is part of key PRT, and U is non-prime  → partial dependency

Answer: 1NF (not 2NF).

Problem 4: 3NF but not BCNF

R(A, B, C, D) with F = { A → B, B → A, AC → D }. Highest normal form?

Keys: C is never on a right side.  (AC)⁺ = {A, B, C, D}, (BC)⁺ = {A, B, C, D}
Candidate keys: AC, BC        Prime: A, B, C      Non-prime: D

AC → D: AC is a super key                       fine for BCNF
A → B:  A is not a super key, but B is prime    allowed in 3NF, breaks BCNF
B → A:  same reasoning

Answer: 3NF (see BCNF, 4NF & 5NF).

Problem 5: lossless join

R(A, B, C, D, E) with F = { A → B, C → D, AC → E }. Is the decomposition {AB, CD, ACE} lossless? Is {AB, CDE} lossless?

Method (from Lossless Join & Dependency Preservation): join two pieces at a time and check the common attributes.

{AB, CD, ACE}:
  AB ⋈ ACE: common = {A}, A → B, so A is a key of AB         lossless → ABCE
  ABCE ⋈ CD: common = {C}, C → D, so C is a key of CD         lossless → ABCDE
  LOSSLESS (and each FD sits inside one piece, so dependencies are preserved too)

{AB, CDE}:
  common = {} (no shared attribute)                         LOSSY

Answer: {AB, CD, ACE} is lossless; {AB, CDE} is not.

Problem 6: conflict serialisability

Schedule S: R1(X) R2(Y) R3(Z) W2(Y) R1(Y) W3(Z) R2(Z). Is S conflict serialisable? How many serial schedules is it conflict equivalent to?

Method (from Schedules, Serialisability & Recoverability): find conflicting pairs, draw edges, look for cycles, count topological orders.

On Y: W2(Y) before R1(Y)       → T2 → T1
On Z: W3(Z) before R2(Z)       → T3 → T2
On X: only T1 touches X        → no edge

Graph: T3 → T2 → T1      no cycle
Topological orders: only T3, T2, T1

Answer: yes, conflict serialisable, equivalent to exactly 1 serial schedule (T3, T2, T1).

Problem 7: recoverability

Classify W1(A) R2(A) W2(B) C2 C1 and W1(A) R2(A) W2(B) C1 C2.

Both: T2 reads A written by uncommitted T1 (a dirty read)  → not cascadeless, not strict

First:  T2 commits before T1     → NOT recoverable
Second: T1 commits before T2     → recoverable (but cascading rollback is possible)

Answer: the first is not recoverable; the second is recoverable but not cascadeless.

Problem 8: B+ tree order

Block size 4,096 bytes, search key 16 bytes, block pointer 8 bytes, record pointer 8 bytes. Find the maximum order of a B+ tree internal node and leaf node.

Method (from B-Trees, B+ Trees & Hashing):

Internal: 8p + 16(p − 1) ≤ 4096  →  24p ≤ 4112  →  p = 171
Leaf:     p_leaf(16 + 8) + 8 ≤ 4096  →  24 p_leaf ≤ 4088  →  p_leaf = 170

Answer: internal order 171, leaf order 170.

Problem 9: index block accesses

A file has 1,20,000 records of 120 bytes in 4,096-byte blocks (unspanned). A dense multilevel secondary index is built on a unique 12-byte field with 8-byte block pointers. How many block accesses does an equality search need? Compare with binary search on the data file if it were sorted on that field.

Method (from File Organisation & Indexing):

bfr = floor(4096 / 120) = 34            data blocks = ceil(120000 / 34) = 3,530
fo  = floor(4096 / 20)  = 204           index entries = 1,20,000 (dense)
Level 1 = ceil(120000 / 204) = 589 blocks
Level 2 = ceil(589 / 204)    = 3 blocks
Level 3 = ceil(3 / 204)      = 1 block
Search = 3 index levels + 1 data block = 4 accesses
Binary search on 3,530 sorted blocks = ceil(log2 3530) = 12 accesses

Answer: 4 block accesses with the multilevel index, against 12 for binary search.

Problem 10: predicting SQL results

GATE often shows a query and asks how many rows it returns. Two classic traps: outer joins and NOT IN with NULL.

Part (a): on the practice database, how many rows does this return? Every order has a customer, and exactly one customer (Divya) has no orders.

SELECT COUNT(*) AS result_rows
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.customer_id;

result_rows
-----------
16
(1 row)

Reasoning: 15 orders each match one customer, giving 15 rows, plus 1 row for Divya with NULLs: 16.

Part (b): table blocked(id) holds 2, 5 and NULL. How many products have an ID not in that list?

CREATE TABLE blocked (id INTEGER);
INSERT INTO blocked VALUES (2), (5), (NULL);

SELECT COUNT(*) AS not_in_count
FROM products
WHERE product_id NOT IN (SELECT id FROM blocked);

SELECT COUNT(*) AS not_exists_count
FROM products p
WHERE NOT EXISTS (SELECT * FROM blocked b WHERE b.id = p.product_id);

not_in_count
------------
0
(1 row)

not_exists_count
----------------
10
(1 row)

You should see 0 and then 10. x NOT IN (2, 5, NULL) means x <> 2 AND x <> 5 AND x <> NULL. The last part is UNKNOWN for every x, so no row passes. NOT EXISTS ignores the NULL row, so it returns the 10 products whose ID is neither 2 nor 5. This is the three-valued logic from SQL: The Practical Side of DBMS.

A quick reference of methods

Common mistakes

• Rounding the wrong way. Orders and blocking factors use floor; block counts and levels use ceil.
• Ignoring other candidate keys. A normal form check must use every key to know which attributes are prime.
• Forgetting the data block. Index searches cost index levels plus one data access.
• Assuming NOT IN and NOT EXISTS always agree. They differ when the subquery returns NULL.

Key points

• Most DBMS exam problems follow a fixed method; practise the method, not the answer.
• Closure is the key tool for keys, FD implication, normal forms and lossless checks.
• Precedence graphs answer serialisability; commit order answers recoverability.
• Block arithmetic: floor for how many fit, ceil for how many are needed.
• Read SQL questions for NULLs and outer joins before counting rows.

(a) Z never appears on a right side.  Z⁺ = {Z, W}.
    (VZ)⁺: Z → W, VW → X, X → Y      = all      key
    (XZ)⁺: X → Y, Y → V, Z → W        = all      key
    (YZ)⁺: Y → V, Z → W, VW → X       = all      key
    (WZ)⁺ = {W, Z}                               not a key
    Candidate keys: VZ, XZ, YZ

(b) Prime: V, X, Y, Z.  Non-prime: W.
    Z → W: Z is part of key VZ and W is non-prime → partial dependency.  Highest: 1NF

(c) Super keys contain Z plus at least one of V, X, Y; W is free.
    Subsets of {V, X, Y} that are non-empty: 2^3 − 1 = 7; W in or out: × 2
    Super keys = 14