What are common examiner traps in Integrity Constraints and Normal Forms?

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. Counting the initial deleted tuple when the question explicitly asks for the number of 'additional' records deleted. Confusing existential quantification ('appears in at least one candidate key') with universal quantification ('must appear in all candidate keys'). Restricting the definition of prime attribute only to the chosen Primary Key rather than any valid Candidate Key. Assuming a relation is NOT in BCNF/3NF simply because it was decomposed into smaller relations. Neglecting to project functional dependencies onto the decomposed sub-schemas when evaluating their normal forms. Confusing the lossless join condition ((R1 R2)+ R1 or R2) with dependency preservation. Misidentifying candidate keys by failing to include essential attributes (attributes never appearing on the RHS of any FD). Assuming an FD X Y is valid for 3NF when X is not a superkey and Y is non-prime. Forgetting that prime attributes are attributes belonging to *any* candidate key, not just the primary key. Selecting affirmative options ('R is in 3NF') by checking only one FD instead of checking every non-trivial FD.

Integrity Constraints and Normal Forms

30 Qs · since 2011 · 43 marks · 1.7 marks/paperMedium yield

Take topic test

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

Type

GATE CSE 2026 Set 1Q30MSQ1 markEasyLet $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \rightarrow Y$ indicate functional dependency in the context of a relational database, where $X, Y \subseteq \{P, Q, R, S\}$ . Which of the following options is/are always true?
GATE CSE 2026 Set 1Q31MSQ1 markMediumIn the context of relational database normalization, which of the following statements is/are true?
GATE CSE 2026 Set 1Q65NAT2 marksEasyConsider a relational database schema with a relation $R(A, B, C, D)$ . If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$ , then the number of superkeys of relation $R$ is ________. (answer in integer)
GATE CSE 2026 Set 2Q42MCQ2 marksMediumIn the context of schema normalization in relational DBMS, consider a set F of functional dependencies. The set of all functional dependencies implied by F is called the closure of F. To compute the closure of F, Armstrong's Axioms can be applied. Consider $X, Y,$ and $Z$ as sets of attributes over a relational…
GATE CSE 2025 Set 1Q47MSQ2 marksEasyConsider a relational schema $team(name, city, owner)$ , with functional dependencies $\{name \rightarrow city, name \rightarrow owner\}$ . The relation $team$ is decomposed into two relations, $t1(name, city)$ and $t2(name, owner)$ . Which of the following statement(s) is/are TRUE?
GATE CSE 2025 Set 2Q46MSQ2 marksMediumConsider the following relational schema along with all the functional dependencies that hold on them. $R1(A, B, C, D, E): \{ D \to E, EA \to B, EB \to C \}$ $R2(A, B, C, D): \{ A \to D, A \to B, C \to A \}$ Which of the following statement(s) is/are TRUE?
GATE CSE 2024 Set 1Q22MSQ1 markEasyWhich of the following statements about a relation $\mathbf{R}$ in first normal form (1NF) is/are TRUE ?
GATE CSE 2024 Set 1Q44MSQ2 marksEasyThe symbol $\rightarrow$ indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?
GATE CSE 2024 Set 2Q56NAT2 marksMediumA functional dependency $F: X \rightarrow Y$ is termed as a $\textit{useful functional dependency}$ if and only if it satisfies all the following three conditions: - $X$ is not the empty set. - $Y$ is not the empty set. - Intersection of $X$ and $Y$ is the empty set. For a relation $R$ with 4 attributes,…
GATE CSE 2022Q14MCQ1 markEasyIn a relational data model, which one of the following statements is TRUE?
GATE CSE 2022Q31NAT1 markEasyConsider a relation $R(A, B, C, D, E)$ with the following three functional dependencies. $AB \rightarrow C; \quad BC \rightarrow D; \quad C \rightarrow E;$ The number of superkeys in the relation R is ________.
GATE CSE 2021 Set 1Q33MCQ2 marksMediumConsider the relation $R(P, Q, S, T, X, Y, Z, W)$ with the following functional dependencies. $PQ \rightarrow X;\ P \rightarrow YX;\ Q \rightarrow Y;\ Y \rightarrow ZW$ Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes. $D_1 :\quad R = [(P, Q, S, T);\ (P, T, X);\ (Q, Y);\ (Y, Z, W)]$ …
GATE CSE 2021 Set 2Q6MCQ1 markEasyConsider the following statements S1 and S2 about the relational data model: S1: A relation scheme can have at most one foreign key. S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R. Which one of the following choices is correct?
GATE CSE 2021 Set 2Q40MSQ2 marksEasySuppose the following functional dependencies hold on a relation $U$ with attributes $P, Q, R, S$ , and $T$ : $\begin{aligned} P &\rightarrow QR RS &\rightarrow T \end{aligned}$ Which of the following functional dependencies can be inferred from the above functional dependencies?
GATE CSE 2020Q36MCQ2 marksMediumConsider a relational table $R$ that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
GATE CSE 2017 Set 1Q16MCQ1 markMediumThe following functional dependencies hold true for the relational schema $R\{V, W, X, Y, Z\}$ : $\begin{aligned} V &\to W VW &\to X Y &\to VX Y &\to Z \end{aligned}$ Which of the following is irreducible equivalent for this set of functional dependencies?
GATE CSE 2017 Set 2Q19NAT1 markEasyDiagramConsider the following tables T1 and T2. In table T1, $\mathbf{P}$ is the primary key and $\mathbf{Q}$ is the foreign key referencing $\mathbf{R}$ in table T2 with on-delete cascade and on-update cascade. In table T2, $\mathbf{R}$ is the primary key and $\mathbf{S}$ is the foreign key referencing $\mathbf{P}$ …
GATE CSE 2016 Set 1Q21MCQ1 markEasyWhich of the following is NOT a superkey in a relational schema with attributes $V, W, X, Y, Z$ and primary key $V Y$ ?
GATE CSE 2016 Set 1Q23MCQ1 markMediumA database of research articles in a journal uses the following schema. ( $\text{VOLUME}$ , $\text{NUMBER}$ , $\text{STARTPAGE}$ , $\text{ENDPAGE}$ , $\text{TITLE}$ , $\text{YEAR}$ , $\text{PRICE}$ ) The primary key is ( $\text{VOLUME}$ , $\text{NUMBER}$ , $\text{STARTPAGE}$ , $\text{ENDPAGE}$ ) and the following functional dependencies exist in the…
GATE CSE 2015 Set 3Q20MCQ1 markEasyConsider the relation $X(P, Q, R, S, T, U)$ with the following set of functional dependencies $F = \{ \{P, R\} \rightarrow \{S, T\}, \{P, S, U\} \rightarrow \{Q, R\} \}$ Which of the following is the trivial functional dependency in $F^+$ , where $F^+$ is closure of $F$ ?
GATE CSE 2014 Set 1Q21MCQ1 markEasyConsider the relation scheme $R = (E, F, G, H, I, J, K, L, M, N)$ and the set of functional dependencies $\{\{E, F\} \rightarrow \{G\}, \{F\} \rightarrow \{I, J\}, \{E, H\} \rightarrow \{K, L\}, \{K\} \rightarrow \{M\}, \{L\} \rightarrow \{N\}\}$ on $R$ . What is the key for $R$ ?
GATE CSE 2014 Set 1Q30MCQ2 marksMediumGiven the following two statements: S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF. S2: $AB\rightarrow C, D\rightarrow E, E\rightarrow C$ is a minimal cover for the set of functional dependencies $AB\rightarrow C, D\rightarrow E, AB\rightarrow E, E\rightarrow C$ . Which one of the…
GATE CSE 2014 Set 2Q21NAT1 markEasyThe maximum number of superkeys for the relation schema $\text{R} (\text{E}, \text{F}, \text{G}, \text{H})$ with $\text{E}$ as the key is _______.
GATE CSE 2014 Set 2Q22NAT1 markEasyDiagramGiven an instance of the STUDENTS relation as shown below: For ( $\textit{StudentName}$ , $\textit{StudentAge}$ ) to be a key for this instance, the value X should NOT be equal to _________.
GATE CSE 2014 Set 3Q22MCQ1 markEasyA prime attribute of a relation scheme $R$ is an attribute that appears
GATE CSE 2013Q54MCQ2 marksMediumStatement for Linked Answer Questions 54 and 55: Relation $R$ has eight attributes $ABCDEFGH$ . Fields of $R$ contain only atomic values. $F=\{CH\rightarrow G, A\rightarrow BC, B\rightarrow CFH, E\rightarrow A, F\rightarrow EG\}$ is a set of functional dependencies (FDs) so that $F^+$ is exactly the set of…
GATE CSE 2013Q55MCQ2 marksMediumStatement for Linked Answer Questions 54 and 55: Relation $R$ has eight attributes $ABCDEFGH$ . Fields of $R$ contain only atomic values. $F=\{CH\rightarrow G, A\rightarrow BC, B\rightarrow CFH, E\rightarrow A, F\rightarrow EG\}$ is a set of functional dependencies (FDs) so that $F^+$ is exactly the set of…
GATE CSE 2012Q2MCQ1 markEasyWhich of the following is $\textbf{TRUE}$ ?
GATE CSE 2012Q43MCQ2 marksEasySuppose $R_1(A, B)$ and $R_2(\underline{C}, D)$ are two relation schemas. Let $r_1$ and $r_2$ be the corresponding relation instances. B is a foreign key that refers to C in $R_2$ . If data in $r_1$ and $r_2$ satisfy referential integrity constraints, which of the following is ALWAYS TRUE?
GATE CSE 2011Q12MCQ1 markEasyConsider a relational table with a single record for each registered student with the following attributes. 1. $Registration\_Num$ : Unique registration number of each registered student 2. $UID$ : Unique identity number, unique at the national level for each citizen 3. $BankAccount\_Num$ : Unique account number…

