Deriving Production Rules for Incremental View Maintenance.

@inproceedings{DBLP:conf/vldb/CeriW91,
  author    = {Stefano Ceri and
               Jennifer Widom},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {Deriving Production Rules for Incremental View Maintenance},
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {577-589},
  ee        = {db/conf/vldb/CeriW91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

It is widely recognized that production rules in database systems can be used to automatically maintain de- rived data such as views. However, writing a correct set of rules for efficiently maintaining a given view can be a diffi- cult and ad-hoc process. We provide a facility whereby a user delines a view as an SQL select expression, from which the system automatically derives set-oriented production rules that maintain a materialization of that view.

The maintenance rules are triggered by operations on the view's base tables. Generally, the rules perform incremental maintenance: the materialized view is modified according to the sets of changes made to the base tables, which are ac- cessible through logical tables provided by the rule language. However, for some operations substantial recomputation may be required. We give algorithms that, based on key information, perform syntactic analysis on a view definit,ion to determine when efficient maintenance is possible.

Copyright © 1991 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[ACL91]

Rakesh Agrawal, Roberta Cochrane, Bruce G. Lindsay: On Maintaining Priorities in a Production Rule System. VLDB 1991: 479-487 BibTeX

[BLT86]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[CG85]

Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985) BibTeX

[CW90]

Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX

[CW91]

...

[DE89]

Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351 BibTeX

[Han87]

...

[IBM88]

...

[Kim82]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[KP81]

Shaye Koenig, Robert Paige: A Transformational Framework for the Automatic Control of Derived Data. VLDB 1981: 306-318 BibTeX

[MD89]

Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224 BibTeX

[RCBB89]

Arnon Rosenthal, Sharma Chakravarthy, Barbara T. Blaustein, José A. Blakeley: Situation Monitoring for Active Databases. VLDB 1989: 455-464 BibTeX

[SI84]

Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 BibTeX

[SJGP90]

Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX

[SP89]

Arie Segev, Jooseok Park: Updating Distributed Materialized Views. IEEE Trans. Knowl. Data Eng. 1(2): 173-184(1989) BibTeX

[Sto85]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[WCL91]

Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285 BibTeX

[WF90]

Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX

[Wid91]

...

Referenced by

1. Chen Li, Mayank Bawa, Jeffrey D. Ullman: Minimizing View Sets without Losing Query-Answering Power. ICDT 2001: 99-113
2. Stefano Ceri, Roberta Cochrane, Jennifer Widom: Practical Applications of Triggers and Constraints: Success and Lingering Issues (10-Year Award). VLDB 2000: 254-262
3. Himanshu Gupta, Inderpal Singh Mumick: Selection of Views to Materialize Under a Maintenance Cost Constraint. ICDT 1999: 453-470
4. 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)
5. 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
6. Dimitri Theodoratos, Timos K. Sellis: Data Warehouse Schema and Instance Design. ER 1998: 363-376
7. Dimitra Vista: Integration of Incremental View Maintenance into Query Optimizers. EDBT 1998: 374-388
8. Michael O. Akinde, Ole Guttorm Jensen, Michael H. Böhlen: Minimizing Detail Data in Data Warehouses. EDBT 1998: 293-307
9. Uday R. Kulkarni, Richard G. Ramirez: Independently Updated Views. IEEE Trans. Knowl. Data Eng. 9(5): 798-812(1997)
10. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
11. Inderpal Singh Mumick, Dallan Quass, Barinderpal Singh Mumick: Maintenance of Data Cubes and Summary Tables in a Warehouse. SIGMOD Conference 1997: 100-111
12. Latha S. Colby, Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Supporting Multiple View Maintenance Policies. SIGMOD Conference 1997: 405-416
13. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
14. Brad Adelberg, Hector Garcia-Molina, Jennifer Widom: The STRIP Rule System For Efficiently Maintaining Derived Data. SIGMOD Conference 1997: 147-158
15. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
16. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Dallan Quass, Kenneth A. Ross: Concurrency Control Theory for Deferred Materialized Views. ICDT 1997: 306-320
17. James Bailey, Guozhu Dong, Kotagiri Ramamohanarao: Structural Issues in Active Rule Systems. ICDT 1997: 203-214
18. Akira Kawaguchi, Daniel F. Lieuwen, Inderpal Singh Mumick, Kenneth A. Ross: Implementing Incremental View Maintenance in Nested Data Models. DBPL 1997: 202-221
19. Arthur M. Keller, Julie Basu: A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB J. 5(1): 35-47(1996)
20. Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language. ACM Trans. Database Syst. 21(3): 370-426(1996)
21. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Modularization Techniques for Active Rules Design. ACM Trans. Database Syst. 21(1): 1-29(1996)
22. Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996)
23. 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)
24. Martin Staudt, Matthias Jarke: Incremental Maintenance of Externally Materialized Views. VLDB 1996: 75-86
25. Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458
26. Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492
27. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
28. Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148
29. Harumi A. Kuno, Elke A. Rundensteiner: Using Object-Oriented Principles to Optimize Update Propagation to Materialized Views. ICDE 1996: 310-317
30. Sofien Gannouni, Emmanuel Gleizer: Incremental View Maintenance for Data Warehousing. ADBIS 1996: 93-101
31. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
    Contents
32. Piero Fraternali, Letizia Tanca: A Structured Approach for the Definition of the Semantics of Active Databases. ACM Trans. Database Syst. 20(4): 414-471(1995)
33. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
34. I-Min A. Chen, Richard Hull, Dennis McLeod: An Execution Model for Limited Ambiguity Rules and Its Application to Derived Data Update. ACM Trans. Database Syst. 20(4): 365-413(1995)
35. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
36. Alexander Aiken, Joseph M. Hellerstein, Jennifer Widom: Static Analysis Techniques for Predicting the Behavior of Active Database Rules. ACM Trans. Database Syst. 20(1): 3-41(1995)
37. Jeng-Rung Chen, Albert Mo Kim Cheng: Response Time Analysis of EQL Real-Time Rule-Based Systems. IEEE Trans. Knowl. Data Eng. 7(1): 26-43(1995)
38. Lars Bækgaard, Leo Mark: Incremental Computation of Time-Varying Query Expressions. IEEE Trans. Knowl. Data Eng. 7(4): 583-590(1995)
39. Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Data Integration and Warehousing Using H2O. IEEE Data Eng. Bull. 18(2): 29-40(1995)
40. Joachim Hammer, Hector Garcia-Molina, Jennifer Widom, Wilburt Labio, Yue Zhuge: The Stanford Data Warehousing Project. IEEE Data Eng. Bull. 18(2): 41-48(1995)
41. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
42. Tor Didriksen, César A. Galindo-Legaria, Eirik Dahle: Database De-Centralization - A Practical Approach. VLDB 1995: 654-665
43. Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327
44. James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351
45. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
46. Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. PODS 1995: 126-138
47. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
48. Danilo Montesi, Riccardo Torlone: A Rewriting Technique for the Analysis and the Optimization of Active Databases. ICDT 1995: 238-251
49. Ernest Teniente, Toni Urpí: A Common Framework for Classifying and Specifying Deductive Database Updating Problems. ICDE 1995: 173-182
50. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
51. Alejandro P. Buchmann, Jürgen Zimmermann, José A. Blakeley, David L. Wells: Building an Integrated Active OODBMS: Requirements, Architecture, and Design Decisions. ICDE 1995: 117-128
52. Gio Wiederhold: Modelling and System Maintenance. OOER 1995: 1-20
53. Danilo Montesi, Riccardo Torlone: A Framework for the Specification of Active Rule Language Semantics. DBPL 1995: 4
54. Tadashi Ohmori, Mamoru Hoshi: Gaming-Simulations of Multi-Agent Information Systems using Large Databases: The Concept and Database Algorithms. DASFAA 1995: 95-106
55. Jennifer Widom: Research Problems in Data Warehousing. CIKM 1995: 25-30
56. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
57. Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55
58. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
59. Rainer Manthey: Active and Passive Rules in Database Systems: How Do They Relate? (Invited Paper). ADBIS 1994: 104-115
60. Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou: On Implementing a Language for Specifying Active Database Execution Models. VLDB 1993: 441-454
61. Stefano Ceri, Jennifer Widom: Managing Semantic Heterogeneity with Production Rules and Persistent Queues. VLDB 1993: 108-119
62. Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
63. Michael Stonebraker: The Integration of Rule Systems and Database Systems. IEEE Trans. Knowl. Data Eng. 4(5): 415-423(1992)
64. Jennifer Widom: The Starburst Rule System: Language Design, Implementation, and Applications. IEEE Data Eng. Bull. 15(1-4): 15-18(1992)
65. Toni Urpí, Antoni Olivé: A Method for Change Computation in Deductive Databases. VLDB 1992: 225-237
66. Eric Simon, Jerry Kiernan, Christophe de Maindreville: Implementing High Level Active Rules on Top of a Relational DBMS. VLDB 1992: 315-326
67. Frank Olken, Doron Rotem: Maintenance of Materialized Views of Sampling Queries. ICDE 1992: 632-641
68. Jan Chomicki: History-less Checking of Dynamic Integrity Constraints. ICDE 1992: 557-564
69. Stefano Ceri: A Declarative Approach to Active Databases. ICDE 1992: 452-456
70. Svein Erik Bratsberg: Unified Class Evolution by Object-Oriented Views. ER 1992: 423-439
71. Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285