ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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
@inproceedings{DBLP:conf/pods/BeeriLR97,
  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        = {http://doi.acm.org/10.1145/263661.263673, db/conf/pods/BeeriLR97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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]

References

[AKS96]
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
[BBM+91]
...
[BDS93]
Martin Buchheit, Francesco M. Donini, Andrea Schaerf: Decidable Reasoning in Terminological Knowledge Representation Systems. J. Artif. Intell. Res. (JAIR) 1: 109-138(1993) BibTeX
[BH91]
Franz Baader, Bernhard Hollunder: A Terminological Knowledge Representation System with Complete Inference Algorithms. PDK 1991: 67-86 BibTeX
[Bor95]
Alexander Borgida: Description Logics in Data Management. IEEE Trans. Knowl. Data Eng. 7(5): 671-682(1995) BibTeX
[Bar96]
Alexander Borgida: On the Relative Expressiveness of Description Logics and Predicate Logics. Artif. Intell. 82(1-2): 353-367(1996) BibTeX
[BPS94]
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
[CKPS95]
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX
[DG97]
Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116 BibTeX
[FRV96]
...
[GMR95]
Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222 BibTeX
[KB94]
Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. PDIS 1994: 229-238 BibTeX
[LMSS95]
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
[LR96a]
...
[LR96b]
Alon Y. Levy, Marie-Christine Rousset: The Limits on Combining Recursive Horn Rules with Description Logics. AAAI/IAAI, Vol. 1 1996: 577-584 BibTeX
[LRO96]
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX
[LRU96]
Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237 BibTeX
[Mac88]
Robert M. MacGregor: A Deductive Pattern Matcher. AAAI 1988: 403-408 BibTeX
[Pet91]
Christof Peltason: The BACK System - An Overview. SIGART Bulletin 2(3): 114-119(1991) BibTeX
[Qia96]
Xiaolei Qian: Query Folding. ICDE 1996: 48-55 BibTeX
[SDJL96]
...
[TSI94]
Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378 BibTeX
[Ull97]
Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX
[WAF+93]
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
[WWB+93]
...
[YL87]
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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:16 2009