GATE DA

The relational model

Relational algebra and tuple calculus

The relational model stores data as relations (sets of tuples) identified by keys. Relational algebra (procedural) and tuple relational calculus (declarative) are two formal languages for querying them, and their safe forms express exactly the same queries. GATE DA questions on this topic ask you to evaluate an expression on small tables and count the result tuples, to pick the expression that answers a stated query, and to judge which calculus expressions are safe, so these notes concentrate on exact operator rules, equivalences and cardinality bounds.

5 previous-year questions · 5 solved · 6 practice questions

Relations, tuples and keys

A relation schema $R (A_{1}, \dots, A_{n})$ names the attributes; a relation instance is a finite set of tuples, each giving one value per attribute. Because a relation is a set, there is no tuple order and no duplicate tuple. The degree is the number of attributes and the cardinality $∣ R ∣$ is the number of tuples.

Convention used in these notes. Relational algebra and tuple calculus use set semantics: no result ever contains a duplicate tuple. SQL uses bag semantics: SELECT keeps duplicates unless DISTINCT is written, while UNION, INTERSECT and EXCEPT remove duplicates unless ALL is written. Wherever NULL appears, any comparison involving it is unknown (three-valued logic), and a selection or join condition that is unknown does not select the tuple, as in a SQL WHERE clause. SQL keywords are written in capitals.

Term	Meaning
Superkey	A set of attributes $K$ such that no two distinct tuples agree on all of $K$ (in every legal instance)
Candidate key	A minimal superkey: removing any attribute breaks uniqueness
Primary key	The one candidate key chosen to identify tuples; its attributes cannot be `NULL`
Alternate key	A candidate key that was not chosen as primary
Prime attribute	An attribute that belongs to at least one candidate key
Foreign key	A set of attributes of $R_{1}$ whose value in every tuple is either `NULL` or equal to the value of a candidate key (usually the primary key) in some tuple of the referenced relation $R_{2}$

SUPERKEY CONDITION

K superkey of R ⟺ \forall t_{1} \neq = t_{2} \in R : t_{1} [K] \neq = t_{2} [K]

Every superset of a superkey (within the attributes of $R$ ) is a superkey, so under set semantics the set of all attributes is always a superkey. Candidate keys are the minimal superkeys.

COUNTING SUPERKEYS

one candidate key K : 2^{n - ∣ K ∣}, two candidate keys K_{1}, K_{2} : 2^{n - ∣ K_{1} ∣} + 2^{n - ∣ K_{2} ∣} - 2^{n - ∣ K_{1} \cup K_{2} ∣}

$n$ is the number of attributes of $R$ . A superkey is any attribute set that contains at least one candidate key. With two keys, inclusion-exclusion subtracts the sets counted twice: those containing $K_{1} \cup K_{2}$ .

EXAM TIP

Keys are a property of the schema (they must hold for every legal instance), not of one instance. A small table can show that a set is not a key (two rows agree), but it can never prove that a set is a key.

Basic relational algebra operators

Every operator takes relations and returns a relation (the algebra is closed), so expressions nest. The basic operators are selection $σ$ , projection $π$ and rename $ρ$ (unary), and union $\cup$ , set difference $-$ and Cartesian product $\times$ (binary). Theta and natural joins, intersection and division can all be written using these six. Rename only changes names, so ${σ, π, \cup, -, \times}$ is often called the complete set.

SELECTION

σ_{θ} (R) = {t \in R ∣ θ (t) is true}

Keeps whole tuples satisfying the condition; schema unchanged; $∣ σ_{θ} (R) ∣ \leq ∣ R ∣$ .

PROJECTION

π_{A_{1}, \dots, A_{k}} (R) = {t [A_{1}, \dots, A_{k}] ∣ t \in R}

Keeps the listed columns and removes duplicate rows (set semantics). For non-empty $R$ , $1 \leq ∣ π_{L} (R) ∣ \leq ∣ R ∣$ , with $∣ π_{L} (R) ∣ = ∣ R ∣$ whenever the list $L$ contains a superkey.

