Search

The task of designing relational databases has always been the subject of scientific research, as it is associated with a number of interrelated steps. The result of each step is the development of models for presenting the future database with further refinement and, finally, the creation of an adequate relational database as a set of relations with the corresponding links between them. The article focuses on the normalization of databases, as one of the steps to create a datalogical model, namely, the use of the first three Normal Forms. As a result of the analysis carried out in the article, it was concluded that the definition of the Second Normal Form can be modernized and thus achieve two goals: to ensure the correct creation of potential primary keys and, thereafter, the correct external connections between relations, even before creating the data schema in a specific relational database. Moreover, to reconsider the necessity of applying the so-called “strengthened” or a higher version of the Third Normal Form, which speaks of mutual dependencies between key and non-key attributes.

International audience; Driven by the dominance of the relational model, we investigate how the requirements of applications on the certainty of functional dependencies can improve the outcomes of relational database schema design. For that purpose, we assume that tuples are assigned a degree of possibility with which they occur in a relation, and that functional dependencies are assigned a dual degree of certainty which says to which tuples they apply. A design theory is developed for functional dependencies with degrees of certainty, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples bring forward different degrees of data redundancy, caused by functional dependencies with the dual degree of certainty. Variants of the classical syntactic Boyce–Codd and Third Normal Forms are established. They are justified semantically in terms of eliminating data redundancy and update anomalies of given degrees, and minimizing data redundancy of given degrees across all dependency-preserving decompositions, respectively. As a practical outcome of our results, designers can simply fix the degree of certainty they target, and then apply classical decomposition and synthesis to the set of functional dependencies whose associated degree of certainty meets the target. Hence, by fixing the certainty degree a designer controls which integrity requirements will be enforced for the application and which data will be processed by the application. The choice of the certainty degree also balances the classical trade-off between query and update efficiency on future database instances. Our experiments confirm the effectiveness of our control parameter, and provide original insight into classical normalization strategies and their implementations.

Introduction Designing database is an art process similar to building a house. Database designers always face the problems of designing a relational database that will be free of database anomalies. These anomalies bring repetition of tuples that delay processing time and occupy memory spaces. Suppose that the value of the attribute BUILDER determines values of the attribute MODEL and PRICE, (BUILDER [right arrow] MODEL, PRICE) and that the value for the attribute MODEL determines the value for PRICE, (MODEL [right arrow] PRICE). Grouping these attributes in relation HOUSE(BUILDER, MODEL, PRICE) has several undesirable properties. First the relationship between MODEL and PRICE is repeated in the relation for each BUILDER who builds a particular MODEL of home. This repetition creates difficulties if a BUILDER who happens to be the last BUILDER of a certain MODEL home is deleted from the relation, then the relationship between the MODEL and its PRICE also disappears from the relation. This is called a deletion anomaly. Similarly, if a new builder who happens to be the first BUILDER of a certain MODEL home is added then the relationship between MODEL of a home and its PRICE will also be added. This is called an insertion anomaly. Suppose that the relationship between a MODEL and its PRICE is changed e.g. the price is increased; then the MODEL and PRICE relationship should be affected for every BUILDER of the MODEL. This is called update anomaly. These anomalies are undesirable since the user is not likely to realize the consequence of the insertion, deletion or updating. The user may inadvertently affect a relationship that was not intended to be modified. Consistency, insertion, deletion and updating are not probe effecting all groupings of attributes. If the relation HOUSE(BUILDER, MODEL, PRICE) is normalized then the consistency and anomaly problems disappear. Normalization is a step by step reversible process of replacing a given collection of relations by successive collection in which the relations have a progressively simpler and more regular structure (Date & Darwen, 2000). The reversibility guarantees that the original collection of relations can be recovered and therefore no information has been lost. Codd proposed three normal forms which he called first normal form (1NF), second normal form (2NF) and third normal form (3NF). A stronger definition of 3NF was proposed by Boyce and Codd and is known as Boyce-Codd Normal Form (BCNF). All these normal forms except 1NF are based on the functional dependencies among the attributes of a relation (Elmasri & Navathe, 1994). First normal form relates to the structure of the relation. It requires that every attribute of a relation be based on a simple domain. The database designers have no problem to know if a relation violates first normal form. They can put the relation into first normal form algorithmically by replacing a non-simple domain by its constituent simple domains. In the second (2NF), third (3NF) and Boyce Codd normal form (BCNF), there is a need for the database designers to know the real meaning and application of database keys such as candidate key, primary key, super key, etc,. Problem Statement Database designers always find it difficult to determine these keys from relational database schemas. It has been difficult to motivate students and database designers to derive primary, candidate, alternative and super keys because they think this area is dry and theoretical. There are many algorithms to determine the database keys but they look abstract for students. Many database researchers indicated that relational database model to derive database keys tends to be complex for the average designers. Failure to determine the database keys at times leads to poor design that can generate database anomalies. The database key algorithms often require extensive relational algebraic backgrounds that database designers lack. …

