CRITERIA FOR DATABASE DESIGN Database Management System

CRITERIA FOR DATABASE DESIGN Database Management System

CRITERIA FOR DATABASE DESIGN

CRITERIA FOR DATABASE DESIGN Database Management System : We will follow the decomposition approach based on FD’s and normalization. If a relation is not in the normal form that was being checked for and we wished the relation to be normalised to that normal form.So that Some of the anomalies can be eliminated, it was necessary to decompose the relation in two or more relations. The process of decomposition of a relation R into a set of relations R, R2, …, Rn  was based on identifying different components and using that as a basis of decomposition. The decomposed relations R1, R2, …, Rn, are projections of R and are of course not disjoint otherwise the glue holding the information together would be lost. Decomposing relations in this way based on a recognise and split method is not a particularly sound approach since we do not even have a basis to determine that the original relation can be Constructed if necessary from the decomposed relations. We now discuss desirable properties of good decomposition and identify difficulties that may arise if the decomposition is done without adequate care. The next section will discuss how such decomposition may be derived with the given FD’s.

Desirable properties of a decomposition are:

  1. Content Preserving (Lossless-join decomposition)
  2. Dependency preservation
  3. Attribute preservation
  4. Lack of redundancy

Content preserving (Lossless-join decomposition)

The design is said to be content preserving if original relation (tuples) can be derived from the decomposed relations by join operation. This is also known as lossless join decomposition.

 

Dependency preserving

The design is said to be dependency preserving if original set of Constraints or dependencies can be derived from the decomposed relations without joining the relations.

Attribute preservation means all the attributes must be present in decomposed relations and there should be minimal redundancy.

Content preserving (Lossless-join decomposition) Example

We illustrate how a careless decomposition may lead to problems including loss of information.

Consider the following relation

enroll (sno, Cno, date-enrolled, room-No., instructor)

Suppose we decompose the above relation into two relations enroll and enrol2 as follows

enrol.1 (sino, Cno, date-enrolled}

enrol2(date-enrolled, room-No., instructor)

There are problems with this decomposition but we wish to focus on one aspect at the moment. Let an instance of the relation enrol be

CRITERIA FOR DATABASE DESIGN Database Management System

 

(add further tuples…)

The join contains a number of spurious tuples that was not in the original relation Enrol.  Because of these additional tuples, we have lost the information about which students take courses from WILSON.Yes, we have more tuples but less information because we are unable to say with Certainty who is taking courses from Wilson). Such decompositions are called lossy decompositions. A nonloss or lossess decomposition is that which guarantees that the join will result in exactly the same relation as was decomposed. One might think that there might be other ways of recovering the original relation from the decomposed relations but, sadly, no other operators can recover the original relation if the join does not (why?).

We need to analyse why some decompositions are lossy. The common attribute in above decompositions was Date-enrolled. The common attribute is the glue that gives us the ability to find the relationships between different relations by joining the relations together, if the common attribute is not unique, the relationship information is not preserved. If each tuple had a unique value of Date-enrolled, the problem of losing information would not have existed. The problem arises because several enrolments may take place on the same date.

A decomposition of a relation R into relations R, R2, …, R. is called a lossless-join decomposition (with respect to FDS F) if the relation R is always the natural join of the relations R, R2, …, R. It should be noted that natural join is the only way to recover the relation from the decomposed relations. There is no otherset of operators that can recover the relation if the join cannot. Furthermore, it should be noted when the decomposed relations R. R.,…, R., are obtained by projecting on the relation R, for example Riby projection pi, (R), the relation R may not always be precisely equal to the projection since the relation R might have additional tuples called the dangling tuples. Explain…

It is not difficult to test whether a given decomposition is lossless-join given a set of functional dependencies F. We consider the simple case of a relation R being decomposed into R1 and R2. If the decomposition is lossless-join, then one of the following two conditions must hold :

(R1 intersection R2)- (R1-R2)

(R1  intersection R2) – (R1-R2)

That is, the common attributes in R1 and R must include a candidate key of either R1 or R2.

Dependency Preserving Example

It is clear that a decomposition must be lossless so that we do not lose any information from the relation that is decomposed. Dependency preservation is another important requirement since a dependency is a Constraint on the database and if X-> Y holds than we know that the two (sets) attributes are closely related and it would be useful if both attributes appeared in the same relation so that the dependency can be checked easily.

Let us Consider a relation R{A, B, C, D) that has the dependencies F that include the following:

A -> B

A -> B etc.

 

If we decompose the above relation into R1(A, B) and R2(B, C, D) the dependency A – C cannot be checked (or preserved) by looking at only one relation. It cesirable that decompositions be such that each dependency in F may be checked by looking at only one relation and that no joins need be computed for checking dependencies. In some cases, it may not be possible to preserve each and every dependency in F but as long as one dependencies that are preserved are equivalent to F, it should be sufficient.

Let F be the dependencies on a relation R which is Clecomposed in relations R, R2, …, Rn.

We can partition the dependencies given by F such that F, F2, …, Fn. Fn, are dependencies that only involve attributes from relations R, R2, …, Rn, respectively. If the union of dependencies Fi imply all the dependencies in F, then we say that the decomposition has preserved dependencies, otherwise not.

If the decomposition does not preserve the dependencies F, then the decomposed relations may contain relations that do not satisfy For the updates to the decomposed relations may require a join to check that the Constraints implied by the dependencies still hold.

Consider the following relation

Sub(sno, instructor, office)

We may wish to decompose the above relation to remove the transitive dependency of office on sno. A possible decomposition is

 

51(sno, instructor)

S2(sno, office)

The relations are now in 3NF but the dependency instructor – office cannot be verified by looking at one relation, a join of S1 and S2 is needed. In the above decomposition, it is quite possible to have more than one office number for one instructor although the functional dependency instructor- office does not allow it.