CARTESIAN PRODUCT

∣ R \times S ∣ = ∣ R ∣ \cdot ∣ S ∣, de g (R \times S) = de g R + de g S

Pairs every tuple of $R$ with every tuple of $S$ . Clashing attribute names are qualified ( $R . A$ , $S . A$ ) or renamed with $ρ$ .

UNION AND SET DIFFERENCE

R \cup S = {t ∣ t \in R \lor t \in S}, R - S = {t ∣ t \in R \land t \in / S}

Defined only for union-compatible relations: the same degree, with the $i$ -th attributes of both having the same domain. By convention the result takes its attribute names from the first operand. Union is commutative and associative; difference is neither.

RENAME

ρ_{T (X_{1}, \dots, X_{n})} (R)

Gives the result the relation name $T$ and attribute names $X_{i}$ ; needed for self-joins.

CARDINALITY BOUNDS FOR SET OPERATIONS

max (∣ R ∣, ∣ S ∣) \leq ∣ R \cup S ∣ \leq ∣ R ∣ + ∣ S ∣, 0 \leq ∣ R \cap S ∣ \leq min (∣ R ∣, ∣ S ∣), max (0, ∣ R ∣ - ∣ S ∣) \leq ∣ R - S ∣ \leq ∣ R ∣

Set semantics, $R$ and $S$ union-compatible. Also $∣ R \cup S ∣ = ∣ R ∣ + ∣ S ∣ - ∣ R \cap S ∣$ and $∣ R - S ∣ = ∣ R ∣ - ∣ R \cap S ∣$ . The upper bounds of $\cup$ and $-$ are reached when $R \cap S = \emptyset$ ; their lower bounds when the smaller relation is contained in the larger.

EXAM TIP

Projection and union remove duplicates, so a count taken after $π$ or $\cup$ can be smaller than you expect. Always list the distinct rows before counting.

Joins, intersection and division

Theta join, natural join, intersection and division are derived operators: each can be rewritten with the basic ones, and they exist because they shorten common queries. Outer joins, at the end of this section, are an extension: they also need NULL to pad the missing side.

THETA JOIN

R ⋈_{θ} S = σ_{θ} (R \times S)

$0 \leq ∣ R ⋈_{θ} S ∣ \leq ∣ R ∣ \cdot ∣ S ∣$ . An equi-join is a theta join whose condition is only equalities; it keeps both copies of the compared attributes.

NATURAL JOIN

R ⋈ S = π_{all attributes, common ones once} (σ_{R . C_{1} = S . C_{1} \land \dots \land R . C_{m} = S . C_{m}} (R \times S))

$C_{1}, \dots, C_{m}$ are the attributes with the same name in both relations, and the result has degree $de g R + de g S - m$ . With no common attribute it equals $R \times S$ ; when the two schemas are identical it equals $R \cap S$ . A NULL never matches, not even another NULL. Natural join is commutative and associative (up to column order).

INTERSECTION

R \cap S = R - (R - S)

Union-compatible relations; $∣ R \cap S ∣ \leq min (∣ R ∣, ∣ S ∣)$ .

DIVISION

R \div S = π_{X} (R) - π_{X} ((π_{X} (R) \times S) - R)

$R (X, Y)$ and $S (Y)$ , where the attributes $Y$ of $S$ are a proper subset of those of $R$ and $X$ is the rest. The result has schema $X$ (degree $de g R - de g S$ ): the $X$ -values that appear in $R$ paired with every tuple of $S$ . If $S$ is empty, the formula gives $R \div S = π_{X} (R)$ .

DIVISION SIZE BOUNDS

∣ R \div S ∣ \leq ∣ π_{X} (R) ∣, ∣ R \div S ∣ \leq ⌊ \frac{∣ R ∣}{∣ S ∣} ⌋ (S \neq = \emptyset)

Each $X$ -value in the result needs its own $∣ S ∣$ tuples in $R$ , one for each tuple of $S$ , and these tuples are different for different $X$ -values.

