Back to Study Material GATE Exam

Last Minute Notes DBMS

Relational model essentials: data is stored in tables (relations), rows are tuples, columns are attributes. Schema defines attribute names and domains. Ins...

Last Minute Notes DBMS

Quick Revision: Relational Model, Keys, and SQL Essentials

Relational model essentials: data is stored in tables (relations), rows are tuples, columns are attributes. Schema defines attribute names and domains. Instance is the actual data at a point in time. Null represents unknown or missing value.

Key types to memorize: superkey uniquely identifies tuples but may have redundant attributes. Candidate key is a minimal superkey. Primary key is the chosen candidate key. Foreign key references the primary key of another relation and enforces referential integrity. Prime attribute is one that belongs to at least one candidate key. Non-prime attribute does not belong to any candidate key.

Relational algebra operators: selection sigma filters rows by a condition. Projection pi selects specified columns. Natural join joins on all common attributes. Theta join is Cartesian product with a condition. Division finds tuples in one relation related to all tuples in another. The division operator is the most frequently forgotten but appears in GATE.

SQL must-knows: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY. Aggregate functions COUNT, SUM, AVG, MIN, MAX. NULL handling: IS NULL and IS NOT NULL predicates. Three-valued logic: true, false, unknown. WHERE rejects tuples with unknown condition.

JOIN types: INNER JOIN returns matched tuples only. LEFT JOIN returns all left tuples, null for unmatched right. RIGHT JOIN is symmetric. FULL OUTER JOIN returns all tuples from both sides.

Subquery types: correlated (references outer query, runs once per outer tuple), non-correlated (runs once). EXISTS returns true if subquery returns at least one row. IN tests membership. ANY and ALL for comparison with sets.

Index types: B-plus tree for range queries and equality, stores all data in leaves with linked leaf nodes. Hash index for equality only, not range queries. Clustered index physically orders data by index key, only one per table. Non-clustered index keeps a separate structure.

Common SQL pitfalls: GROUP BY must include all non-aggregated columns in SELECT. HAVING filters after grouping, WHERE filters before. COUNT of a column skips NULLs, COUNT star counts all rows including NULLs. ORDER BY uses position numbers or aliases.

Quick Revision: Normalization and Functional Dependencies

Functional dependency rules: reflexivity means if B is a subset of A then A determines B. Augmentation means if A determines B then AC determines BC. Transitivity means if A determines B and B determines C then A determines C. These three rules form Armstrong's Axioms and are sound and complete.

Derived rules from Armstrong's Axioms: union means if A determines B and A determines C then A determines BC. Decomposition means if A determines BC then A determines B and A determines C. Pseudotransitivity means if A determines B and CB determines D then CA determines D.

Closure computation: to find X-plus, start with X. For each dependency L goes to R where L is a subset of current closure, add R to closure. Repeat until no change. X is a superkey if closure equals all attributes.

Finding candidate keys algorithm: attributes only on right sides of all dependencies cannot be in any candidate key. Attributes only on left sides must be in every candidate key. Attributes on both sides may or may not appear. Start from attributes that must be in every key and compute closure. If closure is complete, that is a candidate key. Otherwise try adding one attribute at a time from the third category.

Normal form identification: 1NF requires atomic values. 2NF requires no partial dependency of non-prime attributes on a composite primary key. 3NF requires no transitive dependency of non-prime attributes through other non-prime attributes. BCNF requires every determinant to be a superkey.

3NF synthesis algorithm: compute canonical cover (minimal equivalent set of FDs). Create a relation for each dependency in the canonical cover. If no relation contains a candidate key, add one relation containing a candidate key. Remove any redundant relations. Result is lossless and dependency-preserving in 3NF.

Canonical cover: eliminate redundant attributes from left sides of dependencies (check if closure still same without each attribute). Eliminate redundant dependencies (check if dependency is derivable from others). Result has no extraneous attributes or redundant rules.

Lossless join test for binary decomposition into R1 and R2: check if R1 intersect R2 determines R1 minus R2, or R1 intersect R2 determines R2 minus R1. If either holds, decomposition is lossless. If neither holds, it is lossy.

Quick Revision: Transactions, Concurrency, and Indexing

ACID properties recap: Atomicity means all-or-nothing execution. Consistency means transactions preserve database integrity constraints. Isolation means concurrent transactions appear to run serially. Durability means committed changes survive failures.

Transaction states: active during execution, partially committed after last instruction, committed after successful completion, failed if normal execution cannot proceed, aborted after rollback. A committed transaction cannot be aborted. An aborted transaction is either restarted or killed.

Serializability: conflict serializability is the standard. Draw precedence graph: edge from Ti to Tj if Ti has an operation that conflicts with and precedes a Tj operation. Conflict means same data item and at least one write. Acyclic graph means conflict serializable. Cycle means not conflict serializable.

Two-phase locking: growing phase allows only lock requests. Shrinking phase allows only lock releases. Guarantees conflict serializability. Does not prevent deadlocks. Strict 2PL holds all locks until commit, prevents cascading aborts. Rigorous 2PL also holds shared locks until commit.

Deadlock handling: deadlock prevention uses wait-die or wound-wait schemes based on transaction timestamps. Deadlock detection uses a wait-for graph: edge from Ti to Tj if Ti is waiting for Tj to release a lock. Cycle in wait-for graph means deadlock. Resolution: abort one transaction (victim selection).

Lock types: shared lock allows concurrent reads. Exclusive lock for writes, exclusive access required. Upgrade allows shared to exclusive if no other holder. Lock compatibility: shared is compatible with shared, exclusive is compatible with neither.

Timestamp ordering: each transaction gets a timestamp when it starts. For each data item, track the read timestamp and write timestamp. Enforce that operations execute in timestamp order. If a younger transaction has already read or written an item, an older transaction trying to write must abort.

B-plus tree key points: all data in leaves, leaves linked as sorted list. Internal nodes contain only keys for routing. Height is proportional to log base order of n. Insertion may cause splits that propagate up. Deletion may cause merges or redistribution. For GATE, know the order of a B-plus tree (maximum children per node) and how to compute maximum and minimum keys per node.

Recovery log records: write log before data page (WAL rule). On recovery: redo all committed after checkpoint, undo all uncommitted. Checkpoint reduces redo work. ARIES algorithm: analysis pass identifies dirty pages, redo pass replays all changes, undo pass reverses incomplete transactions.