Computing Complete Answers to Queries with Binding Restrictions

We consider the problem of computing the complete answer to a query when there is limited access to relations, i.e., when binding patterns require values to be specified for certain attributes in order to retrieve data from a relation. This problem is common in information-integration systems, where heterogeneous sources have diverse and limited query capabilities. A query is stable if for any instance of the relations mentioned in the query, the complete answer to the query can be computed, using only the binding patterns permitted for queries at the various sources. We first study conjunctive queries, and we show that a conjunctive query is stable if and only if its minimal equivalent query Qm has an order of all the subgoals in Qm , such that each subgoal in the order can be queried with a legal binding pattern. We propose two algorithms for testing stability of conjunctive queries, and we prove this problem is NP-hard. For a nonstable conjunctive query, whether its comp...