This chapter covers the process of transforming an ER diagram into a well-designed relational database. For each normal norm, the chapter presents the rules that relations must meet to reach that normal form, and the design problems that may remain. It also covers the process for transforming relations into higher normal forms, including relational algebra operations, where appropriate.

This paper discusses normalization of relations when the candidate keys of a relation have missing information represented by nulls. The paper shows that when the missing information is of the type “not applicable” or “does not exist,” problems and confusion can arise in normalizing relations. Candidate keys with missing information commonly are found in relations that represent information on two entities with a one-to-one relationship between them. The current definition of Boyce-Codd Normal Form (BCNF) is ineffective in identifying poor designs in such relations that may have insertion/deletion anomalies. It is shown that the above problem can be corrected by incorporating the concept of entity integrity rule into the definition of BCNF. This paper also shows that incorporating the entity integrity rule into the definition of either a relation or a candidate key does not provide a satisfactory solution to the problem.

The issue of providing a formal justification for the use of fourth normal form (4NF) in relational database design is investigated. The motivation and formal definitions for three goals of database design are presented. These goals are the elimination of: redundancy, key-based update anomalies and fact-based replacement anomalies. It is then shown that, depending on the type of constraints permitted, either Boyce-Codd normal form (BCNF) or 4NF are the exact conditions needed to ensure most of the design goals. However, it is also shown that the conditions required to ensure the absence of a particular class of key-based update anomaly are new normal forms which have not previously been identified. In particular, for the case where the only constraints are functional dependencies (FDs), it is shown that the required normal form is a new normal form that is stronger than third normal form (3NF) yet weaker than BCNF. Similarly, in the more general case where both FD and multivalued dependencies (MVDs) are present, the required normal form is a new normal form that is weaker than 4NF.

In this paper, the adequacy of fifth normal form (5NF) in relational database design is investigated. It is shown that 5NF is inadequate because it does not generalise fourth normal form (4NF) and because it is equivalent to the very stringent requirement that every attribute is a key, a requirement that is effectively impossible to satisfy in practical database design. By restricting the join dependencies (JDs) in the set of constraints to those that do not have superfluous components, the definition of 5NF is then changed to a new normal form, called reduced fifth normal form (5NFR), and it is shown that 5NFR generalises 4NF. It is also shown that 5NFR is a strictly weaker condition than projection-join normal form (PJ/NF), the other normal form that has been proposed for JDs.

In this paper, we give a necessary and sufficient condition for a Boyce-Codd Normal Form (BCNF) relation scheme to be in Fourth Normal Form (4NF). We also give a necessary and sufficient condition for a 4NF relation scheme to be in Projection-Join Normal Form (PJNF). From these results, we derive necessary and sufficient conditions for a BCNF relation scheme to be in PJNF. In addition, we give a less stringent condition for a Third Normal Form (3NF) relation scheme to be in BCNF. Finally, we show that our theorems generalize the results by Date and Fagin (1992).

In Database design, the attributes and their functional dependencies are abstracted from the software requirements specification (SRS) by the forward engineering process. The abstracted attributes from a forward engineering process are structured depending on the functional requirements. Then, the database relations are composed, by the related attributes and their functional dependencies, based on the structures defined by Codd. Any random structural composition of relations leads to INSERT, DELETE and UPDATE anomalies This paper presents a simple methodology that blends the analytical approach and the synthetic approach, to constitute the relations from a set of attributes and minimally covered functional dependencies, through the use of a dependency matrix to get the desired manipulation. The distinct attribute(s) from a set of functional dependencies is identified for a separate relation. All the dependencies are preserved and the lossless join is ensured by the framed algorithm. Further, the Boyce-Codd Normal Form (BCNF) is persuaded on each relation by revamping the determinant attributes to candidatekey.

In this paper a new method to judge the grade of normal form for relational database is proposed based on rough sets theory. First, some concepts about INF, 2NF, 3NF and BCNF are given and the principles of rough set theory are discussed. Second, the method to judge the grade of normal forms for a given relation is analyzed using rough sets theory, and some properties of a relation satisfying some grade of normal form are obtained. The study in this paper is a new application of rough sets theory.

It is well known that faithful (i.e. dependency preserving) decompositions of relational database schemas into Boyce-Codd Normal Form (BCNF) do not always exist, depending on the set of functional dependencies given, and that the corresponding decision problem is NP-hard. The only algorithm to guarantee both faithfulness and BCNF (if possible) proposed so far in [Os79] is a brute-force approach which always requires exponential time. To be useful in practice, e.g. in automated design tools, we require more efficient means. In this paper we present an algorithm which always finds a faithful BCNF decomposition if one exists, and which is usually efficient, and exponential only in notorious cases.

