Story so Far…..

​

Intro to Databases and Data Management Systems

​

Conceptual modeling using ER

​

Relational Model

​

Mapping ER → Relations

​

Preview of SQL to support database creation

​

NEXT: More general forms of constraints and a bit more about relational design, and then relational algebra enroute to learning SQL query language!

​

​

1

More Constraints in the Relational model …

• Functional dependencies, multi-valued dependencies, conditional functional dependencies, denial constraints, join constraints, ….

​

2

2

Functional Dependencies

​

• Relation R(A1,...,An, B1,...,Bm, C1,...,Cp)

​

• Definition: A1,...,An functionally determine B1,...,Bm denoted by

(A1,...,An → B1,...,Bm) iff

for any two tuples r1 and r2 in R,

r1(A1,...,An ) = r2(A1,...,An ) implies r1(B1,...,Bm) = r2(B1,...,Bm)

​

​

• A superkey → all attributes of the relation. (by definition)

​

• In general, the left-hand side of a FD may not be a superkey.

3

3

Example

• Illegal

4

4

Take(StudentID, CID, Semester, Grade)

FD: (StudentId,Cid,semester) → Grade

What if FD: (StudentId, Cid) → Semester?

Illegal

“Each student can take a course only once.”

Types of Functional Dependencies

• Trivial Dependencies:
• Those that are true for every relation

​

• X1X2…Xn→Y1 Y2…Ym is trivial if Y’s are a subset of the X’s.

Example: AB→A

​

• Nontrivial Dependencies:
• if at least one of the Y’s are not among the X’s.

Examples: AB→AC

​

• Completely Nontrivial
• if none of the Y’s is one of the X’s.
• Example: AB→C

​

We can always change a set of FDs to an equivalent set that are completely non-trivial.

5

functional dependencies can help determine if relational representation stores data redundantly!

​

Good Design Principle: Avoid redundancy

Why?

Wastage of Storage

Anomalies during modifications

Increased programming benefits to ensure consistency

​

​

​

​

6

FD can lead to Redundancy

​

• FD :
• Student → project
• project → date

​

• Even if we did not store 11/16/2021 as a date with Stefan’s tuple, we could derive it given the FD (hence redundant representation)

Redundancy in turn leads to Anomalies

​

• Update Anomaly:
• if we modify presentation date for the Document Stores project, we need to modify the date in each of the tuples in which it is stored (one per member). Else, database will be inconsistent.

Error in

Updating. Forgot to update all entries

More Anomalies...

• Insertion Anomaly: how to insert that the presentation on vector databases has been set for 12/1/2021 without associating any students first with the project. (possible solution: use null values in the student field)

�More Anomalies ...

• Deletion Anomaly:how to delete the fact that monica dropped out of the project without deleting information about the vector dbms project. (possible solution: use null values in the student field)

Redundancy and FDs

• Example above, redundancy arises due to FD project → date

​

• If the FD did not hold, there would be no redundancy. Why?

​

​

When does a relation contain no redundancy due to FDs?

Assume functional dependency: X → Y

Since t1[X] = t2[X], we have that t1[Y] = t2[Y] (potential redundancy!)

​

However, if X is a superkey, then t1[Z] = t2[Z], thus, z2 == z1

​

Since x1 = x2, y1 = y2 and z1 = z2 , then , t2 == t1

​

Since R is a set (no duplicate tuples), so such a t2 cannot exist!

Thus, R does not contain redundancy if for each FD X → Y, when X is a superkey.

Such a relational scheme is said to be boyce-codd normal form

z1

X

Boyce Codd Normal Form

Let R be a relation scheme. F be the functional dependency set. R is in BCNF if for all functional dependencies X → Y in F, either

Y is a subset of X (i.e., trivial dependency), or

X is a superkey.

X is a superkey for R if X → A1, A2, ..., An , where A1,A2, ....An is the set of attributes of R.

Example (BCNF Violation)

• FD :
• Student → project
• Student → date
• Project → date

​

project is not superkey!

Example (BCNF Violation)

