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

Relational database design addresses applications for data that is certain. Modern applications require the handling of uncertain data. Indeed, one dimension of big data is veracity. Ideally, the design of databases helps users quantify their trust in the data. For that purpose, we need to establish a design framework that handles responsibly any knowledge of an organization about the uncertainty in their data. Naturally, such knowledge helps us find database designs that process data more efficiently. In this paper, we apply possibility theory to introduce the class of possibilistic multivalued dependencies that are a significant source of data redundancy. Redundant data may occur with different degrees, derived from the different degrees of uncertainty in the data. We propose a family of fourth normal forms for uncertain data. We justify our proposal showing that its members characterize schemata that are free from any redundant data occurrences in any of their instances at the targeted level of uncertainty in the data. We show how to automatically transform any schema into one that satisfies our proposal, without loss of any information. Our results are founded on axiomatic and algorithmic solutions to the implication problem of possibilistic functional and multivalued dependencies which we also establish.

In previous work, we explored a new context of technical debt that relates to database normalization design decisions. We claimed that database normalization debts are likely to be incurred for tables below the fourth normal form. We proposed a method to prioritize the tables that should be normalized based on their impact on data quality and performance. In this study, we propose a framework to identify normalization debt items (i.e. tables below the fourth normal form) by mining the data stored in each table. Our framework makes use of association rule mining to discover functional dependencies between attributes in a table, which will help determine the current normal form of that table and reveal debt tables. To illustrate our method, we use a case study from Microsoft, AdventureWorks database. The results revealed the applicability of our framework to identify debt tables.

Database normalization is the one of main principles for designing relational databases. The benefits of normalization can be observed through improving data quality and performance, among the other qualities. We explore a new context of technical debt manifestation, which is linked to ill-normalized databases. This debt can have long-term impact causing systematic degradation of database qualities. Such degradation can be liken to accumulated interest on a debt. We claim that debts are likely to materialize for tables below the fourth normal form. Practically, achieving fourth normal form for all the tables in the database is a costly and idealistic exercise. Therefore, we propose a pragmatic approach to prioritize tables that should be normalized to the fourth normal form based on the metaphoric debt and interest of the ill-normalized tables, observed on data quality and performance. For data quality, tables are prioritized using the risk of data inconsistency metric. Unlike data quality, a suitable metric to estimate the impact of weakly or un-normalized tables on performance is not available. We estimate performance degradation and its costs using Input\Output (I\O) cost of the operations performed on the tables and we propose a model to estimate this cost for each table. We make use of Modern Portfolio Theory to prioritize tables that should be normalized based on the estimated I\O cost and the likely risk of cost accumulation in the future. To evaluate our methods, we use a case study from Microsoft, AdventureWorks. The results show that our methods can be effective in reducing normalization debt and improving the quality of the database.

Database normalization is one of the main principles for designing relational databases, which is the most popular database model, with the objective of improving data and system qualities, such as performance. Refactoring the database for normalization can be costly, if the benefits of the exercise are not justified. Developers often ignore the normalization process due to the time and expertise it requires, introducing technical debt into the system. Technical debt is a metaphor that describes trade-offs between short-term goals and applying optimal design and development practices. We consider database normalization debts are likely to be incurred for tables below the fourth normal form. To manage the debt, we propose a multi-attribute analysis framework that makes a novel use of the Portfolio Theory and the TOPSIS method (Technique for Order of Preference by Similarity to Ideal Solution) to rank the candidate tables for normalization to the fourth normal form. The ranking is based on the tables estimated impact on data quality, performance, maintainability, and cost. The techniques are evaluated using an industrial case study of a database-backed web application for human resource management. The results show that the debt-aware approach can provide an informed justification for the inclusion of critical tables to be normalized, while reducing the effort and cost of normalization.

