Search

The transformation of a relational database schema into fourth normal form, which minimizes data redundancy, relies on the correct identification of multivalued dependencies. In this work, we study the learnability of multivalued dependency formulas (MVDF), which correspond to the logical theory behind multivalued dependencies. As we explain, MVDF lies between propositional Horn and 2-Quasi-Horn. We prove that MVDF is polynomially learnable in Angluin et al.'s exact learning model with membership and equivalence queries, provided that counterexamples and membership queries are formulated as 2-Quasi-Horn clauses. As a consequence, we obtain that the subclass of 2-Quasi-Horn theories which are equivalent to MVDF is polynomially learnable.

Other things being equal, we generally want our databases to be as free of redundancy as possible, where by redundancy I mean more specifically—at least as far as the present chapter is concerned—any redundancy that can be removed by taking projections. And of course we use the discipline of further normalization, or just normalization for short, to help us reach that goal. Now, for many years it was believed that a relvar had to be in fifth normal form (5NF, also known as projection-join normal form or PJ/NF) in order for it to be free of redundancy in the foregoing sense. Somewhat surprisingly, however, it turns out that this belief was incorrect—that is, it turns out that several other normal forms can be defined, all of them both weaker than 5NF and stronger than fourth normal form (4NF), and all of them just as effective as 5NF at eliminating redundancy. The normal forms in question are

Multivalued dependencies (MVDs) are an important class of relational constraints that is fundamental to relational database design. Reflexivity axiom, complementation rule, and pseudo-transitivity rule form a minimal set of inference rules for the implication of MVDs. The complementation rule plays a distinctive role as it takes into account the underlying relation schema R which the MVDs are defined on. The R-axiom ∅↠R is much weaker than the complementation rule, but is sufficient to form a minimal set of inference rules together with augmentation and pseudo-difference rule. Fagin has asked whether it is possible to reduce the power of the complementation rule and drop the augmentation rule at the same time and still obtain a complete set. It was argued that there is a trade-off between complementation rule and augmentation rule, and one can only dispense with one of these rules at the same time. It is shown in this paper that an affirmative answer to Fagin's problem can nevertheless be achieved. In fact, it is proven that R-axiom together with a weaker form of the reflexivity axiom, pseudo-transitivity rule and exactly one of union, intersection or difference rule form such desirable minimal sets. The positive solution to this problem gives further insight into the difference between the notions of functional and multivalued dependencies.

In this paper we present an algorithm that determines whether or not a relation R is in Third Normal Form (3NF). The algorithm works by classifying the attributes of R into so-called dependency sets that are based on the set of functional dependencies defined on R. A new type of dependency graph is introduced to visualize the dependencies. The algorithm will run faster than algorithms designed to find all of the candidate keys of R, especially if there exists more than one dependency set.

A new normal form, namely, object-normal form (ONF), is introduced. It is shown that the existing definitions of the fifth normal form (5NF) are unsatisfactory. The correct definition is given for the first time. The importance of the 5NF is demonstrated. For improving data representation in a database with a 5NF schema, the notion of negating relation is introduced. It serves as a basis for the new normal form, namely, the sixth normal form. Combining requirements of the ONF and other normal forms, new normal forms are defined: the fourth object-normal form, the fifth object-normal form, and the sixth object-normal form. It is shown that the standard order of steps of the normalization procedure should be changed: first, the specific requirements of the fourth normal form should be satisfied, and only then the requirements of the second normal form, and so forth.

This paper studies functional dependencies in q-Horn theories, and discusses their use in knowledge condensation. We introduce compact model-based representations of q-Horn theories, analyze the structure of functional dependencies in q-Horn theories, and show that every minimal functional dependency in a q-Horn theory Σ can be expressed either by a single term or by a single clause. We also prove that the set of all minimal functional dependencies in Σ is quasi-acyclic. We then develop polynomial time algorithms for recognizing whether a given functional dependency holds in a q-Horn theory, which is represented either by a q-Horn CNF or as the q-Horn envelope of a set of models. Finally, we show that every q-Horn theory has a unique condensation, and can be condensed in polynomial time.

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).

The functional dependency inference problem is the following. Given a relation r, find a set of functional dependencies that is equivalent with the set of all functional dependencies holding in r. All known algorithms for this task have running times that can be in the worst case exponential in the size of the smallest cover of the dependency set. We consider approximate dependency inference. We define various measures for the error of a dependency in a relation. These error measures have the value 0 if the dependency holds and a value close to 1 if the dependency clearly does not hold. Depending on the measure used, all dependencies with error at least ϵ in r can be detected with high probability by considering only O(1ε) or O(|r|12/ε) random tuples of r. We also show how a machine learning algorithm due to Angluin et al. can be applied to give in output-polynomial time an approximately correct cover for the set of dependencies holding in r.