Topic guide

What does GATE test in Integrity Constraints and Normal Forms?

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). Questions combine normal form verification with decomposition analysis, frequently formatted as multi-select questions (MSQs) requiring rigorous evaluation of all properties across both the original and decomposed relations.

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
Set difference and projection formulations of integrity constraints
Prime Attribute (Key Attribute)
Non-prime Attribute
Candidate Key
Primary Key vs. Candidate Key distinction
Attribute closure computation
Candidate key and superkey identification
Boyce-Codd Normal Form (BCNF)
Third Normal Form (3NF)
Lossless join decomposition test
Functional dependency projection on sub-relations
Candidate key identification
Prime vs non-prime attribute classification
Third Normal Form (3NF) criteria
Transitive and partial functional dependencies

Recurring question patterns

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).
Candidate Key Uniqueness on Table Instances
occasional · NAT · 1 marks · 2014
Given a relation instance with a masked or variable attribute value $X$ , find the value that would violate the uniqueness property of a proposed composite or single-attribute candidate key.
Referential Actions Simulation (CASCADE vs SET NULL)
occasional · NAT · 1 marks · 2017
Given two or more interacting tables with defined foreign key actions (ON DELETE CASCADE, ON DELETE SET NULL, ON UPDATE CASCADE), trace the cascade steps upon deleting a tuple and count the additional deleted or modified tuples.
Conceptual Properties of Keys and Constraints
occasional · MCQ · 1 marks · 2021
True/False or matching statements evaluating fundamental properties of foreign keys, including self-referencing relations (unary/recursive relationships) and relations containing multiple foreign keys.
Formal Definition of Relational Schema Terminology
common · MCQ · 1 marks · 2014
Direct, 1-mark conceptual MCQ testing the exact mathematical/relational definition of key normalization concepts such as prime attributes, candidate keys, or superkeys.
Decomposition and Normal Form Verification
common · MSQ · 2 marks · 2025
A relational schema along with a set of functional dependencies is provided and decomposed into two or more sub-relations. Candidates must evaluate multiple statements regarding the normal form (BCNF/3NF) of the original relation, the normal form of the sub-relations, and decomposition properties such as lossless join.
Multi-Schema Normal Form Identification
common · MSQ · 2 marks · 2025
Given two or more relational schemas along with their sets of functional dependencies, evaluate candidate keys and test non-trivial FDs against normal form rules (such as 3NF or BCNF) to verify positive or negative assertions about their normal forms.

