Relational Algebra

DBMS
CS-116

Ms. Jyoti Snehi

Department of Computer Science and Engineering
Chitkara University, Punjab
8/10/2021 Faculty Name - Jyoti Snehi 1
 Query Languages

• Language in which user requests information from the database.

• Categories of languages
– procedural
– non-procedural
• “Pure” languages:
– Relational Algebra
– Tuple Relational Calculus
– Domain Relational Calculus
• Pure languages form underlying basis of query languages that
people use.

8/10/2021 Faculty Name - Jyoti Snehi 2

 Relational Query Languages

• Query languages: Allow manipulation and retrieval of data from a

database.
• Relational model supports simple, powerful QLs:
– Strong formal foundation based on logic.
– Allows for much optimization.
• Query Languages != programming languages!
– QLs not expected to be “Turing complete”.
– QLs not intended to be used for complex calculations.
– QLs support easy, efficient access to large data sets.

8/10/2021 Faculty Name - Jyoti Snehi 3

 Preliminaries

• A query is applied to relation instances, and the result of a query is

also a relation instance.
– Schemas of input relations for a query are fixed (but query will
run regardless of instance!)
– The schema for the result of a given query is also fixed!
Determined by definition of query language constructs.
• Positional vs. named-field notation:
– Positional notation easier for formal definitions, named-field
notation more readable.
– Both used in SQL

8/10/2021 Faculty Name - Jyoti Snehi 4

 Relational database

8/10/2021 Faculty Name - Jyoti Snehi 5

 Relational Algebra Overview

• Relational algebra is the basic set of operations for the relational model
• Relational algebra is a procedural query language that works on relational
model. The purpose of a query language is to retrieve data from database
or perform various operations such as insert, update, delete on the data.
When I say that relational algebra is a procedural query language, it means
that it tells what data to be retrieved and how to be retrieved.
• These operations enable a user to specify basic retrieval requests (or
queries)
• The result of an operation is a new relation, which may have been formed
from one or more input relations
– This property makes the algebra “closed” (all objects in relational
algebra are relations)

8/10/2021 Faculty Name - Jyoti Snehi 6

 Relational Algebra Overview

• The algebra operations thus produce new relations

– These can be further manipulated using operations of the same
algebra
• A sequence of relational algebra operations forms a relational
algebra expression
– The result of a relational algebra expression is also a
relation that represents the result of a database query
(or retrieval request)

8/10/2021 Faculty Name - Jyoti Snehi 7

 Relational algebra

8/10/2021 Faculty Name - Jyoti Snehi 8

Relational Algebra:
Types:
• Unary operation
• Binary operation

• Unary operation Relational Algebra Operations from Set Theory.

• Binary operation (Join and Divison)

8/10/2021 Faculty Name - Jyoti Snehi 9

 Relational algebra

8/10/2021 Faculty Name - Jyoti Snehi 10

8/10/2021 Faculty Name - Jyoti Snehi 11
 Relational algebra Operations

8/10/2021 Faculty Name - Jyoti Snehi 12

 Relational Algebra

8/10/2021 Faculty Name - Jyoti Snehi 13

 Example of a Relation

8/10/2021 Faculty Name - Jyoti Snehi 14

 Basic Structure

 Formally, given sets D1, D2, …. Dn a relation r is a subset of

D1 x D2 x … x Dn
Thus, a relation is a set of n-tuples (a1, a2, …, an) where each ai  Di
 Example: If
customer_name = {Jones, Smith, Curry, Lindsay}
customer_street = {Main, North, Park}
customer_city = {Harrison, Rye, Pittsfield}
Then r = { (Jones, Main, Harrison),
(Smith, North, Rye),
(Curry, North, Rye),
(Lindsay, Park, Pittsfield) }
is a relation over
customer_name x customer_street x customer_city
8/10/2021 Faculty Name - Jyoti Snehi 15
 Attribute Types

 Each attribute of a relation has a name

 The set of allowed values for each attribute is called the domain
of the attribute
 Attribute values are (normally) required to be atomic; that is,
indivisible
◦ Note: multi-valued attribute values are not atomic
◦ Note: composite attribute values are not atomic
 The special value null is a member of every domain
 The null value causes complications in the definition of many
