Rewriting queries using views with access patterns under integrity constraints

Alin Deutsch, Bertram Ludäscher, Alan Nash

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationDatabase Theory - ICDT 2005 - 10th International Conference, Proceedings
Number of pages16
StatePublished - 2005
Externally publishedYes
Event10th International Conference on Database Theory, ICDT 2005 - Edinburgh, United Kingdom
Duration: Jan 5 2005Jan 7 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3363 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th International Conference on Database Theory, ICDT 2005
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this