Formula Vault · DBMS

Database Management

Sheet 1

ER Model & Normalization

2 formulas

Core concepts

Candidate key: minimal superkey (no proper subset also determines all attributes)
1NF: all attributes atomic. 2NF: 1NF + no partial dependency
3NF: 2NF + no transitive dependency. BCNF: every non-trivial FD X->Y has X as a superkey

Key formulas

Functional Dependency ☆

\[ X \to Y \]

X determines Y

Attribute Closure ☆

\[ X^{+} \]

everything functionally determined by X

Test your recall

Can you recall the attribute closure formula?

Reveal formula

\[ X^{+} \]

GATE traps 4 traps

BCNF is strictly stronger than 3NF

BCNF is strictly stronger than 3NF -- every BCNF relation is in 3NF but not vice versa. The classic 3NF-but-not-BCNF case involves overlapping composite candidate keys, a recurring GATE numerical.

3NF can preserve both properties

BCNF decomposition is always lossless but NOT always dependency-preserving -- 3NF decomposition can always achieve BOTH lossless join and dependency preservation. This tradeoff is directly and frequently tested.

Check minimality for candidate keys

A minimal superkey qualifies as a candidate key only if removing ANY single attribute breaks the closure -- skipping this minimality check is the most common error when finding candidate keys.

Every candidate key's attributes are prime

A relation can have multiple candidate keys -- only one becomes the primary key, but attributes in ANY candidate key count as 'prime' for normalization purposes.

Sheet 2

SQL & Relational Algebra

Core concepts

Selection (sigma) filters rows; Projection (pi) filters columns and removes duplicates
Natural join matches automatically on common attribute names; theta join uses an explicit condition
Division (no direct SQL keyword) finds X related to ALL Y -- done via double NOT EXISTS
SQL NULL comparisons yield UNKNOWN, not TRUE/FALSE; NULL <> NULL is UNKNOWN, not TRUE

GATE traps 4 traps

WHERE filters rows, HAVING filters groups

WHERE filters rows BEFORE grouping; HAVING filters groups AFTER aggregation -- using HAVING where WHERE would work (or the reverse when aggregates are involved) is one of the most common SQL-writing mistakes.

COUNT(*) vs COUNT(column)

COUNT(*) counts every row including NULLs; COUNT(column) skips NULLs in that column -- a frequently tested subtlety that silently changes the numeric answer.

Natural join can silently misfire

Natural join matches on ALL identically-named columns automatically -- if two tables happen to share a column name that isn't meant to be a join key, natural join silently gives wrong results; theta join with explicit conditions avoids this.

Division needs nested NOT EXISTS

There's no single SQL keyword for relational division -- translating a 'related to ALL Y' query into nested NOT EXISTS is a genuinely tricky pattern worth memorizing as a template.

Sheet 3

Transactions & Concurrency Control

Core concepts

ACID: Atomicity, Consistency, Isolation, Durability
Conflicting operations: same data item, at least one is a write
Precedence graph acyclic <=> schedule is conflict-serializable
2PL: growing phase (acquire only) then shrinking phase (release only) -- guarantees serializability
Strict 2PL: all locks held until commit/abort -- additionally prevents cascading rollback

GATE traps 4 traps

Check serializability via precedence graph

Conflict-serializability is checked by building the precedence graph from conflicting operations and testing for a cycle -- a mechanical, frequently tested procedure.

2PL doesn't prevent deadlock

2PL guarantees serializability but does NOT prevent deadlock -- in fact 2PL can itself cause deadlock. Serializability and deadlock-freedom are commonly confused as the same guarantee; they aren't.

View-serializable is weaker

View-serializability is WEAKER (more permissive) than conflict-serializability -- every conflict-serializable schedule is view-serializable but not the reverse. GATE sometimes gives a schedule that's view- but not conflict-serializable as a trick.

Strict 2PL avoids cascading rollback

Strict 2PL avoids cascading rollback because no transaction can read/write data written by an uncommitted transaction -- plain 2PL only guarantees serializability, not this extra property.

Sheet 4

Indexing & File Organization

3 formulas

Core concepts

B-Tree/B+-Tree order p = the maximum number of children a node can have; every node except the root must be at least half full
B+-Tree stores all keys/records in leaf nodes, linked in sorted order for range scans; a B-Tree stores keys and data at every level

Key formulas

B-Tree Order Bound ☆

\[ p \cdot P + (p-1) \cdot K \le B \]

P=pointer, K=key, B=block size; solve for the largest integer p

Keys per Non-Root Node ☆

\[ \lceil p/2 \rceil - 1 \ \text{ to } \ p-1 \]

B-Tree Height (worst case) ☆

\[ h \le \log_{\lceil p/2 \rceil}\left(\frac{n+1}{2}\right) \]

n = number of keys

Test your recall

Can you recall the b-tree order bound formula?

Reveal formula

\[ p \cdot P + (p-1) \cdot K \le B \]

GATE traps 4 traps

B+-trees win on range queries

B+-trees are preferred over B-trees for range queries and full scans, since all records live in leaf nodes linked in sorted order -- a B-tree has records scattered across internal levels and needs a full in-order traversal instead.

Solve for the largest p, don't round up

The order formula p.(pointer size) + (p-1).(key size) <= block size must be solved for the LARGEST integer p satisfying it, not rounded up -- rounding up would let a node overflow its block.

Minimum children is a ceiling, not p/2

Every non-root node must have at least ceil(p/2) children (ceil(p/2)-1 keys) -- a node with fewer triggers a merge/redistribution on deletion, and GATE numericals on minimum keys hinge on this ceiling, not a plain p/2.

Insert splits up, delete merges/borrows

Insertion that overflows a node SPLITS it and pushes the middle key up to the parent; deletion that underflows a node borrows from a sibling or merges with one -- confusing which direction applies to insert vs. delete is a common trace error.