Relational Algebra (Part 1)
Two Questions
1 What is the difference between procedural and declarative languages?
2 What is the foundation for relational query languages like SQL?
Why Relational Algebra?
SQL is a (fairly) declarative query language:
SQL queries describe the set of tuples you want to get.
To be efficiently implemented, SQL queries need to be translated into
procedural programs.
Relational algebra (RA) provides an intermediate step for evaluating SQL.
RA is a query language for relational databases.
RA is not visible from the user interface, but at the core of SQL.
RA is used by relational DBMSs internally for representing and
optimising SQL queries.
What is Relational Algebra?
It’s an algebra, like elementary algebra in math.
An algebra is a set A together with a collection of operators on this set:
each operator has an arity n, i.e., the number of its arguments;
each operator on A of arity n is a (possibly partial) function
An → A.
Example: {1, 2, . . . }, {+,−,×, /}.
((1 + 2)× 4)− 7
((9 − 3)× 5)
Relational algebra is an algebra that is
a set of all possible relations for a database, together with
a collection of relational operators for processing relations.
Example: {R1,R2, . . . }, {σ,π,∪,∩, ��, . . . }, σA=2(πA(R1 �� R2))
Relational Operators
Relational algebra (RA) provides a number of relational operators:
Selection: choose certain tuples (i.e., rows).
Projection: choose certain attributes (i.e., columns).
Renaming: change the names of attributes or the relation name.
Union, intersection and difference: set operations on two relations
that have the same relational schema.
Cartesian product and join (several variations): combine tuples from
multiple relations together.
The operators are applied on one or two relations and the result is always a
relation.
Question One
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
What if we only want to know the matches in which the home and guest
teams had a tie?
Selection – Choose Rows
Selection σϕ(R) chooses tuples that satisfy the condition ϕ from a relation
R (i.e., the condition ϕ acts as a filter).
ϕ is a condition:
< attribute name > < op > < constant >, or
< attribute name > < op > < attribute name >,
and op is normally one of the operators {=, <, ≤, >, ≥, �=}.
Example:
σSemester=‘2016 S2’(Course)
σName �=‘Tom’(Employee)
σMark>50(Exam)
Selection – Example
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For σHomeScore=GuestScore(SOCCER), we have:
HomeTeam HomeScore GuestScore GuestTeam
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
For σHomeScore=1(σHomeScore=GuestScore(SOCCER)), we have:
HomeTeam HomeScore GuestScore GuestTeam
Frankfurt 1 1 Hamburg
Selection – Properties
Each selection σϕ(R) yields a relation that has the same attributes as R
(i.e., their relation schemas are the same).
Selection is commutative:
σϕ1(σϕ2(R)) = σϕ2(σϕ1(R)).
A sequence of selection operations can be combined into a single selection
operation with a conjunction of all the conditions:
σϕ2(σϕ1(R)) = σϕ1 ∧ ϕ2(R).
Example:
σSemester=‘2016 S2’(σName=‘Tom’(ENROLMENT)) =
σSemester=‘2016 S2’∧Name=‘Tom’(ENROLMENT)
Question Two
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
What if we only want the names of guest and home teams?
Projection – Choose Columns
Projection πA1,…,An (R) only keeps a number of specified attributes
A1, . . . ,An (columns) from a relation R, while the other attributes are
discarded.
Projection – Example
Still consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For πGuestTeam,HomeTeam(SOCCER), we have:
GuestTeam HomeTeam
Munich Kiel
Freiburg Munich
Hamburg Frankfurt
Frankfurt Kiel
Projection – Duplicates
Suppose that one more tuple is added into the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
Kiel 3 3 Munich
For πGuestTeam,HomeTeam(SOCCER), is the following result correct? Why or why
not?
GuestTeam HomeTeam
Munich Kiel
Freiburg Munich
Hamburg Frankfurt
Frankfurt Kiel
Munich Kiel
Projection – Duplicates
Suppose that one more tuple is added into the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
Kiel 3 3 Munich
For πGuestTeam,HomeTeam(SOCCER), is the following result correct? Why or why
not?
GuestTeam HomeTeam
Munich Kiel
Freiburg Munich
Hamburg Frankfurt
Frankfurt Kiel
Munich Kiel
Incorrect
GuestTeam HomeTeam
Munich Kiel
Freiburg Munich
Hamburg Frankfurt
Frankfurt Kiel
Correct
Projection – Duplicates
1 Projection can introduce duplicates that did not exist before, but that has to
be eliminated. Why?
Answer: Relations are sets. The value of an RA expression is a
relation, which does not include duplicates.
2 DBMSs often permit duplicates unless you explicitly say that you want them
removed. How to do this in SQL?
Answer: Using DISTINCT.
3 The number of tuples in the resulting relation πA1,…,An (R) is always less
than or equal to the number of tuples in R. What happens when
{A1, . . . ,An} is a superkey of R?
Answer: The number of tuples in the resulting relation πA1,…,An (R) is
equal to the number of tuples in R.
Projection – Properties
The result of πA1,…,An (R) is a relation with only the attributes in A1, . . . ,An,
and in that order.
πGuestTeam,HomeTeam(SOCCER)
GuestTeam HomeTeam
Munich Kiel
Freiburg Munich
Hamburg Frankfurt
Frankfurt Kiel
πHomeTeam,GuestTeam(SOCCER)
HomeTeam GuestTeam
Kiel Munich
Munich Freiburg
Frankfurt Hamburg
Kiel Frankfurt
Projection can be used to reorder attributes (i.e.,columns).
Projection – Properties
Projection is not commutative:
πB1,…,Bm (πA1,…,An (R)) = πA1,…,An (πB1,…,Bm (R)) does not hold in general
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
Consider the relation SOCCER, are the following expressions correct?
πHomeTeam(πGuestTeam,HomeTeam(SOCCER))
πGuestTeam,HomeTeam(πHomeTeam(SOCCER))
Projection – Properties
Projection is not commutative:
πB1,…,Bm (πA1,…,An (R)) = πA1,…,An (πB1,…,Bm (R)) does not hold in general
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
Consider the relation SOCCER, are the following expressions correct?
πHomeTeam(πGuestTeam,HomeTeam(SOCCER)) Correct
πGuestTeam,HomeTeam(πHomeTeam(SOCCER)) Incorrect
Projection – Properties
If A1, . . . ,An contains all the attributes in B1, . . . ,Bm, then
πB1,…,Bm (πA1,…,An (R)) = πB1,…,Bm (R) holds.
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
The following expression holds:
πHomeTeam(πGuestTeam,HomeTeam(SOCCER))=πHomeTeam(SOCCER)
Selection and Projection
“Selection chooses rows.”
“Projection chooses columns.”
Union, Intersection and Difference
Since relations are sets (of tuples), they are standard operations on sets.
Union, denoted as R1 ∪ R2, results in a relation that includes all tuples
either in R1 or in R2. Duplicate tuples are eliminated.
Intersection, denoted as R1 ∩ R2, results in a relation that includes all
tuples that are in both R1 and R2.
Difference, denoted as R1 − R2, results in a relation that includes all
tuples that are in R1 but not in R2.
Type compatibility: R1 and R2 must have the same type, i.e.,
the same number of attributes, and
the same domains for the attributes (the order is important).
Union – Example
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For σHomeScore=0(SOCCER)∪σGuestScore=3(SOCCER), we have:
HomeTeam HomeScore GuestScore GuestTeam
Munich 0 0 Freiburg
Kiel 1 3 Munich
Kiel 1 3 Frankfurt
Intersection – Example
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For σHomeScore=1(SOCCER)∩σHomeTeam=‘Kiel’(SOCCER), we have:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Kiel 1 3 Frankfurt
Difference – Example
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For SOCCER−σGuestTeam=‘Frankfurt’(SOCCER), we have:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Cartesian Product (Cross Product)
Cartesian product R1 × R2 combines tuples from two relations in a
combinatorial fashion.
The result has one tuple for each combination of two tuples – one from
R1 and the other from R2.
i.e., if R1 has n attributes and p tuples and R2 has m attributes and q tuples,
then R1 × R2 has
n + m attributes, and
p × q tuples.
Cartesian product is expensive, which would result in a very large relation
when R1 and R2 are large!
Cartesian Product – Example
Consider the relations HOME and GUEST:
HomeTeam HomeScore
Kiel 1
Frankfurt 1
GuestScore GuestTeam
3 Munich
1 Hamburg
For HOME×GUEST, we have:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Frankfurt 1 3 Munich
Kiel 1 1 Hamburg
Frankfurt 1 1 Hamburg
Cartesian Product – Example
Consider the slightly modified relations HOME and GUEST:
HomeTeam Score
Kiel 1
Frankfurt 1
Score GuestTeam
3 Munich
1 Hamburg
For HOME×GUEST, we have:
HomeTeam Home.Score Guest.Score GuestTeam
Kiel 1 3 Munich
Frankfurt 1 3 Munich
Kiel 1 1 Hamburg
Frankfurt 1 1 Hamburg
Observations: For R1 × R2,
R1 and R2 do not share any attribute names. If an attribute occurs in both
relations, it occurs twice in the result (prefixed by relation name);
the relations R1 and R2 do NOT have to be type compatible
Cartesian Product – Example
Consider the slightly modified relations HOME and GUEST:
HomeTeam Score
Kiel 1
Frankfurt 1
Score GuestTeam
3 Munich
1 Hamburg
For HOME×GUEST, we have:
HomeTeam Home.Score Guest.Score GuestTeam
Kiel 1 3 Munich
Frankfurt 1 3 Munich
Kiel 1 1 Hamburg
Frankfurt 1 1 Hamburg
Problem:
Many of the tuples in the result do not make sense!
Join
To remove the nonsense tuples generated by Cartesian product, we can
use selection with Cartesian product.
However this is not convenient since two operators have to be used.
Join R1 ��ϕ R2 is introduced as the combination of Cartesian product
and selection. That is,
R1 ��ϕ R2 = σϕ(R1 × R2).
Examples: ϕ may contain {=, <, ≤, >, ≥, �=} such as:
(HomeTeam = GuestTeam) ∧ (Home.Score = Guest .Score)
(Home.Score = Guest .Score) ∨ (HomeTeam = GuestTeam)
where ∧ means AND and ∨ means OR.
Join combines tuples from two relations whenever the combination of
tuples satisfies the join condition ϕ (different from Cartesian product
which includes all combinations of tuples).
Two Variations of Join
Two common variations of join:
Join R1 ��ϕ R2
Natural Join R1 �� R2
1 Implicitly apply the join condition on equality comparisons of
attributes that have the same name in both relations.
2 Project out one copy of the attributes that have the same name in
both relations.
Join – Example
Consider the relations MATCH and TEAM.
HomeTeam GuestTeam
Kiel Munich
Frankfurt Munich
Kiel Hamburg
Frankfurt Hamburg
TeamName Coach
Kiel Sven
Munich Tim
Hamburg Martin
Frankfurt Kai
For MATCH ��HomeTeam=TeamName TEAM, we have:
HomeTeam GuestTeam TeamName Coach
Kiel Munich Kiel Sven
Frankfurt Munich Frankfurt Kai
Kiel Hamburg Kiel Sven
Frankfurt Hamburg Frankfurt Kai
Note that, the tuples (Munich, Tim) and (Hamburg, Martin) in TEAM are
filtered out because they do not satisfy the join condition.
What will we have for MATCH �� TEAM?
Natural Join – Example
Still consider the relations MATCH and TEAM.
HomeTeam GuestTeam
Kiel Munich
Frankfurt Munich
Kiel Hamburg
Frankfurt Hamburg
HomeTeam Coach
Kiel Sven
Munich Tim
Hamburg Martin
Frankfurt Kai
For MATCH �� TEAM, we have:
HomeTeam GuestTeam Coach
Kiel Munich Sven
Frankfurt Munich Kai
Kiel Hamburg Sven
Frankfurt Hamburg Kai
Note that, the attribute HomeTeam shared by TEAM and MATCH occurs
only once in the result.
Attribute Names in Join
What if two attributes in different relations have the same name but we
don’t want them to match?
Example:
‘TeamName’ in the relation TEAM and ‘TeamName’ in the relation PROJECT
What if two attributes in different relations don’t have the same name but
we do want them to match?
Example:
‘HomeTeam’ in the relation MATCH and ‘TeamName’ in the relation TEAM
Renaming
Renaming is used to rename either the relation name or the attribute
names, or both.
Renaming is denoted as
ρR� (A1,…,An)
(R): renaming the relation name to R
�
and the attribute
names to A1, . . . ,An,
ρR� (R): renaming the relation name to R
�
and keeping the attribute
names unchanged, or
ρ(A1,…,An)(R): renaming the attribute names to A1, . . . ,An and keeping
the relation name unchanged.
Renaming is useful for giving names to the relations that hold the
intermediate results.
Renaming – Example
Consider the relation SOCCER:
HomeTeam HomeScore GuestScore GuestTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
For ρFootball (SOCCER), we have a relation FOOTBALL that has the same
attributes and tuples as ones in SOCCER.
For ρ(HTeam,HScore,GScore,GTeam)(SOCCER), we have the relation below:
HTeam HScore GScore GTeam
Kiel 1 3 Munich
Munich 0 0 Freiburg
Frankfurt 1 1 Hamburg
Kiel 1 3 Frankfurt
Renaming – Exercise
COURSE
Code Name Unit
COMP2400 Relational Databases 6
COMP3600 Algorithms 6
ENROL
StudentID Name CourseNo Semester EnrolDate
456 Tom COMP2400 2010 S2 02-Jul-2010
458 Mike COMP2400 2010 S2 23-Jun-2010
458 Mike COMP3600 2010 S2 05-Aug-2010
Exercise:
Who did enrol the course “Relational Databases”?
πStudentID,Name(σCName=‘Relational Databases’
(ρ(CourseNo,CName,Unit)(COURSE) �� ENROL))
Relational Operators 1
. . . . . .
. . . . . .
. . . . . .
1
http://merrigrove.blogspot.com.au/2011/12/another-introduction-to-algebraic-data.html (with some changes)