Rewriting queries using views with access patterns under integrity constraints

Alin Deutsch, Bertram Ludäscher, Alan Nash

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)200-226
Number of pages27
JournalTheoretical Computer Science
Issue number3
StatePublished - Mar 1 2007
Externally publishedYes


  • Access patterns
  • Integrity constraints
  • Query rewriting
  • Views

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Rewriting queries using views with access patterns under integrity constraints'. Together they form a unique fingerprint.

Cite this