Functional Dependency
Armstrong’s Axioms

Completeness

Functional Dependency
Armstrong’s Axioms

Functional Dependency (reminder)

Definition

Inference rules

Closure of F

Set of all FDs obtained by applying inferences rules on a basic set of FDs

Problem issues and solutions

Armstrong’s Axioms (reminder)

3 inferences rules for obtaining the closure of F

Properties of the Armstrong’s Axioms

They are a sound an complete set of inference rules

Proof of the completeness

Functional Dependency

A functional dependency (FD) has the form X  Y where X and Y are sets of attributes in a relation R

X  Y iff any two tuples that agree on X value also agree on Y value

X  Y if and only if:

for any instance r of R

for any tuples t1 and t2 of r

t1(X) = t2(X)  t1(Y) = t2(Y)

Inference of Functional Dependencies

Suppose R is a relation scheme, and F is a set of functional dependencies for R

If X, Y are subsets of attributes of R and all instances r which satisfy the FDs in F also satisfy X  Y, then say F logically implies X  Y, written F  X  Y

In other words, there is no instance that does not satisfy X  Y

Example

if F = { A  B, B  C } then F  A  C

if F = { S  A, SI  P } then

F  S I  AP, F  SP  SAP etc.

A

B

C

S

A

P

I

Functional Dependency

Problematic issue:

representing set of ALL FDs for a relation R

Solution

find a basic set of FDs

Use axioms for infering

represent the set of all FDs as the set of FDs that can be inferred from a basic set of FDs

Axioms

they must be a sound and complete set of inference rules

Set of Functional Dependencies
F*

Formal Definition

Informal Definitions

F* is the set of all FDs logically implied by F

... usually F* is much too large even to enumerate!

if F is a set of FDs, then F* { X  Y  F  X  Y }

F*

Usually F* is much too large even to enumerate!

Example (3 attributes, 2 FDs and 52 dependencies)

R=ABC and F ={ A  B, B  C } then F* is

A  S for all [subset of ABC]	8 FDs

B  BC, B  B, B  C, B  	4 FDs

C  C,	C  	2 FDs

AB  S for all subsets S of ABC	8 FDs

AC  S for all subsets S of ABC	8 FDs

BC  BC, BC  B, BC  C, BC  	4 FDs

ABC  S for all subsets S of ABC	8 FDs

A

B

C

F+
Armstrong’s Axioms

Axioms for reasoning about FDs

Definition

A1-3 are Armstrong’s axioms

F + is the set of dependencies which can be deduced from F by applying three inference rules:

A1: reflexivity	if Y  X then X  Y

A2: augmentation	if X  Y then XZ  YZ

A3: transitivity	if X  Y and Y  Z then X  Z

Armstrong’s Axioms

The theorem asserts that Armstrong’s axioms are a sound and complete set of inference rules

Sound: the Armstrong’s rules generate only FDs in F*

F+  F*

Complete: the Armstrong’s rules generate all FDs in F*

F*  F +

If complete and sound then F+ = F*

Here

Proof of the completeness

Armstrong’s Axioms

Additional rules derived from axioms

Union

if A  B and A  C, then A  BC

Decomposition

if A BC, then A  B and A  C

A

B

C

A

B

C

Completeness of the
Armstrong’s Axioms

Proving that Armstrong’s axioms are a complete set of inference rules

Armstrong’s rules generate all FDs in F*

Completeness of the
Armstrong’s Axioms

First define X+, the closure of X with respect to F:

X+ is the set of attributes A such that X  A can be deduced from Armstrong’s axioms

Note that we can deduce that X  Y for some set Y by consulting Armstrong’s axioms if and only if Y  X+

R=LMNO

X=L

F={L  M , M  N, O  N}

then X+ = L+ = LMN

L

M

N

O

Completeness of the
Armstrong’s Axioms

Note that we can deduce that X  Y for some set Y by consulting Armstrong’s axioms if and only if Y  X+

X  Y  F+  Y  X+

Y  X+ and suppose that A Y then X  A  F+ (definition of X+)

 A Y: X  A  F+

X  Y  F+ (union rule)

X  Y  F+  Y  X+

X  Y  F+ and suppose that A Y then X  A  F+ (decomposition rule)

A  X+ (definition of X+)

 A Y: A  X+

Y  X+

