CSE 344: Section 5

BCNF, Relational Algebra

October 26th, 2023

​

Announcements

Announcements

• Homework 5:
• Due at 10:00 pm on Tuesday, October 31st
• Focus on Relational Algebra and Cardinality Estimation

​

​

​

Boyce-Codd Normal Form (BCNF)

Motivation of BCNF

Recall the three anomalies:

• Redundancy anomaly
• Update anomaly
• Deletion anomaly

​

If a relation is in BCNF, then it does not have these anomalies

​

If it is not in BCNF, then it does have these anomalies

​

BCNF Algorithm

​

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

• Example: We know that popularity determines rec (ex: Okay = N, Respectable = N, Poppin = Y)
• What if we want to update the rec so that a popularity = ‘Respectable’ has rec= ‘Y’
• UPDATE Restaurant

SET rec? = ‘Y’

WHERE popularity = ‘Respectable’;

​

1. How many tuples in the Restaurant table do we need to update? How can we reduce this number?

​

Restaurant

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

rating⁺ = rating, popularity, rec?

Restaurant

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

R₂

R₁

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

R₃

R₄

Example: BCNF Decomposition

Restaurant(id,name,rating,popularity,rec)

1. id -> name, rating
2. rating -> popularity
3. popularity -> rec?

Restaurant

rating⁺ = rating, popularity, rec

R₁(rating,popularity,rec?)

R2(rating,id,name)

popularity⁺ = popularity, rec?

R₂

R₄(popularity,rating)

R₃(popularity,rec?)

R₃

R₄

R2, R3, R4 is the normalized database schema. No more anomalies!

Example: BCNF Decomposition

Now when we update the rec? so that a popularity = ‘Respectable’ has rec?= ‘Y’

UPDATE R3 SET rec? = ‘Y’ WHERE popularity = ‘Respectable’;

​

• Now we only update 1 tuple in the R3 table so we have reduced redundancy, and therefore avoid redundancy anomalies, update anomalies and deletion anomalies

R₂

R₃

R₄

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

15

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

16

Format

• _{Follows FJWGHOS structure}

17

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

18

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

19

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

);

​

20

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

21

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

EXCEPT

SELECT R1.a FROM Table_R R1, Table_S S

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

22

π_R2.a

SQL TO RA

General Approach

• _{Follows FJWGHOS structure}

24

Subqueries in FROM to RA

Relational Algebra

84

Subqueries in FROM to RA

Relational Algebra

85

Subqueries in FROM to RA

Relational Algebra

86

Subqueries in FROM to RA

Relational Algebra

87

Subqueries in FROM to RA

Relational Algebra

88

Subqueries in WHERE/HAVING

Relational Algebra

99

Subqueries in WHERE/HAVING

Relational Algebra

100

Subqueries in WHERE/HAVING

Relational Algebra

101

Subqueries in WHERE/HAVING

Relational Algebra

100

Subqueries in WHERE/HAVING

Relational Algebra

100

Query Optimizations

Rewrite Rules

• WHERE
• SELECT
• WHERE-AND
• WHERE-OR
• SELECT-WHERE
• WHERE-HAVING
• WHERE-JOIN

RA to RA: WHERE

Query Optimization

37

=

Idempotency

RA to RA: SELECT

Query Optimization

38

=

=

Idempotency

RA to RA: WHERE-AND

Query Optimization

39

=

=

Commutativity

RA to RA: WHERE-OR

Query Optimization

40

=

RA to RA: SELECT-WHERE

Query Optimization

41

=

Conditional* Commutativity�* if c only references attributes in A

RA to RA: WHERE-HAVING

Query Optimization

42

Schema(G,A)

Schema(G,A)

=

Conditional* Commutativity�* if c only references attributes in G

Conditional Commutativity

Query Optimization

43

RA to RA: WHERE-JOIN

Query Optimization

44

=

Distributive

Example Query Optimization

Query Optimization

45

Push Selections Down��σ_{C1 and C2}(R ⋈ S)

= σ_C1(σ_C2(R ⋈ S))

= σ_C1(R ⋈ σ_C2(S))

= σ_C1(R) ⋈ σ_C2(S)

Supplier(sid, name, city, state)

Supply(sid, pid, quantity)

Worksheet

Cardinality Estimation: Factors

T(R) = # tuples for relation R

V(R, a) = # of unique values of attribute a in relation R

Selectivity Formulas

• Selectivity Factor (X) → Proportion of total data needed
• Assuming uniform distribution of data values on numeric attribute a in table R, if the condition is:
• a = c → X ≅1 / V(R, a)
• a < c→ X ≅ (c - min(R, a))/ (max(R, a) - min(R, a))
• c1 < a < c2→ X ≅ (c2 - c1)/ (max(R, a) - min(R, a))
• cond1 and cond2 → X ≅ X1 * X2

Cardinality Estimation Example

Cardinality Estimation

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

SELECT sname

FROM Supply x, Supplier y

WHERE x.sid=y.sid AND x.pno=2 AND y.scity=’Seattle’ AND y.sstate=’WA’;

Supply(sid, pno, quantity)

Supplier(sid, sname, scity, sstate)

⋈sid=sid

Cardinality Estimation

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

⋈sid=sid

Cardinality Estimation

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

​

T(Supply) * 1 / V(Supply, pno)

= 4

​

​

T(Supplier) * 1 / V(Supplier, scity) * 1 / V(Supplier, sstate)

= 5

​

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

⋈sid=sid

Cardinality Estimation

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 5

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

⋈sid=sid

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

But wait a second…. Seattle is in Washington!

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

​

(4 * 50) /

max(

V(Supplier, sid),

V(Supply, sid)

)

​

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

​

(4 * 50) / 1000

​

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

T3 = 0.2

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

T3 = 0.2

No filtering at this step

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname

Cardinality Estimation

⋈supplier_id=sid

Supply Statistics:

• T(Supply) = 10000
• B(Supply) = 100
• V(Supply, pno) = 2500
• V(Supply, sid) = 1000

​

Supplier Statistics:

• T(Supplier) = 1000
• B(Supplier) = 100
• V(Supplier, scity) = 20
• V(Supplier, sstate) = 10
• V(Supplier, sid) = 100

​

T1 = 4

T2 = 50

T3 = 0.2

Total ≅ 0.2

Supply

σpno=2

Supplier

σscity=’Seattle’ Λ sstate=’WA’

πsname