INFO20003 Database Systems
Dr Renata Borovica-Gajic
Lecture 07 Relational Algebra
Week 4
1
INFO20003 Database Systems
© University of Melbourne
What we have done so far
Modelling (ER)
create_tables.sql
Database
How do we manipulate with relations?
SQL:
• •
Language for data manipulation Allow to create/delete tables, add/update/remove data, etc
Introduced next time
Relational algebra:
• The theory behind SQL
• Makes sure that SQL produces
correct answers
• Inputs/outputs are relations
Today
INFO20003 Database Systems
© University of Melbourne
2
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
© University of Melbourne
3
Coverage : Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection • Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems
© University of Melbourne
4
Example Instances
sid
bid
day
22 58
101 103
10/10/96 11/12/96
Boats
Reserves (R1)
Sailors 1 (S1)
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
bid
bname
color
101
102
103
104
Interlake Interlake Clipper Marine
blue red green red
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
Sailors 2 (S2)
INFO20003 Database Systems
© University of Melbourne
5
Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection • Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems
© University of Melbourne
6
Projection
• 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
INFO20003 Database Systems
© University of Melbourne
7
Projection Examples
1. Find ages of sailors :
2. Find names and rating of sailors :
(S2)
age (S2)
sname,rating
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
sname
rating
yuppy
lubber guppy rusty
9
8 5 10
S2
sname,rating(S2)
age
35.0 55.5
Removed duplicates
age(S2)
INFO20003 Database Systems
© University of Melbourne
8
Selection ()
• Selects rows that satisfy 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 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
sid
sname
rating
age
28 58
yuppy rusty
9 10
35.0 35.0
(S2) rating 8
(S2) rating 8
INFO20003 Database Systems
© University of Melbourne
9
Conditions
• 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)
INFO20003 Database Systems
© University of Melbourne
10
Selection & Projection
• 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
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
sname
rating
yuppy rusty
9 10
( (S2)) sname,rating rating 8
INFO20003 Database Systems
© University of Melbourne
11
Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection • Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems
© University of Melbourne
12
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
© University of Melbourne
13
Union
sid
sname
rating
age
22 31 58 44 28
dustin lubber rusty guppy yuppy
7 8 10 5 9
45.0 55.5 35.0 35.0 35.0
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
S1
S1S2 Duplicates are removed
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
S2
INFO20003 Database Systems
© University of Melbourne
14
Set Difference
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
sid
sname
rating
age
22
dustin
7
45.0
S1
S1− S2
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
S2
INFO20003 Database Systems
© University of Melbourne
15
Set Difference
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
sid
sname
rating
age
22
dustin
7
45.0
S1
S1− S2
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
sid
sname
rating
age
28 44
yuppy guppy
9 5
35.0 35.0
S2
S2 – S1 Set-difference is not symmetrical
INFO20003 Database Systems
© University of Melbourne
16
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
© University of Melbourne
17
Intersection
Example:
Find sailors who appear in both relations S1 and S2
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
sid
sname
rating
age
31 58
lubber rusty
8 10
55.5 35.0
S1
S1S2
sid
sname
rating
age
28 31 44 58
yuppy lubber guppy rusty
9 8 5 10
35.0 55.5 35.0 35.0
S2
INFO20003 Database Systems
© University of Melbourne
18
Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection • Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems
© University of Melbourne
19
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
© University of Melbourne
20
Cross Product Example
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
sid
bid
day
22 58
101 103
10/10/96 11/12/96
S1 S1 X R1 =
(sid)
22
22
31
31
58
58
sname
dustin dustin lubber lubber rusty rusty
rating
7 7 8 8 10 10
age
45.0 45.0 55.5 55.5 35.0 35.0
(sid)
22
58
22
58
22
58
R1
bid
day
101
103
101
103
101
103
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
21
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(1→sid1,5→sid2), S1R1) Result relation name
C
sid1
22
22
31
31
58
58
sname
dustin dustin lubber lubber rusty rusty
rating
7 7 8 8 10 10
age
45.0 45.0 55.5 55.5 35.0 35.0
sid2
22
58
22
58
22
58
bid
day
101
103
101
103
101
103
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
22
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 obtain cross product a DBMS must:
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
© University of Melbourne
23
Natural Join Example
Example:
Find all sailors (from relation S1) who have reserved a boat
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
sid
bid
day
22 58
101 103
10/10/96 11/12/96
S1 R1 S1 R1 =
sid
sname
rating
age
bid
day
22 58
dustin rusty
7 10
45.0 35.0
101 103
10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
24
Natural Join Example
(sid)
sname
rating
age
(sid)
bid
day
22
22
31
31
58
58
dustin dustin lubber lubber rusty rusty
7 7 8 8 10 10
45.0 45.0 55.5 55.5 35.0 35.0
22
58
22
58
22
58
101
103
101
103
101
103
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
1
S1 X R1 =
INFO20003 Database Systems
© University of Melbourne
25
Natural Join Example
(sid)
sname
rating
age
(sid)
bid
day
22
22
31
31
58
58
dustin
7
45.0
22
101
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
rusty
10
35.0
58
103
1
S1 X R1 =
dustin
7 45.0 8 55.5 8 55.5 10 35.0
58 103 22 101 58 103 22 101
2
lubber lubber
rusty
INFO20003 Database Systems
© University of Melbourne
26
Natural Join Example
(sid)
sname
rating
age
(sid)
bid
day
22
22
31
31
58
58
dustin
7
45.0
22
101
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
rusty
10
35.0
58
103
1
S1 X R1 =
dustin
7 45.0 8 55.5 8 55.5 10 35.0
58 103 22 101 58 103 22 101
2
lubber lubber
rusty
3
sid
sname
rating
age
bid
day
22 58
dustin rusty
7 10
45.0 35.0
101 103
10/10/96 11/12/96
S1 R1=
INFO20003 Database Systems
© University of Melbourne
27
Other Types of Joins
• Condition Join (or theta-join) is a cross product with a
condition.
R c S = c ( R S )
(sid)
sname
rating
age
(sid)
bid
day
22 31
dustin lubber
7 8
45.0 55.5
58 58
103 103
11/12/96 11/12/96
S1 S1.sid R1.sid R1
–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?
INFO20003 Database Systems
© University of Melbourne
28
Relational Algebra
• Selection & Projection
• Union, Set Difference & Intersection • Cross product & Joins
• Examples
Readings: Chapter 4, Ramakrishnan & Gehrke, Database Systems
INFO20003 Database Systems
© University of Melbourne
29
Let’s try it...
Boats Sailors
bid
bname
color
101
102
103
104
Interlake Interlake Clipper Marine
Blue Red Green Red
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
Reserves
sid
bid
day
22 58
101 103
10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
30
Question
Find names of sailors who have reserved boat #103
Boats
Sailors
Reserves
bid
bname
color
101
102
103
104
Interlake Interlake Clipper Marine
Blue Red Green Red
sid
bid
day
22 58
101 103
10/10/96 11/12/96
sid
sname
rating
age
22
31 58
dustin
lubber rusty
7
8 10
45.0
55.5 35.0
Solution 1: Solution 2:
(( sname
( sname
Reserves) Sailors) 103
bid =12
(Reserves Sailors))
bid=12
103
INFO20003 Database Systems
© University of Melbourne
31
Question
Find all pairs of sailors in which the older sailor has a lower rating
INFO20003 Database Systems
© University of Melbourne
34
What’s Examinable
• Relational Algebra Operations: Selection, Projection, Union, Set, Difference, Intersection, JOINS...
• Draw different queries with Relational Algebra operations
INFO20003 Database Systems - -
© University of Melbourne
44
Next Lecture
• Introducing SQL
INFO20003 Database Systems
© University of Melbourne
45