Completeness of the
Armstrong’s Axioms

Idea

To establish completeness, it is sufficient to show:

if X  Y cannot be deduced from Armstrong’s axioms
(so X  Y not in F+)
then there is a relational instance r for R in which all the dependencies in F are true, but X  Y does not hold
(so X  Y not in F*)

Completeness of the
Armstrong’s Axioms

Idea

If X  Y cannot be deduced from Armstrong’s axioms then there is a relational instance r for R in which all the dependencies in F are true, but X  Y does not hold

R=LMNO

X=L

F={L  M , M  N, O  N}

then X+ = LMN

L

M

N

O

L  O cannot

be deduced (not in F+)

Completeness of the
Armstrong’s Axioms

Suppose one can not deduce X  Y from Armstrong’s axioms

Consider the instances r for R with 2 tuples

(make the two tuples agree on X+ but disagree elsewhere)

0 0 … 0

1 1 …. 1

1 1 … 1

1 1 … 1

Other Attributes

Attributes of X+

Relational instance r for R with 2 tuples

L+ = LMN

Completeness of the
Armstrong’s Axioms

Check that all the dependencies in F are true:

Suppose that V  W is a dependency in F

If V is not a subset of X+, the dependency holds in r

If V is a subset of X+, then both X  V, and X  W can be deduced by Armstrong’s axioms. This means that W is a subset of X+, and thus V  W holds in r

0 0 … 0

1 1 …. 1

1 1 … 1

1 1 … 1

Other Attributes

Attributes of X+

Relational instance r for R with 2 tuples

Completeness of the
Armstrong’s Axioms

Check that all the dependencies in F are true

Illustration

O  N is a dependency in F but O is not a subset of X+, the dependency holds in r

M  N is a dependency in F and M is a subset of X+, then both L  M, and L  N can be deduced by Armstrong’s axioms. This means that N is a subset of X+, and thus M  N holds in r

R=LMNO

X=L

F={L  M , M  N, O  N}

then X+ = LMN

Completeness of the
Armstrong’s Axioms

Confirm that X  Y does not hold in r:

Recall that we can deduce that X  Y for some set Y by consulting Armstrong’s axioms if and only if Y  X+

By assumption, we can’t deduce that X  Y holds in r

Hence Y contains an attribute not in the subset X+, confirming that X  Y does not hold in r

0 0 … 0

1 1 …. 1

1 1 … 1

1 1 … 1

Other Attributes

Attributes of X+

Relational instance r for R with 2 tuples

Completeness of the
Armstrong’s Axioms

We have proved the correctness (last colstructie) and the completeness of Armstrong’s Axioms:

How to prove the soundness of another set of rules?

From the definition

Deduce from the Armstrong’s Axioms

How to disprove their soundness

By a counter example

Completeness of the
Armstrong’s Axioms

How to prove completeness of another set of rules?

Repeat the given proof

Deduce Armstrong’s Axioms from them

How to disprove completeness

By showing (via a counterexample)
that some consequence of Armstrong's rules
cannot be deduced from them

Completeness of the
Armstrong’s Axioms

Exercise

Are the following set of rules a sound and complete set of inference rules?

S1: X  X

S2: if X  Y then XZ  Y

S3: if X  Y, Y  Z then XW  ZW

(This is a typical exam question )

Solution (soundness)

so by A1

then by A2

so by A1

if

so by A3

if

then by A3

so by A2

S1

S2

S3

Solution (completeness)

so {S1} Y  Y,

{S2}YZ  Y

if

then

hence X  Y

{S1} X  X, X  Y, so

{S3} XZ  YZ

if

then

hence

A1

A2

A3

if

then {S3}

hence

Completeness of the
Armstrong’s Axioms

Exercises

Are the following set of rules a complete set of inference rules?

1

1

1

1

1

1

1

1

1

1

1

Ø A B AB

Ø A B AB

Suppose

Apply above rules exhaustively

Hence: answer is NO

obtained from A1-3
but not from R1-3

R1: X  X
R2: X  Y then XZ  Y
R3: X  Y, Y  Z then X  Z

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Example

----------

Introduction

--------------

Presentation

---------------

Example

----------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

Introduction

--------------

Presentation

---------------

colstructie 5

pthiran

2004-04-13T09:36:11

Paul De Bra