CSE 344: Section 3

Witnessing Problem + �Relational Algebra

Relational Algebra

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

3

Ɣ 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}

4

Format

• _{Follows FJWGHOS structure}

5

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

6

Query Plans (Example SQL -> RA)

Select-Join-Project structure

Make this SQL query into RA (remember FJWGHOS):

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

π_{R.b, T.c, T_max}

|

σ_{T_max > 99}

|

ɣ_{R.b, T.c, max(T.a)->T_max}

|

⨝_R.b=T.b

/ \

R T

7

The Witnessing Problem

The Witnessing Problem

• “Return the row with the maximum/minimum of this column grouped by that column”
• Also known as argmax/argmin

​

• Ex: Return the person with the highest salary for each job type

The Witnessing Problem

10

(AGAIN) Witnessing (i.e. argmax)

Find the student who is taking the most classes.

Student(stu_name, 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);

11

Witnessing (i.e. argmax)

Find the student who is taking the most classes.

Student(stu_name, 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));

12

Alternative to “ALL”

Worksheet