Li, C. (1999) Computing Complete Answers to Queries with Binding Restrictions. Technical Report. Stanford.
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.
|Item Type:||Techreport (Technical Report)|
|Uncontrolled Keywords:||complete answers to queries, binding restrictions, information-integration systems, query containment, query equivalence, Datalog programs.|
|Subjects:||Computer Science > Data Integration and Mediation|
|Related URLs:||Project Homepage||http://infolab.stanford.edu/|
|Deposited By:||Import Account|
|Deposited On:||25 Feb 2000 16:00|
|Last Modified:||28 Dec 2008 09:30|
Available Versions of this Item
- Computing Complete Answers to Queries with Binding Restrictions. (deposited 25 Feb 2000 16:00) [Currently Displayed]
Repository Staff Only: item control page