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

Maintaining Views Incrementally.

Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
@inproceedings{DBLP:conf/sigmod/GuptaMS93,
  author    = {Ashish Gupta and
               Inderpal Singh Mumick and
               V. S. Subrahmanian},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Maintaining Views Incrementally},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {157-166},
  ee        = {http://doi.acm.org/10.1145/170035.170066, db/conf/sigmod/GuptaMS93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present incremental evaluation algorithms to compute changes to materialized views in relational and deductive database systems, in response to changes (insertions, deletions, and updates) to the relations. The view definitions can be in SQL or Datalog, and may use UNION, negation, aggregation (e.g. SUM, MIN), linear recursion, and general recursion.

We first present a counting algorithm that tracks the number of alternative derivations (counts) for each derived tuple in a view. The algorithm works with both set and duplicate semantics. We present the algorithm for nonrecursive views (with negation and aggregation), and show that the count for a tuple can be computed at little or no cost above the cost of deriving the tuple. The algorithm is optimal in that it computes exactly those view tuples that are inserted or deleted. Note that we store only the number of derivations, not the derivations themselves.

We then present the Delete and Rederive algorithm, DRed, for incremental maintenance of recursive views (negation and aggregation are permitted). The algorithm works by first deleting a superset of the tuples that need to be deleted, and then rederiving some of them. The algorithm can also be used when the view definition is itself altered.

Copyright © 1993 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 ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

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

References

[ABW88]
...
[BC79]
Peter Buneman, Eric K. Clemons: Efficient Monitoring Relational Databases. ACM Trans. Database Syst. 4(3): 368-382(1979) BibTeX
[BCL89]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[BLR91]
...
[BLT86]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[BMM92]
François Bry, Rainer Manthey, Bern Martens: Integrity Verification in Knowledge Bases. RCLP 1991: 114-139 BibTeX
[BT88]
Frank Wm. Tompa, José A. Blakeley: Maintaining materialized views without accessing base data. Inf. Syst. 13(4): 393-406(1988) BibTeX
[CW91]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 BibTeX
[CW92]
...
[DAJ91]
Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354 BibTeX
[DS92]
...
[DT92]
Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296 BibTeX
[GKM92]
Ashish Gupta, Dinesh Katiyar, Inderpal Singh Mumick: Counting solutions to the View Maintenance Problem. Workshop on Deductive Databases, JICSLP 1992: 185-194 BibTeX
[GMS92]
...
[HD92]
John V. Harrison, Suzanne W. Dietrich: Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. Workshop on Deductive Databases, JICSLP 1992: 56-65 BibTeX
[ISO90]
...
[Kuc91]
Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 BibTeX
[MS93a]
Inderpal Singh Mumick, Oded Shmueli: Finiteness Properties of Database Queries. Australian Database Conference 1993: 274-288 BibTeX
[Mum91]
Inderpal Singh Mumick: Query Optimization in Deductive and Relational Databases. Ph.D. thesis, Department of Computer Science, Stanford University 1991
BibTeX
[NY83]
Jean-Marie Nicolas, Kioumars Yazdanian: An Outline of BDGEN: A Deductive DBMS. IFIP Congress 1983: 711-717 BibTeX
[QW91]
Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) BibTeX
[RS93]
Tore Risch, Martin Sköld: Active Rules based on Object-Oriented Queries. IEEE Data Eng. Bull. 15(1-4): 27-30(1992) BibTeX
[SI84]
Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 BibTeX
[SPAM91]
Ulf Schreier, Hamid Pirahesh, Rakesh Agrawal, C. Mohan: Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS. VLDB 1991: 469-478 BibTeX
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[UO92]
Toni Urpí, Antoni Olivé: A Method for Change Computation in Deductive Databases. VLDB 1992: 225-237 BibTeX
[VG86]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[WDSY91]
Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87 BibTeX