operations
◦ We shall ignore the effect of null values in our main
presentation and consider their effect later

8/10/2021 Faculty Name - Jyoti Snehi 16

 Relation Schema

 A1, A2, …, An are attributes

 R = (A1, A2, …, An ) is a relation schema

Example:
Customer_schema = (customer_name, customer_street,
customer_city)

 r(R) is a relation on the relation schema R

Example:
customer (Customer_schema)

8/10/2021 Faculty Name - Jyoti Snehi 17

 Relation Instance

 The current values (relation instance) of a relation are

specified by a table
 An element t of r is a tuple, represented by a row in a table

attributes
(or columns)
customer_name customer_street customer_city

Jones Main Harrison

Smith North Rye tuples
Curry North Rye (or rows)
Lindsay Park Pittsfield

customer

8/10/2021 Faculty Name - Jyoti Snehi 18

 Relations are Unordered
Order of tuples is irrelevant (tuples may be stored in an arbitrary order)
Example: account relation with unordered tuples

8/10/2021 Faculty Name - Jyoti Snehi 19

 Relational Algebra

 Procedural language
 Six basic operators
◦ select: 
◦ project: 
◦ union: 
◦ set difference: –
◦ Cartesian product: x
◦ rename: 
 The operators take one or two relations as inputs and produce
a new relation as a result.

8/10/2021 Faculty Name - Jyoti Snehi 20

 Select Operation

 Notation:  p(r)
 p is called the selection predicate
 Defined as:

p(r) = {t | t  r and p(t)}

Where p is a formula in propositional calculus consisting of terms

connected by :  (and),  (or),  (not)
Each term is one of:
<attribute> op <attribute> or <constant>
where op is one of: =, , >, . <. 

 Example of selection:

 branch_name=“Perryridge”(account)
8/10/2021 Faculty Name - Jyoti Snehi 21
 Select Operation

8/10/2021 Faculty Name - Jyoti Snehi 22

 Select Operation

8/10/2021 Faculty Name - Jyoti Snehi 23

 Select Operation – Example

Relation r
A B C D

  1 7
  5 7
  12 3
  23 10

 A=B ^ D > 5 (r)

A B C D

  1 7
  23 10

8/10/2021 Faculty Name - Jyoti Snehi 24

 Project Operation
 Project operations selects specific columns from the specified
relation.
 Notation:
 A1 , A2 ,, Ak
( r )

where A1, A2 are attribute names and r is a relation name.

 The result is defined as the relation of k columns obtained by
erasing the columns that are not listed
 Duplicate rows removed from result, since relations are sets
 Example: To eliminate the branch_name attribute of account

account_number, balance (account)

8/10/2021 Faculty Name - Jyoti Snehi 25

 Project Operation

8/10/2021 Faculty Name - Jyoti Snehi 26

Project and select Operation example

8/10/2021 Faculty Name - Jyoti Snehi 27

 Project Operation – Example

 Relation r: A B C

 10 1
 20 1
 30 1
 40 2

A,C (r) A C A C

 1  1
 1 =  1
 1  2
 2
8/10/2021 Faculty Name - Jyoti Snehi 28
8/10/2021 Faculty Name - Jyoti Snehi 29
 Set Operations

8/10/2021 Faculty Name - Jyoti Snehi 30

 Union Operation

 Notation: r  s
 Defined as:
r  s = {t | t  r or t  s}
 For r  s to be valid.
1. r, s must have the same arity (same number of attributes)
2. The attribute domains must be compatible (example: 2nd column
of r deals with the same type of values as does the 2nd
column of s)
 Example: to find all customers with either an account or a loan

customer_name (depositor)  customer_name

(borrower)
8/10/2021 Faculty Name - Jyoti Snehi 31
 Union

8/10/2021 Faculty Name - Jyoti Snehi 32

 Union Operation – Example

 Relations r, s:
A B A B

 1  2
 2  3
 1 s
r

A B

 1
r  s:
 2
 1
 3
8/10/2021 Faculty Name - Jyoti Snehi 33
 Intersection

