PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



DBMSUnit7 .pdf



Original filename: DBMSUnit7.pdf
Author: ILOVEPDF.COM

This PDF 1.6 document has been generated by ILOVEPDF.COM, and has been sent on pdf-archive.com on 23/08/2015 at 15:27, from IP address 103.5.x.x. The current document download page has been viewed 361 times.
File size: 223 KB (7 pages).
Privacy: public file




Download original PDF file









Document preview


Database Management System

10CS54

UNIT 7
Data base design 2
7.1 Properties of relational decomposition
7.2 Algorithms for Relational Database Schema Design
7.2.1 Decomposition and Dependency Preservation
7.2.2 Lossless-join Dependency
7.3 Multivolume Dependencies and Fourth Normal Form (4NF)
7.3.1 Fourth Normal Form (4NF)
7.4 Join Dependencies and 5 NF
7.5 Other dependencies:
7.5.1 Template Dependencies
7.5.2 Domain Key Normal Form

Page 85

Database Management System

10CS54

UNIT-7 Data base design 2
7.1 Properties of relational decomposition
Normalization Algorithms based on FDs to synthesize 3NF and BCNF describe two desirable
properties (known as properties of decomposition).
x
Dependency Preservation Property
x

Lossless join property

Dependency Preservation Property enables us to enforce a constraint on the original relation
from corresponding instances in the smaller relations.
Lossless join property enables us to find any instance of the original relation from
corresponding instances in the smaller relations (Both used by the design algorithms to achieve
desirable decompositions).
A property of decomposition, which ensures that no spurious rows are generated when relations
are reunited through a natural join operation.
7.2 Algorithms for Relational Database Schema Design
Individual relations being in higher normal do not guarantee a good deign Database schema must
posses additional properties to guarantee a good design.
Relation Decomposition and Insufficiency of Normal Forms
Suppose R = { A1, A2, …, An} that includes all the attributes of the database. R is a universal
relation schema, which states that every attribute name is unique. Using FDs, the algorithms
decomposes the universal relation schema R into a set of relation schemas
D = {R1, R2, …, Rn} that will become the relational database schema; D is called a
decomposition of R. Each attribute in R will appear in at least one relation schema Ri in the
decomposition so that no attributes are lost; we have

This is called attribute preservation condition of a decomposition.
7.2.1 Decomposition and Dependency Preservation
We want to preserve dependencies because each dependencies in F represents a constraint on the
database.
We would like to check easily that updates to the database do not result in illegal relations being
created.
Page 86

Database Management System

10CS54

It would be nice if our design allowed us to check updates without having to compute natural
joins. To know whether joins must be computed, we need to determine what functional
dependencies may be tested by checking each relation individually.
Let F be a set of functional dependencies on schema R. Let D = {R1, R2, …, Rn} be a
decomposition of R. Given a set of dependencies F on R, the projection of F on Ri, SRi(F),
where Ri is a subset of R, is the set of all functional dependencies XoY such that attributes in
X‰Y are all contained in Ri. Hence the projection of F on each relation schema Ri in the
decomposition D is the set of FDs in F+, such that all their LHS and RHS attributes are in Ri.
Hence, the projection of F on each relation schema Ri in the decomposition D is the set of
functional dependencies in F+.
((SR1(F))‰ (SR2(F))‰ … ‰(SRm(F)))+ = F+
i.e., the union of the dependencies that hold on each Ri belongs to D be equivalent to closure of F (all possible FDs)

/*Decompose relation, R, with functional dependencies, into relations, R1,..., Rn, with associated
functional dependencies,
F1,..., Fk.
The decomposition is dependency preserving iff:
F+=(F1�...�
 F
 k)+ */
If each functional dependency specified in F either appeared directly in one of the relation
schema R in the decomposition D or could be inferred from the dependencies that appear in
some R.
7.2.2 Lossless-join Dependency
A property of decomposition, which ensures that no spurious rows are generated when relations
are reunited through a natural join operation.
Lossless-join property refers to when we decompose a relation into two relations - we can rejoin
the resulting relations to produce the original relation.

Decompose relation, R, with functional dependencies, F, into relations, R1 and R2, with
attributes, A1 and A2, and associated functional dependencies, F1 and F2.
x

Decompositions are projections of relational schemas
Page 87

Database Management System

R A B C

x

A B

A,B

10CS54

B,C

B C

a1 b1 c1

a1 b1

b1 c1

a2 b2 c2

a2 b2

b2 c2

a3 b1 c3

a3 b1

b1 c3

Old tables should be derivable from the newer ones through the natural join operation
A,B(R)

B,C(R)

