Advanced Database Systems
Spring 2025
Lecture #03:
Relational Algebra
R&G: Chapters 4.1 & 4.2
2
Q UERY E XECUTION O VERVIEW
SQL Query Relational Algebra
SELECT S.name π S.name(σ E.cid = ‘INF-11199’(
FROM Student S, Enrolled E
WHERE S.sid = E.sid Student ⋈ S.sid = E.sid Enrolled ))
Query Parser &
AND E.cid = ‘INF-11199’
Optimiser
Equivalent to…
Optimised Physical Query Plan Logical Query Plan
sorting
π S.name π S.name
sort-merge join
⋈ S.sid = E.sid σ E.cid = ‘INF-11199’
But actually will
σ B+ tree
E.cid = ‘INF-11199’ produce plan with ⋈ S.sid = E.sid
scan operator code
Student Enrolled Student Enrolled
3
Q UERY E XECUTION O VERVIEW
SQL Query Relational Algebra
SELECT S.name π S.name(σ E.cid = ‘INF-11199’(
FROM Student S, Enrolled E
WHERE S.sid = E.sid Student ⋈ S.sid = E.sid Enrolled ))
AND E.cid = ‘INF-11199’
Declarative description of computation Operational description of computation
Say what you want, not how to get it Systems execute RA query plans
Enables system to optimize the how
Foundation in formal query languages
Relational Calculus
4
R ELATIONAL Q UERY L ANGUAGES
Relational Calculus (basis for SQL)
Describe the result of computation
Based on first order logic
Tuple Relational Calculus (TRC)
{ S | S ∈ Student ∃E ∈ Enrolled
Are these two
( S.sid = E.sid ∧ E.cid = ‘INF-11199’ ) }
equivalent?
Relational Algebra Can we go from one
Algebra on sets to the other?
Operational description of transformations
5
C ODD ’ S T HEOREM
Established equivalence in expressivity between:
Relational Calculus
Relational Algebra
Why an important result?
Connects declarative representation of
queries with operational description Edgar F. “Ted” Codd
(1923 - 2003)
Constructive: we can compile SQL into relational algebra Turing Award 1981
6
R ELATIONAL A LGEBRA
Algebra of operators on relation instances σ Selection
π Projection
π S.name(σ E.cid = ‘INF-11199’(S ⋈ S.sid = E.sid E))
⍴ Renaming
Closed: result is also a relation instance ∪ Union
Enables rich composition!
– Set Difference
Typed: input schema determines output schema × Cross Product
Can statically check whether queries are legal ∩ Intersection
⋈ Join
7
R ELATIONAL A LGEBRA AND S ETS
Pure relational algebra has set semantics
No duplicate tuples in a relation instance
But can also be defined over bags (multisets)
SQL has multiset (bag) semantics
We will switch to multiset in the system discussion
8
S ELECTION
Syntax: σpredicate (R) R(aid, bid)
aid bid
Select a subset of rows (horizontal) a1 101
that satisfy a selection predicate a2 102
Can combine predicates using conjunctions / disjunctions a2 103
a3 104
Output schema same as input
Duplicate elimination? Not needed
σaid=’a2’ (R)
σaid=’a2’ ∧ bid > 102 (R) aid bid
aid bid a2 102
a2 103 a2 103
9
P ROJECTION
Syntax: πA1, A2, …, An (R) R(aid, bid)
aid bid
Selects a subset of columns (vertical) a1 101
a2 102
Schema determined by schema of attribute list
a2 103
a3 104
Set semantics → results in fewer rows
Real systems don’t automatically remove duplicates π aid (R)
Why? aid
a1
1) Semantics: keep duplicates for aggregates
a2
2) Performance: deduplication not free a3
10
U NION R S R∪S
Syntax: R ∪ S R(aid, bid) S(aid, bid)
aid bid aid bid
Two input relations must be compatible a1 101 a3 103
Same number of fields a2 102 a4 104
Fields in corresponding positions have same type a3 103 a5 105
Duplicate elimination in practice (SQL)? R ∪ S
aid bid
UNION – eliminates duplicates
a1 101
UNION ALL – keeps duplicates
a2 102
a3 103
a4 104
a5 105
11
S ET D IFFERENCE R S R –S S
Syntax: R – S
R(aid, bid) S(aid, bid)
Same as with union, both input relations aid bid aid bid
must be compatible a1 101 a3 103
Duplicate elimination? Not needed a2 102 a4 104
a3 103 a5 105
SQL expression: EXCEPT
EXCEPT vs EXCEPT ALL
R – S S – R
aid bid aid bid
a1 101 a4 103
a2 102 a5 105
12
C ROSS P RODUCT
R(aid, bid) S(bid, cid)
Syntax: R × S aid bid bid cid
a1 101 b3 23
Each row of R paired with each row of S a2 102 b4 24
a3 103
How many rows in result? |R|*|S|
Schema compatibility? Not needed R × S
aid (bid) (bid) cid
Duplicates? None generated
a1 101 b3 23
a1 101 b4 24
R × S has two bid attributes a2 102 b3 23
Not allowed, leave them unnamed a2 102 b4 24
a3 103 b3 23
Identify attributes by position
a3 103 b4 24
13
R ENAMING (⍴ = “rho”)
Renames relations and their attributes R × S
aid (bid) (bid) cid
Note that relational algebra doesn’t require names
a1 101 b3 23
We could just use positional arguments a1 101 b4 24
a2 102 b3 23
⍴ ( Temp(2 → bid1, 3 → bid2), R × S) a2 102 b4 24
Output Relation Renaming List Input
Temp
Name position → new name Expression aid bid1 bid2 cid
a1 101 b3 23
a1 101 b4 24
a2 102 b3 23
a2 102 b4 24
14
C OMPOUND O PERATOR : I NTERSECTION
Syntax: R ∩ S
R(aid, bid) S(aid, bid)
aid bid aid bid
R S R ∩ S
a1 101 a3 103
a2 102 a4 104
a3 103 a5 105
Same as with union, both input relations
must be compatible R ∩ S
aid bid
SQL expression: INTERSECT
a3 103
Equivalent to: R – (R – S) S
15
C OMPOUND O PERATOR : J OIN
Joins are compound operators (like intersection):
Generally, σ θ (R × S)
Hierarchy of common kinds:
Theta Join ( ⋈θ ): join on logical expression 𝜃
Equi-Join: theta join with theta being a conjunction of equalities
Natural Join ( ⋈ ): equi-join on all matching column names
Note: we will need to learn a good join algorithm
Avoid cross-product if we can!
16
T HETA J OIN E XAMPLE
Student Student ⋈sid=sid Enrolled
sid name age (sid) name age (sid) cid grade
12344 Jones 18 12344 Jones 18 12344 INF-10080 65
12355 Smith 23 12355 Smith 23 12355 INF-11199 72
12366 Gold 21
Note that output needs a rename operator!
Enrolled
sid cid grade
12344 INF-10080 65
12355 INF-11199 72
17
T HETA J OIN E XAMPLE 2
Example: Get senior students for each student Student
sid name age
Student ⋈field3 < field6 Student (i.e., age < age2) 12344 Jones 18
R ⋈θ S = 𝜎θ( R × S) 12355 Smith 23
12366 Gold 21
Student ⋈field3 < field6 Student
(sid) (name) (age) (sid) (name) (age)
12344 Jones 18 12355 Smith 23
12344 Jones 18 12366 Gold 21
12366 Gold 21 12355 Smith 23
Output schema same as that of cross product
18
N ATURAL J OIN
Syntax: R ⋈ S R(aid, bid) S(bid, cid)
aid bid bid cid
Special case of equi-join in which equalities a1 101 101 c3
are specified for all matching fields and a2 102 101 c4
duplicate fields are projected away a3 103 105 c5
R ⋈ S = π unique fld. σ eq.matching fld. (R × S)
R ⋈ S
aid bid cid
Compute R × S a1 101 c3
Select rows where fields appearing in a1 101 c4
both relations have equal values
Project onto the set of all unique fields
19
E XTRA O PERATORS
Group By / Aggregation (𝛾)
𝛾dept, AVG(age) ( Student)
𝛾dept, AVG(age), COUNT(*) > 2 ( Student) with selection (HAVING clause)
Duplicate Elimination (δ)
only under multiset (bag) interpretation of relational algebra
Assignment (R ⃪ S)
Sorting (𝜏)
Division (R ÷ S)
20
S UMMARY
Relational Algebra
A small set of operators mapping relations to relations
Operational, in the sense that you specify the explicit order of operations
A closed set of operators! Mix and match
Basic operators: σ, π, ⍴, ∪, –, ×
Important compound operators: ∩, ⋈
