2 of 27

Announcements

Quiz on 11/3

Covers HW 1 - HW 3 and relational algebra concepts
Takes place on Gradescope
Unlimited submissions from 1am Thursday - 11am Friday, not timed

HW4 due on Monday 11/7 @ 11pm

More theory-focused, less SQL queries

HW3 grades released soon
HW2 regrade requests responded to!

4 of 27

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.

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.

DEPENDENCY != CAUSATION

*in other words: A determines B, or A is kinda sorta a key for B

5 of 27

Closures

Goal:

We want everything that an attribute/set of attributes determines

Observation:

If we have A → B and B → C, then A → C
So really, A → B, C
Add A to the RHS so A → A, B, C
Formally, the closure of A is written as {A}⁺ = {A, B, C}

6 of 27

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, but a superkey is not necessarily a minimal key.

7 of 27

Boyce-Codd Normal Form (BCNF)

A relation R is in BCNF if every set of attributes in R is either a superkey or its closure is the same set (trivial FD).

*that is, either {a}+ -> a OR {a}+ -> {all cols}, where a is any col in the table

BCNF reduces redundancy at the expense of creating additional tables.
BCNF may have several correct decompositions.
Some functional dependencies may be lost.

8 of 27

Boyce-Codd Normal Form (BCNF)

Not BCNF! SSN is not a trivial FD or a superkey

9 of 27

BCNF Decomposition Algorithm

X +

10 of 27

BCNF Decomposition Algorithm

C = the set of all attributes in the relation R

Look for an attribute (or a set of attributes) that meets the following conditions (non-BCNF flag!):

X⁺ != X
X⁺ != C

If such attribute exists, it is a violation of the BCNF condition; decompose R:

R1 = X⁺
R2 = (C - X⁺) union (X)
Normalize each table (recursive call)

Else, the table is in BCNF

11 of 27

Example

Relation: R (A, B, C, D, E)

FDs:

A → E
BC → A
DE → B

Goal: Decompose R into BCNF

12 of 27

Example

R (A, B, C, D, E)

R (A, E)

R (A, B, C, D)

R (B, C, A)

R (B, C, D)

A⁺ = {A, E}

BCNF compliant

{B, C}⁺ = {B, C, A}

13 of 27

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
R2 does not satisfy BCNF because: {B,C}⁺ = {B,C,A}

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

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

14 of 27

Motivation for Transactions

15 of 27

ACID

Atomic�Consistent�Isolated�Durable

Everything a concurrent database user wants…

16 of 27

How do ACID properties help us?

Ensure that a transaction maintains database integrity
ACID compliance matters to important databases ($$$)
In this section: delve into the DB Internals required to guarantee ACID

17 of 27

Atomicity

What? “Atom” - a transaction is indivisible; data operations inside the transaction work in an all or nothing fashion

How? Transaction commit and rollback

Example: Transfer of funds from one account to another involves an atomic transaction that includes operations of debit and credit

18 of 27

Consistency

What? Only data operations that comply with database validity constraints are allowed.

Once a transaction is completed, it must not leave the database incomplete or inconsistent.

How? Enforcement of consistency rules upon data entry/updation

Example: A database having both first and last name fields will not accept if you enter only one of those - must enter both for the transaction to be complete

19 of 27

Isolation

What? The appearance of a transaction happening by itself irrespective of what other transactions are happening concurrently

How? User views the database that was present right before the view request is made and any further transactions that are in process after it are ignored

Example: A teller looking up a balance must be isolated from a concurrent transaction involving a withdrawal from the same account

20 of 27

Durability

What? Once a transaction is complete the information as changed will survive failures of any kind

How? Creation of data “mirrors”

Example: Trying to make an update that leads to a system failure should not tamper with any of the previous data and transactions

21 of 27

Txn Perspective

A database is a collection of "elements" that can be written to or read from.

Operation - A read or write to an element (later: or an insert or delete)

example of read (R): SELECT
example of write(W): UPDATE

Example: What operation does the following SQL query contain?�SELECT cases FROM Country WHERE cname = ‘France’;

22 of 27

Txn Perspective

A database is a collection of "elements" that can be written to or read from.

Operation - A read or write to an element (later: or an insert or delete)

Example: What operation does the following SQL query contain?�SELECT cases FROM Country WHERE cname = ‘France’;

Answer: R(Country) or R(France), depending on whether the "element" is a table or a row (assuming cname is a key). Let's go with the finer-grained element.

23 of 27

Practice - convert SQL to operations

Txn 1:

1a) x = SELECT cases FROM Country WHERE cname = ‘France’;

1b) x = x + 200;

1c) UPDATE Country SET cases = `x` WHERE cname = ‘France’;

Txn 2:

2a) y = SELECT cases FROM Country WHERE cname = ‘Spain’;

2b) y = y / 5;

2c) z = SELECT cases FROM Country WHERE cname = ‘France’;

2d) UPDATE Country SET cases = `y + z` WHERE cname = ‘France’;

24 of 27

Practice - convert SQL to operations

Txn 1:

1a) x = SELECT cases FROM Country WHERE cname = ‘France’;

1b) x = x + 200;

1c) UPDATE Country SET cases = `x` WHERE cname = ‘France’;

Txn 2:

2a) y = SELECT cases FROM Country WHERE cname = ‘Spain’;

2b) y = y / 5;

2c) z = SELECT cases FROM Country WHERE cname = ‘France’;

2d) UPDATE Country SET cases = `y + z` WHERE cname = ‘France’;

1a) R(France)

1b)

1c) W(France)

2a) R(Spain)

2b)

2c) R(France)

2d) W(France)

25 of 27

Definitions

Operation -

Transaction -

Schedule -

Serial schedule -�

Serializable schedule - �

26 of 27