1 of 42

CSE 344: Midterm Review

SQL, Relational Algebra

Oct 24th, 2024

2 of 42

SQL Review

3 of 42

Join Types

There will be times we use inner join, full join, and left outer join.

There is never a scenario in this class we need to use a right outer join and sqlite3 does not support this operation. It also doesn’t support full outer join, which you most likely won’t need for this class.

3

4 of 42

SQL 3-Valued Logic

SQL has 3-valued logic

FALSE = 0

[ex] price < 25 is FALSE when price = 99

UNKNOWN = 0.5

[ex] price < 25 is UNKNOWN when price = NULL

TRUE = 1

[ex] price < 25 is TRUE when price = 19

4

5 of 42

SQL 3-Valued Logic (con’t)

Formal definitions:

C1 AND C2 means min(C1,C2)� C1 OR C2 means max(C1,C2)� NOT C means means 1-C

The rule for SELECT ... FROM ... WHERE C is the following:� if C = TRUE then include the row in the output� if C = FALSE or C = unknown then do not include it

5

6 of 42

Nested Queries

Queries inside other queries

Usually simplifies or factors out part of the outer query
Use case is similar to helper methods

Can go in multiple places!

SELECT
FROM
WHERE/HAVING
... basically anywhere we use a table

7 of 42

Nested Queries

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

7

8 of 42

Subquery in SELECT

8

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

FROM Product P

WHERE P.cid = C.cid)

FROM Company C;

9 of 42

Subquery in SELECT

Unnest using JOIN and GROUP BY

9

SELECT C.cname, count(P.cid)

FROM Company C LEFT OUTER JOIN

Product P ON C.cid = P.cid

GROUP BY C.cname;

10 of 42

Nested Queries

If the SQL subquery returns exactly one value it can be used where we use a field

“one value” = one tuple with one attribute

Otherwise, a SQL subquery can be thought of as an "extra table"

Can name the table, its columns, etc

10

11 of 42

Subquery in FROM

11

SELECT X.pname

FROM (SELECT *

FROM Product

WHERE price > 20) AS X

WHERE X.price < 500;

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

12 of 42

Subquery in FROM

12

WITH price_more_20 AS (

SELECT *

FROM Product

WHERE price > 20

)

SELECT X.pname

FROM price_more_20 AS X

WHERE X.price < 500;

13 of 42

Subquery in FROM

Unnest using WHERE

13

SELECT X.pname

FROM Product AS X

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

14 of 42

Subquery in WHERE (example 1)

14

SELECT DISTINCT C.cname

FROM Company C

WHERE EXISTS (SELECT *

FROM Product P

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

15 of 42

Subquery in WHERE (example 1)

15

SELECT DISTINCT C.cname

FROM Company C, Product P

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

16 of 42

Subquery in WHERE (example 2)

16

SELECT S1.major, S1.num_of_students, S1.school_name

FROM Schools S1

WHERE S1.num_of_students >= ALL (SELECT S2.num_of_students

FROM Schools S2

WHERE S1.school_name =

S2.school_name);

17 of 42

Subquery in WHERE (example 2)

17

SELECT S1.major, S1.num_of_students, S2.school_name

FROM Schools S1, Schools S2

WHERE S1.school_name = S2.school_name

GROUP BY S1.major, S1.num_of_students, S2.school_name

HAVING S1.num_of_students = MAX(S2.num_of_students);

18 of 42

Subquery in WHERE Syntax

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

18

Note equivalence

EXISTS will tell you whether a query returned any results. E.g.:

SELECT *

FROM Orders o

WHERE EXISTS

( SELECT *

FROM Products p

WHERE p.ProductNumber = o.ProductNumber

)

IN is used to compare one value to several, and can use literal values, like this:

SELECT *

FROM Orders

WHERE ProductNumber IN (1, 10, 100)

You can also use query results with the IN clause, like this:

SELECT *

FROM Orders

WHERE ProductNumber IN

(

SELECT ProductNumber

FROM Products

WHERE ProductInventoryQuantity > 0

)

The ANY and ALL operators allow you to perform a comparison between a single column value and a range of other values. Best for min/max problems but have other applications. For instance:

select *

from Table1 t1

where t1.Col1 < ANY

(

select value

from Table2

)

ANY means that the condition will be satisfied if the operation is true for any of the values in the range.

ALL means that the condition will be satisfied only if the operation is true for all values in the range.

19 of 42

Witnessing (i.e. argmax)

Find the student(s) 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);

19

johndoe	973
maryjane	712
alsmith	899

973	CSE 311
973	CSE 344
712	CSE 311
899	CSE 351

20 of 42

Witnessing (i.e. argmax) (another way)

20

WITH class_counts AS (SELECT COUNT(E1.class) AS cnt

FROM Enrolled E1

GROUP BY E1.id_num),

max_counts AS (SELECT MAX(cnt) AS max FROM class_counts)

SELECT S.stu_id

FROM Students S, Enrolled E, max_counts Emax

WHERE S.id_num = E.id_num

GROUP BY S.stu_id, Emax.max

HAVING COUNT(E.class) = Emax.max;

21 of 42

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

21

22 of 42

Relational Algebra Review

23 of 42

RA Operators

Standard:

⋂ - Intersect

⋃ - Union

⎼ - Difference

σ - Select

π - Project

⍴ - Rename

Extended:

δ - Duplicate Elim.

ɣ - Group/Agg.

τ - Sorting

Joins:

⨝ - Nat. Join

⟕ - L.O. Join

⟖ - R.O. Join

⟗ - F.O. Join

✕- Cross Product

23

24 of 42

Ɣ Notation

Grouping and aggregation on group:

ɣ_{attr_1, …, attr_k, count/sum/max/min(attr) -> alias}

Aggregation on the entire table:

ɣ_{count/sum/max/min(attr) -> alias}

24

25 of 42

Format

_{Follows FJWGHOS structure}

25

26 of 42

Query Plans (Example SQL -> RA)

Select-Join-Project structure

Make this SQL query into RA (remember FWGHOS):

SELECT R.b, T.c, max(T.a) AS T_max

FROM Table_R AS R, Table_T AS T

WHERE R.b = T.b

GROUP BY R.b, T.c

HAVING max(T.a) > 99

26

27 of 42

Query Plans (Example SQL -> RA)

Select-Join-Project structure

Make this SQL query into RA (remember FWGHOS):

SELECT R.b, T.c, max(T.a) AS T_max

FROM Table_R AS R, Table_T AS T

WHERE R.b = T.b

GROUP BY R.b, T.c

HAVING max(T.a) > 99

27

28 of 42

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

);

28

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!

29 of 42

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

29

π_R2.a

30 of 42

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 * FROM Table_R R2

EXCEPT

SELECT R1.a FROM Table_R R1, Table_S S

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

30

π_R2.a

31 of 42

SQL TO RA

32 of 42

General Approach

_{Follows FJWGHOS structure}

100