CS计算机代考程序代写 Functional Dependencies database flex algorithm Functional Dependency

Functional Dependency

Functional
Dependency

1

Functional Dependency
A “good” database schema should not lead to update anomalies.

• update anomalies,

• functional dependencies,

• Armstrong Axioms,

• closures.

2

Update Anomalies

Redundancy in a database means storing a piece of data more than once.

Redundancy is often useful for efficiency and semantic reasons, but

creates the potential for consistency problems.

A poor redundancy control may cause update anomalies.

Consider the example relation below (adapted from “An Introduction to

Database Systems” by Desai):

3

Modification anomalies: e.g. Jones’s phone number appears 3 times. When a

phone number is changed, it must be changed in all 3 places, or the data will be

inconsistent.

4

STUDENTS

Name Course Phone_no Major Prof Grade

Jones 353 237-4539 Comp Sci Smith A

Ng 329 427-7390 Chemistry Turner B

Jones 328 237-4539 Comp Sci Clark B

Martin 456 388-5183 Physics James A

Dulles 293 371-6259 Decision Sci Cook C

Duke 491 823-7293 Mathematics Lamb B

Duke 356 823-7293 Mathematics Bond UN

Jones 492 237- 4539 Comp Sci Cross UN

Baxter 379 839-0827 English Broes C

Insertion anomalies:

• If Jones enrolls in another course, and a different phone number is

entered, again the data will be inconsistent.

• Also, if the only way that the association between course and

professor is stored in this relation, we can only enter the association when

someone enrolls in the course.

Deletion anomalies: If the last student in a course is deleted, the

association between professor and course is lost.

5

Update Anomalies

Functional dependencies
A function f from S1 to S2 has the property

A generalization of keys to avoid design flaws violating the above rule.

Let X and Y be sets of attributes in R.

X (functionally) determines Y , X → Y , iff t1[X] = t2[X] implies t1[Y ] = t2[Y ].

i.e., f (t(X)) = t [Y]

We also say X →Y is a functional dependency, and that Y is functionally dependent on X.

X is called the left side, Y the right side of the dependency.

6

𝑖𝑓 𝑥, 𝑦 ∈ 𝑆1 and 𝑥 = 𝑦, then 𝑓(𝑥) = 𝑓(𝑦) .

• For every Name, there is a unique Phone_no and Major, assume Name is
unique;

• For every Course, there is a unique Prof;

• For every Name and Course, there is a unique

Grade.

7

Examples

8

In this example:

{Name} →{Phone_no , Major}

{Course} → {Prof}

{Name , Course} → {Grade}

We can also show these in a diagram like this one:

Notice that other FD’s follow from these:

{Name} → {Major}

{Course , Grade} → {Prof , Grade}

8

Name Course Phone_no Major Prof Grade

Let F be a set of FD’s.

Definition 1: X → Y is inferred from F (or that F infers X → Y ), written in

F |= X→ Y

if any relation instance satisfying F must also satisfy X → Y .

Impossible to list every relation to verify if X → Y is inferred from F.

A set ρ of derivation rules are required, such that:

a X → Y is inferred from F according to Definition 1 iff it can be

derived using ρ.

9

Functional dependencies

Armstrong’s axioms (1974)

Notation: If X and Y are sets of attributes, we write XY for their union.

e.g. X = {A, B}, Y = {B, C}, XY = {A, B, C}

F1 (Reflexivity) If X ⊇ Y then X →Y .

F2 (Augmentation) {X → Y } |= XZ → Y Z.

F3 (Transitivity) {X → Y , Y → Z} |= X → Z.

F4 (Additivity) {X→ Y , X → Z} |= X → Y Z.

F5 (Projectivity) {X → Y Z} |= X → Y .

F6 (Pseudotransitivity) {X → Y , Y Z → W} |= XZ → W.

10

11

Example: Given F = {A → B,A → C,BC → D}, derive A → D:

1. A → B (given)

2. A → C (given)

3. A → BC (by F4, from 1 and 2)

4. BC → D (given)

5. A → D (by F3, from 3 and 4)

12

F4 (Additivity) {X→ Y , X → Z} |= X → Y Z.

F5 (Projectivity) {X → Y Z} |= X → Y .

F6 (Pseudotransitivity) {X → Y , Y Z → W} |= XZ → W.

In fact, F4, F5, and F6 can be derived from F1-F3.

Example: Prove {X→ Y , X → Z} |= X → Y Z.

1) X→ Y is given.

2) XX → XY (by F2); that is, X → XY

3) X → Z is given.

4) X Y → Y Z (by F2)

5) X → Y Z (by F3, 2) and 4))

We can prove that Armstrong’s axioms are sound and complete:

Sound: if F derives A →B by using Armstrong’s axioms, then F |= A →

B by Definition 1.

Complete: if F |= M → N by Definition 1, then F derives M → N by

using Armstrong’s axioms.

13

Armstrong’s axioms

Algorithm to Check a FD

Given F, how do we check if X →Y is in F+?

F+ denotes the smallest set of FD’s that

• contains F, and

• is closed under Armstrong’s axioms.

F+ is the closure of F.

14

15

F = { A → B, B → C, A → C }

F+ = {AB -> A, AB -> B, AB -> C, AC -> A, AC -> B,

AC -> C, ABC -> A, ABC -> B, ABC -> C, AB -> AB,

AB -> BC, AB -> AC, …….}

F+ always has an exponential size regarding |F|.

16

Too expensive to compute F+ to verify a membership.

Instead we can compute the closure X+ of X under F, X+ is the largest set of

attributes functionally determined by X.

It can be proven (using additivity) that

S1:

S2:

17

F = { A → B, BC → D, A → C }, compute {A}+

1st scan of F:

X+ := {A}

X+ := {A, B}

X+ := {A, B, C}

2nd scan of F:

X+ := {A, B, C, D }

3rd scan of F: no change, therefore the algorithm terminates.

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

Example:

X+ := X;

change := true;

while change do

begin

change := false;

for each FD W → Z in F do

begin

if (W ⊆ X+) and (Z X+) then do

begin

X+ := X+∪ Z;

change := true;

end

end

end

18

Algorithm to compute X+

Algorithm to Compute a Candidate Key

Given a relational schema R and a set F of functional dependencies on R.

A key X of R must have the property that X+ = R.

Algorithm to compute a candidate key

Step 1: Assign X a superkey in F.

Step 2: Iteratively remove attributes from X while retaining the property X+ =

R till no reduction on X.

The remaining X is a key.

19

20

R = {A, B, C, D} and F = { A → B, BC → D, A → C }

X = {A, B, C} if the left hand side of F is a super key.

A cannot be removed because {BC}+ = {B, C, D} ≠ R

B can be removed because {AC}+ = {A, B, C, D} = R

X = { A, C}

C can be further removed because {A}+ = {A, B, C, D}

X = {A}

Example: