Database - Discussions

Slide 15- 1

Relational Database Design Algorithms and

Further Dependencies

Dr. Buleje

Slide 15- 2

Outline

 1. Further topics in Functional Dependencies

 1.1 Inference Rules for FDs

 1.2 Equivalence of Sets of FDs

 1.3 Minimal Sets of FDs

 2. Properties of Relational Decompositions

 3. Algorithms for Relational Database Schema Design

 4. Nulls, Alternative Relational Designs

 5. Multivalued Dependencies and Fourth Normal Form – further

discussion

Slide 15- 3

1. Functional Dependencies : Inference

Rules, Equivalence and Minimal Cover

 We discussed functional dependencies in the last

chapter.

 To recollect:

 A set of attributes X functionally determines a set

of attributes Y if the value of X determines a

unique value for Y.

1.1 Inference Rules for FDs (1)

 Definition: An FD X  Y is inferred from or implied by

a set of dependencies F specified on R if X  Y holds in

every legal relation state r of R; that is, whenever r

satisfies all the dependencies in F, X  Y also holds in r.

 Given a set of FDs F, we can infer additional FDs that hold whenever the FDs in F hold

Slide 15- 4

Inference Rules for FDs (2)

 Armstrong's inference rules:

 IR1. (Reflexive) If Y subset-of X, then X → Y

 IR2. (Augmentation) If X → Y, then XZ → YZ

 (Notation: XZ stands for X U Z)

 IR3. (Transitive) If X → Y and Y → Z, then X → Z

 IR1, IR2, IR3 form a sound and complete set of inference rules

 These are rules hold and all other rules that hold can be deduced from these

Slide 15- 5

Inference Rules for FDs (3)

 Some additional inference rules that are useful:

 Decomposition: If X → YZ, then X → Y and X → Z

 Union: If X → Y and X → Z, then X → YZ

 Psuedotransitivity: If X → Y and WY → Z, then WX → Z



Slide 15 - 6

Closure

 Closure of a set F of FDs is the set F+ of all FDs

that can be inferred from F

 Closure of a set of attributes X with respect to F

is the set X+ of all attributes that are functionally

determined by X

Slide 15 - 7

1.2 Equivalence of Sets of FDs

 Two sets of FDs F and G are equivalent if:

 Every FD in F can be inferred from G, and

 Every FD in G can be inferred from F

 Hence, F and G are equivalent if F+ =G+

 Definition (Covers):

 F covers G if every FD in G can be inferred from F

 (i.e., if G+ subset-of F+)

 F and G are equivalent if F covers G and G covers F

 There is an algorithm for checking equivalence of sets of

FDs

Slide 15 - 8

1.3 Minimal Sets of FDs (2)

 A set of FDs is minimal if it satisfies the following conditions:

1. Every dependency in F has a single attribute for its RHS.

2. We cannot remove any dependency from F and have a set of dependencies that is equivalent to F.

3. We cannot replace any dependency X  A in F with a dependency Y  A, where Y is a proper- subset-of X and still have a set of dependencies that is equivalent to F.

Slide 15 - 9

Slide 15- 10

DESIGNING A SET OF RELATIONS

 The Approach of Relational Synthesis (Bottom-up Design)

 Goals:

 Lossless join property (a must)

 Dependency preservation property

 Additional normal forms

Slide 15- 11

2. Properties of Relational Decompositions

(1)

 2.1 Relation Decomposition and Insufficiency of Normal

Forms:

 Universal Relation Schema

 A relation schema R = {A1, A2, …, An} that includes all

the attributes of the database.

 Universal relation assumption

 Decomposition:  Attribute preservation condition:

Slide 15- 12

Properties of Relational Decompositions

(2)

2.2 Dependency Preservation Property of a Decomposition:

 Definition: Given a set of dependencies F on R, the projection of F on Ri, denoted by pRi(F) where Ri is a subset of R, is the set of dependencies X  Y in F+ such that the attributes in X υ Y are all contained in Ri.

 Dependency Preservation Property:  A decomposition D = {R1, R2, ..., Rm} of R is

