Chapter-Five

Relational Algebra

1 fundamental of database system CS@SLU

Outlines
♦ Over view of relational Algebra
♦ Basic operations in relational
algebra
Selection
Projection
Cross-product
Set-difference
Union

2 fundamental of database system CS@SLU

Introduction
 Relational algebra are formal languages associated with the relational model.
 Relational algebra is used to define the ways in which relations(tables) can be

operated to manipulate their data.

 Generally,
 Relational algebra is similar to high school algebra except that the variables are tables

not numbers and the results are tables not numbers

 Relational Algebra: More operational, very useful for representing execution plans.

3 Fundamentals of Database Systems 04/15/2025

Relational Algebra
 Relational algebra is a procedural query language, which takes instances of relations
as input and yields instances of relations as output.
 It uses operators to perform queries.
 An operator can be either unary or binary.
 The Relational Algebra Expression either takes one relation or two relations as an
input to the expression or produces a new relation as a result.
 They accept relations as their input and yield relations as their output.
 Relational algebra is performed recursively on a relation and intermediate results are
also considered relations.

4 Fundamentals of Database Systems 04/15/2025

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

5 Fundamentals of Database Systems 04/15/2025

Example Instances
 We’ll use positional or named field notation, assume that names of fields in query
results are `inherited’ from names of fields in query input relations

sid sname rating age

22 dustin 7 45.0
sid bid day
R1 22 101 10/10/96 S131 lubber 8 55.5
58 103 11/12/96 58 rusty 10 35.0
bid bname color sid sname rating age
101 Interlake blue 28 yuppy 9 35.0
102 Interlake red S2 31 lubber 8 55.5
B1 103 Clipper green 44 guppy 5 35.0
104 Marine red 58 rusty 10 35.0
6 fundamental of database system CS@SLU
Basic operations
 Selection ( ) Selects a subset of rows from relation.
 Projection ( ∏ ) Deletes unwanted columns from relation.
 Cross-product (  ) Allows us to combine two relations.
 Set-difference (─ ) Tuples in reln. 1, but not in reln. 2.
 Union (  ) Tuples in reln. 1 and in reln. 2.
 Additional operations:
 Intersection, join, division, renaming: Not essential, but (very!) useful.
 Since each operation returns a relation, operations can be composed! (Algebra is
“closed”.)

7 Fundamentals of Database Systems 04/15/2025

Relational Algebra Operations
The usual set operations: union, intersection, difference

•Operations that remove parts of relations:

 Selection: rows
 Projection: columns
•Operations that combine tuples from two relations:
 Cartesian product, join
 Since each operation returns a relation, operations can be
composed!
 Removing Parts of
Relations
 Selection – rows
 Projection - columns
Selection
 Selects rows that satisfy selection condition.
 No duplicates in result!
 Schema of result identical to schema of (only) input relation.
 Result relation can be the input for another relational algebra operation! (Operator
composition.)

10 Fundamentals of Database Systems 04/15/2025

Example
SSN Name Salary
1234545 John 200000
5423341 Smith 600000
4352342 Fred 500000
s Salary > 40000 (Employee)
SSN Name Salary
5423341 Smith 600000
4352342 Fred 500000
Projection
 Deletes attributes that are not in projection list.
 Duplicate rows are automatically eliminated, as relation is a set.
 Schema of result contains exactly the fields in the projection list, with the same
names that they had in the (only) input relation.

12 Fundamentals of Database Systems 04/15/2025

Example
SSN Name Salary
1234545 John 200000
5423341 John 600000
4352342 John 200000
P Name,Salary (Employee)

Name Salary
John 20000
John 60000
Set Operation (Union, Intersection, Set-
Difference)
 All of these operations take two input relations, which must be union-compatible:
 Same number of fields.
 Corresponding’ fields have the same type.

14 Fundamentals of Database Systems 04/15/2025

Set Operation :Union
 It performs binary union between two given relations and is defined as
r ∪ s = { t | t ∈ r or t ∈ s}
RUS
 returns relation instance containing all tuples that occur in either relation instance R
or S, or both.
 R and S must be union compatible.
 Schema of the result is defined to be that of R.
 r, and s must have the same number of attributes.
 Attribute domains must be compatible.
 Duplicate tuples are automatically eliminated

15 Fundamentals of Database Systems 04/15/2025

Set Operation Union>>Example
sid sname rating age sid sname rating age
28 yuppy 9 35.0
S1 22 dustin 7 45.0 S2 31 lubber 8 55.5
31 lubber 8 55.5 44 guppy 5 35.0
58 rusty 10 35.0 58 rusty 10 35.0

S1 S2

16 Fundamentals of Database Systems 04/15/2025

Set Operation: Intersection
R ⋂ S:
 returns a relation instance
 containing all tuples that occur in both R and S.
 R and S must be union compatible.
 Schema of the result is that of R.

17 Fundamentals of Database Systems 04/15/2025

Set Operation: Intersection>>Example

sid sname rating age sid sname rating age

28 yuppy 9 35.0
S1 22 dustin 7 45.0 S2 31 lubber 8 55.5
31 lubber 8 55.5 44 guppy 5 35.0
58 rusty 10 35.0 58 rusty 10 35.0

18 Fundamentals of Database Systems 04/15/2025

Set Operation: Set-Difference
 The result of set difference operation is tuples, which are present in one relation but
are not in the second relation.
R – S:
 returns a relation instance containing all tuples that occur in R but not in S.
 R and S must be union-compatible.
 Scheme of the result is the schema of R.

19 Fundamentals of Database Systems 04/15/2025

Set Operation: Set-Difference>>Example

sid sname rating age sid sname rating age

22 dustin 7 45.0 28 yuppy 9 35.0
S1 S2 31 lubber 8 55.5
31 lubber 8 55.5
58 rusty 10 35.0 44 guppy 5 35.0
58 rusty 10 35.0

20 Fundamentals of Database Systems 04/15/2025

Cartesian Product
R x S:
 Returns a relation instance whose scheme contains:

 All the fields of R (in the same order as they appear in R)

 All the fields of S (in the same order as they appear in S)
 The result contains one tuple <r,s> for each pair with r ⋳ R and s ⋳ S
Basically, it is the Cartesian product.
 Fields of the same name are unnamed.
 Each row of S1 is paired with each row of R1.
 Result schema has one field per field of S1 and R1, with field names `inherited’ if possible.
 Conflict: Both S1 and R1 have a field called sid.

