Transcript Chapter 7: Relational Database Design

Appendix C: Advanced Relational Database Design
Database System Concepts, 5th Ed.
C.1
©Silberschatz, Korth and Sudarshan
Database System Concepts






Chapter 1: Introduction
Part 1: Relational databases

Chapter 2: Relational Model

Chapter 3: SQL

Chapter 4: Advanced SQL

Chapter 5: Other Relational Languages
Part 2: Database Design

Chapter 6: Database Design and the E-R Model

Chapter 7: Relational Database Design

Chapter 8: Application Design and Development
Part 3: Object-based databases and XML

Chapter 9: Object-Based Databases

Chapter 10: XML
Part 4: Data storage and querying

Chapter 11: Storage and File Structure

Chapter 12: Indexing and Hashing

Chapter 13: Query Processing

Chapter 14: Query Optimization
Part 5: Transaction management

Chapter 15: Transactions

Chapter 16: Concurrency control

Chapter 17: Recovery System
Database System Concepts, 5th Ed.





Part 6: Data Mining and Information Retrieval

Chapter 18: Data Analysis and Mining

Chapter 19: Information Retreival
Part 7: Database system architecture

Chapter 20: Database-System Architecture

Chapter 21: Parallel Databases

Chapter 22: Distributed Databases
Part 8: Other topics

Chapter 23: Advanced Application Development

Chapter 24: Advanced Data Types and New Applications

Chapter 25: Advanced Transaction Processing
Part 9: Case studies

Chapter 26: PostgreSQL

Chapter 27: Oracle

Chapter 28: IBM DB2

Chapter 29: Microsoft SQL Server
Online Appendices

Appendix A: Network Model

Appendix B: Hierarchical Model

