Previous Year Questions: Relational Algebra | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Q1: The relation schema, Person(pid,city), describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cross product, and rename.
To find the list of cities where at least 3 persons reside, using the above operators, the minimum number of cross product operations that must be used is  (2024 SET 2)
(a) 1
(b) 2
(c) 3
(d) 4
Ans: (b)
Sol: A minimum of 2 cross products are required to find the list of cities where at least 3 people reside.
Therefore, the correct answer is B.

Q2: Consider the following three relations in a relational database.  (2022)
Employee (eId, Name), Brand(bId, bName), Own(eId, bId)
Which of the following relational algebra expressions return the set of e I d s eIds who own all the brands?
(MSQ)
(a) II_eId (II_eId,bId (Own) / II_bId (Brand))
(b) II_eId(Own) − II_eId ((II_eId(Own) × II_bId (Brand)) −II_{eId, bId}(Own))
(c) ) II_eId (II_eId,bId (Own) / II_{bId (Own))
(d)} IIe_Id(( II_eId ((IIeId(Own) _{× IIbId} (Own)) _{−IIeId, bId}(Brand)
Ans: (a, b)
Sol: Option A-It will give eid which will pair with every bid of brand so this will give correct answer.
Option B-In this option first there is a cross product between eid of Own and bid of BRAND so it will give all combination of eid and bid then there is a set difference between eid, bid of Own table this will give all employees which does not own all brand. Then at last there is set difference with eid of Own, so it will give eid which pair with every bid of brand (eid which owns all brand)
Option C- it will give eid which pair with every bid of Own (not brand) so this will give wrong answer.
Option d-
Suppose there is an instance of Own(eid, bid) like this (e1,b1) (e1,b2) (e2,b1) and suppose in brand there are only two bid b1 and b2 so it should give e1 as answer but according to option d there will be cross product between eid of Own and bid of Own so after cross product it will look like this (e1,b1), (e1,b2),(e2,b1),(e2,b2) and after performing division with bid of brand it will give eid e1 and e2 as answer which is wrong.
So this is incorrect
option A and option B are correct.

Q3: The following relation records the age of 500 employees of a company, where empNo ( indicating the employee number) is the key:  (2015 SET 1)
 empAge( empNo  ,age)
 Consider the following relational algebra expression:
 II_empNo ( emp Age ⋈ _{( age > age1 ) ρ empNo1 , age1} ( emp Age ) )  What does the above expression generate?
(a) Employee numbers of only those employees whose age is the maximum
(b) Employee numbers of only those employees whose age is more than the age of exactly one other employee
(c) Employee numbers of all employees whose age is not the minimum
(d) Employee numbers of all employees whose age is the minimum
Ans: (c)
Sol: Correct Answer: C
Whenever a Database Problem intimidating like the above one(maybe it’s just me) appears, it’s often worth to Dissect the statements for Individual components and build up your arguments from there rather than attempting it head-on by some random example/argument only to get swayed by your hidden biases and choose the wrong answer.
ρ r 1 ( x , y , … ) is the rename operation here, it’s used to change the name of the empAge ′ s attributes emp No , age to empNo 1 , age1 to resolve potential conflicts that can arise while referring the relations’(the table) attributes(column) when using relations that might share a common attribute name.
⋈ _{< cond >} is a combination of σ and × where we take the Cross Product at First between the two relations and apply the tuple select condition supplied to ⋈ by using σ . So ⋈ equals σ _{< cond >}(A X B)
II_<attr> is a Column Select Operation in naive words, it’s supplied with attributes that needs to be selected.
A Relation contains only unique tuples unlike in conventional SQL Databases.
Now,

1. First the ρ operator renames the RHS relation to empNo 1, age 1
2. We take the cross product of both the relations, each tuple in A(unmodified relation empAge) will be combined with every tuple in B (renamed relation empAge).
3. We filter the tuples according to the condition a g e > a g e 1 which implies those tuples whose age values in A that are greater than at least one of B are selected. Since A are B are the same here only those values which aren’t the minimum are selected in A are selected( > ).
4. We find out the set of unique e m p N o by using Projection( II )(Note: emp No derived from LHS side of ⋈ the original relation A that we were talking about).

Since the empNo is derived from relation A ( LHS ) whose age attribute is greater than the relation’s minimum implies employees from A are selected whose age isn’t the minimum hence, Option C is true.
Also, if emp No1 was chosen instead of e m p N o then it would list all the employee numbers whose age isn’t the maximum.

Q4: Consider the following relation P(X, Y, Z), Q(X, Y, T) and R(Y, V):  (2019) 

How many tuples will be returned by the following relational algebra query?

Answer:______
(a) 1
(b) 2
(c) 3
(d) 4
Ans: (a)
Sol: R ⋅ V = V 2 , there are two tuples which have Y parameter as Y 3 and Y 2 .
P ⋅ Y = R ⋅ Y , there are no coincide with Y 3 , and there is one tuple coincide with Y 2 which have X parameter as X 2 .
IIX (σ_{(P. Y= R.YΛR. V = V2)}(P×R )) = {X₂}
Q ⋅ T > 2 , there are two tuples which have Y parameter as Y 1 and Y 2 which have X parameter as X 1 .
check at least one tuple is matched Q . Y = R . Y in this query, that's enough to result X 1 .
II_X(σ _{(Q.Y=R.YΛQ.T>2)}(Q × R)) = {X₁}
II χ (σ _{(P.Y=RY A. R.V=V2)} (P × R)) - II χ (σ _{(Q.Y=RY A Q.T>2)} (Q X R)) = {X₂} - {X₁} = {X₂}
Number of Tuples = 1

Q5: Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query  (2018)
 Q : r ⋈ ( σ _{B < 5} ( s ) )
Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values.
Which one of the following queries is NOT equivalent to Q?
(a) σ_B<5(r⋈s)
(b)σ_B<5(rLOJs)    
(c) rLOJ(σ_B<5(s))
(d) σ_B<5(r)LOJs
Ans: (c)
Sol: Option a, b, d will restrict all record with B<5 but option C will include record with b>=5 also, so false.
C is the answer.

Q6: Consider a database that has the relation schema CR (StudentName, CourseName). An instance of the schema CR is as given below.  (2017 SET 1)

The following query is made on the database
T1←π _CourseName(σ_{StudentName=′SA′}(CR))
The number of rows in T2 is ____________.
(a) 2
(b) 3
(c) 4
(d) 5
Ans: (c)  
Sol: ANS) 4

T1 WILL GIVE :-  

T2 = CR ÷ T1 = All the tuples in CR which are matched with every tuple in T1
//SB IS NOT MATCHED WITH CA, SE IS NOT MATCHED WITH CC

Q7: Consider two relations R1(A,B) with the tuples (1,5), (3,7) and R2(A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. Consider the following tuples of the form (A,B,C): a = (1,5,null), b = (1,null,7), c = (3, null, 9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9). Which one of the following statements is correct?  (2015 SET 2)
(a) R contains a, b, e, f, g but not c, d.
(b) R contains all of a, b, c, d, e, f, g.
(c) R contains e, f, g but not a, b.
(d) R contains e but not f, g.
Ans: (c)
Sol: R₁ (A, B)
R_{2 (A, C)}

Now , if we do full natural outer join:

So, option (C) is correct.

Q8: Consider the relational schema given below, where eId of the relation dependent  a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.  (2014 SET 3)

The above query evaluates to the set of empIds of employees whose age is greater than that of
(a) some dependent
(b) all dependents
(c) some of his/her dependents
(d) all of his/her dependents
Ans: (d)
Sol: (D) all of his/her dependents.
The inner query selects the employees whose age is less than or equal to at least one of his dependents. So, subtracting from the set of employees, gives employees whose age is greater than all of his dependents.

Q9: What is the optimized version of the relation algebra expression  π A1  (π _A2  (σ _F1  (σ _F2  (r)))) , where A1, A2 are sets of attributes in r with A 1 ⊂ A 2  and F1, F2 are Boolean expressions based on the attributes in r?  (2014 SET 3)
(a) π_A1(σ_(F1∧F2) (r))
(b) π_A1(σ_(F1∨F2) (r))
(c) π_A2(σ_(F1∧F2) (r))
(d) π_A2(σ_(F1∨F2) (r))
Ans: (a)
Sol:  since A1 is subset of A2 will get only A1 attributes as it is in the outside, so we can remove project A2.
Two Selects with boolean expression can be combined into one select with And of two boolean expressions.

Q10: Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R))<size(s(S)), the join will have fewer number of disk block accesses if  (2014 SET 2)
(a) relation r(R) is in the outer loop.
(b) relation s(S) is in the outer loop
(c) join selection factor between r(R) and s(S) is more than 0.5.
(d) join selection factor between r(R) and s(S) is less than 0.5
Ans: (a)
Sol: In joining A and B using nested loop method, with A in outer loop two factors are involved.
i. No. of  blocks containing all rows in A should be fetched.
ii. No. of rows of A times no. of blocks containing all rows of B.
(in worst case all rows of B are matched with all rows of A).
In above ques, |R| < |S|
(i) will be less when number of rows in outer table is less, since less no. of rows will take less no. of blocks
(ii) if we keep R in outer loop, no. of rows in R are less and no. of blocks in S are more
If we keep S in outer loop, no of rows in S are more and no. of blocks in R are less.
In (ii) block accesses will be multiplication and will come same in both cases.
So, (i) will determine no of block accesses
So, answer is A.

Q11: Consider the following relations A, B and C:  (2012)

How many tuples does the result of the following relational algebra expression contain? Assume that the schema of A∪∪B is the same as that of A
(A ∪ B)⋈_{A.Id>40∨C.Id<15}C
(a) 7
(b) 4
(c) 5
(d) 9
Ans: (a)
Sol: Given the relations A, B and 

This is an example of theta join and we know:   R⋈_θS = σ_θ (R x S)
∴ (A U B)  ⋈_{A.Id>40VC.Id<15} C = (_A.Id>40(A U B) x C)  U ( _C.Id<15 (( A U B) X  C))
To make the query more efficient we can perform the select operation before the cross product
∴ (A U B)  ⋈_{A.Id>40VC.Id<15} C = (_A.Id>40(A U B) x C)  U ((A U B)  X _C.Id<15 C)
 Now calculate A U B:  

Please note that union is a set operation and duplicates will not be included by default.
First perform cross-product  ( _{A. Id > 40} (A U B) X C). i.e., Multiply each row of _{A. Id >40} (A U B) with each
row of C.

Now perform cross-product ((A U B) X  _C.Id<15 C) i.e., Multiply each row of  (A U B )  with each row of
_C.Id<15 C

 Now take the union: ( _{A. Id>40} (A U B) X C)  U (A U B) X  _C.Id<15 C)
