Due to the development of the World Wide Web, the integration of heterogeneous data sources has become a major concern of the database community. Appropriate architectures and query languages have been proposed. Yet, the problem of data conversion which is essential for the development of mediators/wrappers architectures has remained largely unexplored.

The goal of this work is to integrate in a general framework the different query optimization techniques that have been proposed in the object-oriented context. As a first step, we focus essentially on the logical aspect of query optimization. In this paper, we propose a formalism (i) that unifies different rewriting formalisms, (ii) that allows easy and exhaustive factorization of duplicated subqueries, and (iii) that supports heuristics in order to reduce the optimization rewriting phase.

According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A positive Boolean dependency is built using the Boolean connectives ⋏, ⋎, and ↛; a general Boolean dependency (with negation) may use also the Boolean connective ¬.) Actually, the definition of satisfaction is not meaningful for Boolean dependencies with negation, since many are never satisfied. We show how the definition of satisfaction should be changed in order to make Boolean dependencies with negation meaningful and correct the error. We associate with each relation r a set α( r ) of truth assignments , as follows. For each pair of distinct tuples of r , the set α( r ) contains the truth assignment that maps an attribute A to true if the two tuples are equal on A , and to false if the two tuples have different values for A . A Boolean dependency σ is satisfied by a relation r if σ (i.e., the corresponding Boolean formula) satisfies every truth assignment of α( r ). The original definition given in the paper is equivalent to having α( r ) also include the truth assignment that is generated by pairs in which both tuples are really the same tuple of r , that is, to having α( r ) also always include the truth assignment τ mapping all attributes to true. Under that definition, however, many Boolean dependencies with negation are never satisfied and, hence, are meaningless. More precisely, according to the original definition, a Boolean dependency is satisfied by

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.

A general study is made of two basic integrity constraints on relations: functional and multivalued dependencies. The latter are studied via an equivalent concept: decompositions. A model is constructed for any possible combination of functional dependencies and decompositions. The model embodies some decompositions as unions of relations having different schemata of functional dependencies. This suggests a new, stronger integrity constraint, the degenerate decomposition. More generally, the theory demonstrates the importance of using the union operation in database design and of allowing different schemata on the operands of a union. Techniques based on the union lead to a method for solving the problem of membership of a decomposition in the closure of a given set of functional dependencies and decompositions. The concept of antiroot is introduced as a tool for describing families of decompositions, and its fundamental importance for database design is indicated.

The purpose of this paper is to present a new approach to the conceptual design of logical schemata for relational databases. One-to-one, one-to-many, and many-to-many relationships between the attributes of database relations are modeled by means of functional dependencies and multivalued dependencies. A new type of dependency is introduced: first-order hierarchical decomposition. The properties of this new type of dependency are studied and related to the normalization process of relations. The relationship between the concept of first-order hierarchical decomposition and the notion of hierarchical organization of data is discussed through the normalization process.