Introduction to Data Management�DSC 100

Lecture 4 Part 1:

Relational Algebra

DSC 100

1

Relational Algebra

DSC 100

2

Relational Algebra

• In SQL we say what we want
• In RA we can express how to get it
• RA = set-at-a-time algebra for relations

​

• Every DBMS implementations converts a SQL query to RA in order to execute it
• An RA expression is called a query plan

DSC 100

3

Basics

• Inputs: Relations (with attributes)
• RA: defines a function on relations
• Returns a relation
• Can be composed together
• Often displayed using a tree rather than linearly
• Use Greek symbols: σ, π, δ, etc

DSC 100

4

Sets v.s. Bags

• Sets: {a,b,c}, {a,d,e,f}, { }, . . .
• Bags: {a, a, b, c}, {b, b, b, b, b}, . . .

​

Relational Algebra has two flavors:

• Set semantics = standard Relational Algebra
• Bag semantics = extended Relational Algebra

​

DB systems implement bag semantics (Why?)

DSC 100

5

Relational Algebra Operators

• Union ∪, intersection ∩, difference -
• Selection σ
• Projection π
• Cartesian product ×, join ⨝
• (Rename ρ)
• Duplicate elimination δ
• Grouping and aggregation ɣ
• Sorting 𝛕

DSC 100

6

RA

Extended RA

All operators take in 1 or 2 relations as inputs �and return another relation

Union and Difference

DSC 100

7

What do they mean over bags ?

R1 ∪ R2

R1 – R2

Only make sense if R1, R2 have the same schema

What about Intersection ?

• Derived operator using minus

​

​

​

• Derived using join

DSC 100

8

R1 ∩ R2 = R1 – (R1 – R2)

R1 ∩ R2 = R1 ⨝ R2

Selection

• Returns all tuples which satisfy a condition

​

​

• Examples
• σ_{Salary > 40000} (Employee)
• σ_{name = “Smith”} (Employee)
• The condition c can be =, <, <=, >, >=, <>�combined with AND, OR, NOT

DSC 100

9

σ_c(R)

DSC 100

10

σ_{Salary > 40000} (Employee)

Employee

Projection

• Eliminates columns

​

​

• Example: project social-security number and names:
• π_{SSN, Name} (Employee) 🡪 Answer(SSN, Name)

​

​

DSC 100

11

π _A1,…,An (R)

Different semantics over sets or bags! Why?

DSC 100

12

π _Name,Salary (Employee)

Employee

Bag semantics

Set semantics

Which is more efficient?

Composing RA Operators

DSC 100

13

Patient

σ_{disease=‘heart’}(Patient)

π_zip,disease(Patient)

π_zip,disease(σ_{disease=‘heart’}(Patient))

Cartesian Product

• Each tuple in R1 with each tuple in R2

​

​

​

• Rare in practice; mainly used to express joins

DSC 100

14

R1 × R2

Cross-Product Example

DSC 100

15

Employee

Dependent

Employee × Dependent

Renaming

• Changes the schema, not the instance

​

​

• Example:
• Given Employee(Name, SSN)
• ρ_{N, S}(Employee) 🡪 Answer(N, S)

DSC 100

16

ρ_B1,…,Bn (R)

Natural Join

​

​

• Meaning: R1⨝ R2 = Π_A(σ_θ (R1 × R2))

​

• Where:
• Selection σ_θ checks equality of all common attributes (i.e., attributes with same names)
• Projection Π_A eliminates duplicate common attributes

DSC 100

17

R1 ⨝ R2

Natural Join Example

DSC 100

18

R

S

R ⨝ S =

Π_ABC(σ_R.B=S.B(R × S))

Natural Join Example 2

DSC 100

19

AnonPatient P

Voters V

P V

Natural Join

• Given 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?

​

• Given R(A, B), S(A, B), what is R ⨝ S?

DSC 100

20

Introduction to Data Management�DSC 100

Lecture 4 Part 2:

Relational Algebra

DSC 100

21

Theta Join

• A join that involves a predicate

​

​

• Here θ can be any condition
• No projection in this case!
• For our voters/patients example:

DSC 100

22

R1 ⨝_θ R2 = σ_θ (R1× R2)

P ⨝ _{P.zip = V.zip and P.age >= V.age -1 and P.age <= V.age +1} V

AnonPatient (age, zip, disease)�Voters (name, age, zip)

Equijoin

• A theta join where θ is an equality predicate

​

​

​

​

• By far the most used variant of join in practice
• What is the relationship with natural join?

DSC 100

23

R1 ⨝_θ R2 = σ_θ (R1 × R2)

Equijoin Example

DSC 100

24

AnonPatient P

Voters V

P _P.age=V.age V

Natural Join Example

DSC 100

25

AnonPatient P

Voters V

P V

Join Summary

• Theta-join: R ⨝_θ S = σ_θ (R × S)
• Join of R and S with a join condition θ
• Cross-product followed by selection θ
• No projection
• Equijoin: R ⨝_θ S = σ_θ (R × S)
• Join condition θ consists only of equalities
• No projection
• Natural join: R ⨝ S = π_A (σ_θ (R × S))
• Equality on all fields with same name in R and in S
• Projection π_A drops all redundant attributes

DSC 100

26

So Which Join Is It ?

When we write R ⨝ S we usually mean an equijoin, but we often omit the equality predicate when it is clear from the context

DSC 100

27

More Joins

