Stanford InfoLab Publication Server

On Answering Queries in the Presence of Limited Access Patterns

Li, Chen and Chang, Edward (2001) On Answering Queries in the Presence of Limited Access Patterns. In: 8th International Conference on Database Theory (ICDT 2001) , January 4-6, 2001, London, UK.


This is the latest version of this item.



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.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:limitations access patterns, complete answer to a query, query stability, query containment
Subjects:Computer Science > Databases and the Web
Computer Science > Data Integration and Mediation
Information Integration
Related URLs:Project Homepage, Project Homepage,
ID Code:718
Deposited By:Import Account
Deposited On:08 Oct 2000 17:00
Last Modified:27 Dec 2008 10:31

Available Versions of this Item

Download statistics

Repository Staff Only: item control page