Relational Algebra - Selection, Projection, Joins etc

The relational algebra defines a set of operations on relations, paralleling the usual algebraic operations such as addition, subtraction etc which operate on numbers.The relational algebra operations take one or two relations (tables) as input and return a relation as output. This post we discuss the following relational operations:
  1. Selection (σ)
  2. Projection (π)
  3. Cartesian product
  4. Joins

Selection Operation (σ)

Selection is a relation operation which returns  rows of the input relation that satisfy the specified condition. The condition is specified along with the select (σ) operator. For example, σsalary>5000 (R) returns all tuples that have salary>5000, from the table R. Let us consider an example. Consider the following relation student(reg_no, semester, mark1, mark2, mark3, total) :

reg_no
semester
mark1
mark2
mark3
total
2008501
S3
87
46
78
211
2008502
S3
45
67
25
137
2008503
S5
81
46
83
210
2008504
S5
35
40
35
110


This table will be used to work out examples in this whole post. Suppose we want to get the table of S3 students only from the table. We use the following Select operation:

σ semester="S3" (student)

The output of above operation is:

reg_no
semester
mark1
mark2
mark3
total
2008501
S3
87
46
78
211
2008502
S3
45
67
25
137

Similarly, if we want to select tuples (rows) of S3 students who have scored a total greater than 200, the following select operation can be used:

σ semester="S3"∧ total>200 (student)

Here we use intersection (ANDing) of two conditions. The connective is used to connect the two conditions. This connective is used to AND the two conditions. Similarly (OR) and ¬ (NOT) can also be used to combine several predicates. The output of last selection operation is:

reg_no
total
2008501
211

Projection Operation (π)

Projection is a relational operator which returns only the specified attributes from the input relation. It also removes the duplicate tuples from the output. Consider the table student. Suppose we want to return only the reg_no and total mark  of the students., we can use the projection operation as follows:

π reg_no,total (student)

The above relational operation returns a table as shown below:

reg_no
total
2008501
211
2008502
137
2008503
210
2008504
110

In short, instead of showing all the tuples, the projection operation is used to return only specified attributes. In above example, we specified the attributes reg_no and total.

Combination of Projection and Selection

Projection and Selection can be performed in combination to obtain desired output. For example, we want to get the reg_no, semester and total of the students whose total mark is greater than 150 from the student table. The following relational algebraic operation can be performed to obtain desired output.

π reg_no, semester, total (σ total>150 (student))

The selection σ total>200 (student) returns the tuples(rows) from student for which total is greater than 150. This output relation is fed as input for the projection operation. Only the columns reg_no, semester and total are returned. ie, the rest of the columns are removed in final output. The output relation (table) is as follows:



reg_no
semester
total
2008501
S3
211
2008503
S5
210

Cartesian Product Operation

The Cartesian product operation, denoted by a cross (x), allows us to combine information from any two relations. Cartesian product of relations R1 and R2 are denoted as R1 x R2. The Cartesian product of relations is similar to Cartesian product of sets. It is a relation which consists of all possible tuples of the form < risj > where rR1  and sR2We will see an example.

Consider two relations:

student_academic(slno, class, total)
slno
class
total
208501
S5R
211
208502
S5R
137
208503
S5R
210

and
student_personal(sno, sname, city)
sno
sname
city
208501
ANIL
EKM
208502
BABU
TVM

Now, we are finding the Cartesian product of these two relations:

student_academic X student_personal
slno
class
total
sno
sname
city
208501
S5R
211
208501
ANIL
EKM
208502
S5R
137
208502
BABU
TVM
208503
S5R
210
208501
ANIL
EKM
208501
S5R
211
208502
BABU
TVM
208502
S5R
137
208501
ANIL
EKM
208503
S5R
210
008502
BABU
TVM
The number of rows (tuples) in Cartesian product is equal to m*n, if the number of tuples in the two tables are m and n. In this example student_academic has 3 tuples and student_personal has 2 tuples. Therefore, the cross product has 6 tuples in it.

Join Operation (⋈)

Join Operation is used to combine related tuples from two relations. Join operation specifies a condition and the only tuples satisfying the condition will be selected for Join. The join condition is specified on the attributes from the two relations R and S and is evaluated for each combination of tuples. In another words, Join operation is filtering out some of the tuples from the Cartesian product of the two relations by specifying some conditions. If any of the tuples don't find a matching tuple (based on the specified join condition), that tuple is avoided from the output.

The Join operation on student_academic and student_personal tables on the condition slno=sno, will produce a table as follows:

student_academic slno=sno student_personal
slno
class
total
sno
sname
city
208501
S5R
211
208501
ANIL
EKM
208502
S5R
137
208502
BABU
TVM
It is just like filtering out the tuples satisfying the condition specified, from the Cartesian product of the two tables. Join operation can be classified into two.
Join operation Relational Algebra selection projection equijoin equi join theta table set theory theoretic operation

Equijoin: if the join condition includes only = operator, it is called equijoin.
If the join condition includes any other operator other than =, then it is called theta join.

Natural Join (*):

if the = condition is specified on identical attributes of the relations, equijoin will result in many superfluous attributes. Natural join is a join operation which helps to avoid superfluous attributes. Natural join is an equijoin for which the condition is not explicitly specified. To apply Natural Join, the join attributes should have the same name in both relations. In natural join operation, the equality condition is applied on the attribute common to both the relations. Natural join of A and B is denoted by A*B. For example, consider following two tables:

student_academic(sno, class, total)
sno
class
total
208501
S5R
211
208502
S5R
137
208503
S5R
210

and
student_personal(sno, sname, city)
sno
sname
city
208501
ANIL
EKM
208502
BABU
TVM


In both these tables, sno is a common attribute. The equijoin student_academic sno=sno student_personal will give a table having two attributes with same name. This superfluous and redundant attribute is removed in natural join. In natural join, we cannot specify the condition. The condition is presumed as equating the values of common attribute. The natural join of student_academic and student_personal is:

student_academic * student_personal
sno
class
total
sname
city
208501
S5R
211
ANIL
EKM
208502
S5R
137
BABU
TVM

Outer Join

In natural join, tuples without matching (related) tuples and null tuples are eliminated from Join result. They are considered in outer join. There are three types of outer join.


  • Left outer join
  • Right outer join
  • Full outer join

Left outer join: All tuples in the left relation will be retained in the join result, even if it is null or does not have a matching tuple. If  it does not have a matching tuple, the corresponding attributes from the right relation in the resultant is kept null.

Symbol for left outer join:
Left Outer Join symbol Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection
Example:

Example for left outer join - Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection
Example for left outer join
Right Outer Join: All tuples in the right relation will be retained in the join result, even if it is null or does not have a matching tuple.

Symbol for right outer join:
Left Outer Join symbol Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection
Example:
Example for left outer join - Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection
Example for right outer join
Full Outer Join: All tuples in both left and right relations will be retained in the join result, even if it is null or does not have a matching tuple. Symbol of Full outer join:

Left Outer Join symbol Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection

Example:
Example for left outer join - Relational Algebra - Selection, Projection, Joins etc natural join left outer join right outer join full outer join selection projection examples workout problem tutorial DBMS database management system software
Example for Full outer Join


No comments :

Post a Comment