A491298007 23888 29 2019 relational algebra PDF

Preview

Summary

IT2002 (Semester 1, 2004/5) 67Relational Algebra(Reference: Chapter 4 of Ramakrishnan & Gehrke)IT2002 (Semester 1, 2004/5): Relational Algebra 68Example DatabaseMoviestitle director myear ratingFargo Coen 1996 8.Raising Arizona Coen 1987 7.Spiderman Raimi 2002 7.Wonder Boys Hanson 2000 7.Act...

Description

IT2002 (Semester 1, 2004/5)

67

Relational Algebra (Reference: Chapter 4 of Ramakrishnan & Gehrke)

IT2002 (Semester 1, 2004/5): Relational Algebra

68

Example Database Actors

Movies title

director

myear

rating

actor

ayear 1964

Fargo

Coen

1996

8.2

Cage

Raising Arizona

Coen

1987

7.6

Hanks

1956

Spiderman

Raimi

2002

7.4

Maguire

1975

Wonder Boys

Hanson

2000

7.6

McDormand

1957

Acts actor

title

Cage

Raising Arizona

Maguire

Spiderman

Maguire

Wonder Boys

McDormand

Fargo

McDormand

Raising Arizona

McDormand

Wonder Boys

Directors director

dyear

Coen

1954

Hanson

1945

Raimi

1959

IT2002 (Semester 1, 2004/5): Relational Algebra

69

Some Queries • Find movies made after 1997 • Find movies made by Hanson after 1997 • Find all movies and their ratings • Find all actors and directors • Find Coen’s movies with McDormand • Find movies with Maguire but not McDormand • Find actors who have acted in some Coen’s movie • Find (director, actor) pairs where the director is younger than the actor • Find actors who have acted in all of Coen’s movies

IT2002 (Semester 1, 2004/5): Relational Algebra

Relational Algebra • A formal query language for asking questions • A query is composed of a collection of operators called relational operators • Unary operators: selection, projection, renaming • Binary operators: union, intersect, difference, cartesian product, join • Relations are closed under relational operators • Operators can be composed to form relational algebra expressions

70

IT2002 (Semester 1, 2004/5): Relational Algebra

71

Selection: σ • σc (R) selects rows from relation R that satisfy selection condition c • Example: Find movies made after 1997

Movies

title

director

Fargo

Coen

myear 1996

rating

Raising Arizona

Coen

1987

7.6

Spiderman

Raimi

2002

7.4

Wonder Boys

Hanson

2000

7.6

8.2

σmyear>1997 (Movies)

title

director

myear

Spiderman

Raimi

2002

rating 7.4

Wonder Boys

Hanson

2000

7.6

IT2002 (Semester 1, 2004/5): Relational Algebra

72

Selection Condition • Selection condition is a boolean combination of terms • A term is one of the following forms: 1. attribute op constant

op ∈ {=, =, , ≥}

2. attribute1 op attribute2 3. term1 ∧ term2 4. term1 ∨ term2 5. ¬ term1 6. (term1 ) • Operator precedence: (), op, ¬, ∧, ∨ • Examples:

IT2002 (Semester 1, 2004/5): Relational Algebra

73

Selection Condition (cont.) • Example: Find movies made by Hanson after 1997

Movies

title

director

Fargo

Coen

myear 1996

Raising Arizona

Coen

1987

7.6

Spiderman

Raimi

2002

7.4

Wonder Boys

Hanson

2000

7.6

title

director

myear

Hanson

2000

8.2

∧ director=‘Hanson′ (Movies)

σmyear>1997

Wonder Boys

rating

rating 7.6

IT2002 (Semester 1, 2004/5): Relational Algebra

74

Projection: π • πL (R) projects columns given by list L from relation R • Example: Find all movies and their ratings

Movies

title

director

Fargo

Coen

1996

Raising Arizona

Coen

1987

7.6

Spiderman

Raimi

2002

7.4

Wonder Boys

Hanson

2000

7.6

πtitle,

myear

rating 8.2

rating (Movies)

title

rating

Fargo

8.2

Raising Arizona

7.6

Spiderman

7.4

Wonder Boys

7.6

IT2002 (Semester 1, 2004/5): Relational Algebra

75

Renaming: ρ • Given relation R(A, B, C), ρS(X,Y,Z) (R) renames it to S(X, Y, Z)

Actors

actor

ayear

Cage

1964

Hanks

1956

Maguire

1975

McDormand

1957

ρStars(name,yob) (Actors)

Stars

name

yob

Cage

1964

Hanks

1956

Maguire

1975

