INFO20003 Database Systems
Dr Renata Borovica-Gajic
Lecture 07 Relational Algebra
INFO20003 Database Systems
Copyright By PowCoder代写 加微信 powcoder
© University of Melbourne
What we have done so far
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
Modelling (ER)
create_tables.sql
How do we manipulate with relations?
INFO20003 Database Systems
© University of Melbourne
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
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
Example Instances
Reserves (R1)
Sailors 1 (S1)
22 101 10/10/96 58 103 11/12/96
101 Interlake blue 102 Interlake red 103 Clipper green 104 Marine red
31 lubber 58 rusty
28 yuppy 31 lubber 44 guppy 58 rusty
8 55.5 10 35.0
9 35.0 8 55.5 5 35.0 10 35.0
Sailors 2 (S2)
INFO20003 Database Systems
© University of Melbourne
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
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
Projection Examples
1. Find ages of sailors :
2. Find names and rating of sailors :
age (S2)
sname,rating
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
lubber 8 guppy 5
rusty sname,rating
Removed duplicates
INFO20003 Database Systems
© University of Melbourne
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
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
yuppy rusty
(S2) rating 8
(S2) rating 8
INFO20003 Database Systems
© University of Melbourne
Conditions
• Conditions are standard arithmetic expressions
>, <, >=, <=, =, !=
• Conditions are combined with AND/OR clauses And: Λ
• Example:
Find sailors whose rating is above 8 and who are younger than 50
𝜎𝑟𝑎𝑡𝑖𝑛𝑔>8 Λ 𝑎𝑔𝑒<50 (𝑆2)
INFO20003 Database Systems
© University of Melbourne
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
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
yuppy rusty
( (S2)) sname,rating rating 8
INFO20003 Database Systems
© University of Melbourne
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
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
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
lubber rusty
S1S2 Duplicates are removed
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
INFO20003 Database Systems
© University of Melbourne
Set Difference
lubber rusty
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
INFO20003 Database Systems
© University of Melbourne
Set Difference
lubber rusty
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
yuppy guppy
S2 – S1 Set-difference is not symmetrical
INFO20003 Database Systems
© University of Melbourne
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
Intersection
Find sailors who appear in both relations S1 and S2
lubber rusty
lubber rusty
28 31 44 58
yuppy lubber guppy rusty
35.0 55.5 35.0 35.0
INFO20003 Database Systems
© University of Melbourne
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
Cross Product
• Cross product combines two relations:
–Each row of one input is merged with each row from another
–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
Cross Product Example
lubber rusty
10/10/96 11/12/96
S1 S1 X R1 =
dustin dustin lubber lubber rusty rusty
7 7 8 8 10 10
45.0 45.0 55.5 55.5 35.0 35.0
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
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
dustin dustin lubber lubber rusty rusty
7 7 8 8 10 10
45.0 45.0 55.5 55.5 35.0 35.0
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
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
Natural Join Example
Find all sailors (from relation S1) who have reserved a boat
lubber rusty
10/10/96 11/12/96
S1 R1 S1 R1 =
dustin rusty
10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
Natural Join Example
dustin dustin lubber lubber rusty rusty
7 7 8 8 10 10
45.0 45.0 55.5 55.5 35.0 35.0
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
Natural Join Example
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
7 45.0 8 55.5 8 55.5 10 35.0
58 103 22 101 58 103 22 101
lubber lubber
INFO20003 Database Systems
© University of Melbourne
Natural Join Example
10/10/96 11/12/96 10/10/96 11/12/96 10/10/96 11/12/96
7 45.0 8 55.5 8 55.5 10 35.0
58 103 22 101 58 103 22 101
lubber lubber
dustin rusty
10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
Other Types of Joins
• Condition Join (or theta-join) is a cross product with a
condition.
R c S = c ( R S )
dustin lubber
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
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
Let’s try it...
Boats Sailors
Clipper Marine
lubber rusty
10/10/96 11/12/96
INFO20003 Database Systems
© University of Melbourne
Find names of sailors who have reserved boat #103
101 Interlake Blue 102 Interlake Red 103 Clipper Green 104 Marine Red
Solution 1: Solution 2:
lubber rusty
45.0 22 101
55.5 58 103 10 35.0
10/10/96 11/12/96
(Reserves Sailors))
Reserves) Sailors) 103
INFO20003 Database Systems
© University of Melbourne
Find all pairs of sailors in which the older sailor has a lower rating
INFO20003 Database Systems
© University of Melbourne
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
Next Lecture
• Introducing SQL
INFO20003 Database Systems
© University of Melbourne
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com