Relational Algebra

KALINGA INSTITUTE OF INDUSTRIAL

TECHNOLOGY

School Of Computer
Engineering

Dr. Pradeep Kumar Mallick

Associate Professor [II]
School of Computer Engineering,
Kalinga Institute of Industrial Technology (KIIT),
Deemed to be University,Odisha

4 Credit Lecture Note 11

Chapter Contents
2

 Query Language
 Relational Algebra
 SELECT Operator (σ)
 PROJECT Operator (π)

 Composition of Relational Operators

 RENAME Operator (ρ)
 Union Compatibility
 UNION Operator (∪)
 DIFFERENCE Operator (-)
 Cartesian Product Operator (×)
 Intersection Operator (∩)
 JOIN Operator (⋉⋊)
 Division Operator (÷)
 Assignment Operator (←)
Query Language
3
 Language in which user requests information from the database are:
 Procedural language
 Nonprocedural language
 The categories of different languages are:
SQL
Relational Algebra
Relational Calculus
Tuple Relational Calculus
Domain Relational Calculus
Relational Algebra
4
 Relational Algebra is a set of basic operations used to manipulate the data in
relational model. These operations enable the user to specify basic retrieval
request. The result of retrieval is a new relation, formed from one or more
relations. These operations can be classified in two categories:
A. Basic Set Operations
1. UNION
2. INTERSECTION
3. SET DIFFERENCE
4. CARTESIAN PRODUCT
B. Relational Operations
1. SELECT (Unary Operation)
2. PROJECT (Unary Operation)
3. Rename (Umnary Operation)
4. JOIN
5. DIVISION
6. Asignment
Relational Algebra…
5
 The relational schemas used for different operations are:

 Customer(cust_name, cust_street, cust_city)

used to store customer details
 Branch(branch_name, branch_city, assets)
used to store branch details
Account(acc_no, branch_name, balance)
stores the account details
 Loan(loan_no, branch_name, amount)
stores the loan details
 Depositor(cust_name, acc_no)
stores the details about the customers’ account
 Borrower(cust_name, loan_no)
used to store the details about the customers’ loan
SELECT Operator (σ)
6
 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 operator is:

σ <selection−condition> (<relation name>)

 Query: Find the details of the loans taken from ’Bhubaneswar Main’ branch.

σ branch_name=′ BhubaneswarMain′ (Loan)

 The operators used in selection predicate may be: =, 6=, <, ≤, >, ≥.
 Different predicates can be combined into a larger predicate by using the
connectors like: AND(V), OR(W), NOT(¬)
SELECT Operator (σ)
7
PROJECT Operator(π)
8
 PROJECT operation can be thought of as eliminating unwanted columns. It is
denoted by pie (π) symbol. The attributes needed to be appeared in the resultant
relation appear as subscript to π.
 The argument relation follows in parenthesis. The general syntax of project
operator is:

π <attribute−list > (<relation name>)

 Query: Find the loan numbers and respective loan amounts.

π loan_no,amount (Loan)
Loan π loan_no, amount (Loan)
loan_no branch_name amount loan_no amount
L201 Bhubaneswar Main 50,000,000.00 L201 50,000,000.00
L202 Bhubaneswar Main 5,000,000.00 L202 5,000,000.00
L203 Mumbai Main 100,000,000.00 L203 100,000,000.00
L204 Juhu 60,000,000.00 L204 60,000,000.00
PROJECT Operator(π)
9
Composition of Relational Operators
10
 Relational algebra operators can be composed together into a relational algebra
expression to answer the complex queries.
 Q: Find the name of the customers who live in Bhubaneswar.

Customer
cust_name cust_street cust_city
Rishi India Gate New Delhi
Sarthak M. G. Road Bangalore
Manas Shastri Nagar Bhubaneswar
Ramesh M. G. Road Bhubaneswar
Mahesh Juhu Mumbai

π cust _name (σ cust _city =′ Bhubaneswar ′ (Customer))

cust_name
Manas
Ramesh
RENAME Operator(ρ)
11
 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 operator is:
ρ X (E)
 Assume E is a relational-algebra expression with arity n. The second form of
rename operation is:
ρ X (b1 ,b2 ,...bn ) (E)
 π cust _name (σ cust _city =′ Bhubaneswar ′ (Customer)) can be written as:

1. ρ Customer _Bhubaneswar (σ cust _city =′ Bhubaneswar ′ (Customer))