Formulas GATE uses

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.

Lossless Join Decomposition Condition

(R_1 \cap R_2 \rightarrow R_1) \in F^+ \quad \text{or} \quad (R_1 \cap R_2 \rightarrow R_2) \in F^+

Checking whether decomposing relation $R$ into $R_1$ and $R_2$ guarantees a lossless (non-additive) join.

3NF Condition

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

Determining if a relation satisfies Third Normal Form.

Third Normal Form (3NF) Condition

\forall (X \to Y) \in F^+ \text{ (non-trivial)},\ X \text{ is a superkey} \lor Y \subseteq \text{Prime Attributes}

Used to verify whether a relation schema satisfies 3NF after finding candidate keys and prime attributes.

Attribute Closure Computation

X^{(i+1)} = X^{(i)} \cup \{B \mid \exists (A \to B) \in F \text{ such that } A \subseteq X^{(i)}\}

Used to compute attribute closure $X^+$ to find candidate keys and determine if $X$ is a superkey.

Examiner traps in Integrity Constraints and Normal Forms

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.
Counting the initial deleted tuple when the question explicitly asks for the number of 'additional' records deleted.
Confusing existential quantification ('appears in at least one candidate key') with universal quantification ('must appear in all candidate keys').
Restricting the definition of prime attribute only to the chosen Primary Key rather than any valid Candidate Key.
Assuming a relation is NOT in BCNF/3NF simply because it was decomposed into smaller relations.
Neglecting to project functional dependencies onto the decomposed sub-schemas when evaluating their normal forms.
Confusing the lossless join condition ((R1 R2)+ R1 or R2) with dependency preservation.
Misidentifying candidate keys by failing to include essential attributes (attributes never appearing on the RHS of any FD).
Assuming an FD X Y is valid for 3NF when X is not a superkey and Y is non-prime.
Forgetting that prime attributes are attributes belonging to *any* candidate key, not just the primary key.
Selecting affirmative options ('R is in 3NF') by checking only one FD instead of checking every non-trivial FD.