dependency-preserving with respect to F if the union of the projections of F on each Ri in D is equivalent to F.

Slide 15- 13

Properties of Relational Decompositions

(3)

2.3 Non-additive (Lossless) Join Property of a Decomposition:

 Definition: Lossless join property: a decomposition D = {R1, R2, ..., Rm} of R has the lossless (nonadditive) join property with respect to the set of dependencies F on R if, for every relation state r of R that satisfies F, the following holds, where * is the natural join of all the relations in D:

* ( R1(r), ..., Rm(r)) = r

Slide 15- 14

Properties of Relational Decompositions

(4)

Lossless (Non-additive) Join Property of a Decomposition :

 Algorithm: 15.3: Testing for Lossless Join Property

 Input: A universal relation R, a decomposition D = {R1, R2, ..., Rm} of R, and a set F of functional dependencies.

1. Create an initial matrix S with one row i for each relation Ri in D, and one column j for each attribute Aj in R.

2. Set S(i,j):=bij for all matrix entries. (* each bij is a distinct symbol associated with indices (i,j) *).

3. For each row i representing relation schema Ri

{for each column j representing attribute Aj

{if (relation Ri includes attribute Aj) then set S(i,j):= aj;};};

 (* each aj is a distinct symbol associated with index (j) *)

 CONTINUED on NEXT SLIDE

Slide 15- 15

Properties of Relational Decompositions

(5)

 Lossless (Non-additive) Join Property of a Decomposition (cont.):

Algorithm 15.3: Testing for Lossless Join Property (continued)

4. Repeat the following loop until a complete loop execution results in no changes to S

{for each functional dependency X Y in F

{for all rows in S which have the same symbols in the columns corresponding to attributes in X

{make the symbols in each column that correspond to an attribute in Y be the same in all these rows as follows:

If any of the rows has an “a” symbol for the column, set the other rows to that same “a” symbol in the column.

If no “a” symbol exists for the attribute in any of the rows, choose one of the “b” symbols that appear in one of the rows for the attribute and set the other rows to that same “b” symbol in the column ;};

};

};

5. If a row is made up entirely of “a” symbols, then the decomposition has the lossless join property; otherwise it does not.

Slide 15- 16

Test for checking non-additivity of Binary

Relational Decompositions (6)

2.4 Testing Binary Decompositions for Non- additive Join (Lossless Join) Property

 Binary Decomposition: Decomposition of a relation R into two relations.

 PROPERTY NJB (non-additive join test for binary decompositions): A decomposition D = {R1, R2} of R has the lossless join property with respect to a set of functional dependencies F on R if and only if either

 The f.d. ((R1 ∩ R2)  (R1- R2)) is in F+, or

 The f.d. ((R1 ∩ R2)  (R2 - R1)) is in F+.

Slide 15- 17

Properties of Relational Decompositions

(7)

2.5 Successive Non-additive Join Decomposition:

 Claim 2 (Preservation of non-additivity in

successive decompositions):

 If a decomposition D = {R1, R2, ..., Rm} of R has

the lossless (non-additive) join property with respect

to a set of functional dependencies F on R,

 and if a decomposition Di = {Q1, Q2, ..., Qk} of Ri

has the lossless (non-additive) join property with

respect to the projection of F on Ri,

 then the decomposition D2 = {R1, R2, ..., Ri-1, Q1, Q2, ...,

Qk, Ri+1, ..., Rm} of R has the non-additive join property

with respect to F.

Slide 15- 18

3. Algorithms for Relational Database

Schema Design (1)

 Design of 3NF Schemas:

 Algorithm 15.4 Relational Synthesis into 3NF with Dependency Preservation and Non-Additive (Lossless) Join Property

 Input: A universal relation R and a set of functional dependencies F on the attributes of R.

 Design of BCNF Schemas

 Algorithm 15.5: Relational Decomposition into BCNF with Lossless (non-additive) join property

 Input: A universal relation R and a set of functional dependencies F on the attributes of R.

Slide 15- 19

4. Problems with Null Values

Problems with NULL values

 when some tuples have NULL values for attributes that will be used to join individual relations in the decomposition that may lead to incomplete results.

