GATE Databases questions come back in a small number of shapes. For each shape: the cue in the question, the fastest method, and the lesson that teaches it.
| # | Pattern (cue) | Fastest method | Lesson | ||
|---|---|---|---|---|---|
| 1 | "minimum number of tables" for an ER diagram | M:N → table; 1:N → FK on N side; 1:1 both total → merge; + multivalued + weak | Lesson 2.4.2 | ||
| 2 | "number of superkeys" | find keys; inclusion–exclusion over supersets 2ⁿ⁻ | K | Lesson 2.2.1 | |
| 3 | "tuples deleted by cascade" | follow child pointers until nothing new | Lesson 2.3.2 | ||
| 4 | "number of tuples" of an RA expression | project removes duplicates; natural join matches all common names | Lesson 3.1.3 | ||
| 5 | "students who took every …" | division or double NOT EXISTS; watch empty divisor | Lesson 3.1.5 | ||
| 6 | SQL with NULL | F wins AND, T wins OR; NOT IN with NULL → nothing; COUNT(*) vs COUNT(col) | Lesson 3.3.4 | ||
| 7 | correlated subquery output | trace table: outer row → inner result → condition | Lesson 3.3.9 | ||
| 8 | "all candidate keys" | never-on-right attributes first, then grow; closure | Lesson 4.2.3 | ||
| 9 | "highest normal form" | keys → prime set → classify each FD | Lesson 4.4.5 | ||
| 10 | "lossless / dependency preserving" | common⁺ ⊇ a side; chase for 3+; piecewise closure | Lesson 4.3.1 | ||
| 11 | "minimal cover / number of FDs" | split → shrink LHS → drop redundant | Lesson 4.2.5 | ||
| 12 | "block accesses with an index" | entries by index type → index blocks → ⌈log₂⌉ + 1, or levels + 1 | Lesson 5.3.3 | ||
| 13 | "order of B / B+ tree" | pP + (p−1)K (+ (p−1)Pr for B-tree) ≤ B; leaf: p(K+Pr) + P ≤ B | Lesson 5.6.2 | ||
| 14 | "insert keys into B / B+ tree" | split, median up (B) / copy up (B+ leaf) | Lesson 5.6.3 | ||
| 15 | "conflict serializable?" | precedence graph, look for a cycle | Lesson 6.4.2 | ||
| 16 | "view serializable?" | CS? else blind writes? else check reads-from and final writes | Lesson 6.4.3 | ||
| 17 | "recoverable / cascadeless / strict" | commit order / read after commit / no touch before commit | Lesson 6.5.1 | ||
| 18 | "who waits / dies / wounds" | smaller TS = older; wait-die: old waits; wound-wait: old wounds | Lesson 6.6.4 | ||
| 19 | "timestamp ordering trace" | read: TS < WTS → abort; write: TS < RTS or TS < WTS → abort (Thomas ignores the second) | Lesson 6.7.1 |
Time budget in the exam
1-mark questions: under 90 seconds. 2-mark questions: under 3 minutes. If a 2-mark NF or key question is taking longer, you skipped the "never on the right" step.
10 questions · 19 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1 · NAT · 2 mark(s) — Pattern 1
Entity sets A, B, C, D: A—B is M:N, B—C is 1:1 with B total and C partial, C—D is 1:N. No multivalued attributes. Minimum tables?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Pattern 2
R(A, B, C, D) has candidate keys {A, B} and {C, D}. How many superkeys?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Pattern 4
How many tuples are in πname(STUDENT ⋈ ENROLL ⋈ COURSE) (natural joins, 5-row STUDENT)?
Numerical answer: ________
Q4 · NAT · 2 mark(s) — Pattern 8
R(A, B, C, D, E, F), F = {A → B, B → C, C → D, D → E, E → A}. How many candidate keys?
Numerical answer: ________
Q5 · MCQ · 2 mark(s) — Pattern 9
R(A, B, C, D), F = {AB → C, BC → D, CD → A}. Highest normal form?
- (A) 1NF
- (B) 2NF
- (C) 3NF
- (D) BCNF
Q6 · NAT · 2 mark(s) — Pattern 12
A secondary index on a key field of a file with 1,000,000 records; K = 12, P = 4, B = 1024. Block accesses through the multilevel index?
Numerical answer: ________
Q7 · NAT · 2 mark(s) — Pattern 13
B = 1024, K = 10, P = 8, Pr = 8. Order p of a B-tree (max children)?
Numerical answer: ________
Q8 · MCQ · 2 mark(s) — Pattern 15
S = R1(A) W2(A) W1(A) R2(B) W1(B). Conflict serializable?
- (A) Yes, T1, T2
- (B) Yes, T2, T1
- (C) No
- (D) Yes, both
Q9 · NAT · 2 mark(s) — Pattern 19
TS(T1) = 1, TS(T2) = 2, TS(T3) = 3. Basic TO on R2(A) W1(A) R3(B) W2(B) W3(A). How many transactions abort?
Numerical answer: ________
Q10 · MCQ · 1 mark(s) — Pattern 18
Wound-wait. TS(T1) = 10 holds item Q; T2 with TS 5 requests Q. What happens?
- (A) T1 is wounded (rolled back)
- (B) T1 waits
- (C) T2 waits
- (D) T2 dies
✓Answer Vault
Reveal answers when you’re ready
Q1 Answer: 5 · 2 mark(s)
A, B, C, D (4) + M:N (1). 1:1 with only one side total does not merge.
Re-read: Lesson 2.4.2 — Mapping 1:1, 1:N, M:N with participation; minimum number of tables
Q2 Answer: 7 · 2 mark(s)
Contain AB: 4. Contain CD: 4. Contain ABCD: 1. 4 + 4 − 1.
Re-read: Lesson 2.2.1 — Superkey, candidate key, primary key, alternate key; counting superkeys
Q3 Answer: 4 · 2 mark(s)
Common attributes include dept: only own-department enrolments survive: Asha, Bhavin, Chirag, Diya.
Re-read: Lesson 3.1.3 — Cartesian product, theta join, equijoin, natural join
Q4 Answer: 5 · 2 mark(s)
F is never on the right; AF, BF, CF, DF, EF all reach everything.
Re-read: Lesson 4.2.3 — Attribute closure; all candidate keys; prime vs non-prime; counting superkeys
Q5 Answer: (C) · 2 mark(s)
Keys AB, BC (B is never on the right). Prime: A, B, C. BC → D: superkey. CD → A: CD is not a superkey, but A is prime. 3NF, not BCNF.
- (A) is wrong: No partial dependency on a non-prime attribute.
- (B) is wrong: Every FD passes 3NF.
- (D) is wrong: CD → A fails BCNF.
Re-read: Lesson 4.4.5 — Drill: highest normal form of a given relation
Q6 Answer: 5 · 2 mark(s)
fo = ⌊1024/16⌋ = 64. Levels: 1,000,000/64 = 15,625 → 245 → 4 → 1: 4 levels (64³ < 10⁶ ≤ 64⁴); cost 4 + 1 = 5.
Re-read: Lesson 5.3.3 — Multilevel indexes; fan-out; logarithm primer
Q7 Answer: 40 · 2 mark(s)
8p + 18(p − 1) ≤ 1024 → 26p ≤ 1042 → p = 40 (26 × 40 = 1040).
Re-read: Lesson 5.5.1 — B-tree structure and order (order conventions and the GATE trap)
Q8 Answer: (C) · 2 mark(s)
R1(A) before W2(A): T1 → T2. W2(A) before W1(A): T2 → T1. Cycle.
- (A) is wrong: T2 → T1 exists.
- (B) is wrong: T1 → T2 exists.
- (D) is wrong: No.
Re-read: Lesson 6.4.2 — Conflict serializability: conflicting ops, precedence graph, equivalent serial orders
Q9 Answer: 2 · 2 mark(s)
W1(A): 1 < RTS(A) = 2 → T1 aborts. W2(B): 2 < RTS(B) = 3 → T2 aborts. W3(A) succeeds.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule
Q10 Answer: (A) · 1 mark(s)
T2 is older: it wounds the younger holder.
- (B) is wrong: T1 holds the lock.
- (C) is wrong: Older requesters do not wait in wound-wait.
- (D) is wrong: That is wait-die for a younger requester.
Re-read: Lesson 6.6.4 — Deadlocks: wait-for graph, wait-die, wound-wait, starvation