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 R₁ and R₂ are denoted as R₁ x R₂. 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 < r_is_j > where r_i R₁  and s_j R₂We 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.

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:

Example:

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:

Example:

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:

Example:

Example for Full outer Join