What are common examiner traps in Databases?

Assuming all prime attributes imply BCNF: If all attributes are prime, the relation is in 3NF, but NOT necessarily in BCNF (e.g., AB C, C B). Confusing partial dependency (violates 2NF) with transitive dependency (violates 3NF): 2NF specifically forbids non-prime attributes depending on a proper subset of ANY candidate key. Forgetting to check the intersection in superkey counting via PIE, leading to double-counting supersets common to both candidate keys. Assuming BCNF decomposition always preserves functional dependencies (BCNF is always lossless, but dependency preservation is guaranteed only up to 3NF). Misidentifying trivial FDs: X Y is trivial if and only if Y X; partial overlap like PR RT is semi-trivial, not purely trivial. Reversing the direction of set difference in referential integrity: confusing FK(r1) - PK(r2) = with PK(r2) - FK(r1) = (referenced table can have extra keys not present in FK). Confusing ON DELETE SET NULL with ON DELETE CASCADE (SET NULL updates the referencing column to NULL and does NOT delete the tuple). Misunderstanding self-referential relationships by assuming a foreign key must always point to a distinct table.

Databases

7 topics · 116 Qs · 6.8 marks/paper · since 2011

Start mock (30 Qs)

In GATE, Normal Forms questions test a candidate's ability to identify candidate keys, classify relational schemas into appropriate normal forms (such as 3NF and BCNF), and evaluat… Guide

Topics

Open a topic to browse, or practice it timed.

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Databases?

In GATE, Normal Forms questions test a candidate's ability to identify candidate keys, classify relational schemas into appropriate normal forms (such as 3NF and BCNF), and evaluate decomposition properties (lossless join and dependency preservation). Across 2012–2026, Transactions and Concurrency Control in GATE CS is heavily weighted towards testing precedence (serialization) graphs for conflict serializability, schedule classification (recoverable, cascadeless, strict), and locking/timestamping protocol mechanics. In GATE CS, SQL is tested through a balanced mix of declarative query semantics, relational-algebra correspondence, subquery evaluation (correlated, nested, and universal quantification), and instance-level tracing.

Core concepts

Attribute closure computation (X+) and minimal candidate key search
Prime vs. non-prime attributes definition
Normal Form definitions and hierarchy: 1NF (atomicity), 2NF (no partial dependency), 3NF (LHS is superkey or RHS is prime), BCNF (LHS is superkey)
Armstrong's Axioms (Reflexivity, Augmentation, Transitivity) and derived rules (Union, Decomposition, Pseudotransitivity, Composition)
Minimal / Canonical cover / Irreducible equivalent computation
Lossless join decomposition test and dependency preservation guarantees across 1NF, 2NF, 3NF, and BCNF
Binary relations R(A, B) properties (always in BCNF)
Referential integrity constraints and foreign key semantics
Self-referencing / recursive foreign keys
Multiple foreign keys in a single relation schema
Referential triggered actions: ON DELETE CASCADE, ON DELETE SET NULL, ON UPDATE CASCADE, RESTRICT
Candidate key uniqueness and minimality properties on relation instances

High-yield formulas

Superkeys from a Single Candidate Key

\text{Number of superkeys} = 2^{n - |K|}

Used when a relation has $n$ total attributes and a single candidate key $K$ of size $|K|$ .

Superkeys with Multiple Candidate Keys (PIE)

|S(K_1 \cup K_2)| = 2^{n - |K_1|} + 2^{n - |K_2|} - 2^{n - |K_1 \cup K_2|}

Used when calculating the total number of distinct superkeys for a relation having two candidate keys $K_1$ and $K_2$ .

Useful / Non-trivial Disjoint FD Count

\text{Number of useful FDs} = 3^n - 2^{n+1} + 1

Used to count non-empty disjoint pairs $(X, Y)$ where $X \cap Y = \emptyset$ on a set of $n$ attributes.

Two-Relation Lossless Join Condition

(R_1 \cap R_2 \to R_1) \lor (R_1 \cap R_2 \to R_2)