Outer joins keep tuples that find no partner, padding the missing side with NULL. Write $⋈^{L}$ (left outer), $⋈^{R}$ (right outer) and $⋈^{F}$ (full outer); the superscripts name the kind of join, not a relation. The left outer join keeps every tuple of the left relation, the right keeps every tuple of the right, and the full outer join keeps both.

OUTER JOIN COUNTS

∣ R ⋈^{F} S ∣ = ∣ R ⋈ S ∣ + u_{R} + u_{S}

$∣ R ⋈ S ∣$ is the inner (natural) join; $u_{R}$ and $u_{S}$ are the numbers of tuples of $R$ and of $S$ that match no tuple of the other relation. Left outer adds only $u_{R}$ , right outer only $u_{S}$ .

NATURAL JOIN SIZE BOUNDS

0 \leq ∣ R ⋈ S ∣ \leq ∣ R ∣ \cdot ∣ S ∣

If the common attributes form a key of $S$ , each tuple of $R$ matches at most one tuple of $S$ , so $∣ R ⋈ S ∣ \leq ∣ R ∣$ . If they are also a foreign key of $R$ referencing $S$ with no NULL in it, the size is exactly $∣ R ∣$ .

WORKED EXAMPLE

Let $R (A, B) = {(1, x), (1, y), (2, x), (3, x), (3, y), (4, y)}$ and $S (B) = {x, y}$ . Find $R \div S$ .

Solution

$π_{A} (R) = {1, 2, 3, 4}$ .
$π_{A} (R) \times S$ has $4 \times 2 = 8$ tuples: every $(a, b)$ with $a \in {1, 2, 3, 4}$ and $b \in {x, y}$ .
Subtract $R$ (6 tuples). The tuples left are the pairs that $R$ lacks: $(2, y)$ and $(4, x)$ .
Project on $A$ : ${2, 4}$ . These $A$ -values are missing at least one $B$ from $S$ .
$R \div S = {1, 2, 3, 4} - {2, 4} = {1, 3}$ . Check: only $1$ and $3$ appear with both $x$ and $y$ .

Answer: $R \div S = {1, 3}$ , two tuples.

EXAM TIP

To read a division quickly, group $R$ by $X$ and ask which groups contain every $S$ -value. A group may contain extra $Y$ -values and still qualify: extras do no harm, only gaps do.

Equivalences and standard query patterns

Two expressions are equivalent when they return the same relation on every legal instance. One counter-example instance is enough to show that two expressions are not equivalent.

Equivalence	Condition
$σ_{θ_{1} \land θ_{2}} (R) = σ_{θ_{1}} (σ_{θ_{2}} (R)) = σ_{θ_{2}} (σ_{θ_{1}} (R))$	Always
$π_{L_{1}} (π_{L_{2}} (R)) = π_{L_{1}} (R)$	$L_{1} \subseteq L_{2}$ (otherwise the left side is undefined)
$π_{L} (σ_{θ} (R)) = σ_{θ} (π_{L} (R))$	$θ$ uses only attributes in $L$
$σ_{θ} (R ⋈ S) = σ_{θ} (R) ⋈ S$ (also for $\times$ )	$θ$ uses only attributes of $R$
$σ_{θ} (R \cup S) = σ_{θ} (R) \cup σ_{θ} (S)$ , and likewise for $\cap$ and $-$	Always; also $σ_{θ} (R - S) = σ_{θ} (R) - S$
$π_{L} (R \cup S) = π_{L} (R) \cup π_{L} (S)$	Always
$π_{L} (R \cap S) \subseteq π_{L} (R) \cap π_{L} (S)$ and $π_{L} (R - S) \supseteq π_{L} (R) - π_{L} (S)$	Equality can fail (example below)
$R ⋈ S = S ⋈ R$ and $(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)$	Natural join, up to column order
$\cup$ and $\cap$ are commutative and associative	$-$ is neither: $R - S \neq = S - R$ and $(R - S) - T \neq = R - (S - T)$ in general

WORKED EXAMPLE

