dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time.

Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
@inproceedings{DBLP:conf/sigmod/RossSS96,
  author    = {Kenneth A. Ross and
               Divesh Srivastava and
               S. Sudarshan},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Materialized View Maintenance and Integrity Constraint Checking:
               Trading Space for Time},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {447-458},
  ee        = {http://doi.acm.org/10.1145/233269.233361},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the problem of incremental maintenance of an SQL view in the face of database updates, and show that is is possible to reduce the total time cost of view maintenance by materializing (and maintaining) additional views. We formulate the problem of determining the optimal set of additional views to materialize as an optimization problem over the space of possible views sets (which includes the empty set). The optimization problem is harder than query optimization since it has to deal with multiple view sets, updates of multiple relations, and multiple ways of maintaining each view set for each updated relation.

We develop a memoing solution for the problem; the solution can be implemented using the expression DAG representation used in rule-based optimizers such as Volcano. We demonstrate that global optimization cannot, in general, be achieved by locally optimizing each materialized subview, because common subexpressions between different materialized subviews can allow nonoptimal local plans to be combined into an optimal global plan. We identify conditions on materialized subviews in the expression DAG when local optimization is possible. Finally, we suggest heuristics that can be used to efficiently determine a useful set of additional views to materialize.

Our results are particularly important for the efficient checking of assertions (complex integrity constraints) in the SQL-92 standard, since the incremental checking of such integrity constraints is known to be essentially equivalent to the view maintenance problem.

Copyright © 1996 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

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

References

[1]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(3&4): 255-299(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
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
[6]
Françoise Fabret, Mireille Régnier, Eric Simon: An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases. VLDB 1993: 455-466 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
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
[12]
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Eric N. Hanson: Rule Condition Testing and Action Execution in Ariel. SIGMOD Conference 1992: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
William J. McKenna: Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator. Ph.D. thesis, University of Colorado-Boulder 1993
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Jim Melton, Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
...
[23]
Yu-Wang Wang, Eric N. Hanson: A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions. ICDE 1992: 88-97 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:14 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page