CSE 414: Section 3

(Un)Nesting Queries

January 23, 2025

​

1

Administrivia

• HW2 due Friday January 24th at 11:59pm
• HW1 grades out soon
• Using Amazon Web Services (AWS) for HW3
• This is our first time using it so bear with us!
• Next week we will do an AWS setup demo in section

2

RECAP: THE WITNESSING PROBLEM

3

WHY SUBQUERIES?

4

Difference?

5

Nested Queries

• Avoid when possible
• Danger of making simple queries slow and complicated
• Just because you can do it, doesn’t mean you should

6

Subquery in SELECT

SELECT DISTINCT C.cname, (SELECT count(*)

FROM Product P

WHERE P.cid=C.cid)

FROM Company C

​

​

​

7

Subquery in SELECT

Unnest using JOIN and GROUP BY

​

SELECT C.cname, count(P.cid)

FROM Company C LEFT OUTER JOIN

Product P ON C.cid = P.cid

GROUP BY C.cname;

8

Subquery in FROM

SELECT X.pname � FROM (SELECT *

FROM Product

WHERE price > 20) AS X

WHERE X.price < 500

​

​

More readable: WITH <name> AS (<subquery>)

9

Subquery in FROM

Unnest using WHERE

​

SELECT X.pname � FROM Product AS X

WHERE X.price < 500 AND X.price > 20;

10

Subquery in WHERE

SELECT DISTINCT C.cname

FROM Company C

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

​

11

Subquery in WHERE

SELECT DISTINCT C.cname

FROM Company C, Product P

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

​

12

Subquery in WHERE Syntax

• SELECT ……… WHERE EXISTS (<sub>);
• SELECT ……… WHERE NOT EXISTS (<sub>);
• SELECT ……… WHERE attribute IN (<sub>);
• SELECT ……… WHERE attribute NOT IN (<sub>);
• SELECT ……… WHERE attribute > ANY (<sub>);
• SELECT ……… WHERE attribute > ALL (<sub>);

13

To Nest or Not to Nest

• Not an exact science
• Figuring out what is actually wanted will help you find simpler solutions (best way is to practice)
• Trigger words to use sub-querying
• Every, All (universal quantifiers)
• No, None, Never (negation)
• Only

14

Monotonicity

15

Monotonicity

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 tuples

​

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

16

(Non-)monotonic Queries

• “Can we take back outputs by looking at more data?”
• Is this a monotonic query?

​

SELECT count(*)

FROM T1

GROUP BY T1.attr

17

(Non-)monotonic Queries

• “Can we take back outputs by looking at more data?”
• Is this a monotonic query?

​

SELECT count(*)

FROM T1

GROUP BY T1.attr

No! This query does not satisfy set containment.

​

Ex:

Current output: {(6), (23), (10)}

After more data: {(6), (23), (11)}

​

{(6), (23), (10)} ⊄ {(6), (23), (11)}

18

(Non-)monotonic Queries

• “Can we take back outputs by looking at more data?”
• Is this a monotonic query?

​

SELECT count(*)

FROM T1

GROUP BY T1.attr

No! This query does not satisfy set containment.

​

Ex:

Current output: {(6), (23), (10)}

After more data: {(6), (23), (11)}

​

{(6), (23), (10)} ⊄ {(6), (23), (11)}

19

Aggregates are generally sensitive to new tuples

Consequences of Monotonicity

Theorem: If a query is monotonic, it implies that a nested query can actually be unnested.

​

20

(AGAIN) Witnessing (i.e. argmax)

Find the student who is taking the most classes.

Student(stu_id, id_num)

Enrolled(id_num, class)

​

SELECT S.stu_id

FROM Student S, Enrolled E

WHERE S.id_num = E.id_num

GROUP BY S.stu_id

HAVING count(E.class) >= ALL(

SELECT count(E1.class)

FROM Enrolled E1

GROUP BY E1.id_num);

21

Witnessing (i.e. argmax)

Find the student who is taking the most classes.

Student(stu_id, id_num)

Enrolled(id_num, class)

​

SELECT S.stu_id

FROM Student S, Enrolled E

WHERE S.id_num = E.id_num

GROUP BY S.stu_id

HAVING COUNT(E.class) = (

SELECT MAX(C) FROM (

SELECT COUNT(E1.class) AS C

FROM Enrolled E1

GROUP BY E1.id_num));

22

Alternative to “ALL”