On the logical foundations of schema integration and evolution in heterogeneous database systems

Developing a declarative approach to schema integration in the context of heterogeneous database systems is a major goal of this research. We take a first step toward this goal in this paper, by developing a simple logic called SchemaLog which is syntactically higher-order but has a first-order semantics. SchemaLog can provide for a logical integration of multiple relational databases in a federation of database systems. We develop a fixpoint theory as well as a sound and complete proof theory for the definite clause fragment of SchemaLog and show their equivalence to the model-theoretic semantics. We argue that a uniform framework for schema integration as well as schema evolution is both desirable and possible. We illustrate the simplicity and power of SchemaLog with a variety of applications involving database programming (with schema browsing), schema integration, schema evolution, and cooperative query answering.