Comprehensive GATE DBMS Questions with Solutions: Relational Algebra, Calculus, and Schema Concepts

Question

In a relational database, if A is a foreign key in relation R that references the primary key B in relation S, and X represents the set of non-null values in A, while Y is the set of all values in B, determine the correct relationship between X and Y.

Options:

1. X is a subset of Y
2. X is a proper subset of Y
3. Y is a subset of X
4. X and Y do not need to be subsets of each other

Correct Answer:

X is a subset of Y

Solution:

A foreign key ensures that every non-null value of A in R corresponds to a value in B in S. Therefore, the set of all non-null values of A (denoted by X) must be contained within the set of all values of B (denoted by Y). Mathematically, this relationship is represented as X ⊆ Y. Thus, the correct answer is X is a subset of Y.

Question

Given the relations S1(P, Q, R) and S2(T, U, V) with the following instances:

Relation S1:

P	Q	R
1	2	3
5	10	4
2	4	3
3	6	5
1	2	5

Relation S2:

T	U	V
1	2	3
2	4	2
1	2	4
3	6	2

Evaluate the result of the following relational algebra query:

ΠP, Q(σR=3 ∨ R=5(S1)) - ΠT, U(σV≠2 ∨ V=3(S2))

Options:

1. Empty relation
2. { (2,4), (3,6) }
3. A relation with schema (P, Q) and tuples { (1,2) }
4. A relation with schema (P, Q) and tuples { (1,2), (2,4), (3,6) }

Correct Answer:

Empty relation

Solution:

1. Step 1: Evaluate ΠP, Q(σR=3 ∨ R=5(S1)).
   Result: { (1,2), (2,4), (3,6) }
2. Step 2: Evaluate ΠT, U(σV≠2 ∨ V=3(S2)).
   Result: { (1,2) }
3. Step 3: Perform the set difference: { (1,2), (2,4), (3,6) } – { (1,2) }.
   Result: Empty relation

Thus, the result of the relational algebra expression is an empty relation.

Question

Given the relations S1(P, Q, R) and S2(T, U, V) with the following instances:

Relation S1:

P	Q	R
1	2	3
5	10	4
2	4	3
3	6	5
1	2	5

Relation S2:

T	U	V
1	2	3
2	4	2
1	2	4
3	6	2

Evaluate the number of tuples in the result of the following relational algebra query:

S1 ⨝S1.Q ≥ S2.V S2

Options:

1. 20
2. 9
3. 8
4. 16

Correct Answer:

16

Solution:

1. Step 1: Understand the query S1 ⨝S1.Q ≥ S2.V S2.
   This is a natural join where tuples from S1 and S2 are combined if S1.Q ≥ S2.V.
2. Step 2: Evaluate the condition:
   • For S1(1,2,3): Valid S2 tuples: { (2,4,2), (3,6,2) } → 2 matches.
   • For S1(5,10,4): Valid S2 tuples: All tuples → 4 matches.
   • For S1(2,4,3): Valid S2 tuples: { (2,4,2), (3,6,2) } → 2 matches.
   • For S1(3,6,5): Valid S2 tuples: { (2,4,2), (1,2,3), (3,6,2) } → 3 matches.
   • For S1(1,2,5): Valid S2 tuples: { (2,4,2), (3,6,2) } → 2 matches.
3. Step 3: Total matches = 2 + 4 + 2 + 3 + 2 = 16.

The result contains 16 tuples.

Question

Four database relations R1(A, B, C), R2(X, Y, Z), R3(A, B, D), and R4(U, X, Y) are defined with the following domains for their attributes:

• A, U: Integers
• B, X: Strings
• C, Y: Single characters
• D, Z: { ‘M’, ‘F’ }

Determine which pair of relations is union-compatible.

Options:

1. R1, R3
2. R1, R4
3. R2, R3
4. R3, R4

Correct Answer:

R1, R4

Solution:

To determine union compatibility, the following conditions must be satisfied:

1. Both relations must have the same number of attributes.
2. Corresponding attributes of both relations must have the same domains.

Step 1: Analyze attribute counts for all relations

