Back to Study Material GATE Exam

DBMS for GATE Exam

For GATE CS aspirants, DBMS carries one of the highest marks-per-study-hour ratios among all subjects. The exam consistently tests relational algebra, SQL,...

DBMS for GATE Exam

GATE Focus: Relational Algebra and SQL Query Strategies

For GATE CS aspirants, DBMS carries one of the highest marks-per-study-hour ratios among all subjects. The exam consistently tests relational algebra, SQL, keys and functional dependencies, normalization, transactions, and basic indexing. This section focuses on the relational algebra and SQL areas, which together account for roughly 40 percent of DBMS marks in most years.

Relational algebra provides the theoretical foundation for SQL. The six fundamental operations are selection, projection, union, set difference, Cartesian product, and rename. From these, derived operations including natural join, theta join, intersection, and division can be expressed. For GATE, you must be able to translate between English descriptions, relational algebra expressions, and SQL queries.

The selection operation sigma applies a condition to filter tuples. The projection operation pi selects specific columns. The natural join symbol joins two relations by matching on all common attributes and eliminating duplicate columns. The theta join is a Cartesian product followed by selection on an arbitrary condition.

SQL extends relational algebra with aggregate functions (COUNT, SUM, AVG, MIN, MAX), GROUP BY for partitioning tuples before aggregation, HAVING for filtering groups, ORDER BY for sorting, and subqueries. GATE questions often combine these features. A typical question gives a schema with two or three tables and asks for the SQL query that retrieves a specific result or asks what a given query returns.

Subqueries can appear in the WHERE clause (as EXISTS, IN, or comparison with a subquery result), in the FROM clause (as a derived table), or in the SELECT clause (as a scalar subquery). Correlated subqueries reference the outer query and are re-evaluated for each outer tuple, making them equivalent to a nested loop.

Joins in SQL: INNER JOIN keeps only tuples with matches in both tables. LEFT OUTER JOIN keeps all tuples from the left table, filling nulls for missing right-side matches. RIGHT OUTER JOIN is symmetric. FULL OUTER JOIN keeps all tuples from both tables. NULL handling in SQL follows three-valued logic: any comparison involving NULL evaluates to UNKNOWN, which behaves like FALSE in WHERE and HAVING conditions but differently in CHECK constraints.

A GATE tip: when faced with a relational algebra question, work from the inside out. Identify the most restrictive selection first, reduce the relation, then join, then project. This mirrors how a query optimizer works and helps you track which attributes are available at each step.

GATE Focus: Keys, Functional Dependencies, and Normalization

Keys and normalization are tested in every GATE CS paper and are among the most reliably scorable topics in DBMS. The questions are mechanical in nature: given a set of functional dependencies, find all candidate keys, determine the highest normal form, or verify whether a decomposition is lossless.

Finding candidate keys from a set of functional dependencies is the foundational skill. Start by computing the closure of every possible attribute subset. Any subset whose closure is the set of all attributes is a superkey. Remove any superkey that has a proper subset that is also a superkey: what remains are the candidate keys. For a relation with n attributes, the worst case requires checking 2 to the power n subsets, but in practice you can use the following heuristic: attributes that appear only on the right side of all functional dependencies are never in any candidate key. Attributes that appear only on the left side must be in every candidate key. Attributes that appear on both sides may or may not be in a candidate key.

Determining normal form violations: 1NF is violated if any attribute is multivalued or composite. 2NF is violated if a non-key attribute is determined by a proper subset of a composite primary key. 3NF is violated if a non-key attribute is determined by another non-key attribute. BCNF is violated if any non-trivial functional dependency has a determinant that is not a superkey.

Lossless decomposition test: given a decomposition of relation R into R1 and R2, the decomposition is lossless if either the intersection of R1 and R2 determines R1 minus R2 (the attributes in R1 but not R2) or the intersection determines R2 minus R1. In other words, if the attributes shared between R1 and R2 form a superkey in at least one of them, the decomposition is lossless.

Dependency preservation test: a decomposition preserves dependencies if every functional dependency in the original schema can be enforced using only the attributes within one of the resulting relations, without needing to join them first. To check, compute the closure of the left side of each dependency within each resulting relation and see if you can derive the right side.

A worked GATE-style example: given R(A, B, C, D) with functional dependencies A goes to B and C goes to D, find all candidate keys. Attribute A is not on any right side, and C is not on any right side, so every candidate key must include both A and C. Compute closure of AC: AC can derive AB from the first dependency and ACD from the second, giving ABCD. So AC is a superkey and since neither A alone nor C alone produces all attributes, AC is the unique candidate key. The relation is not in BCNF because C goes to D and C is not a superkey.

GATE Focus: Transactions, Schedules, and Concurrency Control

Transaction management and concurrency control questions in GATE require you to analyze schedules, determine serializability, identify locking protocol violations, and reason about recovery. These questions carry 2 to 4 marks in most years and are fully tractable with the right framework.

A schedule lists the read and write operations of multiple transactions in the order they execute. A schedule is serial if all operations of one transaction complete before any operation of the next begins. GATE often asks whether a given interleaved schedule is conflict serializable.

To test conflict serializability using the precedence graph: for each pair of conflicting operations in the schedule, draw an edge from the transaction of the earlier operation to the transaction of the later one. Two operations conflict if they both access the same data item and at least one is a write. After drawing all edges, check for cycles. A schedule is conflict serializable if and only if the precedence graph is acyclic. The equivalent serial orderings correspond to topological sorts of the graph.

View serializability is a weaker notion that is harder to test but covers more schedules. Two schedules are view equivalent if the same initial reads occur, the same read-write pairs are in the same order for writes that are read, and the same final writes occur. View serializability is NP-complete to test in general and rarely appears directly in GATE, but you should know the definition.

Two-phase locking: lock-based concurrency control ensures serializability through two-phase locking. GATE might give you a transaction with lock and unlock operations and ask whether it follows 2PL. The rule is that all lock operations must come before all unlock operations. Strict 2PL holds all write locks until commit and additionally prevents cascading aborts.

Recovery questions ask about how a DBMS uses the transaction log to recover from crashes. The UNDO-REDO log protocol writes a log record before modifying the database. On crash recovery, the system redoes all committed transactions and undoes all incomplete ones. The WAL (write-ahead logging) rule requires that log records be written to stable storage before the corresponding data pages. GATE questions in this area typically ask which transactions need to be redone or undone given a specific log state at crash time.

For GATE, the three most important concurrency skills are: draw and analyze precedence graphs for conflict serializability, identify 2PL violations in a given schedule, and determine which transactions are undone versus redone given a log excerpt. Practice each with five examples from previous years.