1 of 26

CSE 414: Section 4

RA + Database Design Theory

October 22nd, 2026

2 of 26

Announcements

Homework 3 due 10/29 (Next Thursday)

3 of 26

Relational Algebra

4 of 26

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

4

5 of 26

RA Operators

5

Operator	Symbol	Description
Selection	σ (sigma) / WHERE	Filters rows that satisfy a condition.
Projection	π (pi) / SELECT	Chooses specific attributes (columns). Eliminates duplicates in pure RA.
Union	∪ / UNION	Combines tuples from both relations; removes duplicates.
Difference	− / EXCEPT	Tuples in R1 that are not in R2.
Intersection	∩ / INTERSECT	Tuples appearing in both relations.
Cartesian Product	× / CROSS JOIN	All combinations of tuples from R1 and R2.

6 of 26

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

6

7 of 26

Format

_{Follows FWGHOS structure}

7

8 of 26

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

8

9 of 26

Query Plans (Example SQL -> RA)

1. FROM + WHERE

Join R and T using the matching b values

9

10 of 26

Query Plans (Example SQL -> RA)

2. GROUP BY

Group by R.b and T.c, calculating the maximum of T.a

10

11 of 26

Query Plans (Example SQL -> RA)

3. HAVING

Keep only groups where the calculated maximum exceeds 99

11

12 of 26

Query Plans (Example SQL -> RA)

4. SELECT

Keep the requested columns

12

13 of 26

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

π_{R.b, T.c, T_max}(σ_{T_max>99}(ɣ_{R.b, T.c, max(T.a)->T_max}(R ⨝_R.b=T.bT)))

13

14 of 26

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

);

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!

15 of 26

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

16 of 26

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;

16

π_R2.a

17 of 26

Database Design

17

Database Design

Database Design or Logical Design or Relational Schema Design is the process of organizing data into a database model.

Consider what data needs to be stored and the interrelationship of the data.

Arbitrary Data

Database

There are no good or bad designs, just tradeoffs.

Design Section

18 of 26

Data Relationship Discovery

How do we find relationships between attributes?

Flights dataset:

Did you know that every canceled flight�has an actual_time of 0?

Domain approach
Data mining approach

18

Design Section

19 of 26

Data Relationship Discovery

Domain approach:

Before looking at the data, �think about the domain

Research the domain and realize that �canceled flights have a 0 flight time!

19

Design Section

20 of 26

Data Relationship Discovery

Data mining approach:

Don’t worry about the domain, �just find patterns in the data

Look at the data and notice that every time canceled = 1, then actual_time = 0.

SELECT DISTINCT actual_time

FROM Flights

WHERE canceled = 1;

The only actual_time value is 0

20

Design Section

21 of 26

Data Relationship Discovery

How do we find relationships between attributes?

21

Domain Approach

E/R Diagrams

Data Approach

Functional Dependencies (FDs)

Boyce-Codd Normal Form (BCNF)

Design Section

22 of 26

ER Diagrams

Visual graph of entities and relationships

22

Product

Company

Person

employs

buys

makes

price

name

ceo

name

address

name

id

Design Section

23 of 26

Relationships

one-one: ssn - UW student id
one-many: ssn - phone #
many-many: store - product
is-a: computer - PC and computer - Mac
has-a: country - city

What country does the city of Cambridge belong to?

�

23

“at most one”

“exactly one”

is a

“subclass”

no constraint

other constraint

Design Section

24 of 26

E/R Demo

Create an ER diagram containing the following:

The id, name, gender, country of birth, �and country region (continent) of birth for students and faculty
The major of students
The salary of faculty
The courses that each student takes
The department each course is offered in

24

Design Section

25 of 26

E/R Demo – Sample Solution

25

The id, name, gender, country of birth, and country region of birth for students and faculty

The major of students

The salary of faculty

The courses that each student takes

The department each course is offered in

Design Section

26 of 26

E/R Demo – Sample Solution

26

The id, name, gender, country of birth, and country region of birth for students and faculty

The major of students

The salary of faculty

The courses that each student takes

The department each course is offered in

Country (name, region)

People (id, country_name, gender, p_name)

Faculty (People.id, salary)

Student (People.id, major)

Course (courseID, dept)

Took (Student.People.id, Course.courseID)

�

Design Section