• FD :
• Student → project
• Student → date
• Project→ date

Now this is in BCNF since Student is a superkey

Checking for BCNF

Given a relation and corresponding functional dependencies, how do we check if it is in BCNF or not?

​

To do so, for each functional dependency X → Y which is non-trivial, we need to check of X is a superkey.

​

To check if X is superkey…..

we need to probe a bit deeper into functional dependency theory….

16

Reasoning about FD’s

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

​

• Functional dependencies:
• A → B (fd1)
• B → C (fd2)
• Then we can show the following FD must hold:
• A → C (fd3)
• Proof:

Suppose fd3 does not hold.

So there are tuples r1, r2 in R: r1[A] = r2[A], but r1[C] <> r2[C]

Because of fd1 and r1[A] = r2[A]: r1[B] = r2[B]

Because of fd2 and r1[B] = r2[B]: r1[C] = r2[C]

Contradiction! So fd3 must hold!

17

17

Thus, given a set of FDs we can derive additional FDs!!

Armstrong’s Axioms: Inferring Additional FDs

​

• Reflexivity:
• If Y is a subset of X, then X →Y.
• Example: AB→A, ABC→AB, etc.

​

• Augmentation:
• If X→Y, then XZ→YZ.
• Example: If A→B, then AC→BC.

​

• Transitivity:
• If X→Y, and Y→Z, then X→Z.
• Example: If AB→C, and C→D, then AB→D.

​

18

18

Importance of Armstrong’s Axioms (AAs)

• Correctness:
• AAs are sound:
• If X→Y is deduced using AAs from F, then X→Y holds over any relation R on which the FDs in F hold.
• AAs are complete:
• If FD X→Y actually holds on the database , then it can be deduced using AAs over F.

​

19

19

More Rules Derived from AAs

• Union Rule:
• If X→Y, X→Z, then X→YZ
• Proof:
• Since X→Y, using augmentation, X→XY (fd1)
• Since X→Z, using augmentation, XY→YZ (fd2)
• Using (fd1) and (fd2) and transitivity: X→YZ.
• Pseudo-Transitivity Rule:
• If X→Y, WY→Z, then WX→Z
• Proof:
• Since X→Y, using augmentation: XW→YW (fd3)
• Given WY→Z and (fd3), using transitivity: WX→Z.

20

20

Closure of FD Set

• Definition: Let F be a set of FDs of a relation R. We use F+ to denote the set of all FDs that must hold over R, i.e.:
• F+ = { X → Y | F logically implies X → Y}
• F+ is called the closure of F.
• Example: F = {A→B, B→C}, then A→C is in F+.

​

21

21

Can we compute F+ -- that is the set of all functional dependencies implied by F?

Using Armstrong’s Axioms to Derive F+

• Since AA are sound and complete, they provide a mechanism to compute F+
• Keep using AA until convergence:

i.e., as long as they keep generating additional FDs.

​

​

We can redefine F+ as all the FDs that follow from F using AAs.

​

22

22

How big can F+ be?

​

• F+ could have many FDs!
• Example:
• Let F = {A→B1, A→B2, ..., A→Bn}, then any A→Y (Y is a subset of {B1, B2, ..., Bn}) is in F+.
• Cardinality of F+ is more than 2^n.
• Fortunately, a given X→Y can be tested efficiently as we will see later

23

23

Back to our problem of checking if a relation is in BCNF…..

Checking for BCNF

Given a relation and corresponding functional dependencies, how do we check if it is in BCNF or not?

​

To do so, for each functional dependency X → Y which is non-trivial, we need to check of X is a superkey.

​

But how do check if X is superkey…..

to learn how to do so, we need to probe a bit deeper into functional dependency theory….

24

Testing if X is a superkey

• Let R be a relation scheme and F be the set of functional dependencies.

​

• X is a superkey if X →A1, A2, ..., An holds, where A1, A2, ..., An are the set of attributes in R.

​

• Hence, we can test if X is a superkey by testing for the membership of X → A1, A2, ..., An in F+.

​

Testing if X → Y is in F+ �

