Title: Query Transformation in Heterogeneous Information Systems
Authors: Sibel Adali and Xiaolei Qian.
Abstract
A natural problem that arises when accessing information from heterogeneous and autonomous sources is that of making available to the user as much of this information as possible without making the overall system very complicated to use. One solution to this problem is to build a system that allows the user to pose queries as if in a centralized information system and then transforms them to the appropriate queries in the underlying information sources using descriptions of the relevant data stored in each source. In this paper we develop an algorithm that takes as input a conjunctive user query and uses a set of conjunctive view definitions over different information systems to generate all possible transformations that can be performed on the given query. In particular, we describe in detail how the output of this algorithm can be easily used to generate (1) the transformations that allows the access of information sources which can answer the query without any modifications, even though some of these sources may only answer a special case of it, (2) the transformations that can provide answer for only a part of the query, in other words for the relaxations of it. Finally, we discuss the research problems related to query optimization in such an environment.
The paper is submitted for publication. It is available in postscript form at this server.