Learning Resource

On
Database Management Systems

Chapter-6
Relational Algebra

Prepared By:
Kunal Anand, Asst. Professor
SCE, KIIT, DU, Bhubaneswar-24
 Chapter Outcomes

• After the completion of this chapter, the students

will be able to:
– Define Relational Algebra
– Identify different types of relational algebra operations
– Explain different types of JOIN operations
– Write queries using relational algebra

20 February 2023 2
 Organization of the Chapter

• Introduction
• Unary Relational Algebra Operations
• Relational Algebra Operations from Set Theory
• Binary Relational Algebra Operations
• Generalized Projection
• Aggregate Functions
• JOIN Operations

20 February 2023 3
 Introduction
• Query Language: The language in which a user requests
information from the database.

• Generally, a query language is of following types:

•Procedural language
•Nonprocedural language

•The categories of different languages are:

•SQL
•Relational Algebra
•Relational Calculus
•Tuple Relational Calculus
•Domain Relational Calculus
20 February 2023 4
 Relational Algebra
• Relational Algebra is a procedural language used to
manipulate relations i.e. these operations use one or two
existing relations to create a new relation.

• These operations enable a user to specify basic retrieval

requests as relational algebra expressions.

• The result of the retrieval query is a new relation. The algebra

operations thus produce new relations, that can be further
manipulated using operations of the same algebra.

• A sequence of relational algebra operations forms a relational

algebra expression.
20 February 2023 5
 contd..

• The relational algebra is very important because of mainly two

reasons as listed below:
– It provides the formal foundation for relational model
operations.
– It provides basis for implementing and optimizing queries
in the query processing and optimizing modules that are the
integral part of RDBMS.

• Although, most commercial RDBMSs in use today do not

provide user interfaces for relational algebra queries, the core
operations and functions in the internal modules of most
relational systems are based on relational algebra operations.

20 February 2023 6
 Relational Algebra Operations
• The operations in relational algebra can be divided into
following three groups:
– Unary RA Operations
• SELECT (symbol: σ)
• PROJECT (symbol: π)
• RENAME (symbol: )
– RA Operations From Set Theory
• UNION (∪)
• INTERSECTION (∩),
• DIFFERENCE (-)
• CARTESIAN PRODUCT ( x )
– Binary RA Operations
• JOIN
• DIVISION
• ASSIGNMENT
20 February 2023 7
 Unary RA Operations
• SELECT Operation (σ)
– SELECT operation is used to create a relation from another
relation by selecting only those tuples or rows from the
original relation that satisfy a specified condition.
– It is denoted by sigma (σ) symbol. The predicate appears
as a subscript to σ .
– The argument relation is in parenthesis after the σ. The
result is a relation that has the same attributes as the
relation specified in <relation-name>.
– The general syntax of select operation is:
σ (<relation name>)
<selection−condition>

20 February 2023 8
 contd..
•The operators used in selection predicate are =, !=, <, ≤, >, ≥ .
•Different predicates can be combined into a larger predicate by
using the connectors like: AND, OR, NOT.
•Examples:
(LOAN)
– Query 1: σ
(Branch_name='BhubaneswarMain')
» SQL: select *
from LOAN
where (Branch_name='BhubaneswarMain')
» Output: Tuples where branch_name is BhubaneswarMain
(BOOK)
– Query 2: σ
Subject = 'database' AND Price = 450
» SQL: select *
fromBooks
where Subject = 'database' AND Price = 450;
» 2023
20 February Output: Tuples where the subject is database and price is 450. 9
 contd..
(EMPLOYEE)
– Query 3: σ
Dno=4 OR Salary>25000
» SQL: select *
from EMPLOYEE
where Dno = 4 OR Salary>25000;
» Output: Selects tuples from employee table where either
Dno is 4 or salary > 25000
– Query 4: σSubject = "database" AND Price = 450 or
Year
(BOOK)
> 2010
» SQL: select *
from Books
where((Subject = 'database' AND Price =
450)
20 February 2023OR Year>2010) ; 10
» Output: Selects tuples from books where subject is 'database'
 Unary RA Operations
• PROJECT Operation (π):
– The PROJECT operation selects certain columns from the
table and discards the other columns.
– The projection method defines a relation that contains a
vertical subset of Relation.
– If the attribute list include only non-key attributes,
duplicate tuples are likely to occur. The PROJECT
operation removes any duplicate tuples and, hence produce
a valid relation which is a set of distinct tuples. This is
known as duplicate elimination.
– The general syntax of project operator is:
(<relation name>)
•π <attribute−list >
20 February 2023 11
 contd..
• Examples
π (LOAN)
– Query 1:
Loan_no,Amount
• SQL: select Loan_no, Amount from LOAN;
• Output: Displays the columns Loan_no and Amount
from the table LOAN.