Used to verify if decomposing $R$ into $R_1$ and $R_2$ is a lossless join decomposition.

Referential Integrity Subset Condition

\Pi_{FK}(r_1) \subseteq \Pi_{PK}(r_2) \iff \Pi_{FK}(r_1) - \Pi_{PK}(r_2) = \varnothing

Used when verifying whether all non-null foreign key values in a referencing relation instance exist in the referenced primary key column of the target relation.

Candidate Key Uniqueness Requirement

\forall t_1, t_2 \in r \, (t_1 \neq t_2 \implies t_1[K] \neq t_2[K])

Used when determining if a given set of attributes $K$ uniquely identifies tuples in a given relation instance $r$ .

Definition of Prime Attribute

A \in \text{Prime}(R) \iff \exists K \in \mathcal{CK}(R) \text{ such that } A \in K

Used to classify whether an attribute $A$ in relation schema $R$ is prime or non-prime with respect to the set of candidate keys $\mathcal{CK}(R)$ .

BCNF Condition

\forall (X \rightarrow Y) \in F^+, \text{ either } Y \subseteq X \text{ (trivial) or } X \text{ is a superkey of } R

Determining if a schema or its projected sub-relations satisfy Boyce-Codd Normal Form.

Examiner traps in Databases

Assuming all prime attributes imply BCNF: If all attributes are prime, the relation is in 3NF, but NOT necessarily in BCNF (e.g., AB C, C B).
Confusing partial dependency (violates 2NF) with transitive dependency (violates 3NF): 2NF specifically forbids non-prime attributes depending on a proper subset of ANY candidate key.
Forgetting to check the intersection in superkey counting via PIE, leading to double-counting supersets common to both candidate keys.
Assuming BCNF decomposition always preserves functional dependencies (BCNF is always lossless, but dependency preservation is guaranteed only up to 3NF).
Misidentifying trivial FDs: X Y is trivial if and only if Y X; partial overlap like PR RT is semi-trivial, not purely trivial.
Reversing the direction of set difference in referential integrity: confusing FK(r1) - PK(r2) = with PK(r2) - FK(r1) = (referenced table can have extra keys not present in FK).
Confusing ON DELETE SET NULL with ON DELETE CASCADE (SET NULL updates the referencing column to NULL and does NOT delete the tuple).
Misunderstanding self-referential relationships by assuming a foreign key must always point to a distinct table.

How questions show up

Superkey Counting via Inclusion-Exclusion
common · NAT · 1 marks · 2026, 2022, 2014
Given a relation schema of $n$ attributes and one or more candidate keys, compute the total number of distinct superkeys using powers of 2 and PIE.
Candidate Key and Normal Form Identification from FD Set
common · MCQ · 2 marks · 2020, 2016, 2014, 2013
Given an attribute set and a set of functional dependencies $F$ , find all candidate keys by attribute closure, identify prime vs. non-prime attributes, and determine the highest normal form satisfied.
Armstrong's Axioms and FD Inferences
common · MSQ · 1.5 marks · 2026, 2024, 2021, 2017
Given a set of FDs or generic rules, determine which dependencies hold, identify minimal/irreducible covers, or find necessary/sufficient axioms for derived rules.
Lossless Join and Dependency Preservation in Decompositions
occasional · MCQ · 2 marks · 2026, 2022, 2021
Given a relation decomposition $D = (R_1, R_2, \dots, R_k)$ , determine whether the decomposition is lossless (via pairwise superkey intersection checks or Chase matrix) and whether it preserves dependencies across normal forms.
Combinatorial Bounds on Functional Dependencies
occasional · NAT · 2 marks · 2024
Counting possible functional dependencies satisfying specified structural constraints (e.g., disjoint LHS and RHS, non-empty) on a relation of $n$ attributes.
Relational Algebra Representation of Referential Integrity
occasional · MCQ · 2 marks · 2012
Given two relations where one has a foreign key referencing the primary/candidate key of the other, identify the valid relational algebra/set expression representing the constraint (e.g., subset relation or empty difference).