Relational-Algebra

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 outer-join operation. Assume that r and s contain no null values.

Which one of the following is NOT equivalent to Q?

A
σB<5 (r ⨝ s)
B
σB<5 (r LOJ s)
C
r LOJ (σB<5(s))
D
σB<5(r) LOJ s
       Database-Management-System       Relational-Algebra       Gate 2018
Question 1 Explanation: 
Consider the following 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 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?

A
(I) and (II) only
B
(I) and (III) only
C
(II) and (III) only
D
(I), (II) and (III)
       Database-Management-System       Relational-Algebra       Gate 2017 set-01
Question 2 Explanation: 
An expression is said to be safe, if it yield a finite number of tuples, otherwise unsafe.
(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 ← πCourseNameStudentName='SA'(CR))
         T2 ← CR ÷ T1

The number of rows in T2 is ____________.

 
A
4
B
5
C
6
D
7
       Database-Management-System       Relational-Algebra       Gate 2017 set-01
Question 3 Explanation: 
(1) T1 ← πCourseNameStudentName = 'SA'(CR))
The σStudentName = 'SA'(CR) will produce the following

⇾ The result of T1 ← πCourseNameStudentName='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
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?  
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
       Database-Management-System       Relational-Algebra       GATE 2015 -(Set-2)
Question 4 Explanation: 

⋆ So, from the above resultant table, R contains e, f, g only but not a, b.
Question 5
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?
A
B (r1) - ∏C (r2) = ∅
B
C (r2) - ∏B (r1) = ∅
C
B (r1) = ∏C (r2)
D
B (r1) - ∏C (r2) ≠ ∅
       Database-Management-System       Relational-Algebra       Gate 2012
Question 5 Explanation: 
Referential integrity means, all the values in foreign key should be present in primary key.
So we can say that r2(C) is the superset of r1(B).
So (subset - superset) is always empty.
Question 6
     
A
7
B
4
C
5
D
9
       Database-Management-System       Relational-Algebra       Gate 2012
Question 6 Explanation: 


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
 
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.
       Database-Management-System       Relational-Algebra       Gate 2011
Question 7 Explanation: 
Hashing works well on the "equal" queries, while ordered indexing works well better on range queries.
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
 
A
100
B
200
C
300
D
2000
       Database-Management-System       Relational-Algebra       2010
Question 8 Explanation: 
Given
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
 
A
Only I and II
B
Only I and III
C
Only I, II and III
D
Only I, III and IV
       Database-Management-System       Relational-Algebra       Gate-2008
Question 9 Explanation: 
Natural join is based on the common columns of the two tables.
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 - (A-B).
So through above formula we can say that (III) and (IV) are equivalent.
So finally (I), (III) and (IV) are equivalent.
Question 10
 
A
Courses in which all the female students are enrolled.
B
Courses in which a proper subset of female students are enrolled.
C
Courses in which only male students are enrolled.
D
None of the above
       Database-Management-System       Relational-Algebra       Gate-2007
Question 10 Explanation: 
Option A: It is not result the all the female students who are enrolled. So option A is false.
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 ?

A
50
B
100
C
150
D
200
       Database-Management-System       Relational-Algebra       Gate 2007-IT
Question 11 Explanation: 
σA≤100(r), r has 1000 tuples.
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 ([0-100], [101-200], [201-300], [301-400], [401-500], 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
 
A
Пc-namebal < 0b-city = “Agra” branch ⋈ account) ⋈ depositor)
B
Пc-nameb-city = “Agra”branch ⋈ (σbal < 0 account ⋈ depositor))
C
Пc-nameb-city = “Agra” branch ⋈ σb-city = “Agra” ⋀ bal < 0 account) ⋈ depositor)
D
Пc-nameb-city = “Agra” ⋀ bal < 0 account ⋈ depositor))
       Database-Management-System       Relational-Algebra       Gate 2007-IT
Question 12 Explanation: 
Answer should be (A) and not (B), because we are doing a join between two massive tables whereas in (A) we are doing join between relatively smaller table and larger one and the output that this inner table gives (which is smaller in comparision to join that we are doing in (B)) is used for join with depositor table with the selection condition.
Options (C) and (D) are invalid as there is no b-city column in a-schema.
Question 13
Let r be a relation instance with schema R = (A, B, C, D). We define r1 = ΠA,B,C (R) and r2 = ΠA,D (R). Let s = r1 * r2 where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE?
A
s ⊂ r
B
r ∪ s = r
C
r ⊂ s
D
r * s = s
       Database-Management-System       Relational-Algebra       Gate-2005
Question 13 Explanation: 
Let us consider an example:
Table r: R(A, B, C, D)

Table r1: ΠA,B,C(R)

Table r2: ΠA,D(R)

S = r1 * r2 (* denotes natural join)
Table S:

Table r ⊂ Table S
⇒ r ⊂ S
Question 14

