Introduction to Data Management�DSC 100�

Lecture 3 Part 1: Nested Queries in SQL

​

DSC 100

1

What have we learned so far

• Data models
• Relational data model
• Instance: relations
• Schema: table with attribute names
• Language: SQL

DSC 100

2

What have we learned so far

SQL features

• Projections
• Selections
• Joins (inner and outer)
• Aggregates
• Group by
• Having
• Inserts, updates, and deletes

​

DSC 100

3

Subqueries

• A subquery is a SQL query nested inside a larger query
• Such inner-outer queries are called nested queries
• A subquery may occur in:
• A SELECT clause
• A FROM clause
• A WHERE clause

​

• Rule of thumb: avoid nested queries when possible
• But sometimes it’s impossible, as we will see

DSC 100

4

Subqueries…

• Can return a single value to be included in a SELECT clause
• Can return a relation to be included in the FROM clause, aliased using a tuple variable
• Can return a single value to be compared with another value in a WHERE clause
• Can return a relation to be used in the WHERE or HAVING clause under an existential quantifier

​

​

​

DSC 100

5

1. Subqueries in SELECT

DSC 100

6

Product (pname, price, cid)

Company (cid, cname, city)

For each product return the city where it is manufactured

SELECT X.pname, (SELECT Y.city � FROM Company Y� WHERE Y.cid=X.cid) as City

FROM Product X

What happens if the subquery returns more than one city?

We get a runtime error� (and SQLite simply ignores the extra values…)

“correlated subquery”

1. Subqueries in SELECT

DSC 100

7

Whenever possible, don’t use a nested queries:

SELECT X.pname, Y.city

FROM Product X, Company Y

WHERE X.cid=Y.cid

=

SELECT X.pname, (SELECT Y.city � FROM Company Y� WHERE Y.cid=X.cid) as City

FROM Product X

Product (pname, price, cid)

Company (cid, cname, city)

We have �“unnested”�the query

1. Subqueries in SELECT

DSC 100

8

Compute the number of products made by each company

Product (pname, price, cid)

Company (cid, cname, city)

1. Subqueries in SELECT

DSC 100

9

Compute the number of products made by each company

SELECT DISTINCT C.cname, (SELECT count(*)� FROM Product P � WHERE P.cid=C.cid)

FROM Company C

Product (pname, price, cid)

Company (cid, cname, city)

1. Subqueries in SELECT

DSC 100

10

Compute the number of products made by each company

SELECT DISTINCT C.cname, (SELECT count(*) � FROM Product P � WHERE P.cid=C.cid)

FROM Company C

Better: we can unnest using a GROUP BY

SELECT C.cname, count(*)

FROM Company C, Product P

WHERE C.cid=P.cid

GROUP BY C.cname

Product (pname, price, cid)

Company (cid, cname, city)

1. Subqueries in SELECT

DSC 100

11

But are these really equivalent?

SELECT DISTINCT C.cname, (SELECT count(*) � FROM Product P � WHERE P.cid=C.cid)

FROM Company C

SELECT C.cname, count(*)

FROM Company C, Product P

WHERE C.cid=P.cid

GROUP BY C.cname

Product (pname, price, cid)

Company (cid, cname, city)

1. Subqueries in SELECT

DSC 100

12

But are these really equivalent?

SELECT DISTINCT C.cname, (SELECT count(*) � FROM Product P � WHERE P.cid=C.cid)

FROM Company C

No! Different results if a company has no products

SELECT C.cname, count(*)

FROM Company C, Product P

WHERE C.cid=P.cid

GROUP BY C.cname

SELECT C.cname, count(pname)

FROM Company C LEFT OUTER JOIN Product P

ON C.cid=P.cid

GROUP BY C.cname

Product (pname, price, cid)

Company (cid, cname, city)

Recall: count of an empty table is 0

2. Subqueries in FROM

DSC 100

13

Find all products whose prices is > 20 and < 500

Product (pname, price, cid)

Company (cid, cname, city)

2. Subqueries in FROM

DSC 100

14

Find all products whose prices is > 20 and < 500

SELECT X.pname �FROM (SELECT * � FROM Product AS Y � WHERE price > 20) as X

WHERE X.price < 500

Product (pname, price, cid)

Company (cid, cname, city)

2. Subqueries in FROM

DSC 100

