程序代写代做代考 database SQL INFO20003 Database Systems

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