Slide 15- 20

Summary of Algorithms for Relational

Database Schema Design

Slide 15- 21

Summary of Algorithms for Relational

Database Schema Design (Cont.)

Slide 15- 22

5. Multivalued Dependencies and Fourth

Normal Form – Further Discussion (1)

Definition:

 A multivalued dependency (MVD) X —>> Y specified on relation

schema R, where X and Y are both subsets of R, specifies the

following constraint on any relation state r of R: If two tuples t 1

and

t 2

exist in r such that t 1 [X] = t

2 [X], then two tuples t

3 and t

4 should

also exist in r with the following properties, where we use Z to

denote (R 2 (X υ Y)):

 t 3 [X] = t

4 [X] = t

1 [X] = t

2 [X].

 t 3 [Y] = t

1 [Y] and t

4 [Y] = t

2 [Y].

 t 3 [Z] = t

2 [Z] and t

4 [Z] = t

1 [Z].

 An MVD X —>> Y in R is called a trivial MVD if (a) Y is a subset of X, or (b) X υ Y = R.

Slide 15- 23

Multivalued Dependencies and Fourth Normal

Form (2)  Inference Rules for Functional and

Multivalued Dependencies:  IR1 (reflexive rule for FDs): If X  Y, then X → Y.

 IR2 (augmentation rule for FDs): {X → Y}  XZ → YZ.  IR3 (transitive rule for FDs): {X → Y, Y → Z}  X → Z.

 IR4 (complementation rule for MVDs): {X —>> Y}  X —>> (R – (X  Y))}.

 IR5 (augmentation rule for MVDs): If X —>> Y and W  Z then WX —>> YZ.

 IR6 (transitive rule for MVDs): {X —>> Y, Y —>> Z}  X —>> (Z - Y).

 IR7 (replication rule for FD to MVD): {X –> Y}  X —>> Y.

 IR8 (coalescence rule for FDs and MVDs): If X —>> Y and there exists W with the properties that

 (a) W  Y is empty, (b) W –> Z, and (c) Y  Z, then X –> Z.

Slide 15- 24

Multivalued Dependencies and Fourth Normal

Form (3)

Definition:

 A relation schema R is in 4NF with respect to a set of dependencies F (that includes functional dependencies and multivalued dependencies) if, for every nontrivial multivalued dependency X —>> Y in F+, X is a superkey for R.

Slide 15- 25

Non-additive( Lossless) Join Decomposition

into 4NF Relations:

 PROPERTY NJB’

 The relation schemas R 1

and R 2

form a lossless

(non-additive) join decomposition of R with respect

to a set F of functional and multivalued

dependencies if and only if

 (R 1

∩ R 2 ) —>> (R

1 - R

2 )

 or by symmetry, if and only if

 (R 1

∩ R 2 ) —>> (R

2 - R

1 )).

Multivalued Dependencies and Fourth Normal

Form (4)

Slide 15- 26

Algorithm 15.7: Relational decomposition into 4NF

relations with non-additive join property

 Input: A universal relation R and a set of functional and

multivalued dependencies F.

Multivalued Dependencies and Fourth Normal

Form (5)

Slide 15- 27

Other Dependencies and Normal Forms

(3)

6.4 Domain-Key Normal Form (DKNF):  Definition:

 A relation schema is said to be in DKNF if all constraints and dependencies that should hold on the valid relation states can be enforced simply by enforcing the domain constraints and key constraints on the relation.

 The idea is to specify (theoretically, at least) the “ultimate normal form” that takes into account all possible types of dependencies and constraints. .

 For a relation in DKNF, it becomes very straightforward to enforce all database constraints by simply checking that each attribute value in a tuple is of the appropriate domain and that every key constraint is enforced.

 The practical utility of DKNF is limited

Slide 15- 28

Summary

 Functional Dependencies Revisited

 Designing a Set of Relations by Synthesis

 Properties of Relational Decompositions

 Algorithms for Relational Database Schema

Design in 3Nf and BCNF

 Multivalued Dependencies and Fourth Normal

Form