21 Fundamentals of Database Systems 04/15/2025

Cartesian Product>>Example
S1
sid sname rating age
22 dustin 7 45.0
31 lubber 8 55.5
58 rusty 10 35.0
S1R1
(sid) sname rating age (sid) bid day
22 dustin 7 45.0 22 101 10/ 10/ 96
22 dustin 7 45.0 58 103 11/ 12/ 96
31 lubber 8 55.5 22 101 10/ 10/ 96
31 lubber 8 55.5 58 103 11/ 12/ 96
58 rusty 10 35.0 22 101 10/ 10/ 96
58 rusty 10 35.0 58 103 11/ 12/ 96

22 Fundamentals of Database Systems 04/15/2025

Cartesian Product>>Example

23 Fundamentals of Database Systems 04/15/2025

Other Operators
 We can define any operation using the operators that we have seen.
 some other operations appear very frequently.
 Join

24 Fundamentals of Database Systems 04/15/2025

JOIN
 JOIN Operation (denoted by (
)
 The sequence of CARTESIAN PRODECT followed by SELECT is used quite
commonly to identify and select related tuples from two relations
 This operation is very important for any relational database with more than a single
relation, because it allows us combine related tuples from various relations
 The general form of a join operation on two relations R(A1, A2, . . ., An) and S(B1,
B2, . . ., Bm) is:
R  <join condition>S
 where R and S can be any relations that result from general relational algebra
expressions.

25 Fundamentals of Database Systems 04/15/2025

Types of Join
NATURAL JOIN (⋈)
Natural join can only be performed if there is a common attribute (column) between the relations.
The name and type of the attribute must be same.
Example
Consider the following two tables
C⋈D
C D
Num Square Num Cube
2 4 2 8
3 9 3 27

C⋈D
Num Square Cube
2 4 8
3 9 27

26 fundamental of database system CS@SLU

Con. …
 In the left outer join, operation allows keeping all tuple in the left relation.
 However, if there is no matching tuple is found in right relation, then the
attributes of right relation in the join result are filled with null values.

A
Num Square
2 4
3 9
4 16 A⋈B

Num Square Cube

B
2 4 8
Num Cube
2 8 3 9 18
3 18
4 16 –
5 75
27 fundamental of database system CS@SLU
Cont. …
Right Outer Join: ( A B)
 In the right outer join, operation allows keeping all tuple in the right relation.
However, if there is no matching tuple is found in the left relation, then the
attributes of the left relation in the join result are filled with null values.

A⋈B
Num Cube Square
2 8 4
3 18 9
5 75 –

28 fundamental of database system CS@SLU

 Cont. …
Full Outer Join: ( A B)
In a full outer join, all tuples from both relations are included in the result, irrespective of the matching condition.

A⋈B

Num Square Cube

2 4 8

3 9 18

4 16 –

5 – 75

29 fundamental of database system CS@SLU

Exercise

30 fundamental of database system CS@SLU

Cont. …

31 fundamental of database system CS@SLU

Summary
Operation(Symbols) Purpose
The SELECT operation is used for selecting a subset of the
Select(σ)
tuples according to a given selection condition

The projection eliminates all attributes of the input relation

Projection(π)
but those mentioned in the projection list.

UNION is symbolized by symbol. It includes all tuples that are

Union Operation(∪)
in tables A or in B.

– Symbol denotes it. The result of A – B, is a relation which

Set Difference(-)
includes all tuples that are in A but not in B.

Intersection defines a relation consisting of a set of all tuple

Intersection(∩)
that are in both A and B.
Cartesian operation is helpful to merge columns from two
Cartesian Product(X)
relations.
32 fundamental of database system CS@SLU
Cont. …
Natural join can only be performed if there is a common
Natural Join(⋈)
attribute (column) between the relations.

In the left outer join, operation allows keeping all tuple in the
Left Outer Join( )
left relation.

Right Outer In the right outer join, operation allows keeping all tuple in the
join( ) right relation.

Full Outer In a full outer join, all tuples from both relations are included in
Join( ) the result irrespective of the matching condition.

33 fundamental of database system CS@SLU

Cont… Chapter-Six

Compiled by Tadesse B (MSc) 04/15/2025