Let R1 (A, B, (D)) and R2 (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R1 referring to R2. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r1 and r2. Which one of the following relational algebra expressions would necessarily produce an empty relation? 

A
ΠD(r2) - ΠC(r1)
B
ΠC(r1) - ΠD(r2)
C
ΠD(r1C≠Dr2)
D
ΠC(r1C=Dr2)
       Database-Management-System       Relational-Algebra       Gate-2004
Question 14 Explanation: 
C be a foreign key in R1 referring to R2.
→ Based on referral integrity C is subset of values in R2 then,
ΠC(r1) - ΠD(r2) results empty relation.
Question 15
 
A
8, 8
B
120, 8
C
960, 8
D
960, 120
       Database-Management-System       Relational-Algebra       Gate-2004
Question 15 Explanation: 
Natural join is a JOIN operation that creates an implicit join cause for you based on common columns in the two tables being joined.
→ 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
     
A
names of girl students with the highest marks
B
names of girl students with more marks than some boy student
C
names of girl students with marks not less than some boy students
D
names of girl students with more marks than all the boy students
       Database-Management-System       Relational-Algebra       Gate-2004
Question 16 Explanation: 
In the operator '-' between the two subexpression gives the names of all female students whose marks are greater than the all the male students of the class.
Question 17
With regard to the expressive power of the formal relational query languages, which of the following statements is true?
A
Relational algebra is more powerful than relational calculus.
B
Relational algebra has the same power as relational calculus.
C
Relational algebra has the same power as safe relational calculus.
D
None of the above.
       Database-Management-System       Relational-Algebra       Gate-2002
Question 17 Explanation: 
Relational algebra has the same power as safe relational calculus.
A query can be formulated in safe Relational Calculus if and only if it can be formulated in Relational Algebra.
Question 18
 
A
Department address of every employee
B
Employees whose name is the same as their department name
C
The sum of all employees’ salaries
D
All employees of a given department
       Database-Management-System       Relational-Algebra       Gate-2000
Question 18 Explanation: 
The sum of all employee’s salaries can’t be represented by using the given six basic algebra operation. If we want to represent sum of salaries then we need to use aggregation operator.
Question 19
Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are
A
m + n and 0
B
mn and 0
C
m + n and |m – n|
D
mn and m + n
       Database-Management-System       Relational-Algebra       Gate-1999
Question 19 Explanation: 
For maximum:
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
σ(A=10∨B=20) (r)
B
σ(A=10) (r) ∪ σ(B=20) (r)
C
σ(A=10) (r) ∩ σ(B=20) (r)
D
σ(A=10) (r) - σ(B=20) (r)
       Database-Management-System       Relational-Algebra       Gate-1999
Question 20 Explanation: 
The given relational algebra expression represents tuples having A=10 and B=20 which is equivalent to
σ(A=10) (r) ∩ σ(B=20) (r)
Question 21
Given two union compatible relations R1(A,B) and R2 (C,D), what is the result of the operation R1A = CAB = DR2?
A
R1 ∪ R2
B
R1 × R2
C
R1 - R2
D
R1 ∩ R2
       Database-Management-System       Relational-Algebra       Gate-1998
Question 21 Explanation: 
The join here will be selecting only those tuples where A=C and B=D, meaning it is the intersection.
Question 22

Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R1 and R2 are relations, C1, C2 are selection conditions and A1, A2 are attributes of R1?

 
A
σC1C1(R1)) → σC2C2(R1))
B
σC1A1(R1)) → σA1C1(R1))
C
σC1(R1 ∪ R2) → σC1(R1) ∪ σC1(R2)
D
πA1C1(R1)) → σC1A1(R1))
       Database-Management-System       Relational-Algebra       Gate-1998
Question 22 Explanation: 
If the selection condition is on attribute A2, then we cannot replace it by RHS as there will not be any attribute A2 due to projection of A1 only.
Question 23
Give a relational algebra expression using only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.  
A
Out of syllabus (For explanation see below)
       Database-Management-System       Relational-Algebra       Gate-1994
Question 23 Explanation: 
R - (R - S)
→ 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
Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?
A
List of all vertices adjacent to a given vertex
B
List all vertices which have self loops
C
List all vertices which belong to cycles of less than three vertices
D
List all vertices reachable from a given vertex
       Database-Management-System       Relational-Algebra       Gate-2001
Question 24 Explanation: 
(a) Finding a adjaceny vertex for the given vertex is too simple i.e., Adj(X,Y).
(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
Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression σA=a(r⋈s) is always equal to
A
σA=a (r)
B
r
C
σA=a (r)⨝s
D
None of the above
       Database-Management-System       Relational-Algebra       Gate-2001
Question 25 Explanation: 
(a) A=a for all r
(b) Display table
(c) A=a for all Tables r and s
There are 25 questions to complete.