Show that projection does not distribute over set difference or intersection, using $R (A, B) = {(1, x)}$ and $S (A, B) = {(1, y)}$ .

Solution

$R - S = {(1, x)}$ , so $π_{A} (R - S) = {1}$ .
$π_{A} (R) - π_{A} (S) = {1} - {1} = \emptyset$ . The two sides differ.
$R \cap S = \emptyset$ , so $π_{A} (R \cap S) = \emptyset$ .
$π_{A} (R) \cap π_{A} (S) = {1}$ . The two sides differ again.

Answer: Both equalities fail on this instance, so neither is a valid rewrite. Only the one-way inclusions in the table hold.

LARGEST VALUE WITHOUT AGGREGATION

π_{A} (R) - π_{R . A} (σ_{R . A < T . A} (R \times ρ_{T} (R)))

$ρ_{T} (R)$ is a renamed copy of $R$ . The subtracted part is every $A$ -value that some other value of $A$ exceeds, so what remains is the maximum value of $A$ . Use $>$ in place of $<$ for the minimum. This assumes $A$ contains no NULL.

EXAM TIP

To decide whether two expressions are equivalent, first try a tiny instance (one or two tuples per relation, sharing a value so the operators interact). A counter-example settles a no; a yes needs an argument that works for every instance.

Evaluating expressions and counting tuples

Procedure for a counting question

Write the schema and the tuples of every base relation as a small list.
Evaluate from the innermost bracket outwards, writing out each intermediate relation in full.
For a join, match on the common attributes (or on the stated condition) and list each matching pair; do not guess from sizes.
After any projection or union, delete duplicate rows (set semantics).
For outer joins, add the unmatched tuples with NULL padding last.
Count only at the end, and cross-check with the bounds above.

WORKED EXAMPLE

$R (A, B) = {(1, 2), (2, 3), (3, 3), (4, 5)}$ and $S (B, C) = {(2, a), (3, b), (3, c), (6, d)}$ . How many tuples are in $R ⋈ S$ , $π_{A, C} (R ⋈ S)$ , $π_{C} (R ⋈ S)$ , $R ⋈^{L} S$ and $R ⋈^{F} S$ ?

Solution

Join on $B$ : $(1, 2)$ meets $(2, a)$ ; $(2, 3)$ meets $(3, b)$ and $(3, c)$ ; $(3, 3)$ meets $(3, b)$ and $(3, c)$ ; $(4, 5)$ and $(6, d)$ have no partner.
$R ⋈ S = {(1, 2, a), (2, 3, b), (2, 3, c), (3, 3, b), (3, 3, c)}$ : 5 tuples.
$π_{A, C}$ : $(1, a), (2, b), (2, c), (3, b), (3, c)$ are all distinct: 5 tuples.
$π_{C}$ : ${a, b, c}$ : duplicates collapse, 3 tuples.
Left outer adds the unmatched $R$ tuple $(4, 5)$ as $(4, 5, NULL)$ : $5 + 1 = 6$ .
Full outer also adds the unmatched $S$ tuple $(6, d)$ as $(NULL, 6, d)$ : $6 + 1 = 7$ .

Answer: 5, 5, 3, 6 and 7 tuples respectively.

EXAM TIP

A selection such as $σ_{B = NULL} (R)$ returns nothing, because a comparison with NULL is unknown. Testing for NULL needs IS NULL in SQL, which has no plain equivalent in the basic algebra above.

Tuple relational calculus and safety

Tuple relational calculus (TRC) is declarative: it describes what the answer tuples satisfy, not how to compute them. An expression is ${t ∣ P (t)}$ , where $t$ is a tuple variable and $P$ is a formula.

TRC EXPRESSION

{t ∣ P (t)}

The result is the set of all tuples $t$ for which formula $P$ is true. $t$ is the only free variable of $P$ ; every other tuple variable must be bound by a quantifier.

Building blocks of a formula

