Previous work on schema integration typically has taken either a very ad-hoc approach of identifying a speci c integration problem and providing a solution for it, or a very general approach o f p r o viding a rich i n tegration facility, b u t o n e that requires writing rule-based, logic-based, or conventional programs to specify an integration.The latter approach i s powerful, but places an undue burden on someone to v erify the validity o f a n i n tegration that is de ned, as well as to write and maintain the program(s).Alternatively, one might follow a transformation-based approach where a collection of schema transformations is provided, together with a theoretical basis of validity in applying the transformations.This approach has been applied successfully to certain problem domains, such a s t h e i n tegration of relational schemas with referential integrity.H owever, one can encode information in arbitrary, complex ways with the relational model, including using non-First Normal Form encodings, and with the incorporation of object technology into the relational model, it is becoming increasingly common for users to create new data types that have their own special semantics.Thus, no speci c theory of schema integration, no matter how complete, can ever account for all possible integration problem domains.To address this situation, we propose an extensible theo r y o f s c hema integration that can serve as a framework for developing theories of schema integration in new problem areas.We then present some general theoretical results concerning schema equivalence that could be used to apply the theory to a number of problem domains.

The notion of when two schemas are equivalent is fimdamental to database design, schema integration, and data model translation.An important notion of schema equivalence, query equivalence was introduced in [3], and used to evaluate the correctness of schema transformations.The logically equivalent notion of calculous equivalence, as well as three progressively weaker notions of schema equivalence were introduced in 1984 by Hull [9, lo], who showed that two schemas with no dependencies are equivalent (under all four notions of equivalence) if and only if they are identical (up to renaming and re-ordering of attributes and relations).Hull also conjectured that the same result holds for schemas with primary keys.In this work, we resolve the conjecture in the affirmative for the case of query equivalence based on mappings using conjunctive relational queries with equality selections.'This is a Massive Digital Data Systems (MDDS) project sponsored by the Advanced Research and Development Committee of the Community Management Staff.

The problems of object identification and data integration in heterogeneous multidatabase systems are addressed. The requirement that object identity be an equivalence relation often is not considered, and is shown to require evaluation of recursive queries against external schemas when translating even simple queries against integrated schemas. Data integration facilities which enforce the properties of object identity being an equivalence relation are presented, including techniques for translation of queries of the integrated data.