5.relation Algebra

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.

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.

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

Relational database

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)

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)

Relational algebra

Relational Algebra:
Types:
• Unary operation
• Binary operation
• Unary operation Relational Algebra Operations from Set Theory.

• Binary operation (Join and Divison)

Relational algebra

Relational algebra Operations

Relational Algebra

Example of a Relation

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

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)

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

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

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.

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)
Select Operation

Select Operation

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

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)

Project Operation

Project and select Operation example

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
Set Operations

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)
Union

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
Intersection

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

Set Difference

Set Difference Operation – Example
 Relations r, s:
A B A B
 1  2
 2  3
 1 s
r
r – s:
A B
 1
 1

Assignment-1

Answer

Assignment-2

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

Cartesian product

Cross Product

Cartesian product

Example

Solve

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

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 .

Renaming

Renaming

Renaming

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

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))

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)

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)
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))

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)))

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

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

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)

Set-Intersection Operation
• Relation r, s:
A B A B
 1  2
 2  3
 1
r s
• rs
A B
 2

Binary Relational Operations
• Join
• Division

Join

Theta Join/conditional Join

Conditional Join

Equi Join

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
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))
Natural Join

Natural Join

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 
Natural Join

Natural Join

Excercise

Answer
• 5

Drawback of Natural Join

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

Outer Join

Outer Join

Left Join

Right Join

Full Join

Right outer Join

Full outer join

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

 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
L-260 Perryridge 1700 null

Right Outer Join
loan borrower

L-155 null null Hayes
Full Outer Join
loan borrower

L-260 Perryridge 1700 null
L-155 null null Hayes

JOINS in SQL

Division

Division- example

Example-Division

Revision of Relational algebra

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.

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 )

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

 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))

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)

Aggregate Functions

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

Aggregate Function

Aggregate Operation

Aggregate Operation – Example
 Relation r:
A B C
  7
  7
  3
  10
g sum(c) (r) sum(c )
27

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

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))

Answer

Excercise

Answer

Excercise

Answer

Excercise

Answer

Excercise

Answer

5.relation Algebra

Uploaded by

Copyright:

Available Formats

5.relation Algebra

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5.relation Algebra

Uploaded by

Copyright:

Available Formats

Relational Algebra

Ms. Jyoti Snehi

• Language in which user requests information from the database.

8/10/2021 Faculty Name - Jyoti Snehi 2

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

8/10/2021 Faculty Name - Jyoti Snehi 3

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

8/10/2021 Faculty Name - Jyoti Snehi 4

8/10/2021 Faculty Name - Jyoti Snehi 5

8/10/2021 Faculty Name - Jyoti Snehi 6

• The algebra operations thus produce new relations

8/10/2021 Faculty Name - Jyoti Snehi 7

8/10/2021 Faculty Name - Jyoti Snehi 8

• Unary operation Relational Algebra Operations from Set Theory.

8/10/2021 Faculty Name - Jyoti Snehi 9

8/10/2021 Faculty Name - Jyoti Snehi 10

8/10/2021 Faculty Name - Jyoti Snehi 12

8/10/2021 Faculty Name - Jyoti Snehi 13

8/10/2021 Faculty Name - Jyoti Snehi 14

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

 Each attribute of a relation has a name

8/10/2021 Faculty Name - Jyoti Snehi 16

 A1, A2, …, An are attributes

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

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

8/10/2021 Faculty Name - Jyoti Snehi 17

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

Jones Main Harrison

8/10/2021 Faculty Name - Jyoti Snehi 18

8/10/2021 Faculty Name - Jyoti Snehi 19

8/10/2021 Faculty Name - Jyoti Snehi 20

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

Where p is a formula in propositional calculus consisting of terms

8/10/2021 Faculty Name - Jyoti Snehi 22

8/10/2021 Faculty Name - Jyoti Snehi 23

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

8/10/2021 Faculty Name - Jyoti Snehi 24

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

account_number, balance (account)

8/10/2021 Faculty Name - Jyoti Snehi 25

8/10/2021 Faculty Name - Jyoti Snehi 26

8/10/2021 Faculty Name - Jyoti Snehi 27

8/10/2021 Faculty Name - Jyoti Snehi 30

customer_name (depositor)  customer_name

8/10/2021 Faculty Name - Jyoti Snehi 32

8/10/2021 Faculty Name - Jyoti Snehi 34

• Set differences must be taken between compatible

8/10/2021 Faculty Name - Jyoti Snehi 35

8/10/2021 Faculty Name - Jyoti Snehi 36

8/10/2021 Faculty Name - Jyoti Snehi 37

8/10/2021 Faculty Name - Jyoti Snehi 38

8/10/2021 Faculty Name - Jyoti Snehi 39

8/10/2021 Faculty Name - Jyoti Snehi 40

8/10/2021 Faculty Name - Jyoti Snehi 41

8/10/2021 Faculty Name - Jyoti Snehi 42

8/10/2021 Faculty Name - Jyoti Snehi 43

8/10/2021 Faculty Name - Jyoti Snehi 44

8/10/2021 Faculty Name - Jyoti Snehi 45

8/10/2021 Faculty Name - Jyoti Snehi 46