RelationalAlgebra
Question 1 
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

Q: r⋈(σ_{B<5}(s))
Let LOJ denote the natural left outerjoin operation. Assume that r and s contain no null values.
Which one of the following is NOT equivalent to Q?
σ_{B<5} (r ⨝ s)
 
σ_{B<5} (r LOJ s)
 
r LOJ (σ_{B<5}(s))
 
σ_{B<5}(r) LOJ s 
Consider the following tables without NULL values.
Q: r⨝(σ_{B}<5(S))
The result of σ_{B<5}(S) is
The result of σ_{B<5}(S) is
Option (A):
The result of r⨝S is
The result of σ_{B<5}(r⨝S) is
Option (B):
The result of r LOJ S is
The result of σ_{B<5}(r LOJ S) is
Option (C):
The result of σ_{B<5}(S) is
Now, the result of r LOJ(σ_{B<5}(S))
Option (D):
The result of σ_{B<5}(r) is
Now, the result of σ_{B<5}(r) LOJ S is
Therefore, from the output of above four options, the results of options, the results of options (A), (B) and (D) are equivalent to Q.
Question 2 
Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to a NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

(I) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
(II) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
(III) {t│∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] = v[DeptId]))}
Which of the above queries are safe?
(I) and (II) only  
(I) and (III) only  
(II) and (III) only  
(I), (II) and (III) 
(I) Gives EmpNames who do not belong to any Department. So, it is going to be a finite number of tuples as a result.
(II) Gives EmpNames who do not belong to some Department. This is also going to have finite number of tuples.
(III) Gives EmpNames who do not belong to same Department. This one will also give finite number of tuples.
All the expressions I, II and III are giving finite number of tuples. So, all are safe.
Question 3 
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.
The following query is made on the database.
T1 ← π_{CourseName}(σ_{StudentName='SA'}(CR)) T2 ← CR ÷ T1
The number of rows in T2 is ____________.
4  
5  
6  
7 
The σ_{StudentName = 'SA'}(CR) will produce the following
⇾ The result of T1 ← π_{CourseName}(σ_{StudentName='SA'}(CR)) is
(2) T2 ← CR÷T1
⇾ We see that SA is enrolled for CA, CB and CC.
⇾ T2 will give the StudentNames those who have enrolled for all the CA, C, CC courses. So, the following Students are enrolled for the given 3 courses.
⇾ So, the output of T2 will have 4 rows.
Question 4 
R contains a,b,e,f,g but not c, d.
 
R contains all of a,b,c,d,e,f,g
 
R contains e,f,g but not a,b
 
R contains e but not f,g

⋆ So, from the above resultant table, R contains e, f, g only but not a, b.
Question 5 
∏_{B} (r_{1})  ∏_{C} (r_{2}) = ∅  
∏_{C} (r_{2})  ∏_{B} (r_{1}) = ∅  
∏_{B} (r_{1}) = ∏_{C} (r_{2})  
∏_{B} (r_{1})  ∏_{C} (r_{2}) ≠ ∅ 
So we can say that r_{2}(C) is the superset of r_{1}(B).
So (subset  superset) is always empty.
Question 6 
7  
4  
5  
9 
Performs the cross product and selects the tuples whose A∙Id is either greater than 40 or C∙Id is less than 15. It yields:
Question 7 
Ordered indexing will always outperform hashing for both queries  
Hashing will always outperform ordered indexing for both queries  
Hashing will outperform ordered indexing on Q1, but not on Q2  
Hashing will outperform ordered indexing on Q2, but not on Q1. 
For example, consider B^{+} tree, once you have searched a key in B^{+}; you can find range of values via the block pointers pointing to another block of values on the leaf node level.
Question 8 
100  
200  
300  
2000 
R(A, B, C) – 200 tuples
S(B, D, E) – 100 tuples
FD’s:
B → A
A → C
― ‘B’ is primary key for R and foreign key of S from the given FDs.
― Maximum tuples in natural join of R and S is min(200, 100) = 100.
Question 9 
Only I and II
 
Only I and III
 
Only I, II and III  
Only I, III and IV 
We have two common columns in 'R' and 'S' which are 'P' and 'Q'.
(I) Both P and Q are used while doing the join, i.e., both P and Q are used to filter.
(II) Q is not used here for filtering. Natural join is done on all P's from R and all P's from S. So different from option (I).
(III) Through venn diagram it can be proved that A∩B = A  (AB).
So through above formula we can say that (III) and (IV) are equivalent.
So finally (I), (III) and (IV) are equivalent.
Question 10 
Courses in which all the female students are enrolled.
 
Courses in which a proper subset of female students are enrolled.
 
Courses in which only male students are enrolled.
 
None of the above