Appendix C: Advanced Relational Database Model
C.2
©Silberschatz, Korth and Sudarshan
Online Appendices
(available only in http://www.db-book.com)
 Appendix A: Network Model
 Appendix B: Hierarchical Model
 Although most new database applications use either the relational model or the
object-relational model, the network and hierarchical data models are still in
use in some legacy applications.
 Appendix C: Advanced Relational Database Model

describes advanced relational-database design, including the theory of
multivalued dependencies, join dependencies, and the project-join and
domain-key normal forms.
Database System Concepts, 5th Ed.
C.3
©Silberschatz, Korth and Sudarshan
Table of Contents
 Reasoning with MVDs
 Higher normal forms

Join dependencies and PJNF

DKNF
 Summary
Database System Concepts, 5th Ed.
C.4
©Silberschatz, Korth and Sudarshan
Theory of Multivalued Dependencies
 Let D denote a set of functional and multivalued dependencies. The
closure D+ of D is the set of all functional and multivalued
dependencies logically implied by D.
 Sound and complete inference rules for functional and multivalued
dependencies:
1. Reflexivity rule. If  is a set of attributes and   , then   holds.
2. Augmentation rule. If    holds and  is a set of attributes, then 
  holds.
3. Transitivity rule. If    holds and    holds, then   holds.
Database System Concepts, 5th Ed.
C.5
©Silberschatz, Korth and Sudarshan
Theory of Multivalued Dependencies (Cont.)
4. Complementation rule. If 
holds.
 holds, then 
5. Multivalued augmentation rule. If 
 , then  
  holds.
6. Multivalued transitivity rule. If 
then 
 –  holds.
7. Replication rule. If 
 holds and   R and 
 holds and 
 holds, then 
R––
 holds,
.
8. Coalescence rule. If 
 holds and    and there is a 
such that   R and    =  and 
, then 
 holds.
Database System Concepts, 5th Ed.
C.6
©Silberschatz, Korth and Sudarshan
Simplification of the Computation of D+
 We can simplify the computation of the closure of D by using the following
rules (proved using rules 1-8).

Multivalued union rule. If 

 holds.

Intersection rule. If 
holds.

Difference rule. If If 
 holds and 
holds and 
 –  holds.
Database System Concepts, 5th Ed.
 holds and 
 holds and 
C.7
 holds, then 
 holds, then 
 holds, then 

–
©Silberschatz, Korth and Sudarshan
MVD Example
 R = (A, B, C, G, H, I)
D = {A
B
CG
B
HI
H}
 Some members of D+:

A
CGHI.
Since A
B, the complementation rule (4) implies that
A
R – B – A.
Since R – B – A = CGHI, so A
CGHI.

A
HI.
Since A
B and B
rule (6) implies that B
Since HI – B = HI, A
Database System Concepts, 5th Ed.
HI, the multivalued transitivity
HI – B.
HI.
C.8
©Silberschatz, Korth and Sudarshan
MVD Example (Cont.)
 Some members of D+ (cont.):

B
H.
Apply the coalescence rule (8); B
HI holds.
Since H  HI and CG
H and CG  HI = Ø, the
coalescence rule is satisfied with being B,  being HI,  being
CG, and  being H. We conclude that B
H.

A
CG.
A
CGHI and A
HI.
By the difference rule, A
Since CGHI – HI = CG, A
Database System Concepts, 5th Ed.
CGHI – HI.
CG.
C.9
©Silberschatz, Korth and Sudarshan
Table of Contents
 Reasoning with MVDs
 Higher normal forms

Join dependencies and PJNF

DKNF
 Summary
Database System Concepts, 5th Ed.
C.10
©Silberschatz, Korth and Sudarshan
Normalization using Join Dependencies
 Join dependencies constrain the set of legal relations over a schema R to
those relations for which a given decomposition is a lossless-join
decomposition.
 Let R be a relation schema and R1 , R2 ,..., Rn be a decomposition of R. If R =
R1  R2  ….  Rn, we say that a relation r(R) satisfies the join dependency
*(R1 , R2 ,..., Rn) if:
r =R1 (r) ⋈ R2 (r) ⋈ …… ⋈ Rn(r)
A join dependency is trivial if one of the Ri is R itself.
 A join dependency *(R1, R2) is equivalent to the multivalued dependency R1 
R2
R2. Conversely, 
 is equivalent to
*( (R - ),   )
 However, there are join dependencies that are not equivalent to any
multivalued dependency.
Database System Concepts, 5th Ed.
C.11
©Silberschatz, Korth and Sudarshan
Project-Join Normal Form (PJNF)
 A relation schema R is in PJNF with respect to a set D of functional,
multivalued, and join dependencies if for all join dependencies in D+ of the
form
*(R1 , R2 ,..., Rn ) where each Ri  R
and R =R1 R2  ...  Rn
at least one of the following holds:

*(R1 , R2 ,..., Rn ) is a trivial join dependency.

Every Ri is a superkey for R.
 Since every multivalued dependency is also a join dependency,
every PJNF schema is also in 4NF.
Database System Concepts, 5th Ed.
C.12
©Silberschatz, Korth and Sudarshan
PJNF Example
 Consider Loan-info-schema = (branch-name, customer-name, loan-number,
amount).
 Each loan has one or more customers, is in one or more branches and has
a loan amount; these relationships are independent, hence we have the join
dependency
 *(=(loan-number, branch-name), (loan-number, customer-name), (loan-
number, amount))
 Loan-info-schema is not in PJNF with respect to the set of dependencies
containing the above join dependency. To put Loan-info-schema into PJNF,
we must decompose it into the three schemas specified by the join
dependency:

(loan-number, branch-name)

(loan-number, customer-name)

(loan-number, amount)
Database System Concepts, 5th Ed.
C.13
©Silberschatz, Korth and Sudarshan
Domain-Key Normal Form (DKNY)
 Domain declaration. Let A be an attribute, and let dom be a set of
values. The domain declaration A  dom requires that the A value of
all tuples be values in dom.
 Key declaration. Let R be a relation schema with K  R. The key
declaration key (K) requires that K be a superkey for schema R (K 
R). All key declarations are functional dependencies but not all
functional dependencies are key declarations.
 General constraint. A general constraint is a predicate on the set of
all relations on a given schema.
 Let D be a set of domain constraints and let K be a set of key
constraints for a relation schema R. Let G denote the general
constraints for R. Schema R is in DKNF if D  K logically imply G.
Database System Concepts, 5th Ed.
C.14
©Silberschatz, Korth and Sudarshan
DKNF Example
 Accounts whose account-number begins with the digit 9 are special
high-interest accounts with a minimum balance of 2500.
 General constraint: ``If the first digit of t [account-number] is 9, then t
[balance]  2500.''
 DKNF design:
Regular-acct-schema = (branch-name, account-number,
balance)
Special-acct-schema = (branch-name, account-number,
balance)
 Domain constraints for {Special-acct-schema} require that for each
account:

The account number begins with 9.

The balance is greater than 2500.
Database System Concepts, 5th Ed.
C.15
©Silberschatz, Korth and Sudarshan
DKNF rephrasing of PJNF Definition
 Let R = (A1 , A2 ,..., An) be a relation schema. Let dom(Ai ) denote the
domain of attribute Ai, and let all these domains be infinite. Then all
domain constraints D are of the form Ai  dom (Ai ).
 Let the general constraints be a set G of functional, multivalued, or
join dependencies. If F is the set of functional dependencies in G, let
the set K of key constraints be those nontrivial functional
dependencies in F+ of the form   R.
 Schema R is in PJNF if and only if it is in DKNF with respect to D, K,
and G.
Database System Concepts, 5th Ed.
C.16
©Silberschatz, Korth and Sudarshan
Table of Contents
 Reasoning with MVDs
 Higher normal forms

Join dependencies and PJNF

DKNF
 Summary
Database System Concepts, 5th Ed.
C.17
©Silberschatz, Korth and Sudarshan
Appendix C: Summary

In this chapter we presented the theory of multivalued dependencies, including a set of
sound and complete inference rules for multivalued dependencies.

We then presented two more normal forms based on more general classes of
constraints. Join dependencies are a generalization of multivalued dependencies, and
lead to the definition of PJNF.

DKNF is an idealized normal form that may be difficult to achieve in practice. Yet DKNF
has desirable properties that should be included to the extent possible in a good
database design.
Database System Concepts, 5th Ed.
C.18
©Silberschatz, Korth and Sudarshan
Appendix C: Biblio Notes (1)

The Notations of 4NF, PJNF, and DKNF are from Fagin [1977], Fagin [1979], and Fagin
[1981], respectively.

The synthesis approach to database design is discussed in Bernstein [1976].

Join dependencies were introduced by Rissanen [1979]. Sciore [1982] gives a set of
axioms for a class of dependencies that properly includes the join dependencies. In
addition to their use in PJNF, join dependencies are central to the definition of universal
relation databases.

Fagin et al. [1982] introduces the relationship between join dependencies and the
definition of a relation as a conjunction of predicates (see Section C.2.1).

This use of join dependencies has led to a large amount of research into acyclic
database schemas. Intuitively, a schema is acyclic if if every pair of attributes is related in
a unique way.

Formal treatment of acyclic schemas appears in Fagin [1983] and in Beeri et al. [1983].
Database System Concepts, 5th Ed.
C.19
©Silberschatz, Korth and Sudarshan
Appendix C: Biblio Notes (2)

Additional dependencies are discussed in detail in Maier [1983].

Inclusion dependencies are discussed by Casanova et al. [1984] and Cosmadakis et al.
[1990].

Template dependencies are covered by Sadri and Ulman [1982].

Mutual dependencies are examined by Furtado [1978] and by Mendelzon and
Maier[1979].

Constraints be those nontrivial functional dependencies in F+ of the form  g R. Schema
R is in PJNF if and only if it is in DKNF with respect to D, K, and G.

A consequence of DKNF is that all insertion and deletion anomalies are eliminated.
Database System Concepts, 5th Ed.
C.20
©Silberschatz, Korth and Sudarshan
Appendix C: Biblio Notes (3)

DKNF represents an “ultimate” normal form because it allows arbitrary
constraints, rather than dependencies, yet it allows efficient testing of these
constraints.

Of course, if a schema is not in DKNF, we may be able to achieve DKNF via
decomposition, but such decompositions, as we have seen, are not always
dependency-preserving decompositions. Thus, although DKNF is a goal of a
database designer, it may have to be sacrificed in a practical design.
Database System Concepts, 5th Ed.
C.21
©Silberschatz, Korth and Sudarshan