McDormand

1957

IT2002 (Semester 1, 2004/5): Relational Algebra

Set Operations • Union: R ∪ S returns a relation containing all tuples that occur in R or S (or both) • Intersection: R ∩ S returns a relation containing all tuples that occur in both R and S • Set-difference: R − S returns a relation containing all tuples in R but not in S • Two relations are union compatible if – they have the same arity, and – the corresponding attributes have same domains • union (∪), intersection (∩), and set-difference (−) operators require input relations to be union compatible

76

IT2002 (Semester 1, 2004/5): Relational Algebra

Actors

actor

ayear

Cage

1964

Hanks

1956

Maguire

1975

McDormand

1957

77

director Directors

dyear

Coen

1954

Hanson

1945

Raimi

1959

πactor (Actors)

πdirector(Directors)

actor director

Cage Hanks

Coen

Maguire

Raimi

McDormand

Hanson

πactor (Actors) ∪ πdirector (Directors) actor

Union Example:

Cage Hanks

Find all actors & directors

Maguire McDormand

πactor (Actors) ∪ πdirector (Directors)

Coen Raimi Hanson

IT2002 (Semester 1, 2004/5): Relational Algebra

Acts

78

actor

title

Cage

Raising Arizona

title

director

myear

rating

Maguire

Spiderman

Fargo

Coen

1996

8.2

Maguire

Wonder Boys

Raising Arizona

Coen

1987

7.6

McDormand

Fargo

Spiderman

Raimi

2002

7.4

McDormand

Raising Arizona

Wonder Boys

Hanson

2000

7.6

McDormand

Wonder Boys

Movies

e2

e1 title Fargo Raising Arizona Wonder Boys

title Fargo Raising Arizona

Intersection Example:

e1 ∩ e2 title Fargo Raising Arizona

Find Coen’s movies with McDormand e1 = πtitle (σactor=‘M cDormand′ (Acts)) e2 = πtitle (σdirector=‘Coen′ (M ovies)) result = e1 ∩ e2

IT2002 (Semester 1, 2004/5): Relational Algebra

Acts

actor

title

Cage

Raising Arizona

Maguire

Spiderman

Maguire

Wonder Boys

McDormand

Fargo

McDormand

Raising Arizona

McDormand

Wonder Boys

79

σactor=‘M cDormand′ (Acts)

σactor=‘M aguire′ (Acts) title

title

Fargo

Spiderman

Raising Arizona

Wonder Boys

σactor=‘Maguire′ (Acts) σactor=‘McDormand ′ (Acts) title Spiderman

Wonder Boys

Set-difference Example: Find movies with Maguire but not McDormand σactor=‘M aguire′ (Acts) - σactor=‘M cDormand′ (Acts )

IT2002 (Semester 1, 2004/5): Relational Algebra

Set Operations (cont.) • Consider R(A, B, C) and S(X, Y ) • Cross-product: R × S returns a relation with attribute list (A, B, C, X, Y ) defined as follows: R × S = {(a, b, c, x, y) | (a, b, c) ∈ R, (x, y) ∈ S} • Cross-product operation is also known as cartesian product

80

IT2002 (Semester 1, 2004/5): Relational Algebra

81

Cross-product Example • Find actors who have acted in some Coen’s movies • e1 = ρT (title2) (πtitle (σdirector=‘Coen′ (M ovies))) Movies title

director

Fargo

myear

Coen

rating

1996

T

e1

8.2

title2

Raising Arizona

Coen

1987

7.6

Fargo

Spiderman

Raimi

2002

7.4

Raising Arizona

Wonder Boys

Hanson

2000

7.6

IT2002 (Semester 1, 2004/5): Relational Algebra

82

Cross-product Example (cont.) Acts

e2 =

actor

title

Cage

Raising Arizona

Maguire

Spiderman

Maguire

Wonder Boys

McDormand

Fargo

McDormand

Raising Arizona

McDormand

Wonder Boys

T

×

title2 Fargo Raising Arizona

actor

title

Cage

Raising Arizona

title2 Fargo

Cage

Raising Arizona

Raising Arizona

Maguire

Spiderman

Fargo

Maguire

Spiderman

Raising Arizona

Maguire

Wonder Boys

Fargo

Maguire

Wonder Boys

Raising Arizona

McDormand

Fargo

Fargo

McDormand

Fargo

Raising Arizona

McDormand

Raising Arizona

Fargo

McDormand

Raising Arizona

Raising Arizona

McDormand

Wonder Boys

Fargo

McDormand

Wonder Boys

Raising Arizona

=

