The Havasu Data Integration System
- A data integration system provides an automated method for querying
across multiple heterogeneous databases in a uniform manner.
Essentially a query on the mediated schema is routed to
mutiple data sources that cumulatively project the schema. The mediated
schema can be provided as a view on the sources in the system or it can
represent a particular application scenario and the data sources can be
seen as views on this mediated schema. Till date all data integration
systems give guarantees about cost of answering a user query. Havasu on
the other hand tries to provide a guarantee on both the cost of
answering a query and the number of answers to the query i.e. we
jointly optimize both the cost and coverage of the plans. Since we want
to give the best guarantees for coverage, we will end up calling all
the sources known to the mediator. To be cost effective we then look at
parallel plans to answer the queries. Source statistics needed to optimize the query plans are not easily available since sources are
independent and hence StatMiner (Statistics Mining module) approximates the statistics like coverage and overlap of sources by
using mining algorithms. The execution engine of Havasu will show adaptiveness in terms of
data source sizes, network conditions,
and other factors.
- Joint Optimization of Cost & Coverage
Existing approaches for optimizing queries in information
integration use decoupled strategies, attempting to optimize coverage
and cost in two separate phases. Since sources tend to have a variety
of access limitations, this type of phased optimization of cost and coverage
can unfortunately lead to expensive planning as well as highly
inefficient plans. We present techniques for joint
optimization of cost and coverage of the query plans. Our algorithms
search in the space of parallel query plans that support multiple
sources for each subgoal conjunct. The refinement of the partial plans
takes into account the potential parallelism between source calls, and
the binding compatibilities between the sources included in the plan.
We introduce a new query plan representation and show that our way of
searching in the space of parallel plans can improve both the plan generation
and plan execution costs compared to existing approaches.
We provide both a System-R style query optimization algorithm as
as a greedy local earch algorithm for searching in the space of such query plans.
- Mining Source Coverage Statistics
Recent work in data integration has shown the importance of
statistical information about the coverage and overlap of sources for
efficient query processing. Despite this recognition there are no effective
approaches for learning the needed statistics. The key challenge in learning
such statistics is keeping the number of needed statistics low enough to have
the storage and learning costs manageable. Navie approaches can become
infeasible very quickly. We present a set of connected techniques that
estimate the coverage and overlap statistics while keeping the needed
statistics tightly under control. We use a hierarchical classification
of the queries, and threshold based variants of familiar data mining
techniques to dynamically decide the level of resolution at which to
learn the statitics.
- Professor Subbarao
- Zaiqing Nie is
working on the Havasu Parplan Optimizer. He is also involved in learning
statistics for the sources taking part in the Havasu Integration system.
- Ullas Nambiar is
developing the StatMiner for Havasu. He is also working on developing the
adaptive execution engine for Havasu.
- Sreelakshmi Vaddi is
working on developing the adaptive execution engine for Havasu with a focus
on ranked query results.
A frequency-based approach for mining coverage statistics in Data
Zaiqing Nie and Subbarao Kambhampati. ICDE 2004 (To appear).
Bibfinder/Statminer: Effectively mining and using Coverage and Overlap
Statistics in Data Integration
Zaiqing Nie, Subbarao Kambhampati and Thomas Hernandez.
Proc. VLDB 2003. Here is the
Frequency-based Coverage Statistics Mining for Data Integration.
Zaiqing Nie, Subbarao Kambhampati.
IJCAI Workshop on Information Integration on the Web. 2003.
Answering Imprecise Database Queries
Ullas Nambiar and Subbarao Kambhampati. ACM WIDM 2003 (Workshop on Web
Information and Data Management).
- S. Kambhampati, U. Nambiar, Z. Nie and S. Vaddi Havasu: A Multi-Objective, Adaptive Query Processing Framework for Web Data Integration ASU CSE TR-02-005.
Z.Nie, U. Nambiar, S. Lakshmi and S. Kambhampati. ASU CSE TR
Coverage Statistics for Websource
Selection in a Mediator
(A short version of this
paper appears in Proceedings of CIKM
- Z. Nie,S. Kambhampati,U. Nambiar and S. Vaddi
Mining Source Coverage Statistics for Data Integration. in Proceedings of the 3rd Intl. Workshop
on Web Information and Data Management (WIDM'01), Atlanta, Georgia, November 9, 2001.
- Z. Nie and S. Kambhampati Joint Optimization of Cost and Coverage of Information Gathering Plans. In Proceedings of the 10th ACM International Conference on Information and Knowledge Management (CIKM), Atlanta, Georgia, November 2001.
- Z. Nie and S. Kambhampati Joint Optimization of Cost and
Coverage of Information Gathering Plans..
ASU CSE TR 01-002.