Skip to content
GATETECH
Official PYQ · 2009Q45Tuple Calculus and SQLMCQ1 mark

GATE CS 2009 Q45 — Tuple Calculus and SQL

Explain with AI

Let RR and SS be relational schemes such that R={a,b,c}R=\{a,b,c\} and S={c}.S=\{c\}. Now consider the following queries on the database:

  1. πR−S(r)−πR−S(πR−S(r)×s−πR−S,S(r))\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )
  2. {t∣t∈πR−S(r)∧∀u∈s(∃v∈r(u=v[S]∧t=v[R−S]))}\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}
  3. {t∣t∈πR−S(r)∧∀v∈r(∃u∈s(u=v[S]∧t=v[R−S]))}\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}
  4. Select R.a,R.b
    From R,S
    Where R.c = S.c

Which of the above queries are equivalent?

Choose one option
View worked solution

Answer: A

Given the relational schemas R={a,b,c}R = \{a, b, c\} and S={c}S = \{c\}, we have R−S={a,b}R - S = \{a, b\}. Let rr and ss be relations over RR and SS respectively.

1. Analysis of Query 1

The expression is given as:

πR−S(r)−πR−S(πR−S(r)×s−πR−S,S(r))\pi_{R-S}(r) - \pi_{R-S} \left( \pi_{R-S}(r) \times s - \pi_{R-S, S}(r) \right)

Since R−S={a,b}R-S = \{a, b\} and S={c}S = \{c\}, the combined set of attributes (R−S)∪S(R-S) \cup S is exactly RR. Thus, πR−S,S(r)=r\pi_{R-S, S}(r) = r. Substituting this back, we get:

πR−S(r)−πR−S(πR−S(r)×s−r)\pi_{R-S}(r) - \pi_{R-S} \left( \pi_{R-S}(r) \times s - r \right)

This is the standard relational algebra formulation for the Division operator (r÷sr \div s). It returns all tuples t∈πR−S(r)t \in \pi_{R-S}(r) that pair with every tuple in ss to form a valid tuple in rr.

2. Analysis of Query 2

The Tuple Relational Calculus (TRC) expression is:

{t∣t∈πR−S(r)∧∀u∈s(∃v∈r(u=v[S]∧t=v[R−S]))}\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}

This states that for a tuple tt to be in the result:

  • tt must belong to πR−S(r)\pi_{R-S}(r).
  • For every tuple u∈su \in s, there must exist a tuple v∈rv \in r such that the SS-attributes of vv match uu (v[S]=uv[S] = u) and the (R−S)(R-S)-attributes of vv match tt (v[R−S]=tv[R-S] = t).

Since R=(R−S)∪SR = (R-S) \cup S, this means the combined tuple t⋅ut \cdot u must exist in rr for every u∈su \in s. This is the exact definition of the division operator (r÷sr \div s).

Thus, Query 1 and Query 2 are equivalent.

3. Analysis of Queries 3 and 4

  • Query 3: The universal quantifier ∀v∈r\forall v \in r applies to all tuples in rr, which does not represent the division operation.
  • Query 4: The SQL query performs an inner join on the common attribute cc and projects the attributes aa and bb. This is equivalent to πa,b(r⋈s)\pi_{a, b}(r \bowtie s), which is not equivalent to division.

Therefore, only queries 1 and 2 are equivalent.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Tuple Calculus and SQL questions