An Algebraic Transformation Framework for Multidatabase Queries

Publication Type

Journal Article

Publication Date

7-1995

Abstract

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.

Keywords

multidatabase query, integration operation, algebraic transformation, constrained query tree, outerjoin graph

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Distributed and Parallel Databases

Volume

3

Issue

3

First Page

273

Last Page

307

ISSN

0926-8782

Identifier

10.1007/BF01418060

Publisher

Springer Verlag

Additional URL

https://doi.org/10.1007/BF01418060

Link to Full Text

Share

COinS