Option B: Yes, True. It selects the proper subset of female students which are enrolled because in the expression we are performing the cartesian product.
Option C: False. It doesn’t shows (or) display the males students who are enrolled.
Question 11 
Consider a selection of the form σ_{A≤100}(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?
50  
100  
150  
200 
Values for A among the tuples are uniformly distributed in the interval [0, 500]. This can be split to 5 mutually exclusive and exhaustive intervals of same width of 100 ([0100], [101200], [201300], [301400], [401500], 0 makes the first interval larger  this must be typ0 in this question) and we can assume all of them have same number of values due to uniform distribution. So no. of tuples with A value in first interval should be,
Total no. of tuples/5 = 1000/5 = 200
Question 12 
П_{cname} (σ_{bal < 0} (σ_{bcity = “Agra”} branch ⋈ account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra”}branch ⋈ (σ_{bal < 0} account ⋈ depositor))  
П_{cname} (σ_{bcity = “Agra”} branch ⋈ σ_{bcity = “Agra” ⋀ bal < 0} account) ⋈ depositor)  
П_{cname} (σ_{bcity = “Agra” ⋀ bal < 0} account ⋈ depositor)) 
Options (C) and (D) are invalid as there is no bcity column in aschema.
Question 13 
s ⊂ r
 
r ∪ s = r
 
r ⊂ s  
r * s = s

Table r: R(A, B, C, D)
Table r_{1}: Π_{A,B,C}(R)
Table r_{2}: Π_{A,D}(R)
S = r_{1} * r_{2} (* denotes natural join)
Table S:
Table r ⊂ Table S
⇒ r ⊂ S
Question 14 
Let R_{1} (A, B, (D)) and R_{2} (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R_{1} referring to R_{2}. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r_{1} and r_{2}. Which one of the following relational algebra expressions would necessarily produce an empty relation?
Π_{D}(r_{2})  Π_{C}(r_{1})
 
Π_{C}(r_{1})  Π_{D}(r_{2})
 
Π_{D}(r_{1}⨝_{C≠D}r_{2})
 
Π_{C}(r_{1}⨝_{C=D}r_{2})

→ Based on referral integrity C is subset of values in R_{2} then,
Π_{C}(r_{1})  Π_{D}(r_{2}) results empty relation.
Question 15 
8, 8  
120, 8
 
960, 8
 
960, 120 
→ In the question only enroll Id's are same with the student table.
→ The no. of minimum and maximum tuples is same i.e., 8, 8.
Question 16 
names of girl students with the highest marks
 
names of girl students with more marks than some boy student
 
names of girl students with marks not less than some boy students
 
names of girl students with more marks than all the boy students

Question 17 
Relational algebra is more powerful than relational calculus.  
Relational algebra has the same power as relational calculus.  
Relational algebra has the same power as safe relational calculus.  
None of the above. 
A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.
Question 18 
Department address of every employee  
Employees whose name is the same as their department name  
The sum of all employees’ salaries  
All employees of a given department 
Question 19 
m + n and 0  
mn and 0  
m + n and m – n  
mn and m + n 
Suppose there is no common attribute in R and S due to which natural join will act as cross product. So then in cross product total no. of tuples will be mn.
For minimum:
Suppose there is common attribute in R and S, but none of the row of R matches with rows of S then minimum no. of tuples will be 0.
Question 20 
σ_{(A=10∨B=20)} (r)  
σ_{(A=10)} (r) ∪ σ_{(B=20)} (r)  
σ_{(A=10)} (r) ∩ σ_{(B=20)} (r)  
σ_{(A=10)} (r)  σ_{(B=20)} (r) 
σ_{(A=10)} (r) ∩ σ_{(B=20)} (r)
Question 21 
R_{1} ∪ R_{2}  
R_{1} × R_{2}  
R_{1}  R_{2}  
R_{1} ∩ R_{2} 
Question 22 
Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R_{1} and R_{2} are relations, C_{1}, C_{2} are selection conditions and A_{1}, A_{2} are attributes of R_{1}?
σ_{C1}(σ_{C1}(R_{1})) → σ_{C2}(σ_{C2}(R_{1}))  
σ_{C1}(σ_{A1}(R_{1})) → σ_{A1}(σ_{C1}(R_{1}))  
σ_{C1}(R_{1} ∪ R_{2}) → σ_{C1}(R_{1}) ∪ σ_{C1}(R_{2})  
π_{A1}(σ_{C1}(R_{1})) → σ_{C1}(σ_{A1}(R_{1})) 
Question 23 
Out of syllabus (For explanation see below) 
→ No need of using Union operation here. → In question they gave (∪, −) but we don't use both.
→ And also they are saying that only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
So, the expression is minimal.
Question 24 
List of all vertices adjacent to a given vertex  
List all vertices which have self loops  
List all vertices which belong to cycles of less than three vertices  
List all vertices reachable from a given vertex 
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.
Question 25 
σ_{A=a} (r)  
r  
σ_{A=a} (r)⨝s  
None of the above 
(b) Display table
(c) A=a for all Tables r and s