IT2002 (Semester 1, 2004/5): Relational Algebra

83

Cross-product Example (cont.) actor

e2

title

title2

Cage

Raising Arizona

Fargo

Cage

Raising Arizona

Raising Arizona

Maguire

Spiderman

Fargo

Maguire

Spiderman

Raising Arizona

Maguire

Wonder Boys

Fargo

Maguire

Wonder Boys

Raising Arizona

McDormand

Fargo

Fargo

McDormand

Fargo

Raising Arizona

McDormand

Raising Arizona

Fargo

McDormand

Raising Arizona

Raising Arizona

McDormand

Wonder Boys

Fargo

McDormand

Wonder Boys

Raising Arizona

e3 = σtitle=title2 (e2 ) actor

e3

title

title2

Cage

Raising Arizona

Raising Arizona

McDormand

Fargo

Fargo

McDormand

Raising Arizona

Raising Arizona

πactor (e3 ) actor Cage McDormand

IT2002 (Semester 1, 2004/5): Relational Algebra

84

Cross-product Example (cont.) • Query: Find actors who have acted in some Coen’s movie • Answer: πactor( σtitle=title2 ( Acts × ρT (title2) ( πtitle( σdirector=‘Coen′ (Movies) ) ) ) ) πactor σtitle=title2 × Acts

ρT (title2) πtitle σdirector=‘Coen′ Movies

IT2002 (Semester 1, 2004/5): Relational Algebra

85

Join • Combines cross-product, selection, and projection • Join operator is more useful than the plain cross-product operator • Three types of join: – Condition join – Equijoin – Natural join

IT2002 (Semester 1, 2004/5): Relational Algebra

86

Condition Join: R ⊲⊳ c S • Condition join = Cross-product followed by selection R ⊲⊳c S = σc (R × S) • Example: Find (director,actor) pairs where the director is younger than the actor • Answer: πdirector,actor( Directors ⊲⊳ dyear>ayear Actors) Actors

Directors director

dyear

Coen

1954

Hanson

1945

Raimi

1959

actor

ayear

Cage

1964

Hanks

1956

Maguire

1975

McDormand

1957

πdirector,actor (e1 )

e1 = Directors ⊲⊳ dyear>ayear Actors ayear

director

actor

director

dyear

actor

Raimi

1959

Hanks

1956

Raimi

Hanks

Raimi

1959

McDormand

1957

Raimi

McDormand

IT2002 (Semester 1, 2004/5): Relational Algebra

87

Equijoin: R ⊲⊳c S • Equijoin = Condition join of the form R ⊲⊳c S = πL (σc (R × S)) where – c is a conjunction of equality conditions of the form R.Ai = S.Aj – L is a sequence of attributes consisting of L1 followed by L2 – L1 is a sequence of attributes in schema of R – L2 is a sequence of attributes in schema of S that are not referenced in c

IT2002 (Semester 1, 2004/5): Relational Algebra

88

Equijoin (cont.) • Example: Find actors who have acted in some Coen’s movie • πactor ( σdirector=‘Coen′ ( Acts ⊲⊳ Acts.title =

M ovies.title

Movies ) )

e1 = Acts ⊲⊳ Acts.title = Movies.title Movies title director myear rating

actor Cage

Raising Arizona

Coen

1987

7.6

Maguire

Spiderman

Raimi

2002

7.4

Maguire

Wonder Boys

Hanson

2000

7.6

McDormand

Fargo

Coen

1996

8.2

McDormand

Raising Arizona

Coen

1987

7.6

McDormand

Wonder Boys

Hanson

2000

7.6

πactor (σdirector=‘Coen′ ((e1 ))

actor Cage McDormand

IT2002 (Semester 1, 2004/5): Relational Algebra

89

Natural Join: R ⊲⊳ S • Natural join = Equijoin of the form R ⊲⊳ S = R ⊲⊳c S where c is specified for all attributes having the same name in R and S • Example: Find actors who have acted in some Coen’s movie πactor ( σdirector=‘Coen′ ( Acts ⊲⊳ Movies ) ) • Example: Find the name and the year of birth of all actors who were in some Coen’s movie πactor,ayear ( σdirector=‘Coen′ (Movies) ⊲⊳ Acts ⊲⊳ Actors )

IT2002 (Semester 1, 2004/5): Relational Algebra

90

Example: Condition, Equi-, Natural Joins R

• R ⊲⊳ A=A′

S

A

B

X

A

B

Y

0

6

x1

0

8

y1

1

9

x2

1

5

y2

2

7

x3

2

7

y3

∧ B...