How questions are asked

Given schema + FD set, find candidate keys and highest normal form
Count superkeys for given candidate keys (NAT)
Check valid Armstrong axiom derivations and inferences (MSQ)
Determine lossless join vs. lossy decomposition across subrelations (MCQ)
Identify canonical/minimal cover among given options (MCQ)
Identify true/false theoretical properties of normal forms (MCQ/MSQ)
Relational algebra set difference equivalence
Tabular instance key violation search (NAT)
Cascade/Set-Null deletion tracing and counting (NAT)
Two-statement conceptual validity check (MCQ/MSQ)
Direct conceptual definition MCQ
MSQ evaluating normal forms of original/decomposed schemas and lossless join property
Identifying highest normal form satisfied by a relation given a set of FDs
Determine 3NF/BCNF compliance for multiple schemas
True/False evaluation of normal form status via MSQ

Paper trends

Shift from linked/single-choice MCQs on standard closure drills to MSQs testing edge-case theoretical properties (e.g., 1NF composite attributes, Armstrong axiom derivations, BCNF dependency preservation).
2026, 2024, 2021, 2014, 2013
Introduction of NAT questions testing combinatorial counts (number of superkeys, number of useful FDs) over schemas of small attribute sizes ( $n=4$ or $5$ ).
2026, 2024, 2022, 2014
Questions moved from purely abstract relational algebra representations of foreign keys to concrete instance-based simulation (NATs with tabular data) and statement-based conceptual evaluation.
2021, 2017, 2014, 2012
Even with multi-table cascade definitions, question difficulty has consistently remained easy to moderate, focusing on careful rule application rather than long multi-step chaining.
2017, 2014
Foundational 1-mark conceptual definitions test exact phrasing (e.g., universal quantification 'in all' vs. existential quantification 'in some' candidate keys) to evaluate precision in normalization theory.
2014
Recent papers employ MSQ formats for normal form problems, requiring simultaneous validation of candidate keys, normal form definitions (3NF/BCNF), and decomposition guarantees (lossless join) in a single question.
2025
Introduction of MSQ format pairing complementary assertions (e.g., 'R is in 3NF' vs 'R is NOT in 3NF') across multiple schemas, requiring complete verification of each schema independently without negative marking.
2025