Atoms: $s \in R$ (range of $s$ ), $s [A] θ u [B]$ and $s [A] θ c$ with $θ \in {=, \neq =, <, \leq, >, \geq}$ and $c$ a constant. $s \in / R$ abbreviates $\neg (s \in R)$ .
Connectives: $\land, \lor, \neg$ , and implication $P \Rightarrow Q \equiv \neg P \lor Q$ .
Quantifiers: $\exists s \in R (P) \equiv \exists s (s \in R \land P)$ and $\forall s \in R (P) \equiv \forall s (s \in R \Rightarrow P)$ ; both bind $s$ .
Duality: $\forall s (P) \equiv \neg\exists s (\neg P)$ and $\exists s (P) \equiv \neg\forall s (\neg P)$ .

Reading the table. The answer tuple $t$ has the schema of the algebra result in the same row, and $A$ , $B$ , $C$ may each be a list of attributes. For $\cup$ , $\cap$ and $-$ , $R$ and $S$ are union-compatible. In the product row $R$ has schema $A$ and $S$ has schema $B$ ; in the natural-join row $R (A, B)$ and $S (B, C)$ ; in the division row $R (A, B)$ and $S (B)$ .

Algebra	Tuple calculus
$σ_{θ} (R)$	${t ∣ t \in R \land θ (t)}$
$π_{A} (R)$	${t ∣ \exists r \in R (t [A] = r [A])}$
$R \cup S$	${t ∣ t \in R \lor t \in S}$
$R \cap S$	${t ∣ t \in R \land t \in S}$
$R - S$	${t ∣ t \in R \land t \in / S}$
$R \times S$	${t ∣ \exists r \in R \exists s \in S (t [A] = r [A] \land t [B] = s [B])}$
$R ⋈ S$	${t ∣ \exists r \in R \exists s \in S (r [B] = s [B] \land t [A] = r [A] \land t [B] = r [B] \land t [C] = s [C])}$
$R \div S$	${t ∣ \exists r \in R (t [A] = r [A]) \land \forall s \in S \exists r_{2} \in R (r_{2} [A] = t [A] \land r_{2} [B] = s [B])}$

An expression is safe if it is guaranteed to return a finite set: every value in an answer tuple must come from the relations named in the expression or from the constants written in it, and quantified variables range only over such values. ${t ∣ \neg (t \in R)}$ is unsafe: over an unbounded domain, infinitely many tuples are not in $R$ . ${t ∣ t \in R \lor t \in S}$ is safe when $R$ and $S$ are union-compatible. Safe tuple calculus and basic relational algebra express exactly the same queries; a query language that can express all of them is called relationally complete. Neither can express aggregation (such as counting tuples), ordering, or recursion such as transitive closure.

EXAM TIP

To spot an unsafe expression, check every disjunct separately. In each one, every attribute of the answer variable $t$ must be pinned down positively: by $t \in R$ , or by equality with a constant or with a variable that ranges over a relation. ${t ∣ t [A] > 5}$ (only compared), ${t ∣ \neg (t \in R)}$ (only negated) and ${t ∣ t \in R \lor t [A] > 5}$ (second disjunct unbounded) are all unsafe.

Translating between calculus, algebra and SQL

Each algebra shape has a standard SQL form. A selection-projection-join query is SELECT-FROM-WHERE. Difference becomes EXCEPT or a correlated NOT EXISTS; intersection becomes INTERSECT or EXISTS; division becomes a double NOT EXISTS. NOT IN expresses difference only when the subquery returns no NULL: if it returns one, x NOT IN (...) is never true (it is false or unknown), so the query returns no rows.

The algebra query $π_{A} (σ_{C > 5} (R ⋈ S))$ with $R (A, B)$ and $S (B, C)$ is, in SQL (DISTINCT matches the set semantics of the algebra):

SELECT DISTINCT R.A
FROM R
JOIN S
ON R.B = S.B
WHERE S.C > 5;

Division $R \div S$ for $R (A, B)$ and $S (B)$ reads as: an A such that there is no B of S that fails to appear with it in R. If S is empty, the query returns every A of R, which agrees with $R \div S = π_{A} (R)$ .

