Li, C. (1999) Computing Complete Answers to Queries with Binding Restrictions. Technical Report. Stanford.
![[img]](/style/images/fileicons/application_pdf.png) ![](/364/thumbnails/1/preview.png) Preview |
| PDF 350Kb |
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.
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 |
---|
Projects: | Miscellaneous |
---|
Related URLs: | Project Homepage | http://infolab.stanford.edu/ |
---|
ID Code: | 364 |
---|
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]
Download statistics
![](/irstats.cgi?page=last_month&set=eprint_364)
![](/irstats.cgi?page=last_year&set=eprint_364)
Repository Staff Only: item control page