INFO20003 Database Systems
INFO20003 Database Systems 1© University of Melbourne 2018
INFO20003 Database Systems
Lecture 07
Relational Algebra
Semester 2 2018, Week 4
Dr Renata Borovica-Gajic
INFO20003 Database Systems 2© University of Melbourne 2018
What we have done so far
Modelling (ER)
create_tables.sql
Database
How do we manipulate with this data?
SQL:
• Language for data manipulation
• Allow to create/delete tables,
add/update/remove data, etc
Relational algebra:
• The theory behind SQL
• Makes sure that SQL produces
correct answers
• Inputs/outputs are relations
Introduced next time
Today
INFO20003 Database Systems 3© University of Melbourne 2018
Relational Algebra: 5 Basic Operations
1. Selection ( ): Selects a subset of rows from relation
(horizontal filtering).
2. Projection ( ): Retains only wanted columns from
relation (vertical filtering).
3. Cross-product (x): Allows us to combine two
relations.
4. Set-difference (–): Tuples in one relation, but not in
the other.
5. Union (): Tuples in one relation and/or in the other.
Each operation returns a relation, operations can be composed
INFO20003 Database Systems 4© University of Melbourne 2018
Coverage : Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection
• Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems 5© University of Melbourne 2018
bid bname color
101 Interlake blue
102 Interlake red
103 Clipper green
104 Marine red
Example Instances
sid sname rating age
22 dustin 7 45.0
31 lubber 8 55.5
58 rusty 10 35.0
sid sname rating age
28 yuppy 9 35.0
31 lubber 8 55.5
44 guppy 5 35.0
58 rusty 10 35.0
sid bid day
22 101 10/10/96
58 103 11/12/96
Reserves
(R1)
Sailors 1
(S1)
Sailors 2
(S2)
Boats
INFO20003 Database Systems 6© University of Melbourne 2018
Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection
• Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems 7© University of Melbourne 2018
• Retains only attributes that are in the projection list
• Schema of result:
–Only the fields in the projection list, with the same names
that they had in the input relation
• Projection operator has to eliminate duplicates
–How do they arise? Why remove them?
–Note: real systems typically don’t do duplicate elimination
unless the user explicitly asks for it
Projection
INFO20003 Database Systems 8© University of Melbourne 2018
sname rating
yuppy 9
lubber 8
guppy 5
rusty 10
)2(
,
S
ratingsname
age
35.0
55.5
sid sname rating age
28 yuppy 9 35.0
31 lubber 8 55.5
44 guppy 5 35.0
58 rusty 10 35.0
)2(Sage
S2
Projection Examples
Removed duplicates
age S( )2
sname rating
S
,
( )2
1. Find ages of sailors :
2. Find names and rating of sailors :
INFO20003 Database Systems 9© University of Melbourne 2018
sid sname rating age
28 yuppy 9 35.0
58 rusty 10 35.0
Selection ()
rating
S
8
2( )
• Selects rows that satisfy a selection condition
• Result is a relation. Schema of the result is same as that of the
input relation.
• Do we need to do duplicate elimination?
• Example:
Find sailors whose rating is above 8
sid sname rating age
28 yuppy 9 35.0
31 lubber 8 55.5
44 guppy 5 35.0
58 rusty 10 35.0
rating
S
8
2( )
INFO20003 Database Systems 10© University of Melbourne 2018
• Conditions are standard arithmetic expressions
>, <, >=, <=, =, != • Conditions are combined with AND/OR clauses And: Λ Or: V • Example: Find sailors whose rating is above 8 and who are younger than 50 𝜎 𝑟𝑎𝑡𝑖𝑛𝑔>8Λ 𝑎𝑔𝑒<50 (𝑆2) Conditions INFO20003 Database Systems 11© University of Melbourne 2018 Selection & Projection sname rating yuppy 9 rusty 10 sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 • Operations can be combined • Select rows that satisfy selection condition & retain only certain attributes (columns) • Example: Find names and rating of sailors whose rating is above 8 sname rating rating S , ( ( )) 8 2 INFO20003 Database Systems 12© University of Melbourne 2018 Relational Algebra • Selection & Projection • Union, Set Difference & Intersection • Cross product & Joins • Examples Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems INFO20003 Database Systems 13© University of Melbourne 2018 Union and Set-Difference • Union: Combines both relations together • Set-difference: Retains rows of one relation that do not appear in the other relation • These operations take two input relations, which must be union-compatible: –Same number of fields –Corresponding fields have the same type INFO20003 Database Systems 14© University of Melbourne 2018 Union sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 44 guppy 5 35.0 28 yuppy 9 35.0 S S1 2 sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 S1 S2 Duplicates are removed INFO20003 Database Systems 15© University of Melbourne 2018 Set Difference sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 S1 S2 sid sname rating age 22 dustin 7 45.0 S S1 2 INFO20003 Database Systems 16© University of Melbourne 2018 Set Difference sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 S1 S2 sid sname rating age 22 dustin 7 45.0 S S1 2 S2 – S1 sid sname rating age 28 yuppy 9 35.0 44 guppy 5 35.0 Set-difference is not symmetrical INFO20003 Database Systems 17© University of Melbourne 2018 Compound Operator: Intersection • In addition to the 5 basic operators, there are several additional “Compound Operators” –These add no computational power to the language, but are useful shorthands –Can be expressed solely with the basic operations • Intersection retains rows that appear in both relations • Intersection takes two input relations, which must be union-compatible • Q: How to express it using basic operators? R S = R (R S) INFO20003 Database Systems 18© University of Melbourne 2018 Intersection sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid sname rating age 28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0 S1 S2 sid sname rating age 31 lubber 8 55.5 58 rusty 10 35.0 21 SS Example: Find sailors who appear in both relations S1 and S2 INFO20003 Database Systems 19© University of Melbourne 2018 Relational Algebra • Selection & Projection • Union, Set Difference & Intersection • Cross product & Joins • Examples Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems INFO20003 Database Systems 20© University of Melbourne 2018 Cross Product • Cross product combines two relations: –Each row of one input is merged with each row from another input –Output is a new relation with all attributes of both inputs –X is used to denote cross-product • Example: S1 x R1 –Each row of S1 paired with each row of R1 • Question: How many rows are in the result? –A: card(S1)*card(R1) INFO20003 Database Systems 21© University of Melbourne 2018 Cross Product Example (sid) sname rating age (sid) bid day 22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96 sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid bid day 22 101 10/10/96 58 103 11/12/96 R1 S1 S1 X R1 = INFO20003 Database Systems 22© University of Melbourne 2018 Cross Product: Conflicting names • Result schema has one field per field of S1 and R1, with field names “inherited” if possible. –May have a naming conflict, i.e. both S1 and R1 have a field with the same name (e.g. sid). –In this case, can use the renaming operator: ( ( , ), )C sid sid S R1 1 5 2 1 1 sid1 sname rating age sid2 bid day 22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96 Result relation C INFO20003 Database Systems 23© University of Melbourne 2018 Compound Operator: Join • Joins are compound operators involving cross product, selection, and (sometimes) projection. • Most common type of join is a natural join (often just called join). R S conceptually is a cross product that matches rows where attributes that appear in both relations have equal values (and we omit duplicate attributes). • To perform a natural join a DBMS can: 1. Compute R X S 2. Select rows where attributes that appear in both relations have equal values 3. Project all unique attributes and one copy of each of the common ones. INFO20003 Database Systems 24© University of Melbourne 2018 Natural Join Example sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 sid bid day 22 101 10/10/96 58 103 11/12/96 R1S1 S1 R1 = sid sname rating age bid day 22 dustin 7 45.0 101 10/10/96 58 rusty 10 35.0 103 11/12/96 Example: Find all sailors (from relation S1) who have reserved a boat INFO20003 Database Systems 25© University of Melbourne 2018 Natural Join Example S1 X R1 = (sid) sname rating age (sid) bid day 22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96 1 INFO20003 Database Systems 26© University of Melbourne 2018 S1 X R1 = (sid) sname rating age (sid) bid day 22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96 1 2 Natural Join Example INFO20003 Database Systems 27© University of Melbourne 2018 S1 X R1 = sid sname rating age bid day 22 dustin 7 45.0 101 10/10/96 58 rusty 10 35.0 103 11/12/96 (sid) sname rating age (sid) bid day 22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96 S1 R1= 1 2 3 Natural Join Example INFO20003 Database Systems 28© University of Melbourne 2018 Other Types of Joins • Condition Join (or theta-join) is a cross product with a condition. –Result schema is the same as that of cross-product • Equi-Join is a special case of condition join, where condition c contains only equalities (e.g. S1.sid = R1.sid) –Is this then a natural join? What is different? R c S c R S ( ) (sid) sname rating age (sid) bid day 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 58 103 11/12/96 11 .1.1 RS sidRsidS INFO20003 Database Systems 29© University of Melbourne 2018 Relational Algebra • Selection & Projection • Union, Set Difference & Intersection • Cross product & Joins • Examples Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems INFO20003 Database Systems 30© University of Melbourne 2018 Let’s try it… sid sname rating age 22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 bid bname color 101 Interlake Blue 102 Interlake Red 103 Clipper Green 104 Marine Red sid bid day 22 101 10/10/96 58 103 11/12/96 Reserves SailorsBoats INFO20003 Database Systems 31© University of Melbourne 2018 Find names of sailors who have reserved boat #103 Solution 1: ))Re(( 12 Sailorsserves bidsname Solution 2: ))Re( 12 ( Sailorsserves bidsname Question 1 103 103 INFO20003 Database Systems 32© University of Melbourne 2018 (𝜋𝑠𝑛𝑎𝑚𝑒𝑆𝑎𝑖𝑙𝑜𝑟𝑠) 𝑅𝑒𝑠𝑒𝑟𝑣𝑒𝑠 (𝜎𝑐𝑜𝑙𝑜𝑟=′𝑏𝑙𝑢𝑒′𝐵𝑜𝑎𝑡𝑠) 𝜋𝑠𝑛𝑎𝑚𝑒(𝜎𝑐𝑜𝑙𝑜𝑟=′𝑏𝑙𝑢𝑒′(𝐵𝑜𝑎𝑡𝑠 𝑅𝑒𝑠𝑒𝑟𝑣𝑒𝑠 𝑆𝑎𝑖𝑙𝑜𝑟𝑠)) 𝜋𝑠𝑛𝑎𝑚𝑒( 𝜎𝑐𝑜𝑙𝑜𝑟=′𝑏𝑙𝑢𝑒′𝐵𝑜𝑎𝑡𝑠 𝑅𝑒𝑠𝑒𝑟𝑣𝑒𝑠 𝑆𝑎𝑖𝑙𝑜𝑟𝑠)A: B: C: INFO20003 Database Systems 34© University of Melbourne 2018 Question 3 Find all pairs of sailors in which the older sailor has a lower rating INFO20003 Database Systems 44© University of Melbourne 2018 What’s Examinable - - • Relational Algebra Operations: Selection, Projection, Union, Set, Difference, Intersection, JOINS… • Draw different queries with Relational Algebra operations INFO20003 Database Systems 45© University of Melbourne 2018 Next Lecture • Introducing SQL