SELECT DISTINCT r.A
FROM R r
WHERE NOT EXISTS (
  SELECT *
  FROM S s
  WHERE NOT EXISTS (
    SELECT *
    FROM R r2
    WHERE r2.A = r.A
    AND r2.B = s.B
  )
);

Algebra idea	SQL form	Calculus form
Difference $R - S$	`EXCEPT` or `NOT EXISTS`	$t \in R \land t \in / S$
Intersection $R \cap S$	`INTERSECT` or `EXISTS`	$t \in R \land t \in S$
Division	double `NOT EXISTS`	$\forall$ inside $\exists$
Natural join	`NATURAL JOIN` or `JOIN ... ON`	$\exists r \in R \exists s \in S$ with equal common attributes
Outer join	`LEFT`, `RIGHT`, `FULL OUTER JOIN`	no direct form: it needs tuples padded with `NULL`

EXAM TIP

When a question says every, all or never, think division or difference: for all is $\forall$ , which is $\neg\exists\neg$ , which is a double NOT EXISTS. An inner join alone can only say there exists.

PREVIOUS-YEAR QUESTIONS

5 questions from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2026 · GATE DA 2025 · GATE DA 2024

GATE 2026 DA Q.42

GATE 2026 · DAQ.42 · 2 marks · MCQ

Consider the given relations $X$ , $Y$ and $Z$ . The relation $X$ has three columns $P$ , $Q$ and $R$ . The relation $Y$ has three columns $P$ , $Q$ and $S$ . The relation $Z$ has two columns $P$ and $T$ .

Relation $X (P, Q, R)$ : (P1, Q1, R1), (P2, Q2, R2), (P3, Q3, R2).

Relation $Y (P, Q, S)$ : (P1, Q1, 2), (P1, Q2, 5), (P2, Q1, 6), (P3, Q3, 1).

Relation $Z (P, T)$ : (P1, T1), (P3, T2), (P4, T3), (P4, NULL).

Consider the relational algebra expression

π_{P R S} [(σ_{(Q = Q 3 \lor R = R 2)} [X ⋈ Y]) ⋈ (σ_{(S > 1)} [Y ⋈ Z])]

where $⋈$ denotes natural join operation.

Which of the following options is the correct output for the given expression?

GATE 2026 DA question 42: Three small tables side by side. — Figure from the GATE 2026 DA paper. It is part of the question.

(A)
Two rows (P1, R1, 2) and (P1, R1, 5)
(B)
Three rows (P1, R1, 2), (P1, R1, 5) and (P2, R2, 6)
(C)
One row (P1, R1, 2)
(D)
Zero rows

Answer and solution

GATE 2026 DA Q.42: answer and solution

GATE 2026 DA Q.59

GATE 2026 · DAQ.59 · 2 marks · NAT

Let there be two relations $X$ and $Y$ as shown. $X$ has three columns $P$ , $Q$ and $R$ . $Y$ has two columns $P$ and $S$ .

Relation X (columns P, Q, R): (P1, Q1, R1), (P2, Q2, R2), (P3, Q3, R2).

Relation Y (columns P, S): (P1, 10), (P1, 15), (P2, 20), (P3, 1).

Consider that the following tuple relational calculus expression is evaluated.

{t ∣ t \in X \land \exists z \in X (t [P] = z [P]) \land \exists m \in Y (m [P] = t [P] \land m [S] > 1)}

The number of tuples that will be returned is ______. (Answer in integer)

GATE 2026 DA question 59: Two tables side by side. — Figure from the GATE 2026 DA paper. It is part of the question.

Answer and solution

GATE 2026 DA Q.59: answer and solution

GATE 2025 DA Q.17

GATE 2025 · DAQ.17 · 1 mark · MCQ

Consider the following three relations:

Car (model, year, serial, color)
Make (maker, model)
Own (owner, serial)

A tuple in Car represents a specific car of a given model, made in a given year, with a serial number and a color. A tuple in Make specifies that a maker company makes cars of a certain model. A tuple in Own specifies that an owner owns the car with a given serial number. Keys are underlined; (owner, serial) together form key for Own. (⋈ denotes natural join)

