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.
Copyright By PowCoder代写 加微信 powcoder
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
0551-999-210 0569-988-112 0531-987-654 0566-123-456
Jon Night
Snow expression 𝜋𝜋FirstName, LastName (Person) will result in:
Jon Night
Snow : σ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)
0551-999-210 0566-123-456
Jon Snow Night can combine the two operations in one expression as:
𝜋𝜋FirstName, LastName (𝜎𝜎FirstName = ‘Jon’ ∨ LastName = ‘King’ (Person))
FirstName LastName
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.
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:
Jon Night
Snow Name
Cersei Night
Lannister Guys
Jon Daenerys
Snow Targaryen
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
Jon Night
Snow Name
Night Daenerys
King Targaryen
RandomCombo1 – RandomCombo2 will result in:
Snow Lannister
FirstName LastName Email
Jon Snow Night King
Combine the rows from two relations: Cross Product (×)
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:
Weapon Metal
Sword Dagger
Valyrian steel Dragon glass
INFO20003 Tutorial – Week 5 Solutions
Person × Weapon will result in:
FirstName LastName Email Weapon Metal
Jon Snow Jon Snow Night King Night King
Sword Dagger Sword Dagger
Valyrian steel Dragon glass Valyrian steel 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
Jon Night
Snow Name
Night Daenerys
King Targaryen
RandomCombo1 ∩ RandomCombo2 will result in:
Daenerys Night
Targaryen 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:
FirstName LastName Email
Snow Targaryen Lannister King
WeaponOwner
Weapon LastName Metal
Jon Night
Sword Dagger
Dagger Sword Dagger Sword
Sword Dagger
Sword Dagger
Snow Valyrian steel
Lannister Dragon glass
LastName Metal
Person × Weapon (intermediate result): FirstName LastName Email
Jon Daenerys Tyrion Night Night
Snow Lannister
King steel Dragon glass Valyrian steel Dragon glass Valyrian steel Dragon glass Valyrian steel Dragon glass
Valyrian steel Dragon glass
Person ⋈ Weapon will result in: FirstName LastName Email
Lannister Snow Lannister Snow
Snow Lannister
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
FirstName LastName Email
WeaponOwner
Sword Snow Dagger Lannister
Valyrian steel Dragon glass
Person × Weapon (intermediate result): FirstName LastName Email
Weapon Name
Valyrian steel Dragon glass Valyrian steel Dragon glass Valyrian steel Dragon glass Valyrian steel Dragon glass
Valyrian steel Dragon glass
Jon Daenerys Tyrion Night Night
Snow Lannister
King Sword Dagger Sword
Sword Dagger
Lannister Snow Lannister Snow
Person ⋈LastName = Name Weapon will result in: FirstName LastName Email
Weapon Name
Sword Snow Dagger Lannister
INFO20003 Tutorial – Week 5 Solutions
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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com