Referenced by

  1. Kenneth Salem, Kevin S. Beyer, Roberta Cochrane, Bruce G. Lindsay: How To Roll a Join: Asynchronous Incremental View Maintenance. SIGMOD Conference 2000: 129-140
  2. Esther Pacitti, Pascale Minet, Eric Simon: Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases. VLDB 1999: 126-137
  3. Laks V. S. Lakshmanan, Fereidoon Sadri, Subbu N. Subramanian: On Efficiently Implementing SchemaSQL on an SQL Database System. VLDB 1999: 471-482
  4. Wilburt Labio, Ramana Yerneni, Hector Garcia-Molina: Shrinking the Warehouse Update Window. SIGMOD Conference 1999: 383-394
  5. Yannis Kotidis, Nick Roussopoulos: DynaMat: A Dynamic View Management System for Data Warehouses. SIGMOD Conference 1999: 371-382
  6. Dominique Laurent, Jens Lechtenbörger, Nicolas Spyratos, Gottfried Vossen: Complements for Data Warehouses. ICDE 1999: 490-499
  7. Carlos A. Hurtado, Alberto O. Mendelzon, Alejandro A. Vaisman: Maintaining Data Cubes under Dimension Updates. ICDE 1999: 346-355
  8. Dimitri Theodoratos: Detecting Redundancy in Data Warehouse Evolution. ER 1999: 340-353
  9. Tok Wang Ling, Eng Koon Sze: Materialized View Maintenance Using Version Numbers. DASFAA 1999: 263-270
  10. Elisa Bertino, Claudio Bettini, Elena Ferrari, Pierangela Samarati: An Access Control Model Supporting Periodicity Constraints and Temporal Reasoning. ACM Trans. Database Syst. 23(3): 231-285(1998)
  11. Harumi A. Kuno, Elke A. Rundensteiner: Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(5): 768-792(1998)
  12. Timothy Griffin, Bharat Kumar: Algebraic Change Propagation for Semijoin and Outerjoin Queries. SIGMOD Record 27(3): 22-27(1998)
  13. Hector Garcia-Molina, Wilburt Labio, Jun Yang: Expiring Data in a Warehouse. VLDB 1998: 500-511
  14. Randall G. Bello, Karl Dias, Alan Downing, James J. Feenan Jr., James L. Finnerty, William D. Norcott, Harry Sun, Andrew Witkowski, Mohamed Ziauddin: Materialized Views in Oracle. VLDB 1998: 659-664
  15. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
  16. Yannis Kotidis, Nick Roussopoulos: An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees. SIGMOD Conference 1998: 249-258
  17. Kousha Etessami: Dynamic Tree Isomorphism via First-Order Updates. PODS 1998: 235-243
  18. Sameer Mahajan, Michael J. Donahoo, Shamkant B. Navathe, Mostafa H. Ammar, Sanjoy Malik: Grouping Techniques for Update Propagation in Intermittently Connected Databases. ICDE 1998: 46-53
  19. Sunil Samtani, Mukesh K. Mohania, Vijay Kumar, Yahiko Kambayashi: Recent Advances and Research Problems in Data Warehousing. ER Workshops 1998: 81-92
  20. Tetsuya Furukawa, Fei Sha II: Reducing Algorithms for Materialized View Updates. ER 1998: 377-392
  21. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
  22. Michael O. Akinde, Ole Guttorm Jensen, Michael H. Böhlen: Minimizing Detail Data in Data Warehouses. EDBT 1998: 293-307
  23. Mala Rajamani, Karen C. Davis: Partitioned Auxiliary Views for Self-Maintainable Data Warehouses. DOLAP 1998: 66-71
  24. Andreas Koeller, Elke A. Rundensteiner, Nabil I. Hachem: Integrating the Rewriting and Ranking Phases of View Synchronization. DOLAP 1998: 60-65
  25. Laks V. S. Lakshmanan, Nicola Leone, Robert B. Ross, V. S. Subrahmanian: ProbView: A Flexible Probabilistic Database System. ACM Trans. Database Syst. 22(3): 419-469(1997)
  26. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
  27. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Configuration. VLDB 1997: 126-135
  28. Nam Huyn: Multiple-View Self-Maintenance in Data Warehousing Environments. VLDB 1997: 26-35
  29. Christos Faloutsos, H. V. Jagadish, Nikolaos Sidiropoulos: Recovering Information from Summary Data. VLDB 1997: 36-45
  30. Inderpal Singh Mumick, Dallan Quass, Barinderpal Singh Mumick: Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997: 100-111
  31. Latha S. Colby, Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Supporting Multiple View Maintenance Policies. SIGMOD Conference 1997: 405-416
  32. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
  33. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  34. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Dallan Quass, Kenneth A. Ross: Concurrency Control Theory for Deferred Materialized Views. ICDT 1997: 306-320
  35. Wilburt Labio, Dallan Quass, Brad Adelberg: Physical Database Design for Data Warehouses. ICDE 1997: 277-288
  36. Jun Cai, Kian-Lee Tan, Beng Chin Ooi: On Incremental Cache Coherency Schemes in Mobile Computing Environments. ICDE 1997: 114-123
  37. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221
  38. Rongquen Chen, Weiyi Meng: Efficient View Maintenance in a Multidatabase Environment. DASFAA 1997: 391-400
  39. Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)
  40. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
  41. Elisa Bertino, Claudio Bettini, Elena Ferrari, Pierangela Samarati: A Temporal Access Control Mechanism for Database Systems. IEEE Trans. Knowl. Data Eng. 8(1): 67-80(1996)
  42. Martin Staudt, Matthias Jarke: Incremental Maintenance of Externally Materialized Views. VLDB 1996: 75-86
  43. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
  44. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492
  45. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
  46. Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148
  47. Martin Sköld, Tore Risch: Using Partial Differencing for Efficient Monitoring of Deferred Complex Rule Conditions. ICDE 1996: 392-401
  48. Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144
  49. Sofien Gannouni, Emmanuel Gleizer: Incremental View Maintenance for Data Warehousing. ADBIS 1996: 93-101
  50. Jan Chomicki, David Toman: Implementing Temporal Integrity Constraints Using an Active DBMS. IEEE Trans. Knowl. Data Eng. 7(4): 566-582(1995)
  51. Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Data Integration and Warehousing Using H2O. IEEE Data Eng. Bull. 18(2): 29-40(1995)
  52. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  53. Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327
  54. James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351
  55. Ashish Gupta, Inderpal Singh Mumick, Kenneth A. Ross: Adapting Materialized Views after Redefinitions. SIGMOD Conference 1995: 211-222
  56. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
  57. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
  58. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
  59. Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410
  60. Ernest Teniente, Toni Urpí: A Common Framework for Classifying and Specifying Deductive Database Updating Problems. ICDE 1995: 173-182
  61. Catherine Hamon, Arthur M. Keller: Two-Level Caching of Composite Object Views of Relational Databases. ICDE 1995: 428-437
  62. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  63. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  64. Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221
  65. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
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:40:14 2009