We introduce a new normal form, called essential tuple normal form (ETNF), for relations in a relational database where the constraints are given by functional dependencies and join dependencies. ETNF lies strictly between fourth normal form and fifth normal form (5NF, also known as projection-join normal form). We show that ETNF, although strictly weaker than 5NF, is exactly as effective as 5NF in eliminating redundancy of tuples. Our definition of ETNF is semantic, in that it is defined in terms of tuple redundancy. We give a syntactic characterization of ETNF, which says that a relation schema is in ETNF if and only if it is in Boyce-Codd normal form and some component of every explicitly declared join dependency of the schema is a superkey.

In the relational model of data the Fourth Normal Form condition guarantees the elimination of data redundancy in terms of functional and multivalued dependencies. For efficient means of data processing the industry standard SQL permits partial data and duplicate rows of data to occur in database systems. Here, the combined class of uniqueness constraints, functional and multivalued dependencies is more expressive than the class of functional and multivalued dependencies itself. Consequently, the Fourth Normal Form condition is not suitable for SQL databases. We characterize the associated implication problem of the combined class in the presence of NOT NULL constraints axiomatically, algorithmically and logically. Based on these results we are able to establish a suitable Fourth Normal Form condition for SQL.

The issue of providing a formal justification for the use of fourth normal form (4NF) in relational database design is investigated. Extending earlier work by other authors that provided formal definitions of an insertion anomaly in the case of functional dependency (FD) constraints, formal definitions are provided for two types of an insertion anomaly for the case when both FD and multivalued dependency (MVD) constraints are permitted. It is shown that both types of insertion anomaly are equivalent conditions on a relation scheme and a relation scheme is in 4NF if and only if both anomalies are absent. It is also shown that another type of insertion anomaly that does not reflect the symmetrical nature of MVDs is a weaker condition than 4NF.

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 recently introduced information-theoretic approach to analyzing redundancies in database design was used to justify normal forms like BCNF that completely eliminate redundancies. The main notion is that of an information content of each datum in an instance (which is a number in [0,1]): the closer to 1, the less redundancy it carries. In practice, however, one usually settles for 3NF which, unlike BCNF, may not eliminate all redundancies but always guarantees dependency preservation.In this paper we use the information-theoretic approach to prove that 3NF is the best normal form if one needs to achieve dependency preservation. For each dependency-preserving normal form, we define the price of dependency preservation as an information-theoretic measure of redundancy that gets introduced to compensate for dependency preservation. This is a number in the [0,1] range: the smaller it is, the less redundancy a normal form guarantees. We prove that for every dependency-preserving normal form, the price of dependency preservation is at least 1/2, and it is precisely 1/2 for 3NF. Hence, 3NF has the least amount of redundancy among all dependency-preserving normal forms. We also show that, information-theoretically, unnormalized schemas have at least twice the amount of redundancy than schemas in 3NF.

In the relational model, various relationships may exist between the attributes in a relation. The relationships are described by functional and multivalued dependencies. The functional dependencies are the basic elements for the decomposition of a relation into a family of relations in second, third, and Boyce-Codd normal forms. The multivalued dependencies, which include the functional dependencies as a special case, extend the decomposition further into a collection of relations in fourth normal form. This paper examines the conditions under which a relation in Boyce-Codd normal form should be decomposed further into fourth normal form and a fourth normal form normalization procedure is presented.

Publisher Summary Normal forms are an attempt to make sure that true data is not destroyed or false data is not created in the database. One of the ways of avoiding errors is to represent a fact only once in the database, because if a fact appears more than once, one of the instances of it is likely to be in error. This process of table design is called “normalization.” A normal form is a way of classifying a table based on the functional dependencies (FDs) in it. A multivalued dependency (MVD) means that if the value of one attribute is known, the values of a set of another attribute can always be determined. The definition of first normal form (1NF) is that the table has no repeating groups and that all columns have scalar values. A table is in second normal form (2NF) if it has no partial key dependencies. A table is in third normal form (3NF) if for all X→Y—where X and Y are columns of a table—X is a key or Y is part of a candidate key. Elementary key normal form (EKNF) is a subtle enhancement on 3NF. The Boyce–Codd normal form (BCNF) is the normal form that actually removes all transitive dependencies. Fourth normal form (4NF) makes use of multivalued dependencies. Fifth normal form (SNF), also called the “Join-Projection Normal Form” or the “Projection-Join Normal Form,” is based on the idea of a lossless JOIN or the lack of a join-projection anomaly.