• R1(A, B, C): 3 attributes
• R2(X, Y, Z): 3 attributes
• R3(A, B, D): 3 attributes
• R4(U, X, Y): 3 attributes

Since all relations have 3 attributes, we proceed to domain comparison.

Step 2: Compare attribute domains

• Pair R1, R3: Mismatch in the third attribute: C (Single Character) vs. D ({ ‘M’, ‘F’ }) → Not compatible.
• Pair R1, R4: All attributes match in domains → Compatible.
• Pair R2, R3: Mismatch in the first attribute: X (String) vs. A (Integer) → Not compatible.
• Pair R3, R4: Mismatch in the third attribute: D ({ ‘M’, ‘F’ }) vs. Y (Single Character) → Not compatible.

Step 3: Identify the correct pair

The only pair of union-compatible relations is R1 and R4.

Question

Given the relations S1(P, Q, R) and S2(P, R) as shown below, calculate the result of the relational algebra division operation S1 ÷ S2.

Relation S1
P	Q	R
1	2	2
1	4	2
2	4	4
1	6	2
2	2	4

Relation S2
P	R
1	2
2	4

Options:

1. Empty relation
2. A relation with scheme Q and tuples { (2), (4) }
3. A relation with scheme Q and tuples { (2), (4), (6) }
4. { 2, 4 }

Correct Answer:

A relation with scheme Q and tuples { (2), (4) }

Solution:

Relational division S1 ÷ S2 computes all values in S1.Q such that for every tuple in S2(P, R), there exists a corresponding tuple in S1(P, Q, R).

Step 1: Identify S2(P, R) tuples:

The tuples in S2 are:

• (1, 2)
• (2, 4)

Step 2: Check S1(P, Q, R) for values of Q:

The goal is to find all Q-values in S1 such that for each (P, R)-pair in S2, there is a corresponding tuple in S1.

• Q = 2: All pairs in S2 are matched → Valid.
• Q = 4: All pairs in S2 are matched → Valid.
• Q = 6: Not all pairs in S2 are matched → Invalid.

Step 3: Final result:

The valid Q-values are { 2, 4 }.

Answer: A relation with scheme Q and tuples { (2), (4) }.

Question

Given the relation S1 and its instance shown below, compute the size of the result of the following relational algebra expression:

πP, Q(S1) ⋈ πQ, R(S1)

Relation S1
P	Q	R
1	2	3
3	4	5
2	4	6
3	3	5
4	2	3

Options:

1. 5
2. 6
3. 7
4. 8

Correct Answer:

7

Solution:

Relational algebra expression:

πP, Q(S1) ⋈ πQ, R(S1)

Step 1: Compute πP, Q(S1):

Projection of S1 onto P and Q:

P	Q
1	2
3	4
2	4
3	3
4	2

Step 2: Compute πQ, R(S1):

Projection of S1 onto Q and R:

Q	R
2	3
4	5
4	6
3	5
2	3

Step 3: Perform natural join:

The natural join combines tuples from πP, Q(S1) and πQ, R(S1) where Q matches in both relations.

P	Q	R
1	2	3
4	2	3
3	4	5
2	4	5
2	4	6
3	3	5

Final Result:

The size of the result is 7 tuples.

Answer: 7

Question

Given the relation from the previous question, determine the size of the result for the relational algebra expression below:

ρP,O₁(πP,Q(S1)) ⋈Q₁ ≥ Q₂ ρQ₂,R(πQ,R(S1))

Options:

1. 9
2. 10
3. 11
4. 12

Correct Answer:

12

Solution:

Step 1: Compute π_P,Q(S1)

Project S1 onto P and Q:

P	Q
1	2
3	4
2	4
3	3
4	2

Rename the attributes as P, Q₁:

P	Q₁
1	2
3	4
2	4
3	3
4	2

Step 2: Compute π_Q,R(S1)

Project S1 onto Q and R:

Q	R
2	3
4	5
4	6
3	5
2	3

Rename the attributes as Q₂, R:

Q₂	R
2	3
4	5
4	6
3	5
2	3

