Relational Algebra CSE 544: Relational Operators, Sorting 1. Union and ...

Relational Algebra

? Operates on relations, i.e. sets

¨C Later: we discuss how to extend this to bags

? Five operators:

CSE 544:

Relational Operators, Sorting

Wednesday, 5/12/2004

¨C

¨C

¨C

¨C

¨C

Union: ¡È

Difference: Selection: ¦Ò

Projection: ¦°

Cartesian Product: ¡Á

? Derived or auxiliary operators:

¨C Intersection, complement

¨C Joins (natural,equi-join, theta join, semi-join)

¨C Renaming: ¦Ñ

1. Union and 2. Difference

? R1 ¡È R2

? Example:

ActiveEmployees ¡È RetiredEmployees

What about Intersection ?

?

?

?

?

It is a derived operator

R1 ¡É R2 = R1 ¨C (R1 ¨C R2)

Also expressed as a join (will see later)

Example

UnionizedEmployees ¡É RetiredEmployees

? R1 ¨C R2

? Example:

AllEmployees ¨C RetiredEmployees

3. Selection

? Returns all tuples which satisfy a condition

? Notation: ¦Òc(R)

? Examples

¦ÒSalary > 40000 (Employee)

¦Òname = ¡°Smithh¡± (Employee)

4. Projection

? Eliminates columns, then removes duplicates

? Notation: ¦° A1,¡­,An (R)

? Example: project social-security number and

names:

¦° SSN, Name (Employee)

Output schema: Answer(SSN, Name)

? The condition c can be =, , ¡Ý,

1

Cartesian Product Example

5. Cartesian Product

? Each tuple in R1 with each tuple in R2

? Notation: R1 ¡Á R2

? Example:

Employee ¡Á Dependents

? Very rare in practice; mainly used to

express joins

Renaming

? Changes the schema, not the instance

? Notation: ¦Ñ B1,¡­,Bn (R)

? Example:

¦ÑLastName, SocSocNo (Employee)

Output schema: Answer(LastName, SocSocNo)

Employee

Name

John

Tony

SSN

999999999

777777777

Dependents

EmployeeSSN

999999999

777777777

Dname

Emily

Joe

Employee x Dependents

Name

SSN

EmployeeSSN

John

999999999 999999999

John

999999999 777777777

Tony

777777777 999999999

Tony

777777777 777777777

Renaming Example

Employee

Name

John

Tony

SSN

999999999

777777777

¦ÑLastName, SocSocNo (Employee)

LastName

John

Tony

Natural Join

? Notation: R1 |¡Á| R2

? Meaning: R1 |¡Á| R2 = ¦°A(¦ÒC(R1 ¡Á R2))

? Where:

¨C The selection ¦ÒC checks equality of all common

attributes

¨C The projection eliminates the duplicate common

attributes

Dname

Emily

Joe

Emily

Joe

SocSocNo

999999999

777777777

Natural Join Example

Employee

Name

John

Tony

SSN

999999999

777777777

Dependents

SSN

999999999

777777777

Dname

Emily

Joe

Employee

Dependents =

¦°Name, SSN, Dname(¦Ò

¦Ò SSN=SSN2(Employee x ¦ÑSSN2, Dname(Dependents))

Name

John

Tony

SSN

999999999

777777777

Dname

Emily

Joe

2

Natural Join

? R=

S=

Natural Join

A

B

B

C

X

Y

Z

U

X

Z

V

W

Y

Z

Z

V

Z

V

? R |¡Á| S=

? Given the schemas R(A, B, C, D), S(A, C, E),

what is the schema of R |¡Á| S ?

? Given R(A, B, C), S(D, E), what is R |¡Á| S ?

A

B

C

X

Z

U

X

Z

V

Y

Z

U

Y

Z

V

Z

V

W

? Given R(A, B), S(A, B), what is R |¡Á| S ?

Theta Join

? A join that involves a predicate

? R1 |¡Á| ¦È R2 = ¦Ò ¦È (R1 ¡Á R2)

? Here ¦È can be any condition: =, ¡Ý

Eq-join

? A theta join where ¦È is an equality

? R1 |¡Á| A=B R2 = ¦Ò A=B (R1 ¡Á R2)

? Example:

Employee |¡Á| SSN=SSN Dependents

? Most useful join in practice

Semijoin

? R |¡Á S = ¦° A1,¡­,An (R |¡Á| S)

? Where A1, ¡­, An are the attributes in R

? Example:

Employee |¡Á Dependents

Semijoins in Distributed

Databases

? Semijoins are used in distributed databases

Dependents

Employee

SSN

Name

...

...

SSN

...

Dname

Age

...

network

Employee

(¦Ò age>71(Dependents))

Employee |¡Á|

|¡Á| ssn=ssn

(Dependents))

ssn=ssn (¦Ò age>71

R = Employee |¡Á T

T = ¦° SSN ¦Ò age>71 (Dependents)

Answer = R |¡Á| Dependents

3

Complex RA Expressions

Operations on Bags

¦° name

buyer-ssn=ssn

pid=pid

seller-ssn=ssn

¦° ssn

¦° pid

¦Òname=fred

Person

Purchase

Person

¦Òname=gizmo

A bag = a set with repeated elements

Relational Engines work on bags, not sets !

All operations need to be defined carefully on bags

? {a,b,b,c}¡È{a,b,b,b,e,f,f}={a,a,b,b,b,b,b,c,e,f,f}

? {a,b,b,b,c,c} ¨C {b,c,c,c,d} = {a,b,b,d}

? ¦ÒC(R): preserve the number of occurrences

? ¦°A(R): no duplicate elimination

? Cartesian product, join: no duplicate elimination

Product

Logical Operators in the Bag

Algebra

?

?

?

?

?

?

?

Union, intersection, difference

Selection ¦Ò

Projection ¦°

Join

Duplicate elimination ¦Ä

Grouping ¦Ã

Sorting ¦Ó

Relational

Algebra

(on bags)

Query Plan:

? logical tree

? implementation

choice at every

node

? scheduling of

operations.

SELECT

SELECTcity,

city,count(*)

count(*)

FROM

FROMsales

sales

GROUP

GROUPBY

BYcity

city

HAVING

HAVINGsum(price)

sum(price)>>100

100

City=¡®seattle¡¯

¦Ò p > 100

c

sales

Architecture of a Database Engine

SQL query

buyer

¦Ò

¦° city, c

T(city,p,c)

¦Ã city, sum(price) p, count(*)

Physical Operators

SELECT

SELECT S.buyer

S.buyer

FROM

FROMPurchase

PurchaseP,

P,Person

PersonQQ

WHERE

P.buyer=Q.name

WHERE P.buyer=Q.nameAND

AND

Q.city=¡®seattle¡¯

Q.city=¡®seattle¡¯AND

AND

Q.phone

>

¡®5430000¡¯

Q.phone > ¡®5430000¡¯

Example

Parse Query

phone>¡¯5430000¡¯

Buyer=name

(Simple Nested Loops)

Query

optimization

Select Logical Plan

Logical

plan

Select Physical Plan

Purchase

(Table scan)

Person

(Index scan)

Query Execution

Physical

plan

Some operators are from relational

algebra, and others (e.g., scan)

are not.

4

Cost Parameters

In database systems the data is on disks, not in main memory

The cost of an operation = total number of I/Os

Cost parameters:

? B(R) = number of blocks for relation R

? T(R) = number of tuples in relation R

? V(R, a) = number of distinct values of attribute a

Cost

Cost of an operation =

number of disk I/Os needed to:

¨C read the operands

¨C compute the result

Cost of writing the result to disk is not included on the following

slides

Question: the cost of sorting a table with B blocks ?

Answer:

Sorting While Scanning

? Sometimes it is useful to have the output

sorted

? Three ways to scan it sorted:

¨C If there is a primary or secondary index on it,

use it during scan

¨C If it fits in memory, sort there

¨C If not, use multi-way merge sort

Cost Parameters

? Clustered table R:

¨C Blocks consists only of records from this table

¨C B(R) ¡Ö T(R) / blockSize

? Unclustered table R:

¨C Its records are placed on blocks with other tables

¨C When R is unclustered: B(R) ¡Ö T(R)

? When a is a key, V(R,a) = T(R)

? When a is not a key, V(R,a)

Scanning Tables

? The table is clustered:

¨C Table-scan: if we know where the blocks are

¨C Index scan: if we have a sparse index to find the

blocks

? The table is unclustered

¨C May need one read for each record

Cost of the Scan Operator

? Clustered relation:

¨C Table scan:

? Unsorted: B(R)

? Sorted: 3B(R)

¨C Index scan

? Unsorted: B(R)

? Sorted: B(R) or 3B(R)

? Unclustered relation

¨C Unsorted: T(R)

¨C Sorted: T(R) + 2B(R)

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download