CSE 414: Section 3

(Un)Nesting Queries

January 23rd, 2024

​

1

Solutions to problem 3 on worksheet

2

Administrivia

• HW2 due Monday October 19th at 11:59pm
• HW1 grades out over the weekend

​

3

Where we started

FWS

(From, Where, Select)

4

And now...

FWGHOS^TM

(From, Where, Group By, Having, Order By, Select)

5

And now...

F – FROM: Determines which table(s) to use (including JOINs)

W – WHERE: Filters individual rows before grouping

G – GROUP BY: Groups rows with matching values

H – HAVING: Filters entire groups after grouping

O – ORDER BY: Sorts the final results

S – SELECT: Determines which columns/expressions to return

6

Group By

• Powerful tool to handle “categories”
• Groups rows with the same value of an attribute into a “bucket” (think dividing into categories)
• Careful when selecting
• Only select attributes in GROUP BY or aggregates
• SQLite will guess (arbitrarily pick a value)¯\_(ツ)_/¯
• SQL Server will throw an error ง •̀_•́)ง

7

Group By - Examples

Do these queries work?

​

Enrolled(stu_id, course_num)

​

​

​

​

SELECT stu_id, course_num

FROM Enrolled

GROUP BY stu_id

SELECT stu_id, count(course_num)

FROM Enrolled

GROUP BY stu_id

​

8

Group By - Examples

Do these queries work?

​

Enrolled(stu_id, course_num)

​

​

​

​

SELECT stu_id, course_num

FROM Enrolled

GROUP BY stu_id

SELECT stu_id, count(course_num)

FROM Enrolled

GROUP BY stu_id

9

Group By - Examples

Do these queries work?

​

Enrolled(stu_id, course_num)

​

​

​

​

SELECT stu_id, course_num

FROM Enrolled

GROUP BY stu_id

SELECT stu_id, count(course_num)

FROM Enrolled

GROUP BY stu_id

10

Grouping and Ordering

GROUP BY [attribute], …, [attribute_n]

When using GROUP BY, every column in SELECT must either:

1. Appear in the GROUP BY clause, or

2. Be inside an aggregate function (COUNT, SUM, AVG, MAX, MIN, etc.).

HAVING [predicate] - operates on groups, chooses to keep or remove the entire group

ORDER BY [attribute] [ASC/DESC]

11

RECAP: THE WITNESSING PROBLEM

12

WHY SUBQUERIES?

13

Difference?

14

Nested Queries

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

15

Subquery in SELECT

SELECT C.cname, (SELECT count(*)

FROM Product P

WHERE P.cid=C.cid)

FROM Company C

​

​

Used to calculate a value for each row of the outer query.

​

​

16

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.cid, C.cname;

17

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>)

​

A subquery acts as a temporary table.

18

Subquery in FROM

Unnest using WHERE

​

SELECT X.pname � FROM Product AS X

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

19

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)

​

​

Used to filter rows based on another query.

​

20

Subquery in WHERE

SELECT DISTINCT C.cname

FROM Company C, Product P

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

​

21

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>);

22

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

23

Monotonicity

24

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

25

(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

26

(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)}

27

(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)}

28

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.

​

29

(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);

30

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));

31

Alternative to “ALL”