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

Answering Queries Using Views.

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
@inproceedings{DBLP:conf/pods/LevyMSS95,
  author    = {Alon Y. Levy and
               Alberto O. Mendelzon and
               Yehoshua Sagiv and
               Divesh Srivastava},
  title     = {Answering Queries Using Views},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {95-104},
  ee        = {http://doi.acm.org/10.1145/212433.220198, db/conf/pods/LevyMSS95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider the problem of computing answers to queries by using materialized views. Aside from its potential in optimizing query evaluation, the problem also arises in applications such as Global Information Systems, Mobile Computing and maintaining physical data independence. We consider the problem of finding a rewriting of a query that uses the materialized views, the problem of finding minimal rewritings, and finding complete rewritings (i.e., rewritings that use only the views). We show that all the possible rewritings can be obtained by considering containment mappings from the views to the query, and that the problems we consider are NP-complete when both the query and the views are conjunctive and don't involve built-in comparison predicates. We show that the problem has two independent sources of complexity (the number of possible containment mappings, and the complexity of deciding which literals from the original query can be deleted). We describe a polynomial time algorithm for finding rewritings, and show that under certain conditions, it will find the minimal rewriting. Finally, we analyze the complexity of the problems when the queries and views may be disjunctive and involve built-in comparison predicates.

Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

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

References

[BI94]
Daniel Barbará, Tomasz Imielinski: Sleepers and Workaholics: Caching Strategies in Mobile Environments. SIGMOD Conference 1994: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CKPS95]
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CR94]
Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CV92]
Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DJLS95]
...
[GMR95]
Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW94]
Yixiu Huang, A. Prasad Sistla, Ouri Wolfson: Data Replication for Mobile Computers. SIGMOD Conference 1994: 13-24 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KB94]
Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. PDIS 1994: 229-238 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LSK95]
Alon Y. Levy, Divesh Srivastava, Thomas Kirk: Data Model and Query Evaluation in Global Information Systems. J. Intell. Inf. Syst. 5(2): 121-143(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LS93]
Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LY85]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RSU95]
Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SJGP90]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SY81]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sel88]
Timos K. Sellis: Intelligent caching and indexing techniques for relational database systems. Inf. Syst. 13(2): 175-185(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shm87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TSI94]
Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YL87]
H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[vdM92]
Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:57 2010 by Michael Ley (ley@uni-trier.de)