π (STUDENT)
– Query 2:
Name, Age
• SQL: select Name, Age from STUDENT;
• Output: Displays name and age columns from the table
student.

20 February 2023 12
 contd..
π (BOOK)
– Query 3:
Subject, Author
• SQL: select Subject, Author from BOOK;
• Output: Displays the columns subject and author from
the table Books.

π (EMPLOYEE)
– Query 4:
Gender, Salary
• SQL: select Gender, Salary from EMPLOYEE;
• Output: Displays the columns Gender and Salary from
the table EMPLOYEE.

20 February 2023 13
 Unary RA Operations
Composition of Relational Operators
– Relational algebra operators can be composed together into
a relational algebra expression to answer the complex
queries.
– Relational algebra expression is actually a nesting of
relational operations.

• Query 5:
– π Cust _name (σ Cust _city ='Bhubaneswar '(CUSTOMER))
– Output: Displays the column cust_name for all those
customers who are from the cust_city Bhubaneswar.

20 February 2023 14
 Unary RA Operations
• RENAME Operation (ρ)
– The results of relational algebra expressions do not have a name
that can be used to refer them.
– It is useful to be able to give them names; the rename operator is
used for this purpose.
– It is denoted by rho(ρ) symbol. The general syntax of rename
(E)
operator is: ρ
X
• Example:
π cust _name (σ cust _city ='Bhubaneswar ' (Customer)) can be
written as:
1. ρ (σ (Customer))
Customer _Bhubaneswar cust _city=Bhubaneswar
(Customer_Bhubaneswar)
2. π cust _name
20 February 2023 15
 Union Compatibility

• To perform the set operations such as UNION,

INTERSECTION, and SET DIFFERENCE (also known as
MINUS or EXCEPT) the relations need to be union
compatible for the result to be a valid relation.

• Two relations R1(a1,a2,... an ) and R2(b1,b2,... bm ) are union

compatible iff:
•n = m, i.e., both relations have same degree
•dom(ai ) = dom(bi ) for 1 ≤ i ≤ n
– This mean that the two relations have the same number of
attributes.
– Each corresponding pair of attributes has the same domain.

20 February 2023 16
 RA Operations from Set Theory
• UNION Operation(∪):
– The union operation is used to combine data from two
relations. It is denoted by union(∪) symbol.

– The union of two relations R1(a1,a2,... an ) and R2 (b1,b2,...

bn ) is a relation R3 (c1,c ,... cn ) such that:
• dom(ci ) = dom(ai ) ∪ dom(bi ), 1 ≤ i ≤ n

– R1 ∪ R2 is a relation that includes all tuples that are either

present in R1 or R2 or in both without duplicate tuples.

20 February 2023 17
 Examples
– Query 1: ∏ Cust_name (DEPOSITOR) ∪∏ Cust_name(BORROWER)
• SQL: select Cust_name from DEPOSITOR
union
select Cust_name from BORROWER

20 February 2023 18
 contd..
• Intersection Operation (∩)
– The intersection operation is used to identify the rows that
are common to two relations.

– An intersection is defined by the symbol ∩

– The intersection of two relations R1(a1,a2,... an ) and

R2(b1,b2,... bn ) is a relation R3 (c1,c2,... cn ) such that:
• dom(ci ) = dom(ai ) ∩ dom(bi ), 1 ≤ i ≤ n

– R1 ∩ R2 is a relation that includes all tuples that are present

in both R1 and R2

20 February 2023 19
 contd..
– Query 1: ∏ cust_name (Depositor) ∩ ∏ cust_name (Borrower)
• SQL: select Cust_name from DEPOSITOR
intersect
select Cust_name from BORROWER

Cust_name
Mahesh
Ramesh
20 February 2023 Rishi 20
 contd..
• DIFFERENCE Operation (-)
– The difference operation is used to identify the rows that
are in one relation and not in another. It is denoted as (-)
symbol.
– The difference of two relations R1(a1,a2,... an ) and
R2(b1,b2,... bn ) is a relation R3 (c1,c2,... cn ) such that:
• dom(ci ) = dom(ai ) - dom(bi ), 1 ≤ i ≤ n
– R1 - R2 is a relation that includes all tuples that are in R1, but
not in R2
– Query 1: ∏ author (Books) − ∏ author (Articles)
• Output − Provides the name of authors who have written books but
not articles.
– Query 2: ∏Student(RegularClass) - ∏Student(ExtraClass)
• Output: Provide the name of students who attend the regular
20 February 2023 21
class but not the extra class.
 An Example

20 February 2023 22
 Cartesian Product Operation (×)
