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
Presentations
Publications
This research has been funded in part by NSF grant 9985114.