TY - GEN
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: deutsch@cs.ucsd.edu (A. Deutsch), ludaesch@ucdavis.edu (B. Ludäscher), anash@us.ibm.com (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 - 2005
Y1 - 2005
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 finding minimal containing and maximal contained rewritings and for deciding whether an exact 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 all three problems, based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons.
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 finding minimal containing and maximal contained rewritings and for deciding whether an exact 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 all three problems, based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons.
UR - http://www.scopus.com/inward/record.url?scp=77049127560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77049127560&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30570-5_24
DO - 10.1007/978-3-540-30570-5_24
M3 - Conference contribution
AN - SCOPUS:77049127560
SN - 3540242880
SN - 9783540242888
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 352
EP - 367
BT - Database Theory - ICDT 2005 - 10th International Conference, Proceedings
T2 - 10th International Conference on Database Theory, ICDT 2005
Y2 - 5 January 2005 through 7 January 2005
ER -