7. Relational Algebra
7. Relational Algebra
Housekeeping
7. Relational Algebra
Exam preparation events
Our School is happy to support us for running “Exam Preparation Events” towards the end of semester (likely Week 12 or Week 13). We would like to know how many of you plan to attend so we can facilitate the events. A poll will set up on Piazza for this.
SQL assessment in Week 8
COMP2400
Each student needs to attend a 5-minute oral exam in Week 8 (specific time/venue is available on Wattle).
COMP6240
A mid-term exam will be held during 6:30-8:30pm, 21 Sep 2016 at CSIT labs (student allocation is available on Wattle).
Our IT support will set up the exam lab environment before 12 Sep 2016 and we will release the guideline to help you be familiar with the exam lab environment before the exam.
The best way to prepare is to work through Labs 2 & 4 exercises, as well as the questions in the SQL assessment specification for COMP2400.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 1
7. Relational Algebra
Two Questions
1 What is the difference between procedural and declarative languages?
2 What is the foundation for relational query languages like SQL?
We will study:
1 Introduction
Why relational algebra?
What is relational algebra? 2 Relational operators
Selection
Pro jection
Union, intersection and difference
Cartesian product and join (equi-join and natural join) Renaming
3 A complete set of relational operators
4 Relational algebra queries
5 Equivalence between RA and SQL queries
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 2
7. Relational Algebra
Why Relational Algebra?
SQL is a (fairly) declarative query language:
a query describes 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.
Relational algebra is equivalent to the pure relational kernel of SQL (no consideration of duplicates, aggregate functions, grouping, ordering).
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 3
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 4
7. Relational Algebra
h op
ity n
is
a
(po
ss
ial
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; 6.2 Relational Algebra
ea
) function
c
era
tor
o
• What is an algebra after all? Example: {1,2,…}, {+,−,×,/}.
– It consists of ((1+2)×4)−7
((1•+o3p)e×rat5o)rs and atomic operands. – It allows to
nA
of
ar
An → A.
ibl
yp
art
• build expressions by applying operators to operands Relational algebra is an algebra that is
and / or other expressions of the algebra.
a set of all possible relations for a database, together with – Example: algebra of arithmetics
a collection of relational operators for processing relations. • Atomic operands: variables like x and constants like 15
• Operators: addition, subtraction, multiplication and division Example: {R1,R2,…}, {σ,π,∪,∩,◃▹,…}, σA=2(πA(R1 ◃▹ R2))
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 5
7. Relational Algebra
Relational Operators
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.
Some operators are unary such as selection, projection and renaming, and the others are binary.
R1 op R2: the result is a relation op R: the result is a relation
The operators are applied on relations and the result is always a relation.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 6
• Relational algebra: another example of an algebra
– Atomic operands:
• Variables, that stand for relations
• Constants, which are finite relations
7. Relational Algebra
Relational Database Systems 1 – Wolf-Tilo Balke – Institut für Informationssysteme – TU Braunschweig 9
Consider the relation FOOTBALL:
Question
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?
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 7
7. Relational Algebra
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=‘2013 S2’(Course) σName=‘Tom’ (Employee) σNo=CourseNo (R)
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 8
7. Relational Algebra
Selection – Example
Consider the relation FOOTBALL:
For σHomeScore=GuestScore(FOOTBALL), we have:
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
HomeTeam
HomeScore
GuestScore
GuestTeam
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 9
7. Relational Algebra
Selection – Example
Consider the relation FOOTBALL:
For σHomeScore=GuestScore(FOOTBALL), we have:
For σHomeScore=1(σHomeScore=GuestScore(FOOTBALL)), we have:
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
HomeTeam
HomeScore
GuestScore
GuestTeam
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
HomeTeam
HomeScore
GuestScore
GuestTeam
Frankfurt
1
1
Hamburg
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 10
7. Relational Algebra
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:
Example:
σφ2 (σφ1 (R)) = σφ1 ∧ φ2 (R).
σSemester=‘2013 S2’(σName=‘Tom’(ENROLMENT)) = σSemester=‘2013 S2’∧Name=‘Tom’(ENROLMENT)
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 11
7. Relational Algebra
Question
Consider the relation FOOTBALL:
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 home and guest teams?
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 12
7. Relational Algebra
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.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 13
7. Relational Algebra
Projection – Example
Still consider the relation FOOTBALL:
For πGuestTeam,HomeTeam(FOOTBALL), we have:
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
GuestTeam
HomeTeam
Munich
Kiel
Freiburg
Munich
Hamburg
Frankfurt
Frankfurt
Kiel
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 14
7. Relational Algebra
Projection – Duplicates
Suppose that one more tuple is added into the relation FOOTBALL:
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(FOOTBALL), is the following result correct? Why or why not?
GuestTeam
HomeTeam
Munich
Kiel
Freiburg
Munich
Hamburg
Frankfurt
Frankfurt
Kiel
Munich
Kiel
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 15
7. Relational Algebra
Projection – Duplicates
Suppose that one more tuple is added into the relation FOOTBALL:
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(FOOTBALL), is the following result correct? Why or why not?
GuestTeam
HomeTeam
Munich
Kiel
Freiburg
Munich
Hamburg
Frankfurt
Frankfurt
Kiel
Munich
Kiel
GuestTeam
HomeTeam
Munich
Kiel
Freiburg
Munich
Hamburg
Frankfurt
Frankfurt
Kiel
Incorrect
Correct
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 16
7. Relational Algebra
7. Relational Algebra
Projection – Duplicates
Projection – Duplicates
1 Projection can introduce duplicates that did not exist before, but that has to be eliminated. Why?
2 DBMSs often permit duplicates unless you explicitly say that you want them removed. How to do this in SQL?
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?
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 17
7. Relational Algebra
Projection – Properties
The result of πA1,…,An (R) is a relation with only the attributes in A1, . . . , An, and in that order.
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.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 18
7. Relational Algebra
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
πGuestTeam,HomeTeam(FOOTBALL)
πHomeTeam,GuestTeam(FOOTBALL)
GuestTeam
HomeTeam
HomeTeam
GuestTeam
Munich
Kiel
Kiel
Munich
Freiburg
Munich
Munich
Freiburg
Hamburg
Frankfurt
Frankfurt
Hamburg
Frankfurt
Kiel
Kiel
Frankfurt
Projection can be used to reorder attributes (i.e.,columns).
Consider the relation FOOTBALL, are the following expressions correct? πHomeTeam(πGuestTeam,HomeTeam(FOOTBALL))
πGuestTeam,HomeTeam(πHomeTeam(FOOTBALL))
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 19
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 20
7. Relational Algebra
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 FOOTBALL, are the following expressions correct?
πHomeTeam(πGuestTeam,HomeTeam(FOOTBALL)) Correct πGuestTeam,HomeTeam(πHomeTeam(FOOTBALL)) Incorrect
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 21
7. Relational Algebra
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(FOOTBALL))=πHomeTeam(FOOTBALL)
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 22
7. Relational Algebra
Selection and Projection
“Selection chooses rows.” “Projection chooses columns.”
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 23
7. Relational Algebra
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).
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 24
7. Relational Algebra
7. Relational Algebra
Consider the relation FOOTBALL:
Consider the relation FOOTBALL:
Union – Example
Intersection – Example
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
For σHomeScore=0(FOOTBALL)∪σGuestScore=3(FOOTBALL), we have:
For σHomeScore=1(FOOTBALL)∩σHomeTeam=‘Kiel’(FOOTBALL), we have:
HomeTeam
HomeScore
GuestScore
GuestTeam
Munich
0
0
Freiburg
Kiel
1
3
Munich
Kiel
1
3
Frankfurt
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Kiel
1
3
Frankfurt
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 25
7. Relational Algebra
Difference – Example
Consider the relation FOOTBALL:
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 26
7. Relational Algebra
Suppose that we have
Exercise
ENROL
StudentID
Name
CourseNo
Semester
EnrolDate
456
Tom
COMP2400
2010 S2
02-Jul-2010
458
Mike
COMP2400
2010 S2
23-Jun-2010
458
Mike
COMP2600
2010 S2
05-Aug-2010
…
…
…
…
…
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
For FOOTBALL−σGuestTeam=‘Frankfurt’(FOOTBALL), we have:
Exercise:
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
1 Who did enroll in COMP2400 in 2010 Semester two?
2 Which courses did Mike (458) enroll in?
3 Which courses did Tom (456) and Mike (458) both enroll in?
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 27
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 28
7. Relational Algebra
7. Relational Algebra
Suppose that we have
Suppose that we have
Exercise
Exercise
ENROL
StudentID
Name
CourseNo
Semester
EnrolDate
456
Tom
COMP2400
2010 S2
02-Jul-2010
458
Mike
COMP2400
2010 S2
23-Jun-2010
458
Mike
COMP2600
2010 S2
05-Aug-2010
ENROL
StudentID
Name
CourseNo
Semester
EnrolDate
456
Tom
COMP2400
2010 S2
02-Jul-2010
458
Mike
COMP2400
2010 S2
23-Jun-2010
458
Mike
COMP2600
2010 S2
05-Aug-2010
Exercise:
1 Who did enroll in COMP2400 in 2010 Semester two? πStudentID,Name(σSemester=‘2010 S2’(σcourseNo=‘COMP2400’(ENROL)))
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016
Exercise:
1 …
2 Which courses did Mike (458) enroll in?
πCourseNo(σStudentID=458(ENROL))
29 Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 30
7. Relational Algebra
Suppose that we have
Exercise:
7. Relational Algebra
Exercise
Cartesian Product (Cross Product)
ENROL
StudentID
Name
CourseNo
Semester
EnrolDate
456
Tom
COMP2400
2010 S2
02-Jul-2010
458
Mike
COMP2400
2010 S2
23-Jun-2010
458
Mike
COMP2600
2010 S2
05-Aug-2010
1 …
2 …
3 Which courses did Tom (456) and Mike (458) both enroll in?
πCourseNo(σStudentID=456(ENROL)) ∩ πCourseNo(σStudentID=458(ENROL))
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!
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 31
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 32
7. Relational Algebra
Cartesian Product – Example
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 33
7. Relational Algebra
Cartesian Product – Example
Consider the relations HOME and GUEST:
For HOME×GUEST, we have:
HomeTeam
HomeScore
Kiel
1
Frankfurt
1
GuestScore
GuestTeam
3
Munich
1
Hamburg
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Frankfurt
1
3
Munich
Kiel
1
1
Hamburg
Frankfurt
1
1
Hamburg
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 34
7. Relational Algebra
Cartesian Product – Example
Consider the slightly modified relations HOME and GUEST:
For HOME×GUEST, we have:
HomeTeam
Score
Kiel
1
Frankfurt
1
Score
GuestTeam
3
Munich
1
Hamburg
HomeTeam
Home.Score
Guest.Score
GuestTeam
Kiel
1
3
Munich
Frankfurt
1
3
Munich
Kiel
1
1
Hamburg
Frankfurt
1
1
Hamburg
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 35
7. Relational Algebra
Cartesian Product – Example
Consider the slightly modified relations HOME and GUEST:
For HOME×GUEST, we have:
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
HomeTeam
Score
Kiel
1
Frankfurt
1
Score
GuestTeam
3
Munich
1
Hamburg
HomeTeam
Home.Score
Guest.Score
GuestTeam
Kiel
1
3
Munich
Frankfurt
1
3
Munich
Kiel
1
1
Hamburg
Frankfurt
1
1
Hamburg
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 36
7. Relational Algebra
7. Relational Algebra
Cartesian Product – Example
(Theta) Join
Consider the slightly modified relations HOME and GUEST:
For HOME×GUEST, we have:
Problem:
Many of the tuples in the result do not make sense!
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 37
7. Relational Algebra
Two Variations of Join
Two common variations of join:
Equi-Join R1 ◃▹φ R2:
only equality comparisons (e.g., A=B) combined with AND are used in φ.
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.
Note: It’s common to use R1 ◃▹ R2 for expressing a natural join
between R1 and R2 in the literature.
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,
R 1 ◃▹ φ R 2 = σ φ ( R 1 × R 2 ) . Examples: φ may contain {=, <, ≤, >, ≥, ̸=} such as:
(HomeTeam = GuestTeam) ∧ (Home.Score = Guest.Score) (HomeTeam ̸= GuestTeam)
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).
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 38
7. Relational Algebra
Equi-Join – Example
Consider the relations MATCH and TEAM.
For MATCH ◃▹HomeTeam=TeamName TEAM, we have:
Note that, the tuples (Munich, Tim) and (Hamburg, Martin) in TEAM are filtered out because they do not satisfy the join condition.
HomeTeam
Score
Kiel
1
Frankfurt
1
Score
GuestTeam
3
Munich
1
Hamburg
HomeTeam
Home.Score
Guest.Score
GuestTeam
Kiel
1
3
Munich
Frankfurt
1
3
Munich
Kiel
1
1
Hamburg
Frankfurt
1
1
Hamburg
HomeTeam
GuestTeam
Kiel
Munich
Frankfurt
Munich
Kiel
Hamburg
Frankfurt
Hamburg
TeamName
Coach
Kiel
Sven
Munich
Tim
Hamburg
Martin
Frankfurt
Kai
HomeTeam
GuestTeam
TeamName
Coach
Kiel
Munich
Kiel
Sven
Frankfurt
Munich
Frankfurt
Kai
Kiel
Hamburg
Kiel
Sven
Frankfurt
Hamburg
Frankfurt
Kai
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 39
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 40
7. Relational Algebra
Equi-Join – Example
Consider the relations MATCH and TEAM.
For MATCH ◃▹HomeTeam=TeamName TEAM, we have:
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?
HomeTeam
GuestTeam
Kiel
Munich
Frankfurt
Munich
Kiel
Hamburg
Frankfurt
Hamburg
TeamName
Coach
Kiel
Sven
Munich
Tim
Hamburg
Martin
Frankfurt
Kai
HomeTeam
GuestTeam
TeamName
Coach
Kiel
Munich
Kiel
Sven
Frankfurt
Munich
Frankfurt
Kai
Kiel
Hamburg
Kiel
Sven
Frankfurt
Hamburg
Frankfurt
Kai
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 41
7. Relational Algebra
Natural Join – Example
Still consider the relations MATCH and TEAM.
For MATCH ◃▹ TEAM, we have:
Note that, the attribute HomeTeam shared by TEAM and MATCH occurs only once in the result.
HomeTeam
GuestTeam
Kiel
Munich
Frankfurt
Munich
Kiel
Hamburg
Frankfurt
Hamburg
HomeTeam
Coach
Kiel
Sven
Munich
Tim
Hamburg
Martin
Frankfurt
Kai
HomeTeam
GuestTeam
Coach
Kiel
Munich
Sven
Frankfurt
Munich
Kai
Kiel
Hamburg
Sven
Frankfurt
Hamburg
Kai
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 42
7. Relational Algebra
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
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 43
7. Relational Algebra
Renaming
Renaming is used to rename either the relation name or the attribute names, or both.
Renaming is denoted as ρR′(A1,…,An)(R):renamingtherelationnametoR andtheattribute
names to A1,…,An,
ρR′(R):renamingtherelationnametoR andkeepingtheattribute
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.
′
′
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 44
7. Relational Algebra
7. Relational Algebra
Renaming – Example
Renaming – Exercise
Consider the relation FOOTBALL:
For ρSoccer (FOOTBALL), we have a relation SOCCER that has the same attributes and tuples as ones in FOOTBALL.
For ρ(HTeam,HScore,GScore,GTeam)(FOOTBALL), we have the relation below:
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016
Suppose that we have
HomeTeam
HomeScore
GuestScore
GuestTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
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
HTeam
HScore
GScore
GTeam
Kiel
1
3
Munich
Munich
0
0
Freiburg
Frankfurt
1
1
Hamburg
Kiel
1
3
Frankfurt
Exercise:
1 Who did enrol the course “Relational Databases”?
45 Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 46
7. Relational Algebra
7. Relational Algebra
Renaming – Exercise
Relational Operators 1
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:
1 Who did enrol the course “Relational Databases”? πStudentID,Name(σCName=‘Relational Databases’
(ρ(CourseNo,CName,Unit)(COURSE) ◃▹ ENROL))
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 47
…… …… ……
1
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 48
http://merrigrove.blogspot.com.au/2011/12/another-introduction-to-algebraic-data.html (with some changes)
7. Relational Algebra
RA Queries – Exercises (Self Join)
Given the following relation schema: STUDENT={StudentID, Name, DoB}
Query 1: Find pairs of students who have the same birthday. Show their names.
STUDENT
StudentID
Name
DoB
457
Lisa
18-Oct-1993
458
Mike
16-May-1990
459
Peter
18-Oct-1993
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 49
7. Relational Algebra
RA Queries – Exercises (Self Join)
Given the following relation schema: STUDENT={StudentID, Name, DoB}
Query 1: Find pairs of students who have the same birthday. Show their names.
πR1.Name,R2.Name(σR1.StudentID
SELECT DISTINCT * FROM R1 INNER JOIN R2 ON φ; (φ may only contain =)
Natural-Join: R1 ◃▹ R2 corresponds to
SELECT DISTINCT * FROM R1 NATURAL JOIN R2;
Outer joins are not considered in the traditional relational algebra, as well as aggregation.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 76
7. Relational Algebra
Summary
RA is a procedural query language defined in the relational model. An RA query itself suggests a procedure for constructing the result (i.e.,
implement the query).
RA is not used as a query language by users.
RA is used for the internal representation and processing of SQL queries in relational DBMSs, which is a basis of query optimisation techniques.
Thus, to understand how SQL queries are processed and how they can be optimised, we first need to understand relational algebra.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 77
7. Relational Algebra
Weekly Review
Some questions
What is the relational algebra?
Why is the relational algebra needed in relational databases?
What are the relational operators defined in the relational algebra?
What are the differences among Cartesian product, Theta join, Equi-join and natural join?
Why do we need renaming in the relational algebra?
How do relational algebra expressions correspond to SQL queries, and vice versa?
More exercises
Attend Lab 6 in Week 9, which will be about the relational algebra and prepare you for Assignment 3.
Comp2400/Comp6240 – Relational Databases, Semester 2, 2016 78