The library database design needs to accord certain rules, in relational database, this rule is paradigm. Paradigm is in line with a certain level of relational schema collections. Relational database relationship must meet certain requirements, namely to meet the different paradigms. At present, there are six kinds of relationship database paradigm: the first normal form (1NF), the second normal form (2NF), the third normal form (3NF), BC normal form (BCNF), the fourth normal form (4NF), the fifth normal form (5NF) and the sixth Normal Form (6NF). The 1NF is the minimum paradigm for requirement. Basing on the 1NF, further meeting more requirements is the 2NF and a higher level paradigm, in practical design application, you only need to reach the 3NF.

Intuitionistic fuzzy databases are used to handle imprecise and uncertain data as they represent the membership, nonmembership, and hesitancy associated with a certain element in a set. This paper presents the Intuitionistic Fuzzy Fourth Normal Form to decompose the multivalued dependent data. A technique to determine Intuitionistic Fuzzy multivalued dependencies by working on the closure of dependencies has been proposed. We derive the closure by obtaining all the logically implied dependencies by a set of Intuitionistic Fuzzy multivalued dependencies, i.e., Inference Rules. A complete set of inference rules for the Intuitionistic Fuzzy multivalued dependencies has been given along with the derivation of each rule. These rules help us to compute the dependency closure and we further use the same for defining the Intuitionistic Fuzzy Fourth Normal Form.

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.

Consider a relation schema with a set of dependency constraints. A fundamental question is what is the minimum space where the possible instances of the schema can be "stored". We study the following model. Encode the instances by giving a function which maps the set of possible instances into the set of words of a given length over the binary alphabet in a decodable way. The problem is to find the minimum length needed. This minimum is called the information content of the database. We investigate several cases where the set of dependency constraints consist of relatively simple sets of functional or multivalued dependencies. We also consider the following natural extension. Is it possible to encode the instances such a way that small changes in the instance cause a small change in the code.

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

An equivalence between logic algebra and functional dependencies shows that a functional dependency is implied by a set of functional dependencies if and only if its corresponding product term is implied by corresponding logic function. In this paper we shall state and proof a key point ignored for a long time, that is any prime implicate in a corresponding logic function of a set of functional dependencies correspond a simplest functional dependency whose left side has no redundant attributes. Based on the point many problems in theory of functional dependency, such as computing minimum covers, all candidate keys, and closure of any set of attributes can be solved effectively and uniformly. The conclusion can be extended to data dependencies include multivalued dependencies easily.

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.

The Nested List Normal Form is proposed as a syntactic normal form for semantically well-designed database schemata obtained from any arbitrary finite nesting of records and lists. The Nested List Normal Form is defined in terms of functional and multivalued dependencies, independent from any specific data model, and generalises the well-known Fourth Normal Form from relational databases in order to capture more application domains.

The role of null values in a relational data base is considered within the framework of multivalued dependencies. When a relation contains null values, a different treatment of data dependencies and different relational operations such as projection and join, are necessary. This paper develops a complete axiomatization for the revised multivalued dependencies. In particular, complementation, reflexivity, augmentation, and union are shown to be a complete set of inference rules. In contrast with the conventional multivalued dependencies, the transitivity rule cannot be used. These results provide a framework for the use of the revised multivalued dependencies in choosing relations and their attributes for a feasible data-base design.

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.

It is shown that the analysis of functional dependencies is useful when one wants to decompose a multilevel relation in a collection of single-level relations. The decomposition of a multilevel relation into a collection of fourth normal form (4NF) relations according to various functional dependencies is studied. These decompositions are compared to the decomposition algorithms in single-level relations proposed by the Sea View project and by S. Jajodia and R. Sandhu (IEEE Symp. on Security & Privacy, 1991). It appears that the first step of the decomposition algorithms is simply the normalization of the multilevel relation in 3NF (or in 4NF). The authors propose an analysis of functional dependencies that seem natural from a semantical point of view. A multilevel relation is decomposed into 4NF relations according to these functional dependencies, and it is then shown how to decompose these relations into single-level relations. It is thought this analysis provides a good solution to the polyinstantiation problem and that it would lead to correct definitions of update operations. >

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.