• It is also known as Cross Product. Also, a binary operation,
but the relations on which it is applied do not have to be union
compatible.
• The Cartesian product of two relations R1(a1,a2,... an ) with
cardinality i and R2(b1,b2,... bm ) with cardinality j is a relation
R3 with
•degree k = n + m,
•cardinality i*j and
•attributes (a1,a2,... an , b1,b2,... bm )
• R1 × R2 is a relation that includes all the possible combinations
of tuples from R1 and R2 .
• The Cartesian product is used to combine information from
any two relations. It is not a useful operation by itself; but is
used in conjunction with other operations.
20 February 2023 23
 contd..

20 February 2023 24
 contd..

20 February 2023 25
 Binary RA Operation
Division Operation (/)
• Produces the tuples in one relation, R, that match all tuples in
another relation, S
– R (A1, …An, B1, …Bm)
– S (B1 …Bm)
– R/S, with attributes A1, …An, is the set of all tuples <a>
such that for every tuple <b> in S, <a,b> is in R

• Can be expressed in terms of projection, set difference, and

cross-product.

• The division operator is used when we have to evaluate

queries which contain the keyword ALL.
20 February 2023 26
 contd..

20 February 2023 27
 Assignment Operator(←)
• It works like assignment in a programming language.
• In relational algebra, the assignment operator gives a name to a
relation. It is denoted by (←) symbol.
• The result of the right of the ← symbol is assigned to the
relation variable on the left of the ← symbol.
• Assignment must always be made to a temporary relation
variable.
• With the assignment operator, a query can be written as a
sequential program consisting of:
•a series of assignment,
•followed by an expression whose value is displayed as a
result of the query.

20 February 2023 28
 contd..
•Example:

Temp1 ← π cust _name,branch_name (Depositor_Account)

Temp2← π branch_name (σ branch_city =”Mumbai”(Branch))

Result = Temp1 ÷ Temp2

Output:
customers The result table will have the

Who have deposits in all branches in Mumbai

city.
20 February 2023 29
 Generalized Projection
• The generalized-projection operation extends the projection
operation by allowing arithmetic functions to be used in the
projection list. The general form of generalized-projection is:
π (E)
F1 ,F2 ...Fn
• Ex:
– Emp(ssn, salary, deduction, years_service)
– A report may be required to show
• net_salary=salary-deduction,
• bonus=2000*years_service and
• tax=0.25*salary
•REPORT ← ρ (ssn,net _salary,bonus,tax ) (π ssn,salary
20 February 2023 30
(EMPLOYEE)
)
 Aggregate Functions(g)
• Aggregate functions take a collection of values and return a
single value as a result.

• NULL value will not participate in the aggregate functions.

• The general form of aggregate function is: grouping_attribute

g (R)
aggregate_functions

• Ex: Works(emp_id, ename, salary, branch_name)

• Query: Find the total sum of salaries of all the employees
• Ans: g SUM(salary )(Works)
20 February 2023 31
 contd..
• Query: Find the total sum of salaries of all the employees in
each branch
Ans: branch_name g
SUM(salary )(Works)

•Query: Find the maximum salary for the employees at each

branch, in addition to the sum of the salaries
Ans: branch_name g
SUM(salary ),MAX (salary )(Works)

•Query: Find the number of employees working

Ans: g
COUNT (emp_id )(Works)

20 February 2023 32
 Join Operation
• Join is a combination of a Cartesian product followed by a
selection process.

• A Join operation pairs two tuples from different relations, if

and only if a given join condition is satisfied.

• It is denoted by ⋈.
•Different categories of join are:
•Cross Join (Cartesian Product)
•Inner Join
•Outer Join
•Self Join
20 February 2023 33
 Inner Join
• These joins are the one that has the tuples that satisfy some
conditions and rest are discarded. Further they are classified as
– Theta join:
• They have tuples from different relations if and only if
they satisfy the theta condition.
• R1 and R2 are relations having attributes (A1, A2, ..,
An) and (B1, B2,.. ,Bn) such that the attributes don’t
have anything in common, that is R1 ∩ R2 = Φ.
• It is denoted by R1 ⋈θ R2;
• Here the comparison operators (≤, ≥, ˂, ˃, =, ̚ )come
into picture.
• Degree (Result) = Degree (R) + Degree (S)
• Cardinality (Result) ≤ Cardinality(R) × Cardinality(S)
20 February 2023 34
 An Example
• Suppose a customer wants to buy a car and a boat. But, they
don’t want to spend more money on a boat than a car i.e. car
price >= boat price. Display the car model, car price, boat
model, boat price for the customer.

• SQL: select *
from car JOIN boat
on car.car_price>=boat.boat_price;

π
• Query:
car_model, car_price, boat_model,
boat_price
(car X boat)
( σ car.car_price>=boat.boat_price
20 February 2023
) 35
 contd..

