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}
}
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 ...
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
[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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [BH91]
- Franz Baader, Bernhard Hollunder:
A Terminological Knowledge Representation System with Complete Inference Algorithms.
PDK 1991: 67-86
![bibliographical record in XML](../../xml.gif)
- [Bor95]
- Alexander Borgida:
Description Logics in Data Management.
IEEE Trans. Knowl. Data Eng. 7(5): 671-682(1995)
![bibliographical record in XML](../../xml.gif)
- [Bar96]
- Alexander Borgida:
On the Relative Expressiveness of Description Logics and Predicate Logics.
Artif. Intell. 82(1-2): 353-367(1996)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [CKPS95]
- Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim:
Optimizing Queries with Materialized Views.
ICDE 1995: 190-200
![bibliographical record in XML](../../xml.gif)
- [DG97]
- Oliver M. Duschka, Michael R. Genesereth:
Answering Recursive Queries Using Views.
PODS 1997: 109-116
![bibliographical record in XML](../../xml.gif)
- [FRV96]
- ...
- [GMR95]
- Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross:
Adapting Materialized Views after Redefinitions.
SIGMOD Conference 1995: 211-222
![bibliographical record in XML](../../xml.gif)
- [KB94]
- Arthur M. Keller, Julie Basu:
A Predicate-based Caching Scheme for Client-Server Database Architectures.
PDIS 1994: 229-238
![bibliographical record in XML](../../xml.gif)
- [LMSS95]
- Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [LRO96]
- Alon Y. Levy, Anand Rajaraman, Joann J. Ordille:
Querying Heterogeneous Information Sources Using Source Descriptions.
VLDB 1996: 251-262
![bibliographical record in XML](../../xml.gif)
- [LRU96]
- Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman:
Answering Queries Using Limited External Processors.
PODS 1996: 227-237
![bibliographical record in XML](../../xml.gif)
- [Mac88]
- Robert M. MacGregor:
A Deductive Pattern Matcher.
AAAI 1988: 403-408
![bibliographical record in XML](../../xml.gif)
- [Pet91]
- Christof Peltason:
The BACK System - An Overview.
SIGART Bulletin 2(3): 114-119(1991)
![bibliographical record in XML](../../xml.gif)
- [Qia96]
- Xiaolei Qian:
Query Folding.
ICDE 1996: 48-55
![bibliographical record in XML](../../xml.gif)
- [SDJL96]
- ...
- [TSI94]
- Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis:
The GMAP: A Versatile Tool for Physical Data Independence.
VLDB 1994: 367-378
![bibliographical record in XML](../../xml.gif)
- [Ull97]
- Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [WWB+93]
- ...
- [YL87]
- H. Z. Yang, Per-Åke Larson:
Query Transformation for PSJ-Queries.
VLDB 1987: 245-254
![bibliographical record in XML](../../xml.gif)
Copyright © Fri Mar 12 17:19:58 2010
by Michael Ley (ley@uni-trier.de)