Many practitioners and academicians believe that data violating fourth normal form is rarely encountered. We report upon a study of forty organizational databases; nine of them contained data violating fourth normal form. Consequently, the need to understand and user fourth normal form is more important than previously believed.

The identification and searching problems are because of the fact that some information repeats for a given programmer: a programmer has many skills and this causes the programmer information to be repeated for each such skill. Such repeated information is called a “repeating group.― To avoid the problems, one should avoid repeating groups. When tables contain no repeating groups any more, they are in first normal form. “First normal form― is a basic requirement of the relational model. Tables that are in first normal form and in which all attributes depend on the whole key, are in “second normal form.― Tables that are in second normal form and in which all attributes depend only on the key or upon an alternate key, are in “third normal form.― “Fourth normal form― is a problem only for relations that are all key. If such relations have attributes, then either the attribute depends on the whole key, and the table is in fourth normal form, or the attribute does not depend on the whole key so that the table is not in second normal form and must be split according to that criterion. When anomalous tables have been split as indicated, they are in “fifth normal form.―

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.

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.

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.

In this paper, we show that multivalued dependencies and join dependencies are not very viable for certain cases of relational database design; they are sometimes difficult to be identified; they are relation sensitive; and we are unable to talk about these types of dependencies without referring to some specific relation. We also show that the entity-relationship approach can be used for relational database design without any of the above mentioned undesirable properties of multivalued dependencies and join dependencies.

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes U , and a set of multivalued dependencies (MVDs) M over these attributes, we present an algorithm to obtain a nested normal form decomposition of U with respect to M . Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by M , and being a faithful and nonredundant representation of U . Moreover, if the given set of MVDs is conflict-free, then the nested normal form decomposition is also dependency-preserving. Finally, we show that if M is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [9, 16] of U with respect to M .

Several researchers (Beeri, Bernstein, Chiu, Fagin, Goodman, Maier, Mendelzon, Ullman, and Yannakakis) have introduced a special class of database schemes, called acyclic or tree schemes. Beeri et al. have shown that an acyclic join dependency, naturally defined by an acyclic database scheme, has several desirable properties, and that an acyclic join dependency is equivalent to a conflict-free set of multivalued dependencies. However, since their results are confined to multivalued and join dependencies, it is not clear whether we can handle functional dependencies independently of other dependencies. In the present paper we define an extension of a conflict-free set, called an extended conflict-free set , including multivalued dependencies and functional dependencies, and show the following two properties of an extended conflict-free set: There are three equivalent definitions of an extended conflict-free set. One of them is defined as a set including an acyclic joint dependency and a set of functional dependencies such that the left and right sides of each functional dependency are included in one of the attribute sets that construct the acyclic join dependency. For a relation scheme with an extended conflict-free set, there is a decomposition into third normal form with a lossless join and preservation of dependencies.

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.

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.

We discuss the objectives of including functional dependencies in the definition of a relational database. We find two distinct objectives. The appearance of a dependency in the definition of a database indicates that the states of the database are to encode a function. A method based on the chase of calculating the function encoded by a particular state is given and compared to methods utilizing derivations of the dependency. A test for deciding whether the states of a schema may encode a nonempty function is presented as is a characterization of the class of schemas which are capable of encoding nonempty functions for all the dependencies in the definition. This class is the class of dependency preserving schemas as defined by Beeri et al. and is strictly larger than the class presented by Bernstein. The second objective of including a functional dependency in the definition of a database is that the dependency be capable of constraining the states of the database; that is, capable of uncovering input errors made by the users. We show that this capability is weaker than the first objective; thus, even dependencies whose functions are everywhere empty may still act as constraints. Bounds on the requirements for a dependency to act as a constraint are derived. These results are founded on the notion of a weak instance for a database state, which replaces the universal relation instance assumption and is both intuitively and computationally more nearly acceptable.