On Answering Queries in the Presence of Limited Access Patterns

This is the latest version of this item.

Abstract

In information-integration systems, source relations often have limitations on access patterns to their data; i.e., when one must provide values for certain attributes of a relation in order to retrieve its tuples. In this paper we consider the following fundamental problem: can we compute the complete answer to a query by accessing the relations with legal patterns? The {\em complete} answer to a query is the answer that we could compute if we could retrieve all the tuples from the relations. We give algorithms for solving the problem for various classes of queries, including conjunctive queries, unions of conjunctive queries, and conjunctive queries with arithmetic comparisons. We prove the problem is undecidable for datalog queries. If the complete answer to a query cannot be computed, we often need to compute its maximal answer. The second problem we study is, given two conjunctive queries on relations with limited access patterns, how to test whether the maximal answer to the first query is contained in the maximal answer to the second one? We show this problem is decidable using the results of monadic programs.

Available Versions of this Item

• Computing Complete Answers to Queries with Binding Restrictions. (deposited 25 Feb 2000 16:00)
  • On Answering Queries in the Presence of Limited Access Patterns. (deposited 08 Oct 2000 17:00) [Currently Displayed]