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

• ABW88: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• BC79: O. Peter Buneman , Eric K. Clemons, Efficiently monitoring relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.368-382, Sept. 1979 [doi>10.1145/320083.320099]
• BCL89: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• BLR91: Veronique Benzaken, Christophe Lecluse, and Philippe Richard. Enforcing Integrity Constraints in Database Programming Languages. TR Altair 68-91, Altair, France, 1991.
• BLT86: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• BMM92: François Bry , Rainer Manthey , Bern Martens, Integrity Verification in Knowledge Bases, Proceedings of the First Russian Conference on Logic Programming, p.114-139, September 14-18, 1990
• BT88: F. W. Tompa , J. A. Blakeley, Maintaining materialized views without accessing base data, Information Systems, v.13 n.4, p.393-406, Oct. 1, 1988 [doi>10.1016/0306-4379(88)90005-1]
• CW91: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• CW92: Stefano Ceri and Jennifer Widom. Deriving Incremental Production Rules for Deductive Data. IBM RJ 9071, IBM Almaden, 1992.
• DAJ91: Shaul Dar , Rakesh Agrawal , H. V. Jagadish, Optimization of Generalized Transitive Closure Queries, Proceedings of the Seventh International Conference on Data Engineering, p.345-354, April 08-12, 1991
• 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.
• DT92: Guozhu Dong , Rodney W. Topor, Incremental Evaluation of Datalog Queries, Proceedings of the 4th International Conference on Database Theory, p.282-296, October 14-16, 1992
• GKM92: Ashish Gupta, Dinesh Katiyar, and Inderpal Singh Mumick. Counting Solutions to the View Maintenance Problem. In Workshop on Deductive Databases, JICSLP, 1992.
• GMS92: Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. TR 921214-19-TM, AT&T Bell Labs, 1992.
• 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.
• ISO90: ISO_ANSI. ISO-ANSI Working Draft: Database Language SQL2 and SQL3; X3H2; ISO/IEC JTC1/SC21/WG3, 1990.
• Kuc91: V. Kuchenhoff. On the Efficient Computation of the Difference Between Consecutive Database States. In DOOD, LNCS 566, 1991.
• MS93a: Inderpal Singh Mumick and Oded Shmueli. Finiteness Properties of Database Queries. In Fourth Australian Database Conference, 1993.
• Mum91: Inderpal Singh Mumick. Query Optimization in Deductive and Relational Databases. Ph.D. Thesis, Stanford University, CA 94305, 1991.
• NY83: J.M. Nicolas and Yazdanian. An Outline of BDGEN: A Deductive DBMS. In In}ormation Processing, pages 705-717, 1983.
• QW91: X. Qian , G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.337-341, September 1991 [doi>10.1109/69.91063]
• RS93: Torre Risch and Martin SkSld. Active rules based on object-oriented queries. To Appear, A CM TKDE, 1993.
• SI84: Oded Shmueli , Alon Itai, Maintenance of views, ACM SIGMOD Record, v.14 n.2, June 1984
• SPAM91: Ulf Schreier , Hamid Pirahesh , Rakesh Agrawal , C. Mohan, Alert: An Architecture for Transforming a Passive DBMS into an Active DBMS, Proceedings of the 17th International Conference on Very Large Data Bases, p.469-478, September 03-06, 1991
• Ull89: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• UO92: Toni Urpí , Antoni Olivé, A Method for Change Computation in Deductive Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.225-237, August 23-27, 1992
• VG86: Allen Van Gelder. Negation as failure using tight derivations for general logic programs. In Third IEEE Symposium on Logic Programming, 1986. Springer-Verlag.
• WDSY91: Ouri Wolfson , Hasanat M. Dewan , Salvatore J. Stolfo , Yechiam Yemini, Incremental evaluation of rules and its relationship to parallelism, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.78-87, May 29-31, 1991, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
      H.2.3 Languages

          Nouns: SQL; Datalog

General Terms:
Algorithms, Performance, Theory