Computing Complete Answers to Queries with Binding Restrictions

Abstract

W e consider the problem of computing the complete answer to a query when there is limited access to relations, i.e., when binding patterns require v alues 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 permitted for queries at the v arious sources. W e first study conjunctive queries, and we show that a conjunctive query is stable if and only if its minimal equiv alent query Q m has an order of all the subgoals in Q m , such that each subgoal in the order can be queried with a legal binding pattern. W e propose two algorithms for testing stability of conjunctive queries, and we prove this problem is N P -hard. F or a nonstable conjunctive query , whether its complete answer can be computed is data dependent. W e develop a decision tree that guides the query planning process to compute the complete answer to a conjunctive query , if it can be computed at all. W e also study stability of unions of conjunctive queries, and conjunctive queries with arithmetic comparisons. In both cases we propose algorithms for testing stability of queries. Finally , we study Datalog queries, and prove that if a set of rules and a query goal have feasible rule/goal graph, then the query is stable. Keywords: complete answers to queries, binding restrictions, information-integration systems, query containment, query equiv alence, Datalog programs.

Available Versions of this Item

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