A B C
a1 b1 c1
a2 b2 c2
a3 b1 c3
a1 b1 c3
a3 b1 c1

x
x

Wrong!
R1, R2 is a lossless join decomposition of R iff the attributes common to R1 and R2
contain a key for at least one of the involved relations
R A B C

x

A,B

A B

B,C

B C

a1 b1 c1

a1 b1

b1 c1

a2 b2 c2

a2 b2

b2 c2

a3 b1 c1

a3 b1

A,B(R)

B,C(R)

=B

The decomposition is lossless iff:
x
A1�A2�A1\A2 is in F+, or
Page 88

Database Management System

10CS54

A1�A2�A2 \A1 is in F+
However, sometimes there is the requirement to decompose a relation into more than two
relations. Although rare, these cases are managed by join dependency and 5NF.
x

7.3 Multivalued Dependencies and Fourth Normal Form (4NF)
4NF associated with a dependency called multi-valued dependency (MVD). MVDs in a
relation are due to first normal form (1NF), which disallows an attribute in a row from having a
set of values.
MVD represents a dependency between attributes (for example, A, B, and C) in a relation, such
that for each value of A there is a set of values for B, and a set of values for C. However, the set
of values for B and C are independent of each other.
MVD between attributes A, B, and C in a relation using the following notation

A ���� B

(A multidetermines B)

A ���� C
Formal Definition of Multivalued Dependency
A multivalued dependency (MVD) X ����Y specified on R, where X, and Y are both
subsets of R and Z = (R – (X Y)) specifies the following restrictions on r(R)
t3[X]=t4[X]=t1[X]=t2[X]
t3[Y] = t1[Y] and t4[Y] = t2[Y]
t3[Z] = t2[Z] and t4[Z] = t1 [Z]

7.3.1 Fourth Normal Form (4NF)

A relation that is in Boyce-Codd Normal Form and contains no MVDs. BCNF to 4NF involves
the removal of the MVD from the relation by placing the attribute(s) in a new relation along with
a copy of the determinant(s).
A Relation is in 4NF if it is in 3NF and there is no multivalued dependencies.
Page 89

Database Management System

10CS54

7.4 Join Dependencies and 5 NF
A join dependency (JD), denoted by JD{R1, R2, …, Rn}, specified on relation schema R,
specifies a constraint on the states r of R. The constraint states that every legal state r of R should
have a lossless join decomposition into R1, R2, …, Rn; that is, for every such r we have
* (SR1(r), (SR2(r)
… (SRn(r)) = r
Lossless-join property refers to when we decompose a relation into two relations - we can rejoin
the resulting relations to produce the original relation. However, sometimes there is the
requirement to decompose a relation into more than two relations. Although rare, these cases are
managed by join dependency and 5NF.
5NF (or project-join normal form (PJNF))
A relation that has no join dependency.
7.5 Other dependencies:
7.5.1 Template Dependencies

Page 90

Database Management System

10CS54

The idea behind template dependencies is to specify a template—or example—that defines each
constraint or dependency. There are two types of templates: tuple-generating templates and
constraint-generating templates. A template consists of a number of hypothesis tuples that are
meant to show an example of the tuples that may appear in one or more relations. The other part
of the template is the template conclusion. For tuple-generating templates, the conclusion is a set
of tuples that must also exist in the relations if the hypothesis tuples are there. For constraintgenerating templates, the template conclusion is a condition that must hold on the hypothesis
tuples.
7.5.2 Domain Key Normal Form
The idea behind domain-key normal form (DKNF) is to specify (theoretically, at least) the
"ultimate normal form" that takes into account all possible types of dependencies and constraints.
A relation is said to be in DKNF if all constraints and dependencies that should hold on the
relation can be enforced simply by enforcing the domain constraints and key constraints on the
relation.
However, because of the difficulty of including complex constraints in a DKNF relation, its
practical utility is limited, since it may be quite difficult to specify general integrity constraints.
For example, consider a relation CAR(MAKE, VIN#) (where VIN# is the vehicle identification
number) and another relation MANUFACTURE(VIN#, COUNTRY) (where COUNTRY is the
country of manufacture). A general constraint may be of the following form: "If the MAKE is
either Toyota or Lexus, then the first character of the VIN# is a "J" if the country of manufacture
is Japan; if the MAKE is Honda or Acura, the second character of the VIN# is a "J" if the
country of manufacture is Japan." There is no simplified way to represent such constraints short
of writing a procedure (or general assertions) to test them.

Page 91


Related documents


dbmsunit7
dbmsunit6
dbmssyllabus
comps sem4 dbms assignments
dbmsunit2
a guide to sql 9th edition pratt solution manual


Related keywords