Step 3: Perform the natural join with condition Q₁ ≥ Q₂

Join the two relations on Q₁ and Q₂ such that Q₁ ≥ Q₂:

P	Q₁	Q₂	R
1	2	2	3
4	2	2	3
3	4	2	3
3	4	3	5
3	4	4	5
2	4	2	3
2	4	4	5
3	3	2	3
3	3	3	5
4	2	2	3
1	2	2	3
3	3	3	5

Final Result:

The size of the result is 12 tuples.

Answer: 12

Question

Consider two weak entities E₁ and E₂, where E₁ serves as the owner entity for E₂. During relational representation, which of the following is true?

Options:

1. E₁ should be mapped before E₂
2. E₂ should be mapped before E₁
3. Both E₁ and E₂ can be mapped in any order
4. The partial key of E₁ encompasses the partial key of E₂

Correct Answer:

E₁ should be mapped before E₂

Solution:

Explanation:

• Weak entities depend on their owner entities for identification, as they cannot be uniquely identified by their attributes alone.
• In this case, E₂ is dependent on E₁ since E₁ is the owner entity.
• Therefore, E₁ must be mapped first in order to establish the foreign key reference for E₂.

Answer: E₁ should be mapped before E₂.

Question

Evaluate the following statements regarding referencing and referenced relations:

• S1: Every record in a referencing relation is associated with at most one record in the referenced relation.
• S2: A single record in the referenced relation can correspond to multiple (0 or more) records in the referencing relation.

Which of the following is true?

Options:

1. Both S1 and S2 are true
2. S1 is false, S2 is true
3. Both S1 and S2 are false
4. S1 is true, S2 is false

Correct Answer:

Both S1 and S2 are true

Solution:

Explanation:

• S1: In a referencing relation, foreign keys are used to refer to records in the referenced relation. As a result, each record in the referencing relation can associate with at most one record in the referenced relation through the foreign key. Hence, S1 is true.
• S2: A single record in the referenced relation can correspond to multiple records in the referencing relation, which aligns with the concept of one-to-many or many-to-one relationships. Therefore, S2 is also true.

Answer: Both S1 and S2 are true.

Question

Consider two relations R1(A1, A2, A3, A4) and R2(A1, A2, A5, A6), where the attributes {A1, A2} form the primary key for both relations. Analyze the following statements:

• S1: The projection query πA1(R1 * R2) is equivalent to πA1(R1) * πA1(R2).
• S2: The projection query πA1(R1 * R2) is equivalent to πA1(πA1,A2(R1) - (πA1,A2(R1) - πA1,A2(R2))).

Choose the correct option:

Options:

1. Both S1 and S2 are true
2. S1 is false, S2 is true
3. Both S1 and S2 are false
4. S1 is true, S2 is false

Correct Answer:

S1 is false, S2 is true

Solution:

Explanation:

• S1: The query πA1(R1 * R2) projects only A1 from the natural join of R1 and R2. However, the query πA1(R1) * πA1(R2) computes the Cartesian product of πA1(R1) and πA1(R2), which is not equivalent to the projection of πA1(R1 * R2). Thus, S1 is false.
• S2: The expression πA1(πA1,A2(R1) - (πA1,A2(R1) - πA1,A2(R2))) effectively retains all A1 values in R1 that also exist in R2, which is the correct interpretation of the projection of A1 from R1 * R2. Hence, S2 is true.

Answer: S1 is false, S2 is true.

Question

Consider the following two statements:

• S1: A single relation cannot have multiple foreign keys.
• S2: A relation cannot have multiple foreign keys because a single attribute cannot refer to multiple primary keys in different relations.

Which of the following is correct?

1. S1 is true, S2 is false
2. Both S1 and S2 are true, and S2 correctly explains S1
3. Both S1 and S2 are true, but S2 does not correctly explain S1
4. Both S1 and S2 are false

Correct Answer:

Both S1 and S2 are false

Solution:

Explanation:

• S1: This statement is false because a single relation can have multiple foreign keys. For example, in a student database, a “Course Enrollments” relation can have a foreign key referencing both the “Students” table and the “Courses” table.
• S2: This statement is also false because multiple attributes in a relation can reference primary keys in different relations. What is not allowed is a single attribute serving as a foreign key to multiple primary keys simultaneously, which is not relevant here.

Thus, both statements S1 and S2 are false.

Question

Given two relations R1(A, B) and R2(B, C), the tables are defined as follows:

R1			R2
A	B		B	C
4	8		3	3
3	6		3	6
2	4		2	4

Assume that R(B, B, C) represents the full natural outer join of R1 and R2. Consider the following tuples generated by this join:

• t1 = (4, 8, NULL)
• t2 = (NULL, 3, 6)
• t3 = (2, 4, NULL)
• t4 = (3, 6, 3)
• t5 = (NULL, 6, NULL)
• t6 = (NULL, 2, 4)

Which of the following is true?

1. R contains only t1, t3, and t4
2. R contains only t2, t4, and t6
3. R contains all tuples
4. R contains t1, t2, t3, t4, t6, but not t5

Correct Answer:

R contains t1, t2, t3, t4, t6 but not t5

Solution:

Explanation:

• t1 = (4, 8, NULL): This tuple originates from R1 since B = 8 has no corresponding match in R2.
• t2 = (NULL, 3, 6): This tuple originates from R2 since B = 3 is matched in R1 but does not exist in R1 in the exact form.
• t3 = (2, 4, NULL): This tuple originates from R1 as B = 4 does not find a match in R2.
• t4 = (3, 6, 3): This tuple comes from the natural join of B = 6 from both R1 and R2.
• t5 = (NULL, 6, NULL): This tuple does not belong to R because B = 6 already appears in t4 through a valid join.
• t6 = (NULL, 2, 4): This tuple originates from R2 where B = 2 does not find a match in R1.

Hence, the relation R contains t1, t2, t3, t4, and t6, but not t5.

Question

Evaluate the following statements:

1. Statement P: Any query that can be expressed using relational algebra can also be expressed in relational calculus.
2. Statement Q: Any query that can be expressed using relational calculus can also be expressed in relational algebra.

Select the correct option:

1. Statement P is true, Statement Q is false
2. Statement P is false, Statement Q is true
3. Both Statements P and Q are true
4. Both Statements P and Q are false

Correct Answer:

Both Statements P and Q are true

Solution:

Explanation:

Relational algebra and relational calculus are both formal query languages for relational databases:

• Relational Algebra: A procedural query language that specifies how to retrieve the required data.
• Relational Calculus: A declarative query language that specifies what data is required without stating how to retrieve it.

Both relational algebra and relational calculus are equally expressive, meaning:

• Every query expressible in relational algebra can also be expressed in relational calculus.
• Every query expressible in relational calculus can also be expressed in relational algebra.

Therefore, both statements P and Q are true.

Question

Evaluate the following statements about Tuple Relational Calculus (TRC):

1. Statement P: TRC is a declarative (non-procedural) query language used in relational databases.
2. Statement Q: In TRC, the query specifies what data to retrieve but not how to retrieve it.

Choose the correct option:

1. Statement P is true, Statement Q is false
2. Both Statements P and Q are true, and Statement Q correctly explains Statement P
3. Both Statements P and Q are true, but Statement Q does not explain Statement P
4. Both Statements P and Q are false

Correct Answer:

Both Statements P and Q are true, and Statement Q correctly explains Statement P

Solution:

Explanation:

• Tuple Relational Calculus (TRC) is a non-procedural query language. Unlike procedural query languages like relational algebra, TRC focuses on describing what data needs to be fetched without specifying how to perform the retrieval.
• The goal of TRC is to express conditions that the required tuples must satisfy, thus making Statement P true.
• Statement Q further explains that TRC is declarative in nature because it specifies what to retrieve rather than detailing the steps for retrieval, which is the correct explanation for Statement P.

Therefore, both Statements P and Q are true, and Q correctly explains P.

Question

Given the following relational schema:

• Student(rollNo, name, degree, year, sex, deptNo, advisor)
• Courses(courseId, cname, credits, deptNo)
• Enrollment(rollNo, courseId, sem, year, grade)