$π_{owner} (Own ⋈ (σ_{color = ’red’} (Car ⋈ (σ_{maker = ’ABC’} Make))))$

Which one of the following options describes what the above expression computes?

(A)
All owners of a red car, a car made by ABC, or a red car made by ABC
(B)
All owners of more than one car, where at least one car is red and made by ABC
(C)
All owners of a red car made by ABC
(D)
All red cars made by ABC

Answer and solution

GATE 2025 DA Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 DA Q.17: answer and solution

GATE 2025 DA Q.62

GATE 2025 · DAQ.62 · 2 marks · NAT

Consider the following tables, Loan and Borrower, of a bank.

Query: $π_{branch_name, customer_name} (Loan ⋈ Borrower) \div π_{branch_name} (Loan)$ where $⋈$ denotes natural join.

The number of tuples returned by the above relational algebra query is ______ (Answer in integer)

GATE 2025 DA question 62: Two tables. — Figure from the GATE 2025 DA paper. It is part of the question.

Answer and solution

GATE 2025 DA Q.62: answer and solution

GATE 2024 DA Q.26

GATE 2024 · DAQ.26 · 1 mark · MCQ

Consider a database that includes the following relations:

Defender(name, rating, side, goals)
Forward(name, rating, assists, goals)
Team(name, club, price)

Which ONE of the following relational algebra expressions checks that every name occurring in Team appears in either Defender or Forward, where $ϕ$ denotes the empty set?

(A)
$π_{name} (Team) ∖ (π_{name} (Defender) \cap π_{name} (Forward)) = ϕ$
(B)
$(π_{name} (Defender) \cap π_{name} (Forward)) ∖ π_{name} (Team) = ϕ$
(C)
$π_{name} (Team) ∖ (π_{name} (Defender) \cup π_{name} (Forward)) = ϕ$
(D)
$(π_{name} (Defender) \cup π_{name} (Forward)) ∖ π_{name} (Team) = ϕ$

Answer and solution

GATE 2024 DA Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.26: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 12 marks · NAT

Relation $R (A, B) = {(1, 10), (2, 10), (3, 20), (4, 30), (5, 30)}$ and relation $S (B, C) = {(10, p), (20, q), (20, r), (40, s)}$ . Under set semantics, how many tuples does the full outer join $R ⋈^{F} S$ on the common attribute $B$ contain?

Answer and solution

Answer: $7$

Matching on $B$ : $(1, 10)$ and $(2, 10)$ each meet $(10, p)$ , giving 2 tuples.
$(3, 20)$ meets $(20, q)$ and $(20, r)$ , giving 2 more, so $∣ R ⋈ S ∣ = 4$ .
Unmatched in $R$ : $(4, 30)$ and $(5, 30)$ , since $S$ has no $B = 30$ . So $u_{R} = 2$ .
Unmatched in $S$ : $(40, s)$ , since $R$ has no $B = 40$ . So $u_{S} = 1$ .
Full outer join size $= 4 + 2 + 1 = 7$ .

PRACTICE 22 marks · MSQ

Let $Works (E, P)$ record that employee $E$ works on project $P$ , and let $Proj (P)$ list all projects; $Proj$ is non-empty. Which expressions return exactly the employees who work on every project in $Proj$ , as a relation with schema $(E)$ ?

(A)
$Works \div Proj$
(B)
$π_{E} (Works) - π_{E} ((π_{E} (Works) \times Proj) - Works)$
(C)
$π_{E} (Works ⋈ Proj)$
(D)
$π_{E} (Works) \times Proj$

Answer and solution

Answer: (A), (B)

A is the definition of division with $X = E$ and $Y = P$ : the $E$ -values paired in $Works$ with every tuple of $Proj$ . Correct.
B is the expansion of division: $π_{E} (Works) \times Proj$ lists every possible (employee, project) pair, subtracting $Works$ leaves the missing pairs, and removing those employees leaves exactly the ones with no gap. Correct.
C returns employees who work on at least one project that is in $Proj$ , not necessarily all of them. Wrong.
D is a Cartesian product with schema $(E, P)$ , not a set of employees. Wrong.

