COMP1121

Databases

4: Relational Algebra
Our journey so far ...
Database
Environment Relational Relational
Introduction & Algebra
Model
Architecture

SQL
Entity
Normalisation Relationship
Modelling

Database
Designs

Ethics of
Security & Transaction Using
Administration Management Databases

2
Relational Data Model
• Components of a data model
– A structural part – set of rules
– A manipulative part – operations allowed on
data
– A set of integrity constraints

3
Learning objectives
• To be able to write relational algebra queries.

4
Relational Algebra
• Relational algebra operations work on one or more
relations to define another relation without changing
the original relations.
• Both operands and results are relations, so output
from one operation can become input to another
operation.
• Five basic operations in relational algebra: Selection,
Projection, Cartesian product, Union, and Set
Difference.
• Also have Join, Intersection, and Division operations,
which can be expressed in terms of 5 basic
operations. 5
Relational Algebra Operations

6
Selection
• σpredicate R
– works on a single relation R and
defines a relation with tuples of
R satisfying the condition, the
predicate.
– 𝜎𝑠𝑎𝑙𝑎𝑟𝑦>10000 𝑆𝑡𝑎𝑓𝑓
– 𝜎𝑠𝑎𝑙𝑎𝑟𝑦>10000 𝑎𝑛𝑑 𝑠𝑒𝑥="𝐹" 𝑆𝑡𝑎𝑓𝑓

7
Example - Selection (or Restriction)

• List all staff with a salary greater than 10,000.

𝜎𝑠𝑎𝑙𝑎𝑟𝑦>10000 𝑆𝑡𝑎𝑓𝑓

8
Projection
• Πcol1,… ,coln R
– works on retrieving the attributes from the
relation R with duplicates removed.
– Πsalary (Staff)
– ΠstaffNo,fName,lName,salary (σsalary>10000 (𝑆𝑡𝑎𝑓𝑓)

9
Example - Projection
• Produce a list of salaries for all staff, showing only
staffNo, fName, lName, and salary details.

ΠstaffNo,fName,lName,salary (Staff)

10
Union
• R∪S
– Union of two relations R and S
produces a relation that contains
the tuples of R or S or both with
duplicates removed.
– Πcity Branch ∪
Πcity PropertyForRent

11
Example - Union

• List all cities where there is either a branch office or a

property for rent.
Πcity Branch ∪ Πcity PropertyForRent

12
Cartesian Product

• R×S
• Defines a relation that is the concatenation of every
tuple of R with every tuple in S
– Client x Viewing
– ΠclientNo,fName,lName Client ×
ΠclientNo,propertyNo,comment Viewing 13
Example - Cartesian Product

• List the names and comments of all clients who

have viewed a property for rent.

ΠclientNo,fName,lName Client
× (ΠclientNo,propertyNo,comment Viewing )

14
Example - Cartesian Product
πclientNo,fName,lName Client
× (πclientNo,propertyNo,comment Viewing )

15
Example - Cartesian Product (2 of 2)

16
Intersection

• R∩S
– defines a relation with tuples
that are in both R and S.
– ΠbranchNo Branch ∩
ΠbranchNo (Staff)

17
Example - Intersection

• List all cities where there is both a branch office and at

least one property for rent.

Πcity Branch ∩ Πcity (PropertyForRent)

18
Set difference

• R −S
– defines a relation of the
tuples that are in relation R
but not in S.
– ΠbranchNo Branch −
ΠbranchNo (Staff)

19
Example - Set Difference

• List all cities where there is a branch office but no

properties for rent.
Πcity Branch − Πcity (PropertyForRent)

20
Theta Join

R ⋈F S
– defines a relation that contains tuples satisfying
the predicate F from the Cartesian product of R
and S.
– Can be rewritten using basic Selection and
Cartesian product operations.
– R ⋈F S = σF (R × S)
– If predicate F contains only equality (=), the term
Equijoin is used.

21
Natural Join

Natural join R ⋈ S
• Equijoin of the two relations R and S over all
common attributes x with no duplicate in
each common attribute.
• ClientViewing = Client ⋈ Viewing

22
(Left) Outer Join

• The (left) Outer join is a join in which tuples

from R that do not have matching values in
the common attributes of S are also included
in the result relation. Missing values in the
second relation are set to null.
23
Other joins
• Semijoin
– The Semijoin operation defines a relation that
contains the tuples of R that participate in the join
of R with S satisfying the predicate F.
• Right (outer) join
– defines a relation with all tuples from S including
those without a matching values in common
attributes in R
• Full outer join R ⟗ S
– defines a relation with a tuples from R and S with
matching values in common attributes, and also
those in S and R that have not matching values.
24
Aggregation

• GAL(R) or FAL(R)
– Applies aggregate function list, AL, to R to define a
relation over the aggregate list.
– AL contains one or more (<aggregate_function>,
<attribute>) pairs.
– AL: COUNT, SUM, AVG, MIN, MAX
– Gsum(balance) (credit_acct)
– 𝜌𝑅 𝑚𝑦𝐶𝑜𝑢𝑛𝑡 𝐹𝐶𝑂𝑈𝑁𝑇 (𝑝𝑟𝑜𝑝𝑒𝑟𝑡𝑦𝑁𝑜)(𝜎𝑟𝑒𝑛𝑡 > 350
𝑃𝑟𝑜𝑝𝑒𝑟𝑡𝑦𝐹𝑜𝑟𝑅𝑒𝑛𝑡 )

25
Grouping

• GAGAL(R) or GAFAL(R)
– Groups tuples of R by grouping attributes, G A, and
then applies aggregate function list, A L, to define a
new relation.
– Resulting relation contains the grouping attributes,
G A, along with results of each of the aggregate
functions.
– person_nameGcount(puzzle_name) (completed)
– 𝜌𝑅(branchNo, myCount, mySum) branchNoFCOUNT(staffNo),
SUM(salary)(Staff)

26
Summary

• Writing queries with relational algebra

Next week, we look at Structured Query

Language (SQL)

27
Follow-up work
• Complete required reading:
– Connolly & Begg: Chapter 5: 5.1

• Install Relational [optional]

– Download and install Relational from
https://ltworf.github.io/relational/.
– Download RelationalExamples.zip on Minerva and try
the examples

• Reading for next lecture:

– Connolly & Begg: 6:6.1-6.3.4, Chapter 7:7.1-7.3

28