Mastering Relational Algebra, SQL, and Functional Dependencies for Competitive Exams

 

In today’s competitive world, mastering database concepts is not just a requirement for academic excellence but also a necessity for clearing challenging competitive exams like GATE CSE, UGC NET, NIELIT, and ISRO. Topics like relational algebra, functional dependencies, normalization, and SQL form a crucial part of these exams. This guide is designed to help you understand these key topics and excel in your preparation.

Why Focus on Relational Algebra and SQL?

Relational algebra and SQL are not just theoretical concepts but practical tools for interacting with and managing databases. By mastering these, you can:

• Write optimized database queries.
• Understand and apply normalization techniques.
• Solve tricky questions on functional dependencies and schema design.
• Crack competitive exams like GATE, UGC NET, and ISRO Scientist roles.

Key Topics to Master for Relational Algebra and SQL

1. Relational Algebra

Relational algebra is the foundation of database queries, involving operations like selection (σ), projection (π), natural joins (⋈), and set operations like union (∪) and intersection (∩). Questions often involve deriving equivalent queries or solving complex relational expressions.

2. SQL

SQL (Structured Query Language) is widely used to manage relational databases. Common topics include writing SELECT queries, using GROUP BY and aggregate functions like SUM, and understanding query optimization. Ensure you understand concepts like primary keys, foreign keys, and referential integrity.

3. Normalization and Functional Dependencies

Normalization ensures data integrity by eliminating redundancy. Functional dependencies help determine how attributes in a schema relate to each other. Understand the progression from 1NF to BCNF and beyond, along with rules for lossless join decomposition.

Tips to Excel in DBMS for Competitive Exams

1. Understand Core Concepts: Use standard textbooks like “Database System Concepts” by Korth and Silberschatz.
2. Practice Numerical Examples: Solve questions from past GATE and UGC NET papers.
3. Take Mock Tests: Time-bound practice improves speed and accuracy.
4. Create Cheat Sheets: Summarize formulas and key SQL syntax for quick reference.

Why This Guide Stands Out

At Digiimento Education, we provide easy-to-understand, SEO-friendly content tailored for students preparing for competitive exams. This guide includes:

• Step-by-step solutions to challenging problems.
• Examples and exercises for better clarity.
• Practical tips to improve accuracy and speed in exams.

 

 

Question

Consider the following relations:

• P(X, Y)
• Q(Y, Z)

And the following four relational algebra queries over P and Q:

1. πX,Y(P ⋈ Q)
2. P ⋈ πY(Q)
3. P ∩ (πX(P) × πY(Q))
4. πX,P.Y(P × Q), where P.Y refers to column Y in table P

Determine which of the following statements is true:

1. I, III, and IV are the same query
2. II, III, and IV are the same query
3. I, II, and IV are the same query
4. I, II, and III are the same query

Solution

Let us assume:

• P = {(10, 1), (20, 2)}
• Q = {(2, 30), (3, 40)}

Evaluating the queries:

1. Query I:
   P ⋈ Q = {(20, 2, 30)}.
   Projecting columns X and Y, we get:
   πX,Y(P ⋈ Q) = {(20, 2)}.
2. Query II:
   πY(Q) = {(2), (3)}.
   Performing the natural join with P, we get:
   P ⋈ πY(Q) = {(20, 2)}.
3. Query III:
   πX(P) × πY(Q) = {(10, 2), (10, 3), (20, 2), (20, 3)}.
   Taking the intersection with P, we get:
   P ∩ (πX(P) × πY(Q)) = {(20, 2)}.
4. Query IV:
   P × Q = {(10, 1, 2, 30), (10, 1, 3, 40), (20, 2, 2, 30), (20, 2, 3, 40)}.
   Projecting columns X and P.Y, we get:
   πX,P.Y(P × Q) = {(10, 2), (10, 3), (20, 2), (20, 3)}.
   Note that this differs from the other queries.

Correct Answer: D. I, II, and III are the same query.

 

 

Question

Which of the following relational query languages have equivalent expressive power?

