An Algebraic Transformation Framework for Multidatabase Queries

• Main Authors: LIM, Ee Peng, SRIVASTAVA, Jaideep, HWANG, San-Yih
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1995
• Subjects: multidatabase query; integration operation; algebraic transformation; constrained query tree; outerjoin graph; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/13; https://doi.org/10.1007/BF01418060
• Institution: Singapore Management University

Existence of semantic conflicts between component databases severely impacts query processing in a multidatabase system. In this paper, we describe two types of semantic conflicts that have to be dealt with in the integration of databases modeling information about related sets of real-world entities. These are the entity identification problem and the attribute value conflict problem. While the two-way outerjoin operation has been commonly used for resolving entity identification problem between two component relations, outerjoins using regular equality comparisons between component relation keys is shown to produce counter-intuitive entity identification result. We remedy this by defining a new key-equality comparator in place of regular equality comparator, for outerjoins. For the attribute value conflict problem, we define a Generalized Attribute Derivation (GAD) operation which allows user-defined attribute derivation functions to be used to compute new attributes from the component relations' attributes. By adding two-way outerjoin andGAD to the set of relational operations, the traditional algebraic transformation framework for relational queries is no longer adequate for multidatabase query processing and optimization. As a result, we introduce constrained query tree as the multidatabase query representation. We show that some knowledge about query predicates and attribute derivation functions can be used to simplify queries. Such knowledge is modeled as an outerjoin graph attached to every outerjoin operation in the query tree. Based on this, we further extend the traditional algebraic transformation framework to include two-way outerjoins and GAD operations. Our framework demonstrates that properties of selection/join predicates and attribute derivation functions can be used to provide interesting transformation alternatives. This framework also serves as a formal ground for developing optimization strategies for multidatabase queries.