TY - JOUR
T1 - Rewriting queries using views with access patterns under integrity constraints
AU - Deutsch, Alin
AU - Ludäscher, Bertram
AU - Nash, Alan
N1 - Funding Information:
IA preliminary version of this paper appeared in [Alin Deutsch, Bertram Ludäscher, Alan Nash, Rewriting queries using views with access patterns under integrity constraints, in: Intl. Conference on Database Theory, ICDT, 2005]. ∗Corresponding author. E-mail addresses: [email protected] (A. Deutsch), [email protected] (B. Ludäscher), [email protected] (A. Nash). 1Research conducted while the author was in the mathematics and computer science departments of UC San Diego, supported by a Microsoft Research Fellowship.
PY - 2007/3/1
Y1 - 2007/3/1
N2 - We study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. We provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. We show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. We show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). These reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons. We also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. That is, except for defining the appropriate constraints, binding patterns do not need special treatment. Finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation.
AB - We study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. We provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. We show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. We show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). These reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons. We also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. That is, except for defining the appropriate constraints, binding patterns do not need special treatment. Finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation.
KW - Access patterns
KW - Integrity constraints
KW - Query rewriting
KW - Views
UR - http://www.scopus.com/inward/record.url?scp=33846828477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33846828477&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2006.11.008
DO - 10.1016/j.tcs.2006.11.008
M3 - Article
AN - SCOPUS:33846828477
SN - 0304-3975
VL - 371
SP - 200
EP - 226
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
ER -