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.

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.

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.

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.

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.

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.