Search

We establish a principled schema design framework for data with missing values. The framework is based on the new notion of an embedded functional dependency, which is independent of the interpretation of missing values, able to express completeness and integrity requirements on application data, and capable of capturing redundant data value occurrences that may cause problems with processing data that meets the requirements. We establish axiomatic, algorithmic, and logical foundations for reasoning about embedded functional dependencies. These foundations enable us to introduce generalizations of Boyce-Codd and Third normal forms that avoid processing difficulties of any application data, or minimize these difficulties across dependency-preserving decompositions, respectively. We show how to transform any given schema into application schemata that meet given completeness and integrity requirements, and the conditions of the generalized normal forms. Data over those application schemata are therefore fit for purpose by design. Extensive experiments with benchmark schemata and data illustrate the effectiveness of our framework for the acquisition of the constraints, the schema design process, and the performance of the schema designs in terms of updates and join queries.

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.

A new approach, to measure normalization completeness for conceptual model, is introduced using quantitative fuzzy functionality in this paper. We measure the normalization completeness of the conceptual model in two steps. In the first step, different normalization techniques are analyzed up to Boyce Codd Normal Form (BCNF) to find the current normal form of the relation. In the second step, fuzzy membership values are used to scale the normal form between 0 and 1. Case studies to explain schema transformation rules and measurements. Normalization completeness is measured by considering completeness attributes, preventing attributes of the functional dependencies and total number of attributes such as if the functional dependency is non-preventing then the attributes of that functional dependency are completeness attributes. The attributes of functional dependency which prevent to go to the next normal form are called preventing attributes., Comment: 8 Pages

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.

The purpose of good database logical design is to eliminate data redundancy and isertion and deletion anomalies. In order to achieve this objective for temporal databases, the notions of temporal types , which formalize time granularities, and temporal functional dependencies (TFDs) are intrduced. A temporal type is a monotonic mapping from ticks of time (represented by positive integers) to time sets (represented by subsets of reals) and is used to capture various standard and user-defined calendars. A TFD is a proper extension of the traditional functional dependency and takes the form X → μ Y, meaning that there is a unique value for Y during one tick of the temporal type μ for one particular X value. An axiomatization for TFDs is given. Because a finite set TFDs usually implies an infinite number of TFDs, we introduce the notion of and give an axiomatization for a finite closure to effectively capture a finite set of implied TFDs that are essential of the logical design. Temporal normalization procedures with respect to TFDs are given. Specifically, temporal Boyce-Codd normal form (TBCNF) that avoids all data redundancies due to TFDs, and temporal third normal form (T3NF) that allows dependency preservation, are defined. Both normal forms are proper extensions of their traditional counterparts, BCNF and 3NF. Decompositition algorithms are presented that give lossless TBCNF decompositions and lossless, dependency-preserving, T3NF decompositions.

In this paper we present some characterizations of relation schemes in second normal form (2NF), third normal form (3NF) and Boyce-Codd normal form (BCNF). It is known [6]that the set of minimal keys of a relation scheme is a Sperner system (an antichain) and for an arbitrary Sperner system there exists a relation scheme the set of minimal keys of which is exactly the given Sperner system. We investigate families of 2NF, 3NF and BCNF relation schemes where the sets of minimal keys are given Sperner systems. We give characterizations of these families. The minimal Armstrong relation has been investigated in the literature [3, 7, 11, 15, 18]. This paper gives new bounds on the size of minimal Armstrong relations for relation schemes. We show that given a relation scheme s such that the set of minimal keys is the Sperner system K, the number of antikeys (maximal nonkeys) of K is polynomial in the number of attributes iff so is the size of minimal Armstrong relation of s. We give a new characterization of relations and relation schemes that are uniquely determined by their minimal keys. From this characterization we give a polynomial-time algorithm deciding whether an arbitrary relation is uniquely determined by its set of all minimal keys. We present a new polynomial-time algorithm testing BCNF property of a given relation scheme.

