1.
I. Relational algebra (RA) review – 15 mins
II. Relational algebra and SQL statements – 35 mins
Exercises:
NOTE for students: This is a brief summary of some of the concepts taught in lecture 7 and 8. The lectures contain detailed content related to these and many more concepts. These notes should be considered quick revision instead of a sole resource for the course material.
RA review
Algebra, in general consists of operators and atomic operands. Relational algebra is a procedural query language for relational model and has powerful ways to provide theoretical foundation for relational databases and SQL. It consists of a collection of operators, which take instance(s) of a relation as operand(s), and returns a relation instance as an output. An operator can be either unary or binary; a unary operator is applied on a single relation whereas a binary operator requires two relations to produce an output. The procedural nature of the algebra allows us to think of an algebra expression as a recipe or a plan for evaluating a query and to represent query evaluation plans.
• Fundamental operations
Objectives:
This tutorial will cover:
INFO20003 Tutorial – Week 5 Solutions
(Tutorial: Relational algebra and translation to SQL)
There are five basic operators of Relational Algebra that can form other compound operators (described in the next section). These include Selection, Projection and set operations such as cross product, set difference and set union.
o Removal operators: Selection (𝜎𝜎) and Projection (𝜋𝜋)
These operators remove components from a relation (NOT RELATIONSHIP), selection
removes rows and projection removes some columns.
Projection: πA1, A2, …, An (R) where R is a relation and A1, …, An are attributes that are ‘projected’. This expression creates a new relation with a subset of attributes. All the tuples are included in the new relation, but only the attributes A1, …, An are kept. For example, the table ‘Person’ below contains data about some “random” people:
INFO20003 Tutorial – Week 5 Solutions 1
FirstName
LastName
Phone
Email
Jon
Snow
0551-999-210
knowsnothing@hotmail.com
Daenerys
Targaryen
0569-988-112
bendtheknee@gmail.com
Jamie
Lannister
0531-987-654
handsfree@gmail.com
Night
King
0566-123-456
killerstare@gmail.com
The expression 𝜋𝜋FirstName, LastName (Person) will result in:
FirstName
LastName
Jon
Snow
Daenerys
Targaryen
Jamie
Lannister
Night
King
Selection: σC (R) where R is a relation and C is a condition used to filter rows. This expression creates a new relation consisting of those rows for which C is true. For the same Person table above the following equation will produce the relation with the same schema as Person:
𝜎𝜎FirstName = ‘Jon’ ∨ LastName = ‘King’ (Person)
FirstName
LastName
Phone
Email
Jon
Snow
0551-999-210
knowsnothing@hotmail.com
Night
King
0566-123-456
killerstare@gmail.com
We can combine the two operations in one expression as:
𝜋𝜋FirstName, LastName (𝜎𝜎FirstName = ‘Jon’ ∨ LastName = ‘King’ (Person))
o Set operators: Set-difference (–) and Union (∪)
The three most common operations on set are unions, difference and intersection (explained in next section). In this section, we will describe Union and Difference operations. Every set operation has constraint that both relations such as R and S must have the same attributes with the same domains. In addition, for clarity the ordering of attributes should be kept consistent while performing set operations.
FirstName
LastName
Jon
Snow
Night
King
INFO20003 Tutorial – Week 5 Solutions 2
• Union: R ∪ S where R and S are two relations. The result will be every row which is either in R or S. Example:
GoodGuys BadGuys
GoodGuys ∪ BadGuys will result in:
• Difference: R – S where R and S are two relations. The result will be every row which is in R but not in S. Example:
RandomCombo1 RandomCombo2
RandomCombo1 – RandomCombo2 will result in:
o Combine the rows from two relations: Cross Product (×)
FirstName
LastName
Jon
Snow
Daenerys
Targaryen
FirstName
LastName
Cersei
Lannister
Night
King
FirstName
LastName
Jon
Snow
Daenerys
Targaryen
Cersei
Lannister
Night
King
FirstName
LastName
Jon
Snow
Daenerys
Targaryen
Jamie
Lannister
Night
King
FirstName
LastName
Night
King
Arya
Stark
Cersei
Lannister
Daenerys
Targaryen
FirstName
LastName
Jon
Snow
Jamie
Lannister
Cross Product: R × S where R and S are two relations. Each row of R pairs with each row of S. The resulting schema has all the attributes from both relations. If some attributes have same name, rename them by using renaming operator which we will study later. Example:
Person Weapon
FirstName
LastName
Email
Jon
Snow
knowsnothing@hotmail.com
Night
King
killerstare@gmail.com
Weapon
Metal
Sword
Valyrian steel
Dagger
Dragon glass
INFO20003 Tutorial – Week 5 Solutions
3
Person × Weapon will result in:
FirstName
LastName
Email
Weapon
Metal
Jon
Snow
knowsnothing@hotmail.com
Sword
Valyrian steel
Jon
Snow
knowsnothing@hotmail.com
Dagger
Dragon glass
Night
King
killerstare@gmail.com
Sword
Valyrian steel
Night
King
killerstare@gmail.com
Dagger
Dragon glass
• Compound operations
These operators are not adding any computational power to the language but are useful shorthand.
All these operators can be expressed using the basic operators.
o Intersection(∩)
As intersection is also a set operator. The two relations participating in this operation should be union compatible, i.e. both should have the same number of attributes and corresponding attributes must have the same data type. Intersection can be expressed using basic operators as:
R ∩ S = R − (R − S)
where R and S are two relations. The result is a relation containing all the tuples which are
present in both relations. Example:
RandomCombo1 RandomCombo2
RandomCombo1 ∩ RandomCombo2 will result in:
FirstName
LastName
Jon
Snow
Daenerys
Targaryen
Jamie
Lannister
Night
King
FirstName
LastName
Night
King
Arya
Stark
Cersei
Lannister
Daenerys
Targaryen
FirstName
LastName
Daenerys
Targaryen
Night
King
o NaturalJoin(⨝)
The natural join (R ⋈ S) identifies attributes common to each relation R and S; it creates a new relation, pairing each tuple from R and S where the common attributes are equal. Joins in general are compound operators involving cross product, selection and occasionally projection. A natural join can be broken down into following steps:
INFO20003 Tutorial – Week 5 Solutions 4
Compute R × S
Select rows where attributes that appear in both relations have equal values. Project all unique attributes and one copy of each of the common ones.
For example, here is a natural join between the Person and WeaponOwner relations: Person WeaponOwner
Person × Weapon (intermediate result):
Person ⋈ Weapon will result in:
FirstName
LastName
Email
Jon
Snow
knowsnothing@hotmail.com
Daenerys
Targaryen
bendtheknee@gmail.com
Tyrion
Lannister
idrinkandiknow@gmail.com
Night
King
killerstare@gmail.com
Weapon
LastName
Metal
Sword
Snow
Valyrian steel
Dagger
Lannister
Dragon glass
FirstName
LastName
Email
Weapon
LastName
Metal
Jon
Snow
knowsnothing@hotmail.com
Sword
Snow
Valyrian steel
Jon
Snow
knowsnothing@hotmail.com
Dagger
Lannister
Dragon glass
Daenerys
Targaryen
bendtheknee@gmail.com
Sword
Snow
Valyrian steel
Daenerys
Targaryen
bendtheknee@gmail.com
Dagger
Lannister
Dragon glass
Tyrion
Lannister
idrinkandiknow@gmail.com
Sword
Snow
Valyrian steel
Tyrion
Lannister
idrinkandiknow@gmail.com
Dagger
Lannister
Dragon glass
Night
King
killerstare@gmail.com
Sword
Snow
Valyrian steel
Night
King
killerstare@gmail.com
Dagger
Lannister
Dragon glass
FirstName
LastName
Email
Weapon
Metal
Jon
Snow
knowsnothing@hotmail.com
Sword
Valyrian steel
Tyrion
Lannister
idrinkandiknow@gmail.com
Dagger
Dragon glass
o Condition Join (Theta/Inner Join)
R ⨝C S joins rows from relation R and S such that the Boolean condition C is true. Historically C was designated with a “theta”, hence the name theta-join. Most commonly C is of the type A = B, making the join an “equi-join”. The condition join can be written using the basic operators as below:
𝑅𝑅⋈𝐶𝐶 𝑆𝑆=𝜎𝜎𝐶𝐶(𝑅𝑅×𝑆𝑆)
INFO20003 Tutorial – Week 5 Solutions 5
Example:
Person WeaponOwner
Person × Weapon (intermediate result):
Person ⋈LastName = Name Weapon will result in:
FirstName
LastName
Email
Jon
Snow
knowsnothing@hotmail.com
Daenerys
Targaryen
bendtheknee@gmail.com
Tyrion
Lannister
idrinkandiknow@gmail.com
Night
King
killerstare@gmail.com
Weapon
Name
Metal
Sword
Snow
Valyrian steel
Dagger
Lannister
Dragon glass
FirstName
LastName
Email
Weapon
Name
Metal
Jon
Snow
knowsnothing@hotmail.com
Sword
Snow
Valyrian steel
Jon
Snow
knowsnothing@hotmail.com
Dagger
Lannister
Dragon glass
Daenerys
Targaryen
bendtheknee@gmail.com
Sword
Snow
Valyrian steel
Daenerys
Targaryen
bendtheknee@gmail.com
Dagger
Lannister
Dragon glass
Tyrion
Lannister
idrinkandiknow@gmail.com
Sword
Snow
Valyrian steel
Tyrion
Lannister
idrinkandiknow@gmail.com
Dagger
Lannister
Dragon glass
Night
King
killerstare@gmail.com
Sword
Snow
Valyrian steel
Night
King
killerstare@gmail.com
Dagger
Lannister
Dragon glass
FirstName
LastName
Email
Weapon
Name
Metal
Jon
Snow
knowsnothing@hotmail.com
Sword
Snow
Valyrian steel
Tyrion
Lannister
idrinkandiknow@gmail.com
Dagger
Lannister
Dragon glass
INFO20003 Tutorial – Week 5 Solutions
6
2. Consider the following schema:
Solve the following problems using relational algebra (RA) and translate to SQL statements: a. Find the names of all employees.
Relational Algebra: 𝜋𝜋EmployeeName (Employee) SQL: SELECT EmployeeName
FROM Employee;
b. Find the names of all employees in department number 1.
Relational Algebra: 𝜋𝜋EmployeeName (𝜎𝜎DepartmentID = 1 (Employee))
SQL: SELECT EmployeeName FROM Employee
WHERE DepartmentID = 1; c. List the names of green items of type C.
Relational Algebra: 𝜋𝜋ItemName (𝜎𝜎ItemColour = ‘Green’ ∧ ItemType = ‘C’ (Item))
SQL: SELECT ItemName FROM Item
WHERE ItemType = ‘C’ AND ItemColour = ‘Green’;
INFO20003 Tutorial – Week 5 Solutions 7
d. Find the items sold by the departments on the second floor (only show ItemID).
Relational Algebra: 𝜋𝜋ItemID (𝜎𝜎DepartmentFloor = 2 (Sale ⨝ Department))
SQL: SELECT DISTINCT ItemID
FROM Sale NATURAL JOIN Department WHERE DepartmentFloor = 2;
SQL: SELECT ItemName
FROM Item NATURAL JOIN Sale NATURAL JOIN Department WHERE DepartmentName = ‘Recreation’
AND ItemColour = ‘Brown’;
f. Find the employees whose salary is less than half that of their managers.
e. Find the names of brown items sold by the Recreation department.
Relational Algebra: 𝜋𝜋ItemName (𝜎𝜎DepartmentName = ‘Recreation’ ∧ ItemColour = ‘Brown’ (Item ⨝ Sale ⨝ Department))
Relational Algebra: Note: The RA notation for unary joins is not agreed upon Here are two examples using the rename (𝜌𝜌) operator:
𝜌𝜌𝜌𝜌
(Emp(EmployeeName → EmpName, EmployeeSalary → EmpSalary, BossID → EmpBossID), Employee) 𝜌𝜌(Boss(EmployeeID → BossEmployeeID,
𝜋𝜋EmpName (𝜎𝜎EmpSalary < (BossSalary / 2) (Emp ⋈EmpBossID = BossEmployeeID Boss))
EmployeeSalary → BossSalary), Employee)
(Boss(BossID → BossBossId,
EmployeeID → BossID, Salary → BossSalary, Name → BossName), Employee)
𝜋𝜋EmployeeName (𝜎𝜎EmployeeSalary < (BossSalary / 2) (Employee ⋈ Boss))
Emp ≔ Employee
Boss ≔ Employee
𝜋𝜋Emp.EmployeeName (𝜎𝜎Emp.EmployeeSalary < (Boss.EmployeeSalary / 2) (
Or you could use an SQL-like notation:
Emp ⋈Emp.BossID = Boss.EmployeeID Boss))
SQL: SELECT Emp.EmployeeName FROM Employee AS Emp
INNER JOIN Employee AS Boss
ON Emp.BossID = Boss.EmployeeID
WHERE Emp.EmployeeSalary < (Boss.EmployeeSalary / 2);
INFO20003 Tutorial – Week 5 Solutions 8