2. π cust _name (Customer_Bhubaneswar)
RENAME Operator(ρ)…
12
 The different forms of the rename operation for renaming the relation are:
a. ρ S (R)
b. ρ S(b1 ,b2 ,...bn ) (R)
c. ρ (b ,b ,...b ) (R)

 For example, the attributes of Customer (cust_name, cust_street, cust_city) can

be renamed as:

ρ (name,street ,city )
(Customer)
Basic Set Operation
13

 These are the binary operations; i.e., each is applied to two sets or relations.
These two relations should be union compatible except in case of Cartesian
Product.
 Two relations R (A1, A2,….., An) and S (B1, B2,……,Bn) are said to be union
compatible if they have the same degree n and domains of the
corresponding attributes are also the same i.e.Domain (Ai) = Domain (Bi)
for 1<=i<=n.
Union Compatibility
14

 To perform the set operations such as UNION, DIFFERENCE and

INTERSECTION, 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 arity(degee)

 dom(ai ) = dom(bi ) for 1 ≤ i ≤ n

UNION Operator (∪)
15
 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 ,c2 ,... 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.
 In other words, R3 will have tuples such that R3 = {t | R1 t v R2 t}

Q.Find the name of the customer who have loan or an account or both

 π cust _name (Depositor) ∪ π cust _name (Borrower)

UNION Operator (∪): Rules
16

Conditions;
 Duplicate tuples are eliminated automatically.
 R and S must have the attribute of the same number.

 Note: 1) Union is a commutative operation, i.e, R U S = S U R.

 2) Union is an associative operation, i.e. R U (S U T) = (R U S) U T.

DIFFERENCE Operator(-)
17
 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.

 π cust _name (Depositor) - π cust _name (Borrower)

Cartesian Product Operator(×)
18
 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 conjuction with other
operations.
Cartesian Product Operator(×)…
19
Cartesian Product Operator(×)…
20
 Query: Find out the customer and their loan details taken from Bhubaneswar
Main branch.
Ans: σ branch_name = ′BhubaneswarMain′ AND
Borrower.loan_no=Loan.loan_no (Borrower ×Loan)
Intersection Operator(∩)
21
 The intersection operation is used to identify the rows that are common to two
relations. It is denoted by (∩) 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.
 The intersection operation can be rewritten by a pair of set difference operations
as R ∩ S = R - (R - S).

π cust _name (Depositor) ∩ π cust _name (Borrower)

Division Operator (÷)
22
 The division operation creates a new relation by selecting the rows in one
relation that match every row in another relation. The division operation
requires that we look at an entire relation at once. It is denoted by division (÷)
symbol.
 Let A, B, C are three relations and we desire B ÷ C to give A as the result. This
operation is possible iff:
 The columns of C must be a subset of the columns of B. The columns of A
are all and only those columns of B that are not columns of C
 A row is placed in A if and only if it is associated with B and with every
row of C
 The division operation is the reverse of the Cartesian product operation as: B
= (B × C) ÷ C.
 Division operator is suited to queries that include the phrase every or all as
part of the condition.
Division Operator (÷)…
23
Assignment Operator(←)
24
 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.
 Assignment must always be made to a temporary relation variable. The result of
the right of the ← symbol is assigned to the relation variable on the left of the
← symbol.
 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

π cust _name,branch_name (Depositor ⋊⋉ Account) ÷ π branch_name (σ

branch_city =′ Mumbai ′ (Branch)) can be simplified as:

Temp1 ← π cust _name,branch_name (Depositor ⋊⋉ Account)
Temp2 ← π branch_name (σ branch_city = Mumbai (Branch))
′ ′

Result = Temp1 ÷ Temp2

JOIN (⋈)
25

 A Join operation combines related tuples from different relations, if and only if a

given join condition is satisfied. It is denoted by ⋈.

 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.

Operation: (EMPLOYEE ⋈ SALARY)

EMP_CODE EMP_NAME EMP_CODE SALARY

101 Stephan
 EXAMPLE:Employee 101
Salary 50000
102 Jack 102 30000
103 Harry 103 25000
JOIN Operator(⋈)
26

Result Table:

EMP_CODE EMP_NAME SALARY

101 Stephan 50000

102 Jack 30000

103 Harry 25000

JOIN Operator(⋈)…
27
Types of Join operations:
28
1. Natural Join:
29
 A natural join is the set of tuples of all combinations in R and S that are equal