Multivalued dependencies, which consist of an important class of constraints, are formulated in the same manner as other constraints in fuzzy relational databases. The compatibility degree of a tuple value with a multivalued dependency is a value contained in the interval [0,1]. Whether a tuple satisfies the multivalued dependency is determined by comparing the compatibility degree with the value of membership attribute. The formulations for a multivalued dependency, which do not contain any parameters, are addressed on the basis of two interpretations. They correspond to using Godel implication and material implication, respectively. In the interpretation corresponding to using Godel implication, extended sound and complete inference rules of the conventional ones are valid for any multivalued dependency. On the other hand, in the interpretation corresponding to using material implication, the extended inference rules are valid for multivalued dependencies with identity relations, but is not so for ones with resemblance relations. In the latter case, new sound and complete inference rules have been discovered.

Classical and fuzzy functional dependencies, which consist of an important class of constraints, are examined in fuzzy relational databases. The truth value of a proposition expressing a functional dependency is not a binary value even for a classical functional dependency in fuzzy relational databases. Each tuple has a compatibility degree with a functional dependency degree which is contained in the interval [0, 1]. In each tuple it is determined by the comparison of the compatibility degree with the value of membership attribute whether that tuple satisfies the functional dependency. This means that the functional dependency is dealt with in the same manner as the other constraints. Armstrong's inference rules are sound and complete for classical functional dependencies as well as in relational databases, but they are not for fuzzy functional dependencies. Sound and complete inference rules different from Armstrong's ones hold for fuzzy functional dependencies. >

The relationship between redundancy elimination and normal forms in relational database design is investigated for the case where the constraints contain functional dependencies (FDs) and arbitrary join dependencies (JDs). Extending previous work on the relationship between fourth normal form (4NF) and redundancy elimination, a general definition of redundancy is proposed which is applicable to any type of relational dependency including arbitrary JDs. It is then shown that redundancy is eliminated if and only if the set of dependencies satisfies a new condition called key-complete normal form (KCNF). KCNF requires that the left-hand side of every FD is a superkey and that for every JD, every attribute in the relation scheme is contained in the union of the components of the JD which are superkeys. It is also shown that KCNF is a strictly weaker condition than projection-join normal form (PJ/NF), the original normal form proposed for Jds.

We describe an algorithm to test whether a multivalued dependency is implied by a set of functional and join dependencies. The worst case running time of the algorithm is O(nm), where n is the length of the input and m is the number of the attributes in the universe. We also apply the algorithm to test implication of embedded multivalued dependencies, lossless join dependencies, acyclic join dependencies, first order hierarchical decompositions, and functional dependencies. The worst case running time of the algorithm for all these problems is still polynomial in the length of the input.

An algorithm is given for deciding whether a functional or a multivalued dependency σ (with a right-hand side Y ) is implied by a set of functional and multivalued dependencies Σ. The running time of the algorithm is O (| Y |‖Σ‖), where Y is the number of attributes in Y and ‖Σ‖ is the size of the description of Σ. The problem of constructing the dependency basis of a set of attributes X is also investigated. It is shown that the dependency basis can be found in O ( S ‖Σ‖) time, where S is the number of sets in the dependency basis. Since functional and multivalued dependencies correspond to a subclass of propositional logic (that can be viewed as a generalization of Horn clauses), the algorithm given is also an efficient inference procedure for this subclass of propositional logic.

Although several Fourth Normal Form (4NF) decomposition algorithms have been published, the problem's computational complexity remains an open question. Part of the difficulty is that no one has established an upper bound on the size of a 4NF decomposition scheme for a given number of attributes. We prove such an upper bound and we present an algorithm which is worst-case optimal: it never produces a 4NF decomposition scheme that is larger than the upper bound.

Two decision problems related to multivalued dependencies in a relational database are considered. In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M of multivalued dependencies on a set U of attributes, whose running time is proportional to min $(k^2 |U|,||F \cup M||^2 )$ where k and $|U|$ are the numbers of dependencies in $F \cup M$ and attributes in U, respectively, and $||F \cup M||$ is the size of description of F and M. A related algorithm is also considered which decides whether or not there exists a nontrivial multivalued dependency that is valid in a projection of the original relation.

It is known that there is an eqmvalence between functional dependencies m a relatmonal database and a certain fragment of proposmonal logic Thins eqmvalence is extended to include both functional and multivalued dependencmes. Thus, for each dependency there is a corresponding statement m proposmonal logic. It ms then shown that a dependency (funcuonal or multivalued) is a consequence of a set of dependencies ff and only ff the corresponding proposiuonal statement ~s a consequence of the corresponding set of proposmonal statements. Examples are given to show that these techniques are valuable mn provmdmg much shorter proofs of theorems about dependencies than have been obtained by more tradmonal means It is shown that this eqmvalence cannot be extended to include either join dependencies or embedded multmvalued dependencies.