Difficulty notes

Easy: Direct superkey counting with 1 or 2 keys; trivial FD definitions; 2-attribute relation properties; direct MSQs on Armstrong's rules. Medium: Finding multiple cyclic candidate keys in 8-attribute relations; minimal cover with extraneous LHS/RHS elimination; multi-step lossless join decompositions; combinatorial counting of valid FDs using set partitions.

Integrity Constraints and Normal Forms

30 Qs · since 2011 · 43 marks · 1.7 marks/paperMedium yield

Take topic test

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

Type

Topic guide

What does GATE test in Integrity Constraints and Normal Forms?

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
Set difference and projection formulations of integrity constraints
Prime Attribute (Key Attribute)
Non-prime Attribute
Candidate Key
Primary Key vs. Candidate Key distinction
Attribute closure computation
Candidate key and superkey identification
Boyce-Codd Normal Form (BCNF)
Third Normal Form (3NF)
Lossless join decomposition test
Functional dependency projection on sub-relations
Candidate key identification
Prime vs non-prime attribute classification
Third Normal Form (3NF) criteria
Transitive and partial functional dependencies

Recurring question patterns

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).
Candidate Key Uniqueness on Table Instances
occasional · NAT · 1 marks · 2014
Given a relation instance with a masked or variable attribute value $X$ , find the value that would violate the uniqueness property of a proposed composite or single-attribute candidate key.
Referential Actions Simulation (CASCADE vs SET NULL)
occasional · NAT · 1 marks · 2017
Given two or more interacting tables with defined foreign key actions (ON DELETE CASCADE, ON DELETE SET NULL, ON UPDATE CASCADE), trace the cascade steps upon deleting a tuple and count the additional deleted or modified tuples.
Conceptual Properties of Keys and Constraints
occasional · MCQ · 1 marks · 2021
True/False or matching statements evaluating fundamental properties of foreign keys, including self-referencing relations (unary/recursive relationships) and relations containing multiple foreign keys.
Formal Definition of Relational Schema Terminology
common · MCQ · 1 marks · 2014
Direct, 1-mark conceptual MCQ testing the exact mathematical/relational definition of key normalization concepts such as prime attributes, candidate keys, or superkeys.
Decomposition and Normal Form Verification
common · MSQ · 2 marks · 2025
A relational schema along with a set of functional dependencies is provided and decomposed into two or more sub-relations. Candidates must evaluate multiple statements regarding the normal form (BCNF/3NF) of the original relation, the normal form of the sub-relations, and decomposition properties such as lossless join.
Multi-Schema Normal Form Identification
common · MSQ · 2 marks · 2025
Given two or more relational schemas along with their sets of functional dependencies, evaluate candidate keys and test non-trivial FDs against normal form rules (such as 3NF or BCNF) to verify positive or negative assertions about their normal forms.

Formulas GATE uses

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.

Lossless Join Decomposition Condition

(R_1 \cap R_2 \rightarrow R_1) \in F^+ \quad \text{or} \quad (R_1 \cap R_2 \rightarrow R_2) \in F^+