15

Find all products whose prices is > 20 and < 500

SELECT X.pname �FROM (SELECT * � FROM Product AS Y � WHERE price > 20) as X

WHERE X.price < 500

Try unnest this query !

Product (pname, price, cid)

Company (cid, cname, city)

2. Subqueries in FROM

DSC 100

16

Find all products whose prices is > 20 and < 500

SELECT X.pname �FROM (SELECT * � FROM Product AS Y � WHERE price > 20) as X

WHERE X.price < 500

Try unnest this query !

Product (pname, price, cid)

Company (cid, cname, city)

Side note: This is not a correlated subquery. (why?)

2. Subqueries in FROM

Sometimes we need to compute an intermediate table only to use it later in a SELECT-FROM-WHERE

• Option 1: use a subquery in the FROM clause
• Option 2: use the WITH clause

DSC 100

17

2. Subqueries in FROM

DSC 100

18

SELECT X.pname �FROM (SELECT * � FROM Product AS Y � WHERE price > 20) as X

WHERE X.price < 500

Product (pname, price, cid)

Company (cid, cname, city)

=

WITH myTable AS (SELECT * FROM Product AS Y WHERE price > 20)

SELECT X.pname � FROM myTable as X

WHERE X.price < 500

A subquery whose�result we called myTable

3. Subqueries in WHERE

DSC 100

19

Find all companies that make some products with price < 200

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

20

Find all companies that make some products with price < 200

Existential quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

21

Find all companies that make some products with price < 200

SELECT DISTINCT C.cname

FROM Company C

WHERE EXISTS (SELECT *� FROM Product P� WHERE C.cid = P.cid and P.price < 200)

Existential quantifiers

Using EXISTS:

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

22

SELECT DISTINCT C.cname

FROM Company C

WHERE C.cid IN (SELECT P.cid� FROM Product P� WHERE P.price < 200)

Using IN

Find all companies that make some products with price < 200

Existential quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

23

SELECT DISTINCT C.cname

FROM Company C, Product P

WHERE C.cid = P.cid and P.price < 200

Now let’s unnest it:

Find all companies that make some products with price < 200

Existential quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

24

SELECT DISTINCT C.cname

FROM Company C, Product P

WHERE C.cid = P.cid and P.price < 200

Existential quantifiers are easy! ☺

Now let’s unnest it:

Find all companies that make some products with price < 200

Existential quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

3. Subqueries in WHERE

DSC 100

25

same as:

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies that make only products with price < 200

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

26

same as:

Universal quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies that make only products with price < 200

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

27

Universal quantifiers are hard! ☹

same as:

Universal quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies that make only products with price < 200

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

28

1. Find the other companies that make some product ≥ 200

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

… …which ones?

3. Subqueries in WHERE

DSC 100

29

1. Find the other companies that make some product ≥ 200

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

30

1. Find the other companies that make some product ≥ 200

SELECT DISTINCT C.cname

FROM Company C

WHERE C.cid IN (SELECT P.cid� FROM Product P� WHERE P.price >= 200)

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

31

2. Find all companies s.t. all their products have price < 200

1. Find the other companies that make some product ≥ 200

SELECT DISTINCT C.cname

FROM Company C

WHERE C.cid IN (SELECT P.cid� FROM Product P� WHERE P.price >= 200)

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

SELECT DISTINCT C.cname

FROM Company C

WHERE C.cid NOT IN (SELECT P.cid� FROM Product P� WHERE P.price >= 200)

3. Subqueries in WHERE

DSC 100

32

SELECT DISTINCT C.cname

FROM Company C

WHERE NOT EXISTS (SELECT *� FROM Product P� WHERE P.cid = C.cid and P.price >= 200)

Using EXISTS:

Universal quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

33

SELECT DISTINCT C.cname

FROM Company C

WHERE 200 >= ALL (SELECT price� FROM Product P� WHERE P.cid = C.cid)

Using ALL:

Universal quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

3. Subqueries in WHERE

DSC 100

34

SELECT DISTINCT C.cname

FROM Company C

WHERE 200 >= ALL (SELECT price� FROM Product P� WHERE P.cid = C.cid)

Using ALL:

Universal quantifiers

Product (pname, price, cid)

Company (cid, cname, city)

Find all companies s.t. all their products have price < 200

