Maintaining views incrementally

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.

References

1. ABW88.Krzysztof R. Apt, Howard A. Blair, and Adrian Walker. Towards a Theory o} Declarative Knowledge. In Foundations o} Deductive Databases and Logic Programming. Editor J. Minker, 1988 Morgan Kaufmann.
2. BC79.Peter O. Buneman and Eric K. Clemons. Efficiently Monitoring Relational Databases. In A C#I TODS, Vol 4, No. 3, 1979, 368-382.
3. BCL89.J.A. Blakeley, N. Coburn, and P. Larson. Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. In A CM TODS Vol 14, No. 3, 369-400, 1989.
4. BLR91.Veronique Benzaken, Christophe Lecluse, and Philippe Richard. Enforcing Integrity Constraints in Database Programming Languages. TR Altair 68-91, Altair, France, 1991.
5. BLT86.J.A. Blakeley, P. Larson, and F. W. Tompa. Ej#- c#ently Updating Materiahzed V#ews. In SIGMOD 1986, pages 61-71.
6. BMM92.F. Bry, R. Manthey, and B. Martens. Integrity Verification in Knowledge Bases. In Logic Programm#ng, LNAI #9#, pages 114-189, 1992.
7. BT88.J.A. Blakeley and F. W. Tompa. Maintaining Materialized Views without Accessing Base Data. Information Systems, 13(4):393-406, 1988.
8. CW91.Stefano Ceri and Jennifer Widom. Deriving Production Rules for Incremental View Maintenance. In 17th VLDB, 1991.
9. CW92.Stefano Ceri and Jennifer Widom. Deriving Incremental Production Rules for Deductive Data. IBM RJ 9071, IBM Almaden, 1992.
10. DAJ91.S. Dar, R. Agrawal, and H. V. Jagadish. Optimization of generalized transitive closure, in Seventh IEEE International Con}erence on Data Engineering, Kobe, Japan, 1991.
11. DS92.Guozhu Dong and Jianwen Su. Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. TRCS 92-18, University of California, Santa Barbara, 1992.
12. DT92.Guozhu Dong and Rodney Topor. Incremental Evaluation o} Datalog Queries. In ICDT, 1992.
13. GKM92.Ashish Gupta, Dinesh Katiyar, and Inderpal Singh Mumick. Counting Solutions to the View Maintenance Problem. In Workshop on Deductive Databases, JICSLP, 1992.
14. GMS92.Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. TR 921214-19-TM, AT&T Bell Labs, 1992.
15. HD92.John V. Harrison and Suzanne Dietrich. Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. In Workshop on Deductive Databases, JICSLP, 1992.
16. ISO90.ISO_ANSI. ISO-ANSI Working Draft: Database Language SQL2 and SQL3; X3H2; ISO/IEC JTC1/SC21/WG3, 1990.
17. Kuc91.V. Kuchenhoff. On the Efficient Computation of the Difference Between Consecutive Database States. In DOOD, LNCS 566, 1991.
18. MS93a.Inderpal Singh Mumick and Oded Shmueli. Finiteness Properties of Database Queries. In Fourth Australian Database Conference, 1993.
19. Mum91.Inderpal Singh Mumick. Query Optimization in Deductive and Relational Databases. Ph.D. Thesis, Stanford University, CA 94305, 1991.
20. NY83.J.M. Nicolas and Yazdanian. An Outline of BDGEN: A Deductive DBMS. In In}ormation Processing, pages 705-717, 1983.
21. QW91.Xiaolei Qian and Gio Wiederhold. Incremental Recomputation o} Active Relational Expressions. In A CM TKDE, 1991.
22. RS93.Torre Risch and Martin SkSld. Active rules based on object-oriented queries. To Appear, A CM TKDE, 1993.
23. SI84.Oded Shmueli and Alon Itai. Maintenance o} lQews. In Sigmod Record, 14(2):240-255, 1984.
24. SPAM91.Ulf Schreier, Hmnid Pirahesh, Rakesh Agrawal, and C. Mohan. Alert: An Architecture for Transforming a Passive DBMS Into an Active DBMS. In 17th VLDB, pages 469-478, 1991.
25. Ull89.Jeffrey D. Ullman. Principles o} Database and Knowledge-Base Systems, Volumes I and 2. Computer Science Press, 1989.
26. UO92.Toni Urpi and Antoni Olive. A Method for Change Computation in Deductive Databases. In 18th VLDB, pages 225-237, 1992.
27. VG86.Allen Van Gelder. Negation as failure using tight derivations for general logic programs. In Third IEEE Symposium on Logic Programming, 1986. Springer-Verlag.
28. WDSY91.Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, and Yechiam Yemini. Incremental Evaluation of Rules and its Relationship to Parallelism. In SIGMOD 1991, pages 78-87.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

    • Query languages

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query languages (principles)