on their common attribute names.
 It is denoted by ⋈.
 Example: Let's use the above EMPLOYEE table and SALARY table:
 Example:
∏EMP_NAME, SALARY (EMPLOYEE ⋈ SALARY)
EMP_CODE EMP_NAME EMP_CODE SALARY
101 Stephan 101 50000
102 Jack
102 30000
103 Harry
103 25000

EMP_NAME SALARY
Stephan 50000
Jack 30000
Harry 25000
2. Outer Join:
30
 The outer join operation is an extension of the join operation. It is used to deal
with missing information.
EMPLOYEE ⋈ FACT_WORKERS
 Example: EMPLOYEE FACT_WORKERS

EMP_NAME STREET CITY EMP_NAME BRANCH SALARY

Ram Civil line Mumbai Ram Infosys 10000

Shyam Park street Kolkata Shyam Wipro 20000
Ravi M.G. Street Delhi Kuber HCL 30000
Hari Nehru nagar Hyderabad Hari TCS 50000

EMP_NAME STREET CITY BRANCH SALARY

Ram Civil line Mumbai Infosys 10000

Shyam Park street Kolkata Wipro 20000
Hari Nehru nagar Hyderabad TCS 50000
Left Outer Join(⟕)
31
 An outer join is basically of three types:
a. Left outer join
b. Right outer join
c. Full outer join

A. Left outer join

 Left outer join contains the set of tuples of all combinations in R and S that are
equal on their common attribute names.
 In the left outer join, tuples in R have no matching tuples in S.
 It is denoted by ⟕.
 Example: Using the above EMPLOYEE table and FACT_WORKERS table
Left Outer Join(⟕)
32

EMP_NAME STREET CITY BRANCH SALARY

Ram Civil line Mumbai Infosys 10000

Shyam Park street Kolkata Wipro 20000

Hari Nehru street Hyderabad TCS 50000

Ravi M.G. Street Delhi NULL NULL

Right outer join:( ⟖)
33
 Right outer join contains the set of tuples of all combinations in R and S that are
equal on their common attribute names
 In right outer join, tuples in S have no matching tuples in R.
 It is denoted by ⟖.
Example: Using the above EMPLOYEE table and FACT_WORKERS Relation
EMPLOYEE ⟖ FACT_WORKERS

EMP_NAME BRANCH SALARY STREET CITY

Ram Infosys 10000 Civil line Mumbai

Shyam Wipro 20000 Park street Kolkata

Hari TCS 50000 Nehru street Hyderabad

Kuber HCL 30000 NULL NULL

Full outer join:(⟗)
34
 Full outer join is like a left or right join except that it contains all rows from
both tables.
 In full outer join, tuples in R that have no matching tuples in S and tuples in S
that have no matching tuples in R in their common attribute name.
 It is denoted by ⟗.
 Example: Using the above EMPLOYEE table and FACT_WORKERS table

 Input:
EMPLOYEE ⟗ FACT_WORKERS

EMP_NAME STREET CITY BRANCH SALARY

Ram Civil line Mumbai Infosys 10000
Shyam Park street Kolkata Wipro 20000
Hari Nehru street Hyderabad TCS 50000
Ravi M.G. Street Delhi NULL NULL
Kuber NULL NULL HCL 30000
3. Equi join:
35
 It is also known as an inner join. It is the most common join. It is based on
matched data as per the equality condition. The equi join uses the comparison
operator(=).
CUSTOMER RELATION PRODUCT

CLASS_ID NAME PRODUCT_ID CITY

1 John 1 Delhi
2 Harry 2 Mumbai
3 Jackson 3 Noida
CUSTOMER ⋈ PRODUCT

CLASS_ID NAME PRODUCT_ID CITY

1 John 1 Delhi
2 Harry 2 Mumbai
3 Harry 3 Noida
Theta join
36
 Theta join combines tuples from different relations provided they satisfy the
theta condition. The join condition is denoted by the symbol θ.

 When each condition is of the form A θB, A is an attribute of R1 and B is an

attribute of R2 and have the same domain, and  is one of the comparison
operators { ==, =, <=, <,=>,>}.
Self Join
37
 The self join is similar to the theta join. It joins a relation to itself by a
condition. The self join can be viewed as a join of two copies of the same
relation.
 The general form of self join is:

 Thus, the self join creates two alias or copies of the same relation; then
performs the theta join by a condition based on the attributes of these two
copies.
Self Join
38
39