Logic and Algebraic languages for interoperability in multidatabase systems

Developing a declarative approach to interoperability in the context of multidatabase 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 interoperability among multiple relational databases in a federation of database systems. We develop a fixpoint theory for the definite clause fragment of SchemaLog and show its equivalence to the model-theoretic semantics. We also develop a sound and complete proof procedure for all clausal theories. We establish the correspondence between SchemaLog and first-order predicate calculus and provide a reduction of SchemaLog to predicate calculus. We propose an extension to classical relational algebra, capable of retrieving and manipulating data and schema from databases in a multidatabase system, and prove its equivalence to a form of relational calculus inspired by SchemaLog syntax. We illustrate the simplicity and power of SchemaLog with a variety of applications involving database programming (with schema browsing), schema integration, schema evolution, cooperative query answering, and sophisticated forms of aggregation in the spirit of OLAP (On-Line Analytical Processing). We also highlight our implementation of SchemaLog realized on a federation of INGRES databases. © Elsevier Science Inc., 1997.