PRACTICE 31 mark · MCQ

$R (A)$ has 6 tuples and $S (A)$ has 4 tuples. Under set semantics, let $d = ∣ R \cup S ∣ - ∣ R \cap S ∣$ . What are the minimum and maximum possible values of $d$ , in that order?

(A)
2 and 10
(B)
6 and 10
(C)
0 and 10
(D)
2 and 6

Answer and solution

Answer: (A)

Let $k = ∣ R \cap S ∣$ , so $0 \leq k \leq min (6, 4) = 4$ .
$∣ R \cup S ∣ = 6 + 4 - k$ , hence $d = (10 - k) - k = 10 - 2 k$ .
At $k = 0$ , $d = 10$ (maximum). At $k = 4$ , $d = 2$ (minimum, when $S \subseteq R$ ).
So the range is 2 to 10.

PRACTICE 41 mark · MCQ

Which of the following tuple relational calculus expressions is NOT safe? Here $R$ and $S$ are relations with the same single attribute $A$ , and in every option the answer tuple $t$ has the single attribute $A$ .

(A)
${t ∣ t \in R \land t [A] > 5}$
(B)
${t ∣ \neg (t \in R)}$
(C)
${t ∣ \exists s \in R (t [A] = s [A])}$
(D)
${t ∣ t \in R \lor t \in S}$

Answer and solution

Answer: (B)

A restricts $t$ to tuples of $R$ , so the answer is a subset of a finite relation. Safe.
B asks for every tuple not in $R$ , and there are infinitely many such tuples over an unbounded domain. Unsafe.
C fixes the only attribute of $t$ to an $A$ -value that occurs in $R$ . Safe.
D is the union of two finite relations, and each disjunct bounds $t$ . Safe.

PRACTICE 51 mark · NAT

A relation $R (A, B, C)$ has exactly two candidate keys, ${A}$ and ${B, C}$ . How many distinct non-empty attribute sets are superkeys of $R$ ?

Answer and solution

Answer: $5$

A superkey is any set that contains a candidate key.
Sets containing $A$ : ${A}, {A, B}, {A, C}, {A, B, C}$ , which is 4 sets.
Sets containing ${B, C}$ but not $A$ : only ${B, C}$ , which is 1 set.
Total $= 4 + 1 = 5$ . Check with the formula: $2^{3 - 1} + 2^{3 - 2} - 2^{3 - 3} = 4 + 2 - 1 = 5$ .

PRACTICE 61 mark · MCQ

Let $R$ and $S$ be union-compatible relations with schema $(A, B)$ . Under set semantics, which equivalence does NOT hold for every instance?

(A)
$σ_{A = 1} (R - S) = σ_{A = 1} (R) - σ_{A = 1} (S)$
(B)
$π_{A} (R \cup S) = π_{A} (R) \cup π_{A} (S)$
(C)
$π_{A} (R - S) = π_{A} (R) - π_{A} (S)$
(D)
$σ_{A = 1} (σ_{B = 2} (R)) = σ_{A = 1 \land B = 2} (R)$

Answer and solution

Answer: (C)

A holds: a tuple with $t [A] = 1$ is in $σ_{A = 1} (S)$ exactly when it is in $S$ , so both sides are the tuples of $R$ with $A = 1$ that are not in $S$ .
B holds: every $A$ -value of $R \cup S$ comes from a tuple of $R$ or of $S$ , and conversely.
C fails: with $R = {(1, x)}$ and $S = {(1, y)}$ , the left side is $π_{A} ({(1, x)}) = {1}$ but the right side is ${1} - {1} = \emptyset$ .
D holds: cascading selections is the same as selecting on the conjunction.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

relational model: relational algebra, tuple calculus

Preparing in Kolkata? IAE Academy's course for GATE DA.