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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

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

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