The relationship between the absence of redundancy in relational databases and fourth normal form (4NF) is investigated. A relation scheme is defined to be redundant if there exists a legal relation defined over it which has at least two tuples that are identical on the attributes in a functional dependency (FD) or multivalued dependency (MVD) constraint. Depending on whether the dependencies in a set of constraints or the dependencies in the closure of the set is used, two different types of redundancy are defined. It is shown that the two types of redundancy are equivalent and their absence in a relation scheme is equivalent to the 4NF condition.

A key is simple if it consists of a single attribute. It is shown that if a relation schema is in third normal form 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. Furthermore, it is shown that if a relation schema is in Boyce-Codd normal form and some key is simple, then it is in fourth normal form (but not necessarily projection-join normal form). 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 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.

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.

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.

In order to eliminate redundant information in a database one usually uses decomposition or special database design methods to achieve Third Normal Form (or some other normal form like Boyce-Codd Normal Form). This method of database design assumes that the real world satisfies very strong constraints like functional dependencies (fds), without any exceptions. Most databases in "Whatever" Normal Form still contain a large amount of duplicated information, because the real world satisfies very few constraints, but a lot of "almost" constrains. Horizontal Fragments (resulting from Horizontal Decomposition) can be used to separate information with different properties. The different constraints that hold in these fragments can be used to eliminate redundant information in the fragments. We focus on the horizontal decomposition for eliminating exceptions to fds. We show how to update such horizontally decomposed databases in an efficient way. Generating separate horizontal fragments for all desired fds that do not hold in the real world may not be possible (although for every fd there will be a fragment for its exceptions, but the fragments for a number of fds may coincide). The number of fds for which a separate exception fragment can be generated depends on the choice of fds and the order in which they are used. We show that it is possible to find (in polynomial time) the order which leads to the "optimal" decomposition of a relation into horizontal fragments.

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.

A functional dependency (fd) family was recently defined [20] as the set of all instances satisfying some set of functional dependencies. A Boyce-Codd normal form, abbreviated BCNF, family is defined here as an fd-family specified by some BCNF set of functional dependencies. The purpose of this paper is to present set-theoretic/algebraic characterizations relating to both types of families. Two characterizations of F ( I ), the smallest fd-family containing the family I of instances, are established. The first involves the notion of agreement, a concept related to that of a closed set of attributes. The second describes F ( I ) as the smallest family of instances containing I and closed under four specific operations on instances. Companion results are also given for BCNF- families. The remaining results concern characterizations involving the well-known operations of projection, join and union. Two characterizations for when the projection of an fd-family is again an fd-family are given. Several corollaries are obtained, including the effective decidability of whether a projection of an fd-family is an fd-family. The problem for BCNF-families disappears since it is shown that the projection of a BCNF-family is always a BCNF-family. Analogous to results for fd-families presented in [20], characterizations of when the join and union of BCNF-families are BCNF-families are given. Finally, the collections of all fd-families and all BCNF-families are characterized in terms of inverse projection operations and intersection.

A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is strictly stronger than Codd's “improved third normal form” (or “Boyce-Codd normal form”). It is shown that every relation schema can be decomposed into a family of relation schemata in fourth normal form without loss of information (that is, the original relation can be obtained from the new relations by taking joins).

In a multiattribute relation or, equivalently, a multicolumn table a certain collection of the projections can be shown to be independent in much the same way as the factors in a Cartesian product or orthogonal components of a vector. A precise notion of independence for relations is defined and studied. The main result states that the operator which reconstructs the original relation from its independent components is the natural join, and that independent components split the full family of functional dependencies into corresponding component families. These give an easy-to-check criterion for independence.

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.

In this paper, we show that some Codd third normal form relations may contain “superfluous” attributes because the definitions of transitive dependency and prime attribute are inadequate when applied to sets of relations. To correct this, an improved third normal form is defined and an algorithm is given to construct a set of relations from a given set of functional dependencies in such a way that the superfluous attributes are guaranteed to be removed. This new normal form is compared with other existing definitions of third normal form, and the deletion normalization method proposed is shown to subsume the decomposition method of normalization.

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.