Querying Data under Access Limitations
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 50-59
Abstract
Data sources on the web are often accessible through web interfaces that present them as relational tables, but require certain attributes to be mandatorily selected, e.g., via a web form. In a scenario where we integrate a set of such sources, and we pose queries over them, the values needed to access a source may have to be retrieved from other sources that are possibly not even mentioned in the query: answering queries at best can then be done only with a potentially recursive query plan that gets all obtainable answers to the query. Since data sources are typically distributed over a network, a major cost indicator for the execution of a query plan is the number of accesses to remote sources. In this paper we present an optimization technique for conjunctive queries that produces a query plan that: (1) minimizes the number of accesses according to a strong notion of minimality; (2) excludes all sources that are not relevant for the query. We introduce Toorjah, a prototype system that answers queries posed on sources with limitations by means of optimized query plans. Toorjah adopts a strategy that is aimed to retrieve answers as early as possible during query processing, and to present them to the user as they are computed. We provide experimental evidence of the effectiveness of our optimization, by showing the reduction of the number of accesses in a large number of cases.Keywords
This publication has 11 references indexed in Scilit:
- Efficiently ordering subgoals with access constraints2006
- Computing complete answers to queries in the presence of limited access patternsThe VLDB Journal, 2003
- Query planning with limited source capabilities2002
- Optimized Querying of Integrated Data over the Web2002
- Answering queries using views: A surveyThe VLDB Journal, 2001
- Answering queries with useful bindingsACM Transactions on Database Systems, 2001
- Query optimization in the presence of limited access patterns1999
- Database techniques for the World-Wide WebACM SIGMOD Record, 1998
- Answering queries using templates with binding patterns (extended abstract)1995
- Optimal implementation of conjunctive queries in relational data bases1977