Rewriting Queries Using Views in Description Logics.

Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset: Rewriting Queries Using Views in Description Logics. PODS 1997: 99-108
  author    = {Catriel Beeri and
               Alon Y. Levy and
               Marie-Christine Rousset},
  title     = {Rewriting Queries Using Views in Description Logics},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {99-108},
  ee        = {, db/conf/pods/BeeriLR97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP,}


The problem of rewriting queries using views is to find a query expression that uses only a set of views V and is equivalent to (or maximally contained in) a given query Q. Rewriting queries using views is important for query optimization and for applications such as information integration and data warehousing. Description logics are a family of logics that were developed for modeling complex hierarchical structures, and can also be viewed as a query language with an interesting tradeoff between complexity and expressive power. We consider the problem of rewriting queries using views expressed in description logics and conjunctive queries over description logics. We show that if the view definitions do not contain existential variables, then it is always possible to find a rewriting that is a union of conjunctive queries, and furthermore, this rewriting produces the maximal set of answers possible from the views. If the views have existential variables, the rewriting may be recursive. We present an algorithm for producing a recursive rewriting, that is guaranteed to be a maximal one when the underlying database forms a tree of constants. We show that in general, it is not always be possible to find a maximal rewriting.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACM Press 1997, ISBN 0-89791-910-6
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1809 KB]


Yigal Arens, Craig A. Knoblock, Wei-Min Shen: Query Reformulation for Dynamic Information Integration. J. Intell. Inf. Syst. 6(2/3): 99-130(1996) BibTeX
Martin Buchheit, Francesco M. Donini, Andrea Schaerf: Decidable Reasoning in Terminological Knowledge Representation Systems. J. Artif. Intell. Res. (JAIR) 1: 109-138(1993) BibTeX
Franz Baader, Bernhard Hollunder: A Terminological Knowledge Representation System with Complete Inference Algorithms. PDK 1991: 67-86 BibTeX
Alexander Borgida: Description Logics in Data Management. IEEE Trans. Knowl. Data Eng. 7(5): 671-682(1995) BibTeX
Alexander Borgida: On the Relative Expressiveness of Description Logics and Predicate Logics. Artif. Intell. 82(1-2): 353-367(1996) BibTeX
Alexander Borgida, Peter F. Patel-Schneider: A Semantics and Complete Algorithm for Subsumption in the CLASSIC Description Logic. J. Artif. Intell. Res. (JAIR) 1: 277-308(1994) BibTeX
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX
Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116 BibTeX
Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222 BibTeX
Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. PDIS 1994: 229-238 BibTeX
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
Alon Y. Levy, Marie-Christine Rousset: The Limits on Combining Recursive Horn Rules with Description Logics. AAAI/IAAI, Vol. 1 1996: 577-584 BibTeX
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX
Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX
Robert M. MacGregor: A Deductive Pattern Matcher. AAAI 1988: 403-408 BibTeX
Christof Peltason: The BACK System - An Overview. SIGART Bulletin 2(3): 114-119(1991) BibTeX
Xiaolei Qian: Query Folding. ICDE 1996: 48-55 BibTeX
Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378 BibTeX
Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX
Wolfgang Wahlster, Elisabeth André, Wolfgang Finkler, Hans-Jürgen Profitlich, Thomas Rist: Plan-Based Integration of Natural Language and Graphics Generation. Artif. Intell. 63(1-2): 387-427(1993) BibTeX
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 BibTeX

Referenced by

  1. Todd D. Millstein, Alon Y. Levy, Marc Friedman: Query Containment for Data Integration Systems. PODS 2000: 67-75
  2. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
  3. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
  4. Maurizio Lenzerini: Description Logics and Their Relationships with Databases. ICDT 1999: 32-38
  5. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:16 2009