First compute F+ from F using Armstrong Axioms.

​

Not very practical since the size of F+ can be really very large.

​

​

In general, computing F+ might take exponential time!

​

Membership of F+�

• Testing for membership in F+ can be done efficiently without computing F+.

​

• Let us first define the notion of a closure of a set of attributes

​

Closure of attribute set:

​

• Let R be a relation scheme and F be the functional dependency set.

​

• Closure of a set of attributes X with respect to F denoted by X+ is the set of attributes Ai of R such that X → Ai can be derived using Armstrong Axioms.

​

• Note: X →Y holds over R if and only if Y is a subset of X+.

​

Membership of F+�

Since X →Y holds over R if and only if Y is a subset of X+,

we can check if X →Y holds by computing X+ and testing if Y is a subset of X+.

​

Computing X+

X+ = X

repeat

oldX+ = X+

for each fd Y→ Z in F do

if (Y is a subset of oldX+) then

X+ = X+ union Z

until (oldX+ == X+)

​

maximum number of iterations = cardinality of F times the number of attributes in R!

(polytime)

Example�

Let the set F contain the following fds:

AB → C, D →EG, C→A, BE→C, BC →D CG →BD, ACD→ B, CE→AG

​

Let X = BD. Compute X+.

iteration 1: X+ = {BD}

iteration 2: X+ = {BDEG} (due to dependency 2)

iteration 3: X+ = {BDCEG} (due to dependency 4)

iteration 4: X+ = {BCDEGA} (due to dependency 8)

iteration 5: X+ = {BCDEGA}

Algorithm exits the loop since no new attribute added in last iteration and (BD)+ = {ABCDEG}

​

​

BCNF Examples

Is the following relation in BCNF.

• relation R(A, B, C, D)
• FD = {A → B, B → C, C → D, D → A}

​

To check, for each FD, we determine if the left hand side is a key.

​

Is A a key?

Execute the algorithm to determine {A}+

Step 1: {A}+ = {A}

Step 2: {A}+ = {A,B}

Step 3 : {A}+ = {A,B,C}

Step 4: {A}+ = {A,B,C,D}

Thus, A → ABCD Hence, the constraint A→B does not violate BCNF.

What about the other FDs -- B→C, C→D, D→A? check to make sure that they also do not violate BCNF

​

Another Example

• Now check the following Example.
• relation R(A, B, C, D)
• FD = {A → B, B → C, C → D}

​

​

​

​

Interesting Aside

​

​

​

• Any table with only 2 attributes is always in BCNF! Why?

​

​

​

So far …

We have just learnt how to check if a relation contains redundancy.

​

But what do we do if indeed a relation contains redundancy?....

​

​

33

Schema Normalization

• Given a relational scheme R which is not in BCNF (thus, contains redundancy) can we “decompose” the relational schemes to
• remove redundancy
• remove anomalies

​

• Results in a semantically equivalent relational scheme that represents the same information as the original:
• must be able to reconstruct the original from the decomposed relations by joining them (lossless join property)

​

Lossless Joins

• Let R be a relation schema and let (R1, R2, ... Rn) be its decomposition.
• Let r be any instance of R. Thus, r[R1], r[R2], ... r[Rn] are instances of R1, R2, ..., Rn
• The decomposition should be such that we can reconstruct relation r from r[R1], r[R2], ... r[Rn] using natural joins

r is a subset of r1 r2

hence the join is lossy!

Testing for Lossless Decomposition

Let R be a relation with the set of functional dependencies F.

Let R1 and R2 be a decomposition of R.

Is the decomposition lossless?

To check if the decomposition is lossless, check if either of the following holds:

​

What if R is decomposed into more than 2 subrelations.

Consider the decomposition as a sequence of binary decompositions and test for losslessness at each step.

(this may not always work)

Read the more general algorithm in the Book!

Schema Normalization

Given a relation R which is not in BCNF, we want to decompose it in such a way that the subschemes do not contain redundancy and the decomposition is lossless.

​

this will take us deeper into relational design theory --- we will do so towards the end if we have time.

37