If the relation schemes of any fuzzy database are not properly designed certain anomaly problems may occur when the fuzzy database is updated or maintained. This is because some undesired relationships exist among attributes. Based on the notions of fuzzy functional dependency (FFD) and /spl theta/-keys, the Boyce-Codd normal form is extended to cope with the anomaly problems caused by partial and transitive FFDs of /spl theta/-prime on some /spl theta/-keys, thus resulting in /spl theta/-fuzzy Boyce-Codd normal form (/spl theta/-FBCNF). Furthermore, the relationship between /spl theta/-FBCNF and other existing fuzzy normal forms is analyzed, showing that /spl theta/-FBCNF reflects the strongest restriction for attributes. Finally an algorithm is provided that can decompose, in a lossless-join manner, any scheme into a number of /spl theta/-FBCNF schemes.

We investigate the properties of relation schemes which are in third normal form (3NF) but not in Boyce-Codd normal form (BCNF) and prove that such a relation scheme must have a pair of candidate keys which overlap.

Boyce-Codd Normal Form (BCNF) is an important normal form in the theory of relational databases. Unfortunately, it is not always possible to obtain a lossless functional-dependency-preserving BCNF decomposition. (This decomposition is called a perfect BCNF decomposition for short.) The necessary condition of the existence of a perfect BCNF decomposition is discussed. Three propositions about a perfect BCNF decomposition are obtained. The concrete determining algorithms are given.

Items are introduced as a universal formalism for describing data (ie individual things), information (ie relations) and knowledge (ie rules). A single rule for the normalisation of items is defined. The five normal forms for relational database together with the Boyce-Codd normal form provide a complete characterisation of the normalisation of 3-adic information items. New normal forms may be derived by applying our single rule of normalisation to n-adic items for n>3.

In [DF92], we present simple conditions, which we now describe, for guaranteeing higher normal forms for relational databases. A key is simple if it consists of a single attribute. We show in [DF92] that if a relation schema is in third normal form (3NF) and every key is simple, then it is in projection-join normal form (sometimes called fifth normal form), the ultimate normal form with respect to projections and joins. We also show in [DF92] that if a relation schema is in Boyce-Codd normal form (BCNF) and some key is simple, then it is in fourth normal form (4NF). These results give the database designer simple sufficient conditions, defined in terms of functional dependencies alone, that guarantee that the schema being designed is automatically in higher normal forms.

In Ref. 8, we introduced a simplifying assumption about entity-relationship diagrams (ERDs), called regularity, and showed that regular ERDs have several desirable properties. One such property is that every relation schema in the ERD's canonical relational scheme can be put into Third Normal Form. We left open there the more basic question: under what conditions would the original relation schemas actually be in Boyce-Codd Normal Form (BCNF)? Since the visible semantics of ERDs determine naturally their associated functional dependencies (fd's), it is important to know when an ERD, as designed, already has this strongest normal form given purely in terms of fd's. We show here a sufficient diagrammatic condition (loop-free) under which a regular ERD will have databases enjoying the benefits of BCNF.

A new normal form for relational databases, called domain-key normal form (DK/NF), is defined. Also, formal definitions of insertion anomaly and deletion anomaly are presented. It is shown that a schema is in DK/NF if and only if it has no insertion or deletion anomalies. Unlike previously defined normal forms, DK/NF is not defined in terms of traditional dependencies (functional, multivalued, or join). Instead, it is defined in terms of the more primitive concepts of domain and key, along with the general concept of a “constraint.” We also consider how the definitions of traditional normal forms might be modified by taking into consideration, for the first time, the combinatorial consequences of bounded domain sizes. It is shown that after this modification, these traditional normal forms are all implied by DK/NF. In particular, if all domains are infinite, then these traditional normal forms are all implied by DK/NF.

Decomposition into Boyce-Codd Normal Form (BCNF) with a lossless join and preservation of dependencies is desired in the design of a relational database scheme. However, there may be no decomposition of a relation scheme into BCNF that is dependency preserving, and the known algorithms for lossless join decomposition into BCNF require exponential time and space. In this paper we give an efficient algorithm for lossless join decomposition and show that the problem of deciding whether a relation scheme has a dependency-preserving decomposition into BCNF is NP-hard. The algorithm and the proof assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

It has been proposed that the description of a relational database can be formulated as a set of functional relationships among database attributes. These functional relationships can then be used to synthesize algorithmically a relational scheme. It is the purpose of this paper to present an effective procedure for performing such a synthesis. The schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations. Problems with earlier attempts to construct such a procedure are also discussed.

Ascribing uniqueness and independent existence to objects we formally define these properties for relational database schemes with functional dependencies. Arguing that minimal left-hand sides of functional dependencies should be considered as objects we introduce object normal forms. Finally, showing that object normal forms and Boyce–Codd normal form are closely related, we provide new insight into the achievements of the Boyce–Codd normal form.

We discuss the relationship between normal forms in a relational database and an allowed set of relational operators. We define "projection-join normal form" (PJ/NF), which is the ultimate normal form when only projection and join are allowed. Aho, Beeri and Ullman made the counterintuitive discovery that there is a relation schema with a valid decomposition into three of its projections without the decomposition being equivalent to a cascade of decompositions, each into two projections. Because of this possibility, there exist bizarre relation schemata that are in fourth normal form but not in PJ/NF. We also discuss issues associated with allowing the union operator.