• Outer join
• Include tuples with no matches in the output
• Use NULL values for missing attributes
• Does not eliminate duplicate columns

​

• Variants
• Left outer join
• Right outer join
• Full outer join

DSC 100

28

Outer Join Example

DSC 100

29

AnonPatient P

P ⋊ J

AnnonJob J

Some Examples

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,qty,price)

​

Name of supplier of parts with size greater than 10

π_sname(Supplier ⨝ (Supply ⨝ (σ_psize>10 (Part)))

​

Name of supplier of red parts or parts with size greater than 10

π_sname(Supplier ⨝ (Supply ⨝ (σ _psize>10 (Part) ∪ σ_{pcolor=‘red’} (Part) ) ) )

π_sname(Supplier ⨝ (Supply ⨝ (σ _{psize>10 ∨ pcolor=‘red’} (Part) ) ) )

​

Can be represented as trees as well

DSC 100

30

Some Examples

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,qty,price)

​

Name of supplier of parts with size greater than 10

Project[sname](Supplier Join[sno=sno] � (Supply Join[pno=pno] (Select[psize>10](Part))))

​

Name of supplier of red parts or parts with size greater than 10

Project[sname](Supplier Join[sno=sno]

(Supply Join[pno=pno]

((Select[psize>10](Part)) Union � (Select[pcolor=‘red’](Part)))

​

Project[sname](Supplier Join[sno=sno] (Supply Join[pno=pno] � (Select[psize>10 OR pcolor=‘red’](Part))))

​

Can be represented as trees as well

31

Representing RA Queries as Trees

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,qty,price)

​

​

​

32

Part

Supply

σ_psize>10

π_sname

Answer

Supplier

SELECT z.sname

FROM Part x, Supply y, Supplier z

WHERE x.psize > 10� and x.pno = y.pno� and y.sno = z.sno

π_sname(Supplier ⨝ (Supply ⨝ (σ_psize>10 (Part)))

Relational Algebra Operators

• Union ∪, intersection ∩, difference -
• Selection σ
• Projection π
• Cartesian product X, join ⨝
• (Rename ρ)
• Duplicate elimination δ
• Grouping and aggregation ɣ
• Sorting 𝛕

DSC 100

33

RA

Extended RA

All operators take in 1 or 2 relations as inputs �and return another relation

Extended RA: Operators on Bags

• Duplicate elimination δ
• Grouping γ
• Takes in relation and a list of grouping operations (e.g., aggregates). Returns a new relation.
• Sorting τ
• Takes in a relation, a list of attributes to sort on, and an order. Returns a new relation.

DSC 100

34

Using Extended RA Operators

DSC 100

35

SELECT city, sum(quantity)

FROM sales

GROUP BY city

HAVING count(*) > 100

T1, T2 = temporary tables

Typical Plan for a Query (1/2)

DSC 100

36

R

S

_{join condition}

σ_{selection condition}

π_fields

_{join condition}

…

SELECT-PROJECT-JOIN

Query

Answer

SELECT fields

FROM R, S, …

WHERE condition

Typical Plan for a Query (1/2)

DSC 100

37

π_fields

ɣ_{fields, sum/count/min/max(fields)}

σ_{having condition}

σ_{where condition}

_{join condition}

…

…

SELECT fields

FROM R, S, …

WHERE condition

GROUP BY fields

HAVING condition

How about Subqueries?

DSC 100

38

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,price)

SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’ � and not exists

(SELECT *

FROM Supply P� WHERE P.sno = Q.sno� and P.price > 100)

How about Subqueries?

DSC 100

39

SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’ � and not exists

(SELECT *

FROM Supply P� WHERE P.sno = Q.sno� and P.price > 100)

Correlation !

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,price)

How about Subqueries?

DSC 100

40

SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’ � and not exists

(SELECT *

FROM Supply P� WHERE P.sno = Q.sno� and P.price > 100)

De-Correlation

SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’� and Q.sno not in

(SELECT P.sno

FROM Supply P� WHERE P.price > 100)

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,price)

How about Subqueries?

DSC 100

41

SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’� and Q.sno not in

(SELECT P.sno

FROM Supply P� WHERE P.price > 100)

(SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’)

EXCEPT� (SELECT P.sno

FROM Supply P� WHERE P.price > 100)

EXCEPT = set difference

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,price)

Un-nesting

How about Subqueries?

DSC 100

42

(SELECT Q.sno

FROM Supplier Q

WHERE Q.sstate = ‘WA’)

EXCEPT� (SELECT P.sno

FROM Supply P� WHERE P.price > 100)

Supply

σ_{sstate=‘WA’}

Supplier

σ_{Price > 100}

−

Finally…

π_sno

π_sno

Supplier(sno,sname,scity,sstate)

Part(pno,pname,psize,pcolor)

Supply(sno,pno,price)

Summary of RA and SQL

• SQL = a declarative language where we say what data we want to retrieve
• RA = an algebra where we say how we want to retrieve the data
• Theorem: SQL and RA can express exactly the same class of queries

DSC 100

43

RDBMS translate SQL 🡪 RA, then optimize RA

Summary of RA and SQL

• SQL (and RA) cannot express ALL queries that we could write in, say, Java
• Example:
• Parent(p,c): find all descendants of ‘Alice’
• No RA query can compute this!
• This is called a recursive query
• Next lecture: Datalog is an extension that can compute recursive queries

DSC 100

44