Stanford InfoLab Publication Server

Query Planning with Limited Source Capabilities

Li, C. and Chang, E. (2000) Query Planning with Limited Source Capabilities. In: 16th International Conference on Data Engineering (ICDE 2000), February 29 - March 3, 2000, San Diego, CA.




In information-integration systems, sources may have diverse and limited query capabilities. In this paper we show that because sources have restrictions on retrieving their information, sources not mentioned in a query can contribute to the query result by providing useful bindings. In some cases we can access sources repeatedly to retrieve bindings to answer a query, and query planning thus becomes considerably more challenging. We find all the obtainable answers to a query by translating the query and source descriptions to a simple recursive Datalog program, and evaluating the program on the source relations. This program often accesses sources that are not in the query. Some of these accesses are essential, as they provide bindings that let us query sources, which we could not do otherwise. However, some of these accesses can be proven not to add anything to the query's answer. We show in which cases these off-query accesses are useless, and prove that in these cases we can compute the complete answer to the query by using only the sources in the query. In the cases where off-query accesses are necessary, we propose an algorithm for finding all the useful sources for a query. We thus solve the optimization problem of eliminating the unnecessary source accesses, and optimize the program to answer the query.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:information-integration systems, limited source capabilities, Datalog programs.
Subjects:Computer Science > Data Integration and Mediation
Related URLs:Project Homepage
ID Code:431
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:27 Dec 2008 14:47

Download statistics

Repository Staff Only: item control page