Test: Joins in Relational Algebra - Computer Science Engineering (CSE) MCQ

Concept:
If there are two relations A and B with m and n number of tuples respectively. Then maximum number of tuples in their natural join will be m*n. Maximum tuples will be when one attribute will contain all same values as the other relation having same attribute.
Given: two relations R and S having tuples 3 and 2 respectively. 
So, their natural join will contain maximum of 3 * 2= 6 tuples.
Example:
Consider table R (a, b) as ;

Relation S(a, c) as :

Here, the natural join of R and S will be :

So, it contains total of 6 tuples.

A JOIN clause is used to combine rows from two or more tables, based on a related column between them.
Here are the different types of the JOINs in SQL:

• (INNER) JOIN: Returns records that have matching values in both tables
• LEFT (OUTER) JOIN: Returns all records from the left table, and the matched records from the right table
• RIGHT (OUTER) JOIN: Returns all records from the right table, and the matched records from the left table
• FULL (OUTER) JOIN: Returns all records when there is a match in either left or right table

We can see that left join keeps all the elements from the first relation irrespective of their presence in second relation.

Diagram to visualize joins:

For given relation R1(A, B, C) and R2(B, D, E), functional dependencies are given only for relation R1, not for R2 And the candidate key for R1 is B, so all 35 value must be unique in R1. To get the maximum number of tuples in output, there can be two possibilities.
1) All 34 values of B in R2 are the same and there is an entry in R1 that matches with this value. In this case, we get 34 tuples in output.
Example:
Consider an example, suppose there is two tables R1(A, B, C) consists of 5 tuples and R2( B, D, E) consists of 4 tuples only.


Natural join of R1 and R2 (R1 * R2) gives: 4

2) All 34 values of B in R2 are different and these values are present in R1 also. In this case also, we get 34 tuples.
Example:
Consider an example, suppose there is two tables R1(A, B, C) consists of 5 tuples and R2( B, D, E) consists of 4 tuples only.


Natural join of R1 and R2 (R1 * R2) gives: 4

Concept
Natural join is used to join two relations having any number of attributes. It is denoted by a symbol ( ⨝). It is the combination of projection and filtered cartesian product. It optimizes the query as the cartesian product gives unnecessary results and set union and set intersection operations are application only on those relations that have an equal number of attributes with the same data types. 
Example: Given two relation employee and departments. 
Employee:

Department:

Query: Find the name of all employees from Employee with their respective Department names using natural join :
The result will be : 

Concept: 
A natural join (join) is based on common attributes or common columns to join two tables or relations.
Consider an example, suppose there is two tables Employee(Eid, Ename) consists of 5 tuples and department(Eid, Did) consists of 3 tuples only.


Natural join of employee and department(Employee * Department) gives:
m×n = 5 × 3 = 15
Therefore maximum size is m × n
Minimum size: 
When Both the relations have a common attribute but no tuple in both relations match.
∴ minimum size = 0.

Concept:
Nested loop join algorithm:
No of block transfers = n_r x b_s + b_r
Where n_r is number of tuples in relation R and b_s and b_r are the number of blocks in relation R and S respectively.
In question it is given that size(r(R))_s > b_r and n_r < ns_.
Example:
Suppose relation r is in the outer loop:

Suppose relation s is in the outer loop:
Block transfer = 100 x 10 + 20 = 1020
So relation r should be in the outer loop for effective nested loop join algorithm.
Hence option 1 is the correct answer.

Self-Join:
A self-join is a join in which the table is joined with itself to get the appropriate results. In this case, it is necessary to ensure that the join statement defines an ALIAS name for both copies of the tables to avoid column ambiguity.
Example:

Query:
SELECT A. Coursename AS Course, B. Coursename AS Prerequisite_Course
FROM Course A, Course B
WHERE, A.Precourse = B.CourseID;
OUTPUT

For given relation R1(A, B, C) and R2(B, D, E), functional dependencies are given only for relation R1, not for R2 And the candidate key for R1 is B, so all values must be unique in R1. To get the maximum number of tuples in output, there can be two possibilities.
1) All 100 values of B in R2 are the same and there is an entry in R1 that matches with this value. In this case, we get 100 tuples in output.
Example:
Consider an example, suppose there is two tables R1(A, B, C) consisting of 5 tuples and R2( B, D, E) consisting of 4 tuples only.



Natural join of R1 and R2 (R1 * R2) gives: 4
2) All 100 values of B in R2 are different and these values are present in R1 also. In this case, also we get 100 tuples.
Example:
Consider an example, suppose there is two tables R1(A, B, C) consists of 5 tuples and R2( B, D, E) consists of 4 tuples only.


Natural join of R1 and R2 (R1 * R2) gives: 4

Full natural outer join of R₁ and R₂ is :

Hence option 3 is correct:

 will include record with b > = 5 but other three queries will not.