LOGIC AND ALGEBRAIC LANGUAGES FOR INTEROPERABILITY IN MULTIDATABASE SYSTEMS

Developing a declarative approach to interoperability in the context o f multidatabase systems is a major goal of this research. We take a fi rst step toward this goal in this paper, by developing a simple logic called SchemaLog which is syntactically higher-order but has a first-o rder semantics. SchemaLog can provide for interoperability among multi ple relational databases in a federation of database systems. We devel op a fixpoint theory for the definite clause fragment of SchemaLog and show its equivalence to the model-theoretic semantics. We also develo p a sound and complete proof procedure for all clausal theories. We es tablish 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 re trieving and manipulating data and schema from databases in a multidat abase system, and prove its equivalence to a form of relational calcul us inspired by SchemaLog syntax. We illustrate the simplicity and powe r of SchemaLog with a variety of applications involving database progr amming (with schema browsing), schema integration, schema evolution, c ooperative 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 dat abases. (C) Elsevier Science Inc., 1997.