The STRIP rule system for efficiently maintaining derived data

ABSTRACT

Derived data is maintained in a database system to correlate and summarize base data which records real world facts. As base data changes, derived data needs to be recomputed. This is often implemented by writing active rules that are triggered by changes to base data. In a system with rapidly changing base data, a database with a standard rule system may consume most of its resources running rules to recompute data. This paper presents the rule system implemented as part of the STandard Real-time Information Processor (STRIP). The STRIP rule system is an extension of SQL3-type rules that allows groups of rule actions to be batched together to reduce the total recomputation load on the system. In this paper we describe the syntax and semantics of the STRIP rule system, present an example set of rules to maintain stock index and theoretical option prices in a program trading application, and report the results of experiments performed on the running system. The experiments verify that STRIP's rules allow much more efficient derived data maintenance than conventional rules without batching.

REFERENCES

• Ade97: Bradley Scott Adelberg, Strip: a soft real-time main memory database for open systems, Stanford University, Stanford, CA, 1997
• AKGM96a: Brad Adelberg , Ben Kao , Hector Garcia-Molina, Database Support for Efficiently Maintaining Derived Data, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.223-240, March 25-29, 1996
• AKGM96b: Brad Adelberg , Ben Kao , Hector Garcia-Molina, Overview of the STanford Real-time Information Processor (STRIP), ACM SIGMOD Record, v.25 n.1, p.34-37, March 1996 [doi>10.1145/381854.381882]
• BBKZ93: H. Branding, A. Buchmann, T. Kudrass, and J. Zimmermann. Rules in an open system: The REACH rule system. In Proceedings of the first international workshop on rules in database systems, pages 111-26, 1993.
• BS73: F. Black and M. Scholes. The pricing of options and corporate liabilities. Journal of political economy, 81(3):637-54, 1973.
• CB94: Munir Cochinwala , John Bradley, A Multidatabase System for Tracking and Retrieval of Financial Data, Proceedings of the 20th International Conference on Very Large Data Bases, p.714-721, September 12-15, 1994
• CCS94: Christine Collet , Thierry Coupaye , T. Svensen, NAOS - Efficient and Modular Reactive Capabilities in an Object-Oriented Database System, Proceedings of the 20th International Conference on Very Large Data Bases, p.132-143, September 12-15, 1994
• CJL91: M. J. Carey , R. Jauhari , M. Livny, On Transaction Boundaries in Active Databases: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.320-336, September 1991 [doi>10.1109/69.91062]
• CKAK94: Sharma Chakravarthy , V. Krishnaprasad , Eman Anwar , S.-K. Kim, Composite Events for Active Databases: Semantics, Contexts and Detection, Proceedings of the 20th International Conference on Very Large Data Bases, p.606-617, September 12-15, 1994
• 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
• DD93: C.J. Date and H. Darwen. The SQL standard. Addison-Wesley, 3.0 edition, 1993.
• DHL90: Umeshwar Dayal , Meichun Hsu , Rivka Ladin, Organizing long-running activities with triggers and transactions, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.204-214, May 23-26, 1990, Atlantic City, New Jersey, United States
• GJS92: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• GMS92: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• HSTR90: J. Huang, J. Stankovic, D. Towsley, and K. Ramamritham. Real-time transaction processing: design, implementation and performance evaluation. Technical Report COINS 90-43, Univ. of Massachusetts, 1990.
• Leh86: Tobin Jon Lehman, Design and performance evaluation of a main memory relational database system (t tree), 1986
• New94: New York Stock Exchange, Inc. The TA Q database, 3.0 edition, June 1994.
• PTV90: Philippe Pucheral , Jean-Marie Thévenin , P. Valduriez, Efficient main memory data management using the DBgraph storage model, Proceedings of the sixteenth international conference on Very large databases, p.683-695, September 1990, Brisbane, Australia
• Ram93: Krithi Ramamritham, Real-time databases, Distributed and Parallel Databases, v.1 n.2, p.199-226, April 1993 [doi>10.1007/BF01264051]
• Rou82: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• WC96: J. Widom and S. Ceri. Active database systems. Morgan Kaufmann, 1.0 edition, 1996.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Design, Languages, Management, Measurement, Performance, Theory