DB · GATE CS 2027
11 topics and 22 sheets. Open a topic for its sheets and the topics it depends on.
Chen notation for entities, weak entities, relationships and the attribute kinds; cardinality ratio, participation and (min, max) notation; specialization and aggregation; mapping each construct to tables and counting the minimum number of tables.
Relations as sets of tuples, degree and cardinality; superkeys, candidate, primary, alternate and foreign keys with superkey counting; domain, NOT NULL, entity, key, referential and CHECK constraints; which operations can violate each one, and the referential actions CASCADE, SET NULL, SET DEFAULT, RESTRICT and NO ACTION.
Selection, projection, rename, union, difference, product and the derived intersection, joins and division; result schemas and size bounds; set versus bag semantics; theta, equi, natural, semi and outer joins; equivalence rules and how to disprove a claimed equivalence with a small instance.
Tuple relational calculus: tuple variables, free and bound variables, existential and universal quantifiers, implication, safe expressions and domain independence, and translation to and from relational algebra and SQL, including division.
DDL and DML, the logical evaluation order of a SELECT, SQL joins, duplicates and DISTINCT, set operations with bag counts, NULL and three-valued logic, aggregates and GROUP BY / HAVING, and nested or correlated subqueries with IN, EXISTS, ANY and ALL, with results run on SQLite and PostgreSQL.
Armstrong's axioms and derived rules, attribute closure, finding every candidate key and the prime attributes, counting FDs and superkeys, implied FDs and equivalence of FD sets, minimal cover step by step, and projecting FDs onto a decomposed relation.
1NF, 2NF, 3NF and BCNF with their exact conditions and the anomalies they remove, a routine for the highest normal form, lossless-join tests (common attributes and the chase), dependency preservation, 3NF synthesis and BCNF decomposition; 4NF as a marked note.
Blocking factor, spanned and unspanned records, heap, sorted and hashed files with their access costs; primary, clustering and secondary indexes, dense and sparse; multilevel indexes; B-tree and B+ tree node layouts, order and fan-out, height bounds, insertion with splits and block-access counts.
ACID properties and transaction states, schedules and conflicts, precedence graphs, conflict and view serializability, counting schedules, and the recoverable, cascadeless and strict schedule classes with cascading rollback and isolation anomalies.
Shared and exclusive locks and their compatibility, basic, strict, rigorous and conservative two-phase locking, deadlock handling with wait-die and wound-wait, timestamp ordering and the Thomas write rule, and a short note on log-based recovery with undo and redo.
The traps sheet, the question-pattern sheet and the master last-day sheet for the whole Databases pack.
Chen notation for entity sets, weak entity sets, relationships and identifying relationships; the attribute kinds (simple, composite, multivalued, derived, key, partial key); relationship degree and role names; cardinality ratio versus participation and the (min, max) notation, which places its labels on the opposite side from the ratio; weak entities and their owners; specialization, generalization and aggregation; and why a ternary relationship is not three binary ones.
The mapping rule for each ER construct: strong and weak entities, composite, multivalued and derived attributes, binary 1 : 1, 1 : N and M : N relationships with total or partial participation, recursive and n-ary relationships, and the three ways to map a specialization. A worked fragment shows the six tables it produces, and a counting formula with script-checked cases answers minimum-table questions, including the 1 : 1 cases where the answer depends on participation and on the textbook's convention.
Relation, tuple, attribute, domain, degree and cardinality; superkey, candidate key, primary key, alternate key and foreign key, with prime attributes and superkey counting by inclusion-exclusion; the domain, NOT NULL, entity, key, referential and CHECK constraints; which of insert, delete and update can violate each one; the referential actions CASCADE, SET NULL, SET DEFAULT, RESTRICT and NO ACTION, with a cascade chain run in SQLite; and how CHECK and UNIQUE treat NULL.
The basic operators (selection, projection, rename, union, difference, Cartesian product) and the derived ones (intersection, joins, division, assignment); union compatibility; result schema and the minimum and maximum number of tuples for each operator under set semantics; set versus bag semantics; the equivalence rules used to rewrite queries, with counterexamples for projection over difference and intersection; empty-relation edge cases and the "at least k" pattern with products only.
Theta join, equi-join, natural join, semijoin, antijoin and the left, right and full outer joins, all evaluated on one small instance and checked in SQLite; join size bounds and the exact size when the join column is a key or a NOT NULL foreign key; division by its formula, by its "for all" meaning and in SQL, including the empty-divisor case where formulations disagree.
The form of a TRC query, atoms, connectives and quantifiers, free and bound tuple variables; rewrite rules between the universal and existential quantifier and for implication; how each algebra operator, division included, is written in TRC; safety and domain independence; the pairing of the existential quantifier with conjunction and the universal one with implication, shown on an instance; and checked translations of two past GATE questions.
DDL, DML, DCL and TCL statements; DELETE versus TRUNCATE versus DROP; a table definition with every constraint kind; the logical evaluation order of a SELECT; inner, outer, cross and natural joins counted on one instance, including the left join whose WHERE filter silently turns it into an inner join; duplicates and DISTINCT; UNION, INTERSECT and EXCEPT with their ALL forms and the bag counting rules; LIKE, BETWEEN and NULL sort order. Every result was run on SQLite, and INTERSECT ALL and EXCEPT ALL on PostgreSQL.
Three-valued logic with its AND, OR and NOT tables; comparisons and arithmetic with NULL; which clauses keep TRUE only and which reject only FALSE; every aggregate on one small table with NULLs, including AVG versus SUM divided by COUNT(*), COUNT(column) and COUNT(DISTINCT); aggregates and GROUP BY on empty input; NULLs as one group; the SELECT-list rule for GROUP BY; WHERE versus HAVING; HAVING without GROUP BY. All results were run on SQLite and PostgreSQL.
Scalar, row and table subqueries; uncorrelated versus correlated evaluation; EXISTS, IN, NOT IN, ANY and ALL with their exact truth values when the subquery is empty or contains NULL; the equivalences = ANY with IN and <> ALL with NOT IN, and why > ALL is not > MAX; maximum and second maximum without MAX; "for all" with double NOT EXISTS; IN versus JOIN duplicates; and a checked past GATE query. Every result was run on PostgreSQL 17 and, where supported, SQLite.
What a functional dependency asserts, trivial and non-trivial FDs; Armstrong's axioms with the derived union, decomposition and pseudo-transitivity rules, and the rule that a left side never splits; the attribute-closure algorithm and the membership test; a routine that finds every candidate key from the attributes that appear on no right side; six relations with their keys and prime attributes computed by script; and the counts of all, trivial and non-trivial FDs on n attributes.
The membership test for an implied FD; when one FD set covers another and when two sets are equivalent, with a checked example and a non-example; the three conditions of a minimal (canonical) cover and the extraneous-attribute and redundant-FD tests; a full minimal-cover run step by step; why the steps must run in order, with a script-found counterexample; non-unique covers; and projecting F onto a decomposed relation, which needs the closure of every subset, not just the FDs that fit.
The update, insertion and deletion anomalies that normalization removes; the exact conditions of 1NF, 2NF, 3NF and BCNF stated per FD; prime and non-prime attributes; a routine for the highest normal form that tests BCNF first; nine verdicts computed by script, including a checked past GATE question; the shortcuts that are safe (two attributes, single-attribute keys, all attributes prime) and the ones that are not; and 4NF as a marked note beyond the syllabus.
The binary lossless-join test on the common attributes and the chase for three or more parts, with spurious tuples shown on an instance; the dependency-preservation test that grows a closure across the parts; the 3NF synthesis algorithm and BCNF decomposition, each run on an example by script; why 3NF can always keep every FD while BCNF sometimes cannot; and two checked past GATE questions.
Blocking factor, spanned and unspanned records and the number of blocks; heap, sorted and hashed files with the block accesses for equality search, range search and insertion; primary, clustering and secondary indexes, dense and sparse, and how many of each a file can have; the access count through a single-level index; a single file worked through every access path by script, with all sizes stated.
Multilevel indexes with fan-out and the number of levels; node layouts of the B-tree and the B+ tree; the inequalities that give the order of internal nodes and the capacity of leaves from block, key and pointer sizes; the conventions for "order" and minimum occupancy; the minimum and maximum height for a given number of keys; and block-access counts for search, all computed by script with every size stated.
The B+ tree insertion routine with leaf splits that copy a key up and internal splits that move a key up, the root split that adds a level, and the split-point conventions; a before-and-after diagram generated from a tested insert routine; B-tree insertion for contrast; ascending insertion and its half-full leaves; node counts after splits; deletion with borrowing and merging in brief; and two checked past GATE questions.
ACID and what enforces each property; the transaction state diagram; schedules, serial schedules and how many interleavings exist; conflicting operations; the precedence-graph test with diagrams of a cyclic and an acyclic graph and the serial orders of the second; view equivalence and blind writes; the counts of conflict-serializable interleavings for small transaction pairs; and three checked past GATE questions, all computed by script.
Reads-from; recoverable, cascadeless and strict schedules with their nesting and their independence from serializability; seven schedules classified by script; cascading rollback traced through dirty reads, with a checked past GATE question; the dirty read, unrepeatable read, lost update and phantom anomalies; the four SQL isolation levels and the anomalies each allows; and the lost-update question from GATE CS 2025.
Shared and exclusive locks and their compatibility; two-phase locking and its basic, conservative, strict and rigorous forms with what each prevents; a conflict-serializable schedule that 2PL cannot produce, checked by script; deadlock detection with the wait-for graph and prevention with wait-die and wound-wait; basic timestamp ordering with its read and write rules, the Thomas write rule, and traces of both; a comparison of locking and timestamps; and a short marked note on log-based recovery.
Thirty common mistakes across the Databases syllabus, each paired with the correct rule and a short check or example: ER participation and mapping, keys and foreign keys, functional dependencies and normal forms, decomposition, relational algebra and calculus, SQL with NULLs and duplicates, indexing and B+ trees, serializability, recoverability and concurrency control. Every row links to the sheet that explains it.
Twenty-three recurring question shapes in GATE Databases, each with the cue in the stem, the first step and method, the check that most often changes the answer, and the sheet that holds the routine, with a past GATE question where the pack has a verified one. No claims about how often a pattern appears.
A one-page summary of the whole Databases pack: ER mapping and minimum tables, keys and constraints, algebra and calculus rules, SQL with NULLs, closure, keys, normal forms and decomposition tests, file and index sizing, B+ tree rules, serializability, recoverability and concurrency-control protocols, with the numbers that are worth remembering and the traps that cost the most marks.
Engineering MathematicsData StructuresAlgorithmsOperating Systems
