CSE 344: Section 4

(Un)Nesting Queries

1

Azure Setup Demo

https://docs.google.com/document/d/1tFPsFv6-7nSk49zPl6c_G4dFS6oMBxhnwyUMj9T2nO0/edit#heading=h.wy1xougxikpo

HW3 Setup Demo

https://docs.google.com/document/d/1tFPsFv6-7nSk49zPl6c_G4dFS6oMBxhnwyUMj9T2nO0/edit

@2:28:

You must set “Allow services and resources to access this server” to YES (not mentioned in video. See step L in the doc)

​

Why Subqueries?

4

Subqueries vs. Group By

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 X AS (SELECT * FROM Product

WHERE price > 20)

SELECT X.pname � FROM X

WHERE X.price < 500

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

Difference Operator in RA

SELECT DISTINCT R.a

FROM Table_R AS R

WHERE NOT EXISTS (

SELECT *

FROM Table_S AS S

WHERE S.b = R.a

AND S.c < 15

);

​

14

• We need to correctly exclude rows if they exist in the subquery
• We cannot use σ (select) to compare rows
• Solution is to use the ⎼ (difference) operator!

Difference Operator

SELECT DISTINCT R.a

FROM Table_R AS R

WHERE NOT EXISTS (

SELECT *

FROM Table_S AS S

WHERE S.b = R.a

AND S.c < 15);

15

π_R2.a

Difference Operator

SELECT DISTINCT R.a

FROM Table_R AS R

WHERE NOT EXISTS (

SELECT *

FROM Table_S AS S

WHERE S.b = R.a

AND S.c < 15);

Equivalent SQL:

SELECT DISTINCT R2.a FROM Table_R R2

EXCEPT

SELECT R1.a FROM Table_R R1, Table_S S

WHERE S.c < 15 AND R1.a = S.b;

16

π_R2.a

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

17

Correlated vs. Uncorrelated Subquery

• Correlated subquery
• When a subquery refers to attributes from the main query and is recomputed multiple times
• The subquery is recomputed for EVERY tuple in the main query!
• For example, can be found in WHERE clause with EXISTS/NOT EXISTS
• Uncorrelated subquery
• Subquery is executed once and the subquery result is reused for each tuple of the main query
• No references to tables in the main query: written as its own query
• Usually used when you want to create a table and use that new table in the main query
• For example, can be found in FROM/WITH clause

18

Correlated vs. Uncorrelated Subquery

19

Monotonicity

20

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

​

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

21

(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 data: {(6), (23)}; Output: {(2)}

After more data: {(6), (23), (1)}; Output: {(3)}

{(2)} ⊄ {(3)}

22

Aggregates are generally sensitive to new tuples

Worksheet