where rollNo and courseId serve as foreign keys linking Enrollment to the Student and Courses tables, respectively.

Analyze the TRC query below:

{ s.rollNo, s.name | Student(s) ∧ ∃e1 (Enrollment(e1) ∧ (e1.rollNo = s.rollNo)) }

Which of the following correctly interprets the query?

1. Fetch the roll numbers and names of students who have enrolled in exactly one course.
2. Fetch the roll numbers and names of students who have enrolled in more than one course.
3. Fetch the roll numbers and names of students who have enrolled in at least one course.
4. Fetch the roll numbers and names of students who have all enrolled in the same course.

Correct Answer:

Fetch the roll numbers and names of students who have enrolled in at least one course.

Solution:

Explanation:

• The TRC query { s.rollNo, s.name | Student(s) ∧ ∃e1 (Enrollment(e1) ∧ (e1.rollNo = s.rollNo)) } retrieves the roll number and name of each student s from the Student table who satisfies the condition that there exists at least one record in the Enrollment table such that the rollNo in Enrollment matches that of the student s.
• This indicates that the student has enrolled in at least one course.

Hence, the correct interpretation of the query is: “Fetch the roll numbers and names of students who have enrolled in at least one course.”

Question

Analyze the relational schema provided below and the corresponding TRC query:

Schema:

• Student(rollNo, name, degree, year, sex, deptNo, advisor)
• Courses(courseId, cname, credits, deptNo)
• Enrollment(rollNo, courseId, sem, year, grade)

Query:

{ s.rollNo | Student(s) ∧ ∃e1(Enrollment(e1) ∧ (e1.rollNo = s.rollNo)) ∧ ¬(∃e2)(∃e3)(Enrollment(e2) ∧ Enrollment(e3) ∧ e2.rollNo = e3.rollNo ∧ e2.courseId ≠ e3.courseId ∧ s.rollNo = e2.rollNo)) }

Options:

1. Roll numbers of students who have enrolled in at least one course
2. Roll numbers of students who have enrolled in at least two courses
3. Roll numbers of students who have enrolled in exactly one course
4. Roll numbers of students who have enrolled in some course

Correct Answer:

Roll numbers of students who have enrolled in exactly one course.

Solution:

Explanation:

• The first part of the query, ∃e1(Enrollment(e1) ∧ (e1.rollNo = s.rollNo)), ensures that the student has enrolled in at least one course.
• The negated second part, ¬(∃e2)(∃e3)(Enrollment(e2) ∧ Enrollment(e3) ∧ e2.rollNo = e3.rollNo ∧ e2.courseId ≠ e3.courseId ∧ s.rollNo = e2.rollNo), ensures that there do not exist two distinct enrollments for the same student s where the courses are different (e2.courseId ≠ e3.courseId).

Combining these, the query fetches the roll numbers of students who have enrolled in exactly one course.

Question

Given the following relational schema where cid in the Enrollment relation acts as a foreign key referencing cid in the Courses relation:

Schema:

• Enrollment(sid, cid, grade)
• Courses(cid, cname, instructor)

Relational Algebra Division:

πsid,cid(Enrollment) ÷ πcid(Courses)

Equivalent TRC Query:

{ e.sid | Enrollment(e) ∧ ∀c(Courses(c) op1 ∃e1(Enrollment(e1) ∧ c.cid = e1.cid op2 e1.sid = e.sid)) }

Options:

1. ⇒, ∧
2. ∧, ⇒
3. ⇒, ⇒
4. ∧, ∧

Correct Answer:

⇒, ∧

Solution:

Explanation:

1. The division operation in relational algebra retrieves sid values from Enrollment such that for every cid in Courses, there exists a corresponding tuple in Enrollment with the same cid.
2. The TRC translation requires:
   • op1 = ⇒: Ensures that for all tuples in Courses, the condition holds.
   • op2 = ∧: Specifies that both the cid and sid conditions must hold simultaneously.

Thus, the correct operators are op1 = ⇒ and op2 = ∧.