20 February 2023 36
 Inner Join (contd..)
• Equi Join
– A special theta join based on equality of specified columns.
– The equi join is the special type of theta join where the
comparison operator is =
– It is denoted by R1 ⋈= R2
– Example: Display the student id, student name, and course
name for the students from the same courses.
– SQL: select Student.sid, Student.name, Courses.name
from Student JOIN Courses
on Student.course=Courses.course;
π
– Query: sid, student.name , Courses.name
( σ Student.course=Courses.course (student X courses))
20 February 2023 37
 contd..

20 February 2023 38
 Inner Join (contd..)
• Natural Join
– Natural Join is a type of Inner join which is based on
column having same name and same datatype present in
both the tables to be joined. Natural join does not use any
comparison operator.
– Natural Join is by default inner join because the tuples
which does not satisfy the conditions of join does not
appear in result set.
– Example: Display the details of the students along with
their address.
• SQL:
– select * from class NATURAL JOIN classinfo;
• Query: class ⋈classinfo
20 February 2023 39
 An Example

20 February 2023 40
 Outer Join Operations
• An inner join includes only those tuples with matching
attributes and the rest are discarded in the resulting relation.
Therefore, we need to use outer joins to include all the tuples
from the participating relations in the resulting relation.

• It is an extension of the natural join operation to deal with the

missing information.

• The different types of outer join are:

•Left Outer Join
•Right Outer Join
•Full Outer Join

20 February 2023 41
 Left Outer Join(R⟕S)
• The left outer join preserves all tuples in left relation. All
information from the left relation is present in the result of the
left outer join.

• The tuples of R which do not satisfy join condition will have

values as NULL for attributes of S.

• Example: Consider the relations Instructor and Teaches. Find

the left outer join of them.
• SQL: select *
from instructor LEFT OUTER JOIN teaches
on instructor.ID=teaches.ID;
• Query: instructor ⟕ teaches
20 February 2023 42
 contd..

20 February 2023 43
 Left Outer Join (instructor ⟕ teaches)

20 February 2023 44
 Right Outer Join(R ⟖ S)
• The right outer join preserves all tuples in right relation. All
information from the right relation is present in the result of
the right outer join.

• The tuples of S which do not satisfy join condition will have

values as NULL for attributes of R.

• Example: Consider the relations Instructor and Teaches. Find

the right outer join of them.
• SQL: select *
from teaches RIGHT OUTER JOIN instructor
on teaches.ID = instructor.ID;
• Query: teaches ⟖ instructor
20 February 2023 45
 contd..

20 February 2023 46
 Full Outer Join (R ⟗ S)
• All the tuples from both participating relations are included in
the resulting relation. If there are no matching tuples for both
relations, their respective unmatched attributes are made
NULL.

• Example: Select students whose ROLL_NO is greater than

EMP_NO of employees and details of other Employees as well
and other Students as well.
• SQL: select*
from student FULL OUTER JOIN employee
on student.roll_no>employee.emp_no;
• QUERY:
– STUDENT⟗STUDENT.ROLL_NO>EMPLOYEE.EMP_NOEMPLOYEE

20 February 2023 47
 contd..

20 February 2023 48
 contd..

20 February 2023 49
 Left Outer / Right Outer Join

20 February 2023 50
Full Outer Join

20 February 2023 51
 Self Join
• A self join is a join in which a table is joined with itself (which
is also called Unary relationships), especially when the table
has a FOREIGN KEY which references its own PRIMARY
KEY.
• To join a table itself means that each row of the table is
combined with itself and with every other row of the table.
• The self join can be viewed as a join of two copies of the same
table. The table is not actually copied, but SQL performs the
command as though it were.
• The syntax of the command for joining a table to itself is
almost same as that for joining two different tables.
– SELECT a.column_name, b.column_name...
FROM table1 a, table1 b
WHERE a.common_filed = b.common_field;
20 February 2023 52
 An Example
• Suppose a table EMPLOYEE has been created with the
attributes Emp_ID, Emp_name, dt_of_join, Emp_supv.

• Here, Emp_ID is the PK as well as the FK as the Emp_supv is

also an employee. The FK is used to the refer the PK of the
same table in self join operation.

• Now, If we want a list of employees and the names of their

supervisors, we’ll have to JOIN the EMPLOYEE table to itself
to get this list.

20 February 2023 53
 contd..

20 February 2023 54
 contd..
• SQL:
– SELECT a.emp_id AS "Emp_ID",
a.emp_name AS "Employee Name",
b.emp_id AS "Supervisor ID",
b.emp_name AS "Supervisor Name"
FROM employee a, employee b
WHERE a.emp_supv = b.emp_id;

20 February 2023 55