8/10/2021 Faculty Name - Jyoti Snehi 34

 Set Difference Operation

• Notation r – s
• Defined as:
r – s = {t | t  r and t  s}

• Set differences must be taken between compatible

relations.
– r and s must have the same arity
– attribute domains of r and s must be compatible

8/10/2021 Faculty Name - Jyoti Snehi 35

 Set Difference

8/10/2021 Faculty Name - Jyoti Snehi 36

Set Difference Operation – Example

 Relations r, s:
A B A B

 1  2
 2  3
 1 s
r

r – s:
A B

 1
 1

8/10/2021 Faculty Name - Jyoti Snehi 37

 Assignment-1

8/10/2021 Faculty Name - Jyoti Snehi 38

 Answer

8/10/2021 Faculty Name - Jyoti Snehi 39

 Assignment-2

8/10/2021 Faculty Name - Jyoti Snehi 40

 Cartesian-Product Operation

• Notation r x s
• Defined as:
r x s = {t q | t  r and q  s}

• Assume that attributes of r(R) and s(S) are disjoint. (That is, R 
S =  ).
• If attributes of r(R) and s(S) are not disjoint, then renaming must
be used.
• GP-27

8/10/2021 Faculty Name - Jyoti Snehi 41

 Cartesian product

8/10/2021 Faculty Name - Jyoti Snehi 42

 Cross Product

8/10/2021 Faculty Name - Jyoti Snehi 43

 Cartesian product

8/10/2021 Faculty Name - Jyoti Snehi 44

 Example

8/10/2021 Faculty Name - Jyoti Snehi 45

 Solve

8/10/2021 Faculty Name - Jyoti Snehi 46

Cartesian-Product Operation
Relations r, s:
A B C D E

 1  10 a
 10 a
 2  20 b
r  10 b
s
r x s:
A B C D E
 1  10 a
 1  10 a
 1  20 b
 1  10 b
 2  10 a
 2  10 a
 2  20 b
 2  10 b

8/10/2021 Faculty Name - Jyoti Snehi 47

 Composition of Operations

 Can build expressions using multiple operations

 Example: A=C(r x s)
r x s A B C D E
 1  10 a
 1  10 a
 1  20 b
 1  10 b
 2  10 a
 2  10 a
 2  20 b
 2  10 b
 A=C(r x s)

A B C D E

 1  10 a
 2  10 a
Faculty Name - Jyoti Snehi  2  20 b
8/10/2021 48
 Rename Operation

 Allows us to name, and therefore to refer to, the results of

relational-algebra expressions.
 Allows us to refer to a relation by more than one name.
 Example:
 x (E)

returns the expression E under the name X

 If a relational-algebra expression E has arity n, then

 x ( A ,A
1
(E )
2 ,...,An )

returns the result of expression E under the name X, and with the
attributes renamed to A1 , A2 , …., An .

8/10/2021 Faculty Name - Jyoti Snehi 49

 Renaming

8/10/2021 Faculty Name - Jyoti Snehi 50

 Renaming

8/10/2021 Faculty Name - Jyoti Snehi 51

 Renaming

8/10/2021 Faculty Name - Jyoti Snehi 52

 Banking Example

• branch (branch_name, branch_city, assets)

• customer (customer_name, customer_street, customer_city)
• account (account_number, branch_name, balance)
• loan (loan_number, branch_name, amount)
• depositor (customer_name, account_number)
• borrower (customer_name, loan_number)
• Find all loans of over $1200
• Find the loan number for each loan of an amount greater than
$1200

8/10/2021 Faculty Name - Jyoti Snehi 53

 Example Queries

 Find all loans of over $1200

amount > 1200 (loan)

Find the loan number for each loan of an amount greater than
$1200

loan_number (amount > 1200 (loan))

8/10/2021 Faculty Name - Jyoti Snehi 54

 Example Queries

 Find the names of all customers who have a loan, an account,

or both, from the bank
customer_name (borrower)  customer_name (depositor)

Find the names of all customers who have a loan and an account at
bank.

customer_name (borrower)  customer_name (depositor)

8/10/2021 Faculty Name - Jyoti Snehi 55

 Example Queries

 Find the names of all customers who have a loan at the Perryridge