We will get:

which has 7 Tuples, hence answer is  A

Q12: Suppose R1(A, B) and R2(C, D) are two relation schemas. Let r1 and r2 be the corresponding relation instances. B is a foreign key that refers to C in R2. If data in r1 and r2 satisfy referential integrity constraints, which of the following is ALWAYS TRUE?  (2012)
(a) II_B (r1)−II_C (r2) = ϕ
(b) II_C (r1)−II_B (r2) = ϕ
(c) II_B (r1)−II_C (r2)
(d)  II_B (r1)−II_C (r2)  ≠ = ϕ
Ans: (a) 
Sol:  Referential integrity means, all the values in foreign key should be present in primary key.
r2(c) is the super set of r1(b)
So, {subset - superset} is always empty set.
Answer is A.

Q13: Consider a relational table r with sufficient number of records, having attributes A₁ , A₂ , . . . , A _n  and let 1 ≤ p ≤ n  . Two queries Q1 and Q2 are given below  (2011)
Q1: π A₁  ....A _n   (σ A _p  = c  (r)) where c is a constant
Q 2: π A₁.... A _n ( σ _{c 1} ≤ A p ≤ _{c 2} ( r ) ) where c₁ and c₂  are constant
The database can be configured to do ordered indexing on A_por hashing on A_p .
Which of the following statements is TRUE?
(a) Ordered indexing will always outperform hashing for both queries
(b) Hashing will always outperform ordered indexing for both queries
(c) Hashing will outperform ordered indexing on Q1, but not on Q2
(d) Hashing will outperform ordered indexing on Q2, but not on Q1
Ans: (c)
Sol: (C) Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too. For ex consider B+ Tree, once you have searched a key in B+ tree , you can find range of values via the block pointers pointing to another block of values on the leaf node level.

Q14: The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)  (2010)
B →A,
A →C
The relation R contains 200tuples and the relation S contains 100tuples. What is the maximum number of tuples possible in the natural join R⋈ S?
(a) 100
(b) 200
(c) 300
(d) 2000
Ans: (a)
Sol:  Natural join will combine tuples with the same value of the common rows(if there are two common rows then both values must be equal to get into the resultant set). So by this definition, we can get at the max only 100 common values.