Checking whether decomposing relation $R$ into $R_1$ and $R_2$ guarantees a lossless (non-additive) join.

3NF Condition

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

Determining if a relation satisfies Third Normal Form.

Third Normal Form (3NF) Condition

\forall (X \to Y) \in F^+ \text{ (non-trivial)},\ X \text{ is a superkey} \lor Y \subseteq \text{Prime Attributes}

Used to verify whether a relation schema satisfies 3NF after finding candidate keys and prime attributes.

Attribute Closure Computation

X^{(i+1)} = X^{(i)} \cup \{B \mid \exists (A \to B) \in F \text{ such that } A \subseteq X^{(i)}\}

Used to compute attribute closure $X^+$ to find candidate keys and determine if $X$ is a superkey.

Examiner traps in Integrity Constraints and Normal Forms

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.
Counting the initial deleted tuple when the question explicitly asks for the number of 'additional' records deleted.
Confusing existential quantification ('appears in at least one candidate key') with universal quantification ('must appear in all candidate keys').
Restricting the definition of prime attribute only to the chosen Primary Key rather than any valid Candidate Key.
Assuming a relation is NOT in BCNF/3NF simply because it was decomposed into smaller relations.
Neglecting to project functional dependencies onto the decomposed sub-schemas when evaluating their normal forms.
Confusing the lossless join condition ((R1 R2)+ R1 or R2) with dependency preservation.
Misidentifying candidate keys by failing to include essential attributes (attributes never appearing on the RHS of any FD).
Assuming an FD X Y is valid for 3NF when X is not a superkey and Y is non-prime.
Forgetting that prime attributes are attributes belonging to *any* candidate key, not just the primary key.
Selecting affirmative options ('R is in 3NF') by checking only one FD instead of checking every non-trivial FD.

How questions are asked

Given schema + FD set, find candidate keys and highest normal form
Count superkeys for given candidate keys (NAT)
Check valid Armstrong axiom derivations and inferences (MSQ)
Determine lossless join vs. lossy decomposition across subrelations (MCQ)
Identify canonical/minimal cover among given options (MCQ)
Identify true/false theoretical properties of normal forms (MCQ/MSQ)
Relational algebra set difference equivalence
Tabular instance key violation search (NAT)
Cascade/Set-Null deletion tracing and counting (NAT)
Two-statement conceptual validity check (MCQ/MSQ)
Direct conceptual definition MCQ
MSQ evaluating normal forms of original/decomposed schemas and lossless join property
Identifying highest normal form satisfied by a relation given a set of FDs
Determine 3NF/BCNF compliance for multiple schemas
True/False evaluation of normal form status via MSQ

Paper trends

Shift from linked/single-choice MCQs on standard closure drills to MSQs testing edge-case theoretical properties (e.g., 1NF composite attributes, Armstrong axiom derivations, BCNF dependency preservation).
2026, 2024, 2021, 2014, 2013
Introduction of NAT questions testing combinatorial counts (number of superkeys, number of useful FDs) over schemas of small attribute sizes ( $n=4$ or $5$ ).
2026, 2024, 2022, 2014
Questions moved from purely abstract relational algebra representations of foreign keys to concrete instance-based simulation (NATs with tabular data) and statement-based conceptual evaluation.
2021, 2017, 2014, 2012
Even with multi-table cascade definitions, question difficulty has consistently remained easy to moderate, focusing on careful rule application rather than long multi-step chaining.
2017, 2014
Foundational 1-mark conceptual definitions test exact phrasing (e.g., universal quantification 'in all' vs. existential quantification 'in some' candidate keys) to evaluate precision in normalization theory.
2014
Recent papers employ MSQ formats for normal form problems, requiring simultaneous validation of candidate keys, normal form definitions (3NF/BCNF), and decomposition guarantees (lossless join) in a single question.
2025
Introduction of MSQ format pairing complementary assertions (e.g., 'R is in 3NF' vs 'R is NOT in 3NF') across multiple schemas, requiring complete verification of each schema independently without negative marking.
2025