branch.
customer_name (branch_name=“Perryridge”
(borrower.loan_number = loan.loan_number(borrower x loan)))

Find the names of all customers who have a loan at the

Perryridge branch but do not have an account at any branch of
the bank.

customer_name (branch_name = “Perryridge”

(borrower.loan_number = loan.loan_number(borrower x loan))) –

customer_name(depositor)
8/10/2021 Faculty Name - Jyoti Snehi 56
 Example Queries

 Find the names of all customers who have a loan at the Perryridge
branch.
Query 1

customer_name (branch_name = “Perryridge” (

borrower.loan_number = loan.loan_number (borrower x loan)))

Query 2

customer_name(loan.loan_number = borrower.loan_number (
(branch_name = “Perryridge” (loan)) x borrower))

8/10/2021 Faculty Name - Jyoti Snehi 57

 Example Queries

• Find the largest account balance

– Strategy:
• Find those balances that are not the largest
– Rename account relation as d so that we can compare each
account balance with all others
• Use set difference to find those account balances that were not found
in the earlier step.
– The query is:

balance(account) - account.balance
(account.balance < d.balance (account x d (account)))

8/10/2021 Faculty Name - Jyoti Snehi 58

 Formal Definition

 A basic expression in the relational algebra consists of either one

of the following:
◦ A relation in the database
◦ A constant relation
 Let E1 and E2 be relational-algebra expressions; the following
are all relational-algebra expressions:
◦ E1  E2
◦ E1 – E2
◦ E1 x E2
◦ p (E1), P is a predicate on attributes in E1
◦ s(E1), S is a list consisting of some of the attributes in E1
◦  x (E1), x is the new name for the result of E1

8/10/2021 Faculty Name - Jyoti Snehi 59

 Additional Operations

We define additional operations that do not add any power to the

relational algebra, but that simplify common queries.
 Set intersection
 Natural join
 Assignment

8/10/2021 Faculty Name - Jyoti Snehi 60

 Set-Intersection Operation

• Notation: r  s
• Defined as:
• r  s = { t | t  r and t  s }
• Assume:
– r, s have the same arity
– attributes of r and s are compatible
• Note: r  s = r – (r – s)

8/10/2021 Faculty Name - Jyoti Snehi 61

 Set-Intersection Operation

• Relation r, s:
A B A B
 1  2
 2  3
 1

r s

• rs
A B

 2

8/10/2021 Faculty Name - Jyoti Snehi 62

 Binary Relational Operations

• Join
• Division

8/10/2021 Faculty Name - Jyoti Snehi 63

 Join

8/10/2021 Faculty Name - Jyoti Snehi 64

 Theta Join/conditional Join

8/10/2021 Faculty Name - Jyoti Snehi 65

 Conditional Join

8/10/2021 Faculty Name - Jyoti Snehi 66

 Equi Join

8/10/2021 Faculty Name - Jyoti Snehi 67

 Natural Join

• A NATURAL JOIN is a JOIN operation that creates an implicit join

clause for you based on the common columns in the two tables
being joined. Common columns are columns that have the same
name in both tables.
• A NATURAL JOIN can be an INNER join, a LEFT OUTER join, or
a RIGHT OUTER join. The default is INNER join.
• If the SELECT statement in which the NATURAL JOIN operation
appears has an asterisk (*) in the select list, the asterisk will be
expanded to the following list of columns (in this order):
• All the common columns
• Every column in the first (left) table that is not a common column
• Every column in the second (right) table that is not a common
column
8/10/2021 Faculty Name - Jyoti Snehi 68
 Natural Join
Notation: r s
Let r and s be relations on schemas R and S
respectively.
Then, r s is a relation on schema R  S obtained
as follows:
◦ Consider each pair of tuples tr from r and ts from s.
◦ If tr and ts have the same value on each of the attributes in R  S, add a
tuple t to the result, where
 t has the same value as tr on r
 t has the same value as ts on s
Example:
R = (A, B, C, D)
S = (E, B, D)
◦ Result schema = (A, B, C, D, E)
◦ r s is defined as:
r.A, r.B, r.C, r.D, s.E (r.B = s.B  r.D = s.D (r x s))
8/10/2021 Faculty Name - Jyoti Snehi 69
 Natural Join

