Introduction Relational Algebra Examples Conclusion
Relational Algebra (RA)
Week 7 – CSC 343
Michael Liut & Ilir Dema
Department of Mathematical and Computational Sciences University of Toronto Mississauga
March 4/5, 2021
Michael Liut & Ilir Dema University of Toronto: CSC 343 1 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
After today, you be able to:
1 Understand the differences between the core relational algebra operands and operators.
2 Understand the rules of precedence.
3 Differentiate between bag and set semantics.
4 Utilize expression trees to help formulate your RA solution.
5 Translate SQL to RA and RA to SQL.
Michael Liut & Ilir Dema University of Toronto: CSC 343 2 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
Relational Query Languages
Query Languages allow manipulation and retrieval of data from a database.
The relational model supports simple and powerful Query Languages, those which:
1 have a formal foundation built on logic; and
2 allow optimization.
Query Languages != Programming Languages
Query Languages are not intended for complex calculations. Query Languages support easy and efficient access to large data sets.
Michael Liut & Ilir Dema University of Toronto: CSC 343 3 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
Formal Relational Query Languages
There are two mathematical Query Languages that form the basis of SQL and for its implementation:
Relational Algebra Relational Calculus
is more operational. It is useful for representing execution plans.
is non-operational, it is declarative. It allows users to describe what they want, rather than how to compute it.
Michael Liut & Ilir Dema
University of Toronto: CSC 343 4 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
What is Algebra?
In general, it is a mathematical structure that is defined by the author. For our purposes, it is a system that consists of:
Operands – variables or values from which new values can be constructed.
Operators – symbols which denote procedures that construct new values from inputted/given values.
Michael Liut & Ilir Dema University of Toronto: CSC 343 5 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
What is Relational Algebra?
It is an algebra whose operands are relations or variables that represent relations.
The operators are designed to perform the most common operations that users need to do with relations in a database.
The result is an algebra that can be used as a Query Language for relations.
Michael Liut & Ilir Dema University of Toronto: CSC 343 6 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
What is Relational Algebra?
Operands: tables (relations) Operators:
Regular set operators (union, intersection, difference) Choose only rows you want (selection)
Choose only columns you want (projection)
Combine tables (join)
… andmore!
Michael Liut & Ilir Dema University of Toronto: CSC 343 7 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Base Operators
σ is Selection
Selection is used to specify a certain row.
σc(R) where c is a list of conditions involving the attribute(s) R.
π is Projection
Projection is used to specify a certain column.
πl(R) where l is a list of attributes involving the attribute(s) R.
x is Cartesian Product
Cartesian Product is the combination of two (or more) relations.
R := R1 x R2 where the tuples of R1 and tuples R2 are paired together to form R.
Michael Liut & Ilir Dema University of Toronto: CSC 343 8 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Base Operators
∪ is Union
Union is used to combine two relations into one.
Suppose a tuple t appears in R1 m times, and in R2 n times. Then in the union, t appears m + n times. R1 ̸= R2.
∩ is Intersection
Intersection is used to see what overlaps in two relations. Suppose a tuple t appears in R1 m times, and in R2 n times. Then in the union, t appears min(m, n) times.
− is Difference
Difference is basically subtraction, it is used to see what is left overinR1 whenR1−R2.
Suppose a tuple t appears in R1 m times, and in R2 n times. Then in the union, t appears max(0,m−n) times.
defined for union compatible relations
Michael Liut & Ilir Dema University of Toronto: CSC 343 9 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Extended Relational Algebra
◃▹ is Natural Join
Connects (aka joins) two relations by equating attributes of the same name and by projecting out one copy of each pair of equated attributes.
◃▹c is Theta Join
Where the condition c is:
1 a θ b, where a and b are attribute names; or
2 a θ x, where a is an attribute name and x is value.
θ here represents a binary relational operator belonging to
{≤, <, =, >, ≥}.
Connects (aka joins) two relations by equating attributes based on some condition
◃▹c is Equijoin iff c’s θ is the quality operator (i.e. =).
there are additional types of joins not included in here
Michael Liut & Ilir Dema University of Toronto: CSC 343 10 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Extended Relational Algebra
ρ does Renaming
R1 := ρR1(A1,…,An)(R2), where R1 becomes a new relation with
theattributesA1,…,An ofR2.
ρa/b(R), where b is an attribute of R and a is the renamed attribute name.
δ does Duplicate Elimination
This is used for duplicate elimination in bag semantics.
R1 := δ(R2) will result in R1 containing one copy of each tuple that appears in R2 one or more times.
Michael Liut & Ilir Dema University of Toronto: CSC 343 11 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Extended Relational Algebra
τ is the Sorting of tuples
R1 := τL(R2), where L is a list of R2’s attributes.
R1 is the sorted list of tuples of R2, based on the order specified in list L. Ties are broken arbitrarily.
Items are sorted in ascending order by default. This means if you are attempting to sort in descending order, you will denote the list the prefix −. e.g. R1 := τ−L(R2)
Fun Fact: τ is the only operator whose result is neither a set nor a bag. → Told you it would be fun! 🙂
Michael Liut & Ilir Dema University of Toronto: CSC 343 12 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Extended Relational Algebra
γ is Grouping and Aggregation.
The aggregation operations are: AVG, MIN, MAX, SUM, and COUNT.
R1 := γL(R2), where L is a list of individual grouping attributes or an aggregation operation of an attribute.
note: An arrow to a new attribute name would rename it. (e.g. AVG(salary) → pay)
Michael Liut & Ilir Dema University of Toronto: CSC 343 13 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
RA Rules of Precedence
1 [ σ, π, ρ ] (highest) 2 [x,◃▹]
3 [∩]
4 [ ∪, − ] (lowest)
Note: you may combine operators with parentheses and precedence rules.
Michael Liut & Ilir Dema University of Toronto: CSC 343 14 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Bag vs. Set Semantics
A bag (aka multiset) allows the repetition of objects. A set is a collection of distinct objects.
e.g. {1,2,1,3}isabag.
e.g. {1,2,3} is a bag and a set.
Michael Liut & Ilir Dema University of Toronto: CSC 343 15 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Bag vs. Set Semantics
Real RDBMSs treat relations as bags of tuples. SQL is a bag language.
Fun Fact: some operations, like projection, are more efficient on bags than sets.
Why bags?
This is primarily due to performance. The elimination of duplicates is often computationally expensive, as it requires sorting.
Michael Liut & Ilir Dema University of Toronto: CSC 343 16 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Bag Laws ! = Set Laws
Some algebraic laws that hold for sets also hold for bags, but not all of them do.
e.g. the commutative law for ∪ does hold for bags. i.e.R1∪R2 =R2∪R1
e.g. the idempotent law, in general, for ∪ does not hold for bags. i.e. R1 ∪R1 != R1
e.g. {1}∪{1} = {1,1} ! = {1}
Michael Liut & Ilir Dema University of Toronto: CSC 343 17 / 31
Introduction Relational Algebra Examples Conclusion
The Beginning
Union Compatibility
∪, ∩, and − are three operators defined as being union compatible relations.
i.e. they have two relations with the same set of attributes, and for each attribute, they have the same type (domain).
Michael Liut & Ilir Dema University of Toronto: CSC 343 18 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Selection
Recall: it selects the row which satisfies its condition.
Johnny′s Menu := σbar=“Johnny′s”(Sells)
Michael Liut & Ilir Dema University of Toronto: CSC 343 19 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Projection
The resulting schema (i.e. Price) contains exactly the same fields that are in the projection list, with the same names.
Prices := πbeer,price(Sells)
Michael Liut & Ilir Dema University of Toronto: CSC 343 20 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Extended Projection
R2 := πA+B→C, A→A1, A→A2(R1)
Michael Liut & Ilir Dema University of Toronto: CSC 343 21 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Cartesian Product
Michael Liut & Ilir Dema University of Toronto: CSC 343 22 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Union
Final Result
Michael Liut & Ilir Dema University of Toronto: CSC 343 23 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Intersection
Michael Liut & Ilir Dema University of Toronto: CSC 343 24 / 31
Introduction Relational Algebra Examples Conclusion
Base Operators Examples
Difference
Michael Liut & Ilir Dema University of Toronto: CSC 343 25 / 31
Introduction Relational Algebra Examples Conclusion
Extended Relational Algebra Examples
Natural Join
Michael Liut & Ilir Dema University of Toronto: CSC 343 26 / 31
Introduction Relational Algebra Examples Conclusion
Extended Relational Algebra Examples
Theta Join
In this
example, note that θ is =, therefore, this is also an equijoin.
Michael Liut & Ilir Dema University of Toronto: CSC 343 27 / 31
Introduction Relational Algebra Examples Conclusion
Extended Relational Algebra Examples
Renaming
Michael Liut & Ilir Dema University of Toronto: CSC 343 28 / 31
Introduction Relational Algebra Examples Conclusion
Expression Trees
Expression Trees
Leaves are operands – either variables standing for relations or particular, constant relations.
Interior nodes are operators – applied to their child(ren).
e.g. Using the relations Bars(name, addr) and Sells(bar, beer, price) find the names of all the bars that are either on “Maple St.” or sell “Bud” for less than $3.
Michael Liut & Ilir Dema University of Toronto: CSC 343 29 / 31
Introduction Relational Algebra Examples Conclusion
Expression Trees
Expression Trees
Michael Liut & Ilir Dema University of Toronto: CSC 343 30 / 31
Introduction Relational Algebra Examples Conclusion
Intended Learning Outcomes
Recall: Intended Learning Outcomes
1 Understand the differences between the core relational algebra operands and operators.
2 Understand the rules of precedence.
3 Differentiate between bag and set semantics.
4 Utilize expression trees to help formulate your RA solution.
5 Translate SQL to RA and RA to SQL.
Michael Liut & Ilir Dema University of Toronto: CSC 343 31 / 31