The MiniCon Algorithm is a new algorithm for answering queries using views that is used as the query reformulator for the data integration system Tukwila.

Query Reformulation Overview

A data integration system provides a uniform method for querying across multiple heterogeneous databases.  It presents a mediated schema to represent a particular application domain, and data sources are mapped as views over this mediated schema.  The user asks a query over the mediated schema and the data integration system reformulates this into a query over the data sources and executes it.  The process of  translating the user query into a query over the data systems is the process of query reformulation, which is the problem that MiniCon solves.
Query Reformulating Challenges
In the data integration system, there can by hundreds or thousands of data sources.  These sources may be added or removed from the system at any time.  Thus, there are two main challenges to query reformulation: first, we must insure that user queries can be answered in a short amount of time.  Second, we must enable sources to be added and deleted with the least amount of human intervention.  Representing the data sources as views over the mediated schema enables new data sources to be added with a minimum of human intervention, but the problem of translating the query into queries over the data sources (query reformulation) is NP-Complete for even conjunctive queries.   Our goal in this project was to find a scalable algorithm for query reformulation (which is equivalent to the problem of answering queries using views) and to show experimentally that these algorithms were feasible for even a large number of data sources.

Project Members



This research has been funded in part by NSF grant 9985114.