8/10/2021 Faculty Name - Jyoti Snehi 70

 Natural Join

8/10/2021 Faculty Name - Jyoti Snehi 71

 Natural Join
 Relations r, s:

A B C D B D E

 1  a 1 a 
 2  a 3 a 
 4  b 1 a 
 1  a 2 b 
 2  b 3 b 
r s

r s
A B C D E
 1  a 
 1  a 
 1  a 
 1  a 
 2  b 
8/10/2021 Faculty Name - Jyoti Snehi 72
 Natural Join

8/10/2021 Faculty Name - Jyoti Snehi 73

 Natural Join

8/10/2021 Faculty Name - Jyoti Snehi 74

 Excercise

8/10/2021 Faculty Name - Jyoti Snehi 75

 Answer

• 5

8/10/2021 Faculty Name - Jyoti Snehi 76

 Drawback of Natural Join

8/10/2021 Faculty Name - Jyoti Snehi 77

 Outer Join

 An extension of the join operation that avoids loss of

information.
 Computes the join and then adds tuples form one relation that
does not match tuples in the other relation to the result of the
join.
 Uses null values:
◦ null signifies that the value is unknown or does not exist
◦ All comparisons involving null are (roughly speaking) false
by definition.
 We shall study precise meaning of comparisons with nulls
later

8/10/2021 Faculty Name - Jyoti Snehi 78

 Outer Join

8/10/2021 Faculty Name - Jyoti Snehi 79

 Outer Join

8/10/2021 Faculty Name - Jyoti Snehi 80

 Left Join

8/10/2021 Faculty Name - Jyoti Snehi 81

 Right Join

8/10/2021 Faculty Name - Jyoti Snehi 82

 Full Join

8/10/2021 Faculty Name - Jyoti Snehi 83

 Right outer Join

8/10/2021 Faculty Name - Jyoti Snehi 84

 Full outer join

8/10/2021 Faculty Name - Jyoti Snehi 85

 Outer Join – Example

 Relation loan

loan_number branch_name amount

L-170 Downtown 3000
L-230 Redwood 4000
L-260 Perryridge 1700

Relation borrower

customer_name loan_number
Jones L-170
Smith L-230
Hayes L-155

8/10/2021 Faculty Name - Jyoti Snehi 86

 Outer Join – Example
 Natral Join
loan Borrower

loan_number branch_name amount customer_name

L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith

Left Outer Join

loan Borrower
loan_number branch_name amount customer_name
L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-260 Perryridge 1700 null

8/10/2021 Faculty Name - Jyoti Snehi 87

 Outer Join – Example
Right Outer Join
loan borrower

loan_number branch_name amount customer_name

L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-155 null null Hayes
Full Outer Join
loan borrower

loan_number branch_name amount customer_name

L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-260 Perryridge 1700 null
L-155 null null Hayes

8/10/2021 Faculty Name - Jyoti Snehi 88

 JOINS in SQL

8/10/2021 Faculty Name - Jyoti Snehi 89

 Division

8/10/2021 Faculty Name - Jyoti Snehi 90

 Division- example

8/10/2021 Faculty Name - Jyoti Snehi 91

 Example-Division

8/10/2021 Faculty Name - Jyoti Snehi 92

 Revision of Relational algebra

8/10/2021 Faculty Name - Jyoti Snehi 93

 Assignment Operation

• The assignment operation () provides a convenient way to express complex

queries.
– Write query as a sequential program consisting of
• a series of assignments
• followed by an expression whose value is displayed as a result of the
query.
– Assignment must always be made to a temporary relation variable.
• Example: Write r s as
temp1  R X S
temp2  
result = temp1 – temp2
– The result to the right of the  is assigned to the relation variable on the left
of the .
– May use variable in subsequent expressions.

8/10/2021 Faculty Name - Jyoti Snehi 94

 Bank Example Queries
Find the names of all customers who have a loan and an account
at bank.

customer_name (borrower)  customer_name (depositor)

Find the name of all customers who have a loan at