1. Relational Algebra
2. Tuple Relational Calculus (restricted to safe expressions)
3. Domain Relational Calculus (restricted to safe expressions)

Choose the correct option:

1. II and III only
2. I and II only
3. I and III only
4. I, II, and III

Answer

Correct Option: D. I, II, and III

Explanation: Relational Algebra, Tuple Relational Calculus (safe expressions), and Domain Relational Calculus (safe expressions) all have equivalent expressive power. They can represent the same set of queries over a database. The restriction to safe expressions ensures that both calculi avoid producing infinite or undefined results, making them practically equivalent to Relational Algebra.

 

 

Question

Consider the following schemas:

• Branch(Branch_Name, Assets, Branch_City)
• Customer(Customer_Name, Bank_Name, Customer_City)
• Borrow(Branch_Name, Loan_Number, Customer_Account_Number)
• Deposit(Branch_Name, Account_Number, Customer_Name, Balance)

Using relational algebra, which of the following queries retrieves the names of customers who have a balance greater than 10,000?

1. π_{Customer_Name}(σ_{Balance > 10000}(Deposit))
2. σ_{Customer_Name}(σ_{Balance > 10000}(Deposit))
3. π_{Customer_Name}(σ_{Balance > 10000}(Borrow))
4. σ_{Customer_Name}(π_{Balance > 10000}(Borrow))

Answer

Correct Option: A. π_{Customer_Name}(σ_{Balance > 10000}(Deposit))

Explanation:

The table Deposit contains information about customer balances. To retrieve the names of customers with balances greater than 10,000, we first apply a selection operation (σBalance > 10000) to filter the rows in the Deposit table. Then, we apply a projection operation (πCustomer_Name) to extract the Customer_Name column. Hence, option A is the correct answer.

 

 

Question

Suppose R is a relation schema, and F is a set of functional dependencies on R. Further, assume that R1 and R2 form a decomposition of R. The decomposition is a lossless join decomposition of R if:

1. R1 ∩ R2 → R1 is in F+
2. R1 ∩ R2 → R2 is in F+
3. Both R1 ∩ R2 → R1 and R1 ∩ R2 → R2 are in F+
4. At least one of R1 ∩ R2 → R1 or R1 ∩ R2 → R2 is in F+

Answer

Correct Option: D. At least one of R1 ∩ R2 → R1 or R1 ∩ R2 → R2 is in F+

Explanation:

A decomposition of a relation schema R into R1 and R2 is considered a lossless join decomposition if at least one of the following functional dependencies is present in the closure of F (F+):

• R1 ∩ R2 → R1
• R1 ∩ R2 → R2

This ensures that when R1 and R2 are joined back together, no spurious tuples are introduced, and the original relation R can be accurately reconstructed. Hence, option D is correct.

 

 

Question

Armstrong (1974) proposed a systematic approach to derive functional dependencies. Match the following rules with respect to functional dependencies:

List-I	List-II
a. Decomposition Rule	i. If X → Y and Z → W, then {X, Z} → {Y, W}
b. Union Rule	ii. If X → Y and {Y, W} → Z, then {X, W} → Z
c. Composition Rule	iii. If X → Y and X → Z, then X → {Y, Z}
d. Pseudo Transitivity Rule	iv. If X → {Y, Z}, then X → Y and X → Z

Codes:

1. a-iii, b-ii, c-iv, d-i
2. a-i, b-iii, c-iv, d-ii
3. a-ii, b-i, c-iii, d-iv
4. a-iv, b-iii, c-i, d-ii

Answer

Correct Option: D. a-iv, b-iii, c-i, d-ii

Explanation:

• Decomposition Rule: If X → {Y, Z}, then X → Y and X → Z.
• Union Rule: If X → Y and X → Z, then X → {Y, Z}.
• Composition Rule: If X → Y and Z → W, then {X, Z} → {Y, W}.
• Pseudo Transitivity Rule: If X → Y and {Y, W} → Z, then {X, W} → Z.

 

 

Question

Match the following:

Normalization Form	Characteristics
a. 2NF	i. Transitive dependencies eliminated
b. 3NF	ii. Multivalued attribute removed
c. 4NF	iii. Contain no partial functional dependencies
d. 5NF	iv. Contains no join dependencies

Codes:

1. a-i, b-iii, c-ii, d-iv
2. a-ii, b-iii, c-iv, d-i
3. a-iii, b-iv, c-i, d-ii
4. a-iii, b-ii, c-iv, d-i

Answer

Correct Option: D. a-iii, b-ii, c-iv, d-i

Explanation:

• 2NF: Eliminates partial functional dependencies, ensuring no attribute is partially dependent on a candidate key.
• 3NF: Removes transitive dependencies, ensuring that non-prime attributes are dependent only on the candidate key.
• 4NF: Eliminates multivalued dependencies, ensuring that a relation has no non-trivial multivalued dependencies.
• 5NF: Removes join dependencies, ensuring that a relation is reconstructed without loss using projections.

 

Question

Consider the following relational schemas for a library database:

• Book(Title, Author, Catalog_no, Publisher, Year, Price)
• Collection(Title, Author, Catalog_no)

With the following functional dependencies:

1. Title, Author → Catalog_no
2. Catalog_no → Title, Author, Publisher, Year
3. Publisher, Title, Year → Price

Assume that (Author, Title) is the key for both schemas. Which one of the following is true?

1. Both Book and Collection are in BCNF.
2. Both Book and Collection are in 3NF.
3. Book is in 2NF and Collection is in 3NF.
4. Both Book and Collection are in 2NF.

Answer

Correct Option: C. Book is in 2NF and Collection is in 3NF

Explanation:

Book Schema:

• Keys: (Author, Title)
• From the functional dependencies:
  • Title, Author → Catalog_no eliminates partial dependencies, satisfying 2NF.
  • Catalog_no → Title, Author, Publisher, Year and Publisher, Title, Year → Price introduce transitive dependencies, preventing the schema from satisfying 3NF.
• Hence, the Book schema is in 2NF but not in 3NF.

Collection Schema:

• Keys: (Author, Title)
• There are no partial or transitive dependencies in the Collection schema, satisfying both 2NF and 3NF.
• Additionally, the schema is in BCNF as all dependencies are on superkeys.

Thus, the Book schema is in 2NF, while the Collection schema is in 3NF and BCNF.

 

 

Question

If a relation with a schema R is decomposed into two relations R1 and R2 such that (R1 ∪ R2) = R1, then which one of the following must be satisfied for a lossless join decomposition? (→ indicates functional dependency)

1. (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2
2. R1 ∩ R2 → R1
3. R1 ∩ R2 → R2
4. (R1 ∩ R2) → R1 and (R1 ∩ R2) → R2

Answer

Correct Option: A. (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2

Explanation:

To achieve a lossless join decomposition, the intersection of the two decomposed relations (R1 ∩ R2) must be sufficient to act as a superkey for at least one of the relations, R1 or R2. This ensures no spurious tuples are introduced when the relations are joined back together.

Consider the following:

• If R1 ∩ R2 → R1, it means R1 ∩ R2 contains enough information to reconstruct R1.
• If R1 ∩ R2 → R2, it means R1 ∩ R2 contains enough information to reconstruct R2.

Hence, satisfying either (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 is sufficient for a lossless decomposition.

Example:

Let R(A, B, C) and assume B is a key:

• Decompose R into R1(A, B) and R2(B).
• R1 ∩ R2 = {B}, and B is a key in both R1 and R2.

This satisfies the condition for a lossless decomposition as (R1 ∩ R2) → R1 and (R1 ∩ R2) → R2 hold true.

 

 

Question

The relation schemas R1 and R2 form a lossless join decomposition of R if and only if:

1. R1 ∩ R2 → (R1 - R2)
2. R1 → R2
3. R1 ∩ R2 → (R2 - R1)
4. R2 → R1 ∩ R2

Which of the following is true?

1. i and ii happen
2. i and iv happen
3. i and iii happen
4. ii and iii happen

Answer

Correct Option: C. i and iii happen

Explanation:

To ensure a lossless join decomposition of R into R1 and R2, the intersection of R1 and R2 (R1 ∩ R2) must act as a superkey for at least one of the relations. This ensures no spurious tuples are introduced during the join operation.

Given the conditions:

• R1 ∩ R2 → (R1 - R2): This ensures attributes in R1 that are not in R2 can be determined using R1 ∩ R2.
• R1 ∩ R2 → (R2 - R1): This ensures attributes in R2 that are not in R1 can be determined using R1 ∩ R2.

These two conditions (i and iii) together guarantee a lossless join decomposition.

Example:

Let:

• R1 = {A, B, C, D}
• R2 = {C, D, E, F}

Then:

• R1 ∩ R2 = {C, D}

If {C, D} is a superkey in either R1 or R2, the decomposition is lossless.

 

 

Question

The following table has two attributes Employee_id and Manager_id, where Employee_id is the primary key, and Manager_id is a foreign key referencing Employee_id with on-delete cascade:

Employee_id	Manager_id
20	40
25	40
30	35
35	20
40	45
45	25

On deleting the tuple (20, 40), the set of other tuples that must be deleted to maintain the referential integrity of the table is:

1. (30, 35) only
2. (30, 35) and (35, 20) only
3. (35, 20) only
4. (40, 45) and (25, 40) only

Answer

Correct Option: B. (30, 35) and (35, 20) only

Explanation:

When tuple (20, 40) is deleted:

• The value 20 is referenced in the Manager_id column of tuple (35, 20). Therefore, (35, 20) must also be deleted to maintain referential integrity.
• Similarly, the value 35 is referenced in the Manager_id column of tuple (30, 35). Therefore, (30, 35) must also be deleted.

After these deletions, no other tuples violate referential integrity, so no further deletions are needed.

Hence, the tuples (30, 35) and (35, 20) must be deleted, making option B the correct answer.

 

 

Question

The following table has two attributes A and C, where A is the primary key, and C is the foreign key referencing A with on-delete cascade:

A	C
2	4
3	4
4	3
5	2
7	2
9	5
6	4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2, 4) is deleted is:

1. (3, 4) and (6, 4)
2. (5, 2) and (7, 2)
3. (5, 2), (7, 2), and (9, 5)
4. (3, 4), (4, 3), and (6, 4)

Answer

Correct Option: C. (5, 2), (7, 2), and (9, 5)

Explanation:

When the tuple (2, 4) is deleted:

• The value 2 in the primary key is referenced by tuples (5, 2) and (7, 2) in the foreign key column. Hence, these tuples must be deleted.
• Additionally, the value 5 in the primary key is referenced by tuple (9, 5). Hence, (9, 5) must also be deleted.

After these deletions, no further cascading deletions are needed as no other tuples reference the deleted keys.

Thus, the tuples (5, 2), (7, 2), and (9, 5) must be deleted, making option C the correct answer.

 

 

Question

_____ constraints ensure that a value that appears in one relation for a given set of attributes also appears for a certain set of attributes in another relation.

1. Logical Integrity
2. Referential Integrity
3. Domain Integrity
4. Data Integrity

Answer

Correct Option: B. Referential Integrity

Explanation:

Referential integrity is a type of constraint that ensures relationships between two tables remain consistent. It is achieved using a foreign key, which ensures that the value in a foreign key column of one table matches the primary key value of another table.

For example, if Table A has a primary key and Table B has a foreign key referencing Table A, referential integrity ensures that any value in Table B’s foreign key column exists in Table A’s primary key column.

 

 

Question

Consider a database table R with attributes A and B. Which of the following SQL queries is illegal?

1. SELECT A FROM R;
2. SELECT A, COUNT(*) FROM R;
3. SELECT A, COUNT(*) FROM R GROUP BY A;
4. SELECT A, B, COUNT(*) FROM R GROUP BY A, B;

Answer

Correct Option: B. SELECT A, COUNT(*) FROM R;

Explanation:

The query in option B is illegal because it uses an aggregate function (COUNT(*)) alongside a non-aggregated attribute (A) without a GROUP BY clause. In SQL, when using aggregate functions, all non-aggregated attributes in the SELECT statement must be included in the GROUP BY clause to define how the data should be grouped.

Here’s why the other options are valid:

• Option A: Simply selects attribute A from the table, which is valid.
• Option C: Uses GROUP BY A, allowing the use of A alongside COUNT(*).
• Option D: Uses GROUP BY A, B, which is valid as it groups the data by both attributes A and B before applying COUNT(*).

Therefore, option B is the correct answer.

 

 

Question

Consider the following ORACLE relations:

R(A, B, C) = {<1, 2, 3>, <1, 2, 0>, <1, 3, 1>, <6, 2, 3>, <1, 4, 2>, <3, 1, 4>}
S(B, C, D) = {<2, 3, 7>, <1, 2, 3>, <2, 3, 4>, <3, 1, 4>}

Consider the following two SQL queries:

1. SQ₁: SELECT R.B, AVG(S.B) FROM R, S WHERE R.A = S.C AND S.D < 7 GROUP BY R.B
2. SQ₂: SELECT DISTINCT S.B, MIN(S.C) FROM S GROUP BY S.B HAVING COUNT(DISTINCT S.D) > 1

If M is the number of tuples returned by SQ₁ and N is the number of tuples returned by SQ₂, then:

1. M = 4, N = 2
2. M = 5, N = 3
3. M = 2, N = 2
4. M = 3, N = 3

Answer

Correct Option: A. M = 4, N = 2

Explanation:

SQ₁:

• • Perform a Cartesian product between R and S, filtering tuples where R.A = S.C and S.D < 7.
  • Result after applying the conditions:

R.A	R.B	R.C	S.B	S.C	S.D
1	2	3	3	1	4
1	2	0	3	1	4
1	3	1	3	1	4
1	4	2	3	1	4
3	1	4	2	3	7
3	1	4	3	1	4

• • Grouping by R.B and calculating AVG(S.B) gives:

R.B	AVG(S.B)
2	3
3	3
4	3
1	2

• SQ₁ Output: 4 tuples.

SQ₂:

• • Group S by S.B and calculate MIN(S.C).
  • Only groups where COUNT(DISTINCT S.D) > 1 are retained:

S.B	MIN(S.C)
1	2
2	3

• SQ₂ Output: 2 tuples.

Thus, M = 4 and N = 2, making option A correct.

 

 

Question

The STUDENT information in a university is stored in the relation STUDENT(Name, SEX, Marks, DEPT_Name). Consider the following SQL Query:

SELECT DEPT_Name 
FROM STUDENT 
WHERE SEX='M' 
GROUP BY DEPT_Name 
HAVING AVG(Marks) > (SELECT AVG(Marks) FROM STUDENT);

The query returns the name of the department for which:

1. The average marks of male students is more than the average marks of students in the department
2. The average marks of male students is more than the average marks of students in the university
3. The average marks of students is more than the average marks of male students in the university
4. The average marks of male students is more than the average marks of male students in the university

Answer

Correct Option: B. The average marks of male students is more than the average marks of students in the university

Explanation:

The query performs the following steps:

• Step 1: Filters the data to include only male students (SEX='M').
• Step 2: Groups the male students by their department (GROUP BY DEPT_Name).
• Step 3: Calculates the average marks of male students in each department.
• Step 4: Compares the average marks of male students in each department with the overall average marks of all students in the university (HAVING AVG(Marks) > (SELECT AVG(Marks) FROM STUDENT)).

The query returns the names of departments where the average marks of male students in the department are greater than the overall average marks of all students in the university.

 

Question

Given two relations R₁(A, B) and R₂(C, D), the result of the following query:

SELECT DISTINCT A, B
FROM R₁, R₂;

is guaranteed to be the same as R₁ provided one of the following conditions is satisfied:

1. R₁ has no duplicates and R₂ is empty.
2. R₁ has no duplicates and R₂ is non-empty.
3. Both R₁ and R₂ have no duplicates.
4. R₂ has no duplicates and R₁ is non-empty.

Answer

Correct Option: A. R₁ has no duplicates and R₂ is empty.

Explanation:

• Option A: If R₂ is empty, the Cartesian product between R₁ and R₂ will produce zero tuples. The SELECT DISTINCT A, B will only return the rows from R₁, provided R₁ has no duplicates.
• Option B: If R₂ is non-empty, the Cartesian product will include tuples from both R₁ and R₂. The result cannot be guaranteed to match R₁.
• Option C: If both R₁ and R₂ have no duplicates, the Cartesian product will still include attributes from R₂, which means the result may not match R₁.
• Option D: If R₂ has no duplicates and R₁ is non-empty, the Cartesian product will again include tuples from R₂, which means the result may not match R₁.

Hence, the result is guaranteed to be the same as R₁ only if R₁ has no duplicates and R₂ is empty, making option A the correct answer.

 

 

Question

Given the relations:

• employee(name, salary, dept-no)
• department(dept-no, dept-name, address)

Which of the following queries cannot be expressed using the basic relational algebra operations (σ, π, ×, ⋈, ∪, ∩, −)?

1. Department address of every employee
2. Employees whose name is the same as their department name
3. The sum of all employees’ salaries
4. All employees of a given department

Answer

Correct Option: C. The sum of all employees’ salaries

Explanation:

The basic relational algebra operations do not include aggregate functions such as SUM, COUNT, AVG, etc. These operations are part of extended relational algebra.

• Option A: The query can be expressed using a natural join (⋈) between the employee and department relations on dept-no, followed by a projection (π) of the address attribute.
• Option B: The query can be expressed by selecting tuples where the name attribute in the employee relation matches the dept-name attribute in the department relation.
• Option C: This query requires summation, which is an aggregate function and cannot be expressed using basic relational algebra operations.
• Option D: The query can be expressed by selecting tuples from the employee relation where dept-no matches the given department number.

Therefore, the query in option C cannot be expressed using basic relational algebra operations.

 

 

Question

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:

1. m + n and 0
2. mn and 0
3. m + n and |m – n|
4. mn and m + n

Answer

Correct Option: B. mn and 0

Explanation:

• Maximum size: The maximum number of tuples in the join can be mn. This occurs in the following cases:
  • Case 1: If there is a common attribute between R and S, and every tuple in R matches with every tuple in S. This happens when the join attribute has the same value in all rows of both relations.
  • Case 2: If there is no common attribute between R and S, the Cartesian product is performed, resulting in mn tuples.
• Minimum size: The minimum number of tuples in the join is 0. This happens when there is a common attribute between R and S, but there are no matching values for the join condition.

 

 

Question

Consider the set of relations given below and the SQL query that follows:

Relations:

• Students: (Roll_number, Name, Date_of_birth)
• Courses: (Course_number, Course_name, Instructor)
• Grades: (Roll_number, Course_number, Grade)

SELECT DISTINCT Name
FROM Students, Courses, Grades
WHERE Students.Roll_number = Grades.Roll_number
  AND Courses.Instructor = 'Sriram'
  AND Courses.Course_number = Grades.Course_number
  AND Grades.Grade = 'A';

Which of the following sets is computed by the above query?

1. Names of students who have got an A grade in all courses taught by Sriram
2. Names of students who have got an A grade in all courses
3. Names of students who have got an A grade in at least one of the courses taught by Sriram
4. None of the above

Answer

Correct Option: c. Names of students who have got an A grade in at least one of the courses taught by Sriram

Explanation:

• The query involves a join between the three relations: Students, Courses, and Grades.
• The condition Courses.Instructor = 'Sriram' ensures that only courses taught by Sriram are considered.
• The condition Grades.Grade = 'A' filters students who have received an A grade in those courses.
• The use of SELECT DISTINCT ensures that each student’s name appears only once, even if the student has received an A grade in multiple courses taught by Sriram.

Therefore, the query retrieves the names of students who have received an A grade in at least one of the courses taught by Sriram, making option c the correct answer.