CSE 414: Section 8

BCNF and Views

May 23rd, 2019

Functional Dependencies

A functional dependency (FD) for relation R is a formula of the form A → B

where A and B are sets or individual attributes of R.

​

The meaning of the functional dependency is that for every value of A, there is a unique value of B. We say the FD holds for R if, for any instance of R, whenever two tuples agree in value for all attributes of A, they also agree in value for all attributes of B.

​

Logistics

Homework:

• HW6 is due Friday (tomorrow)!
• Please don’t add Spark package and input data in the git repos, it causes huge download times for us when we grade

​

Webquizzes:

• Webquiz 6 is due Saturday night! Relies on content from Friday’s lecture and today’s section!

​

​

FD Example

For the relation Student(studentID, name, DateOfBirth, phoneNumber), assuming each student has only one name, then the following functional dependency holds

{studentID} → {name, DateOfBirth}

​

However, assuming a student may have multiple phone numbers, then the FD

{studentID} → {phoneNumber} does not hold for the table.

​

Inference Rules and Trivial FDs

Given attributes a, b, c for a relation R, they following inference rules hold for FDs

• a → a (trivial FD)
• If a → b & b → c then a → c
• If a → b & c → d then a,c → b,d

​

​

A trivial FD is one where the RHS is a subset of the LHS. That is, every attribute on the RHS is also on the LHS. For example, the two FDs below are trivial:

{name} → {name}

{studentID,name} → {name}

​

​

​

Note :- Trivial FDs do not provide real restrictions on the data in the relation, and they are usually ignored.

Outline

BCNF decomposition

• Check whether chosen FD violates BCNF
• Use any FD that violates BCNF to decompose.

View construction and query processing� 1) From vertically partitioned tables� 2) From horizontally partitioned tables

​

Keys

We call an attribute (or a set of attributes) that determines all other attributes in a schema to be a superkey.

If it is the smallest set of attributes (in terms of cardinality) that does this we call that set a minimal key or just key

By definition, all minimal keys are superkeys… however a superkey is not necessarily a minimal key.

Superkeys and Minimal Keys

R(A, B, C, D)

A -> B

C -> D

​

Question: is {A, C} a superkey, minimal key, or both?

​

Question: is {A, B, C, D} a superkey, minimal key, or both?

​

Question: is {A, C, D} a superkey, minimal key, or both?

Superkeys and Minimal Keys

R(A, B, C, D)

A -> B

B -> C, D

​

Question: is {A, B} a superkey, minimal key, neither, or both?

​

Question: is {B} a superkey, minimal key, neither, or both?

​

Question: is {A} a superkey, minimal key, neither or both?

Closure Algorithm

Goal:

We want everything that an attribute/set of attributes determine

Observation:

• If we have A -> B and B -> C, then A -> C
• So really, A -> B and C
• Formal notation is {A}⁺ = {A, B, C}
• Since the closure of A is all attributes, A is a key

​

Conceptual Design

SSN Name, City

Conceptual Design

Anomalies:

• Redundancy = repeat data

• Update anomalies = what if Fred moves to “Bellevue”?

• Deletion anomalies = what if Joe deletes his phone number?

​

Conceptual Design

The BCNF (Boyce-Codd Normal Form) ---- A relation R is in BCNF if every set of attributes is either a superkey or its closure is the same set

BCNF Decomposition Algorithm

Normalize(R)

find X s.t.: X ≠ X⁺ and X⁺ ≠ [all attributes]

if (not found) then R is in BCNF

let Z = [all attributes] - X⁺

decompose R into R1(X⁺) and R2(X ∪ Z)

Normalize(R1); Normalize(R2);

​

X +

Example

The relation is R (A, B, C, D, E)

FDs : A → E, BC → A, and DE → B

Question : Decompose R into BCNF.

Solution

Notice that {A}⁺ = {A,E}, which violates the BCNF condition.

We split R to R1(A,E) and R2(A,B,C,D).

R1 satisfies BCNF now, but R2 does not because: {B,C}⁺ = {B,C,A}.

Notice that there is no E in R2 table so we don't need to consider the FD DE → B!

Split R2 to: R21(B,C,A) and R22(B,C,D)

Lossless Decomposition

Consider the relation R(A,B,C,D,E)

FDs: {AB → C, BC → D, AD → E}

S1 = Π_ABC(R), S2 = Π _BCD(R), S3 = Π _ADE(R)

We need to show that R= S1 ⋈ S2 ⋈ S3

​

​

S1(ABC)

S2(BCD)

S3(ADE)

Vertical Partitioning

Vertical Partitioning

Vertical Partitioning

SELECT address

FROM Resumes

WHERE name = ‘Sue’

Vertical Partitioning Applications

• Advantages
• Speeds up queries that touch only a small fraction of columns
• Single column can be compressed effectively, reducing disk I/O
• Disadvantages
• Updates are very expensive!
• Need many joins to access many columns
• Repeated key columns add overhead

Horizontal Partitioning

Horizontal Partitioning

Horizontal Partitioning

Horizontal Partitioning Applications

• Performance optimization
• Especially for data warehousing
• E.g., one partition per month
• E.g., archived applications and active applications
• Distributed and parallel databases