the bank and the loan amount

customer-name, loan-number, amount (borrower loan )

8/10/2021 Faculty Name - Jyoti Snehi 95

 Bank Example Queries
 Find all customers who have an account from at least the
“Downtown” and the Uptown” branches.
Query 1

customer_name (branch_name = “Downtown” (depositor account )) 

customer_name (branch_name = “Uptown” (depositor account))

Query 2
customer_name, branch_name (depositor account)
 temp(branch_name) ({(“Downtown” ), (“Uptown” )})
Note that Query 2 uses a constant relation.

8/10/2021 Faculty Name - Jyoti Snehi 96

 Bank Example Queries

 Find all customers who have an account at all branches located

in Brooklyn city.

customer_name, branch_name (depositor account)

 branch_name (branch_city = “Brooklyn” (branch))

8/10/2021 Faculty Name - Jyoti Snehi 97

 Generalized Projection

 Extends the projection operation by allowing arithmetic functions to

be used in the projection list.

 F1 ,F2 ,..., Fn
(E )
E is any relational-algebra expression
Each of F , F , …, F are are arithmetic expressions
1 2 n

involving constants and attributes in the schema of E.

Given relation credit_info(customer_name, limit,
credit_balance), find how much more each person can
spend:
customer_name, limit – credit_balance (credit_info)

8/10/2021 Faculty Name - Jyoti Snehi 98

 Aggregate Functions

8/10/2021 Faculty Name - Jyoti Snehi 99

 Aggregate Functions and Operations

 Aggregation function takes a collection of values and returns a

single value as a result.
avg: average value
min: minimum value
max: maximum value
sum: sum of values
count: number of values
 Aggregate operation in relational algebra
G1 ,G2 ,,Gn
F ( A
1 1 ),F2 ( A2 ,,Fn ( An )
(E )
E is any relational-algebra expression
◦ G1, G2 …, Gn is a list of attributes on which to group (can be
empty)
◦ Each Fi is an aggregate function
◦ Each Ai is an attribute name

8/10/2021 Faculty Name - Jyoti Snehi 100

 Aggregate Function

8/10/2021 Faculty Name - Jyoti Snehi 101

 Aggregate Operation

8/10/2021 Faculty Name - Jyoti Snehi 102

 Aggregate Operation – Example

 Relation r:
A B C

  7
  7
  3
  10

g sum(c) (r) sum(c )

27

8/10/2021 Faculty Name - Jyoti Snehi 103

 Aggregate Operation –
Example
 Relation account grouped by branch-name:

branch_name account_number balance

Perryridge A-102 400
Perryridge A-201 900
Brighton A-217 750
Brighton A-215 750
Redwood A-222 700

branch_name g sum(balance) (account)

branch_name sum(balance)
Perryridge 1300
Brighton 1500
Redwood 700

8/10/2021 Faculty Name - Jyoti Snehi 104

 Aggregate Functions (Cont.)

• Result of aggregation does not have a name

– Can use rename operation to give it a name
– For convenience, we permit renaming as part of aggregate
operation

1) branch_name g sum(balance) as sum_balance (account)

2) g sum(salary)(instructor)
3) g average(salary)(instructor)
4) g count(ID)(instructor)
5) g count-distinct(ID)( semester=“Spring” ᶺ year = 2010(teaches))

8/10/2021 Faculty Name - Jyoti Snehi 105

8/10/2021 Faculty Name - Jyoti Snehi 106
 Answer

8/10/2021 Faculty Name - Jyoti Snehi 107

 Excercise

8/10/2021 Faculty Name - Jyoti Snehi 108

 Answer

8/10/2021 Faculty Name - Jyoti Snehi 109

 Excercise

8/10/2021 Faculty Name - Jyoti Snehi 110

 Answer

8/10/2021 Faculty Name - Jyoti Snehi 111

 Excercise

8/10/2021 Faculty Name - Jyoti Snehi 112

 Answer

8/10/2021 Faculty Name - Jyoti Snehi 113

 Excercise

8/10/2021 Faculty Name - Jyoti Snehi 114

 Answer

8/10/2021 Faculty Name - Jyoti Snehi 115