An Algebra and Calculus for Multidatabases with Integrity Constraints

Abstract

Litwin et. al. have developed a language called MSQL for query multidatabases. Subsequently, Grant, Litwin, Roussopolous and Sellis have developed a calculus and algebra associated with MSQL that facilitates querying and interoperation in a multidatabase environment. In this paper, we build upon their framework by assuming that a set of integrity constraints must be satisfied. Even though each individual database in a multidatabase may satisfy the integrity constraints, the entire multidatabase itself may not satisfy the constraints. We propose three new data retrieval notions based on whether the constraint semantics is ``naive'', ``skeptical'' or makes ``choices.'' We propose a semantics for these operations, and develop an algebra and calculus based on these operators. We prove that the algebra can be embedded within the calculus -- however, the calculus is strictly more powerful than the algebra. We study various algebraic properties linking the newly defined operators together and show how these algebraic properties can be used for query optimization. (Also cross-referenced as UMIACS-TR-94-86)