Not supported �in sqlite

Question for Database Theory Fans and their Friends

• Can we unnest the universal quantifier query?

​

• We need to first discuss the concept of monotonicity

DSC 100

35

Monotone Queries

• Definition A query Q is monotone if:
• Whenever we add tuples to one or more input tables, the answer to the query will not lose any output tuple

DSC 100

36

Product (pname, price, cid)

Company (cid, cname, city)

Monotone Queries

• Definition A query Q is monotone if:
• Whenever we add tuples to one or more input tables, the answer to the query will not lose any output tuple

DSC 100

37

Product (pname, price, cid)

Company (cid, cname, city)

Product

Company

Q

Monotone Queries

• Definition A query Q is monotone if:
• Whenever we add tuples to one or more input tables, the answer to the query will not lose any output tuple

38

Product (pname, price, cid)

Company (cid, cname, city)

Product

Company

Product

Company

Q

Q

So far it looks monotone...

Monotone Queries

• Definition A query Q is monotone if:
• Whenever we add tuples to one or more input tables, the answer to the query will not lose any output tuple

39

Product (pname, price, cid)

Company (cid, cname, city)

Product

Company

Product

Company

Q

Q

Q is not monotone!

Monotone Queries

• Theorem: If Q is a SELECT-FROM-WHERE query that does not have subqueries, and no aggregates, then it is monotone.

​

DSC 100

40

Monotone Queries

• Theorem: If Q is a SELECT-FROM-WHERE query that does not have subqueries, and no aggregates, then it is monotone.

​

• Proof. We use the nested loop semantics: if we insert a tuple in a relation R_i, this will not remove any tuples from the answer

DSC 100

41

SELECT a₁, a₂, …, a_k

FROM R₁ AS x₁, R₂ AS x₂, …, R_n AS x_n

WHERE Conditions

for x₁ in R₁ do

for x₂ in R₂ do� …

for x_n in R_n do

if Conditions

output (a₁,…,a_k)

Monotone Queries

• Theorem: If Q is a SELECT-FROM-WHERE query that does not have subqueries, and no aggregates, then it is monotone.

​

• Proof. We use the nested loop semantics: if we insert a tuple in a relation R_i, this will not remove any tuples from the answer

DSC 100

42

SELECT a₁, a₂, …, a_k

FROM R₁ AS x₁, R₂ AS x₂, …, R_n AS x_n

WHERE Conditions

for x₁ in R₁ do

for x₂ in R₂ do� …

for x_n in R_n do

if Conditions

output (a₁,…,a_k)

Add a tuple to R₂…

Monotone Queries

• Theorem: If Q is a SELECT-FROM-WHERE query that does not have subqueries, and no aggregates, then it is monotone.

​

• Proof. We use the nested loop semantics: if we insert a tuple in a relation R_i, this will not remove any tuples from the answer

DSC 100

43

SELECT a₁, a₂, …, a_k

FROM R₁ AS x₁, R₂ AS x₂, …, R_n AS x_n

WHERE Conditions

for x₁ in R₁ do

for x₂ in R₂ do� …

for x_n in R_n do

if Conditions

output (a₁,…,a_k)

Add a tuple to R₂…

…can’t lose anything here.

Monotone Queries

• The query: ���is not monotone

​

​

​

​

​

​

DSC 100

44

Find all companies s.t. all their products have price < 200

Product (pname, price, cid)

Company (cid, cname, city)

Monotone Queries

• The query: ���is not monotone

​

​

​

​

​

​

DSC 100

45

Find all companies s.t. all their products have price < 200

Product (pname, price, cid)

Company (cid, cname, city)

Monotone Queries

• The query: ���is not monotone

​

​

​

​

​

​

• Consequence: If a query is not monotone, then we cannot write it as a SELECT-FROM-WHERE query without nested subqueries

46

Find all companies s.t. all their products have price < 200

Product (pname, price, cid)

Company (cid, cname, city)

Queries that must be nested

• Queries with universal quantifiers or with negation

​

​

DSC 100

47

Queries that must be nested

• Queries with universal quantifiers or with negation

​

• Queries with aggregates are usually not monotone
• sum(..) and count(*) are NOT monotone, because they do not satisfy set containment
• select count(*) from R is not monotone!

DSC 100

48

Extra Slides for Practice

DSC 100

49

GROUP BY v.s. Nested Queries

DSC 100

50

SELECT product, Sum(quantity) AS TotalSales

FROM Purchase

WHERE price > 1

GROUP BY product

SELECT DISTINCT x.product, (SELECT Sum(y.quantity)� FROM Purchase y� WHERE x.product = y.product � AND y.price > 1)� AS TotalSales

FROM Purchase x

WHERE x.price > 1

Why twice ?

Purchase(pid, product, quantity, price)

More Unnesting

DSC 100

51

Author(login,name)

Wrote(login,url)

Find authors who wrote ≥ 10 documents:

More Unnesting

DSC 100

52

SELECT DISTINCT Author.name

FROM Author

WHERE (SELECT count(Wrote.url)� FROM Wrote� WHERE Author.login=Wrote.login)� >= 10

This is�SQL by�a novice

Attempt 1: with nested queries

Author(login,name)

Wrote(login,url)

Find authors who wrote ≥ 10 documents:

More Unnesting

DSC 100

53

Attempt 1: with nested queries

Author(login,name)

Wrote(login,url)

Find authors who wrote ≥ 10 documents:

SELECT Author.name

FROM Author, Wrote

WHERE Author.login=Wrote.login

GROUP BY Author.name

HAVING count(wrote.url) >= 10

This is�SQL by�an expert

Attempt 2: using GROUP BY and HAVING

Finding Witnesses

DSC 100

54

Product (pname, price, cid)

Company (cid, cname, city)

For each city, find the most expensive product made in that city

Finding Witnesses

DSC 100

55

SELECT x.city, max(y.price)

FROM Company x, Product y

WHERE x.cid = y.cid

GROUP BY x.city;

Finding the maximum price is easy…

But we need the witnesses, i.e., the products with max price

For each city, find the most expensive product made in that city

Product (pname, price, cid)

Company (cid, cname, city)

Finding Witnesses

DSC 100

56

To find the witnesses, compute the maximum price�in a subquery (in FROM or in WITH)

Product (pname, price, cid)

Company (cid, cname, city)

WITH CityMax AS � (SELECT x.city, max(y.price) as maxprice

FROM Company x, Product y

WHERE x.cid = y.cid

GROUP BY x.city)

Finding Witnesses

DSC 100

57

To find the witnesses, compute the maximum price�in a subquery (in FROM or in WITH)

Product (pname, price, cid)

Company (cid, cname, city)

WITH CityMax AS � (SELECT x.city, max(y.price) as maxprice

FROM Company x, Product y

WHERE x.cid = y.cid

GROUP BY x.city)

SELECT DISTINCT u.city, v.pname, v.price

FROM Company u, Product v, CityMax w

WHERE u.cid = v.cid

and u.city = w.city

and v.price = w.maxprice;

Finding Witnesses

DSC 100

58

To find the witnesses, compute the maximum price�in a subquery (in FROM or in WITH)

SELECT DISTINCT u.city, v.pname, v.price

FROM Company u, Product v,

(SELECT x.city, max(y.price) as maxprice

FROM Company x, Product y

WHERE x.cid = y.cid

GROUP BY x.city) w

WHERE u.cid = v.cid

and u.city = w.city

and v.price = w.maxprice;

Product (pname, price, cid)

Company (cid, cname, city)

Finding Witnesses

DSC 100

59

Or we can use a subquery in where clause

SELECT u.city, v.pname, v.price

FROM Company u, Product v

WHERE u.cid = v.cid

and v.price >= ALL (SELECT y.price � FROM Company x, Product y � WHERE u.city=x.city � and x.cid=y.cid);

Product (pname, price, cid)

Company (cid, cname, city)

Finding Witnesses

DSC 100

60

There is a more concise solution here:

SELECT u.city, v.pname, v.price

FROM Company u, Product v, Company x, Product y

WHERE u.cid = v.cid

and u.city = x.city

and x.cid = y.cid

GROUP BY u.city, v.pname, v.price

HAVING v.price = max(y.price)

Product (pname, price, cid)

Company (cid, cname, city)

SQL: Our first language for the relational model

• Projections
• Selections
• Joins (inner and outer)
• Inserts, updates, and deletes
• Aggregates
• Grouping
• Ordering
• Nested queries

​

DSC 100

61