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

1. Ade97.B. Adelberg. STRIP: A Soft real-time database for open systems. PhD thesis, Stanford University, 1997.
2. AKGM96a.B. Adelberg, B. Kao, and H. Garcia-Molina. Database support for efficiently maintaining derived data. In Proceedings of EDBT, pages 223-40, 1996.
3. AKGM96b.B. Adelberg, B. Kao, and H. Garcia-Molina. Overview of the STanford Real-time Information Processor (STRIP). SIGMOD Record, 25(1):34-7, 1996.
4. 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.
5. BS73.F. Black and M. Scholes. The pricing of options and corporate liabilities. Journal of political economy, 81(3):637-54, 1973.
6. CB94.M. Cochinwala and J. Bradley. A multidatabase system for tracking and retrieval of financial data. In Proceedings of VLDB, pages 714-721, 1994.
7. CCS94.C. Collet, T. Coupaye, and T. Svensen. Naos - efficient and modular reactive capabilities in an objectoriented database system. In Proceedings of the 20th VLDB Conference, pages 132-43, 1994.
8. CJL91.M. Carey, R. Jauhari, and M. Livny. On transaction boundaries in active databases: A performance perspective. IEEE 7kansactions on Knowledge and Data Engineering, 3(3):320-36, 1991.
9. CKAK94.S. Chakravarthy, V. Krishnaprasad, E. Anwax, and S.K. Kim. Composite events for active databases. In Proceedings of VLDB, pages 606-17, 1994.
10. CW91.S. Ceri and J. Widom. Deriving production rules for incremental rule maintenance. In Proceedings of the 17th VLDB Conference, pages 577-89, 1991.
11. DD93.C.J. Date and H. Darwen. The SQL standard. Addison-Wesley, 3.0 edition, 1993.
12. DHL90.U. Dayal, M. Hsu, and R. Ledin. Organizing longrunning activities with triggers and transactions. In Proceedings of the A CM SIGMOD Annual Conference on Management of Data, pages 204-14, 1990.
13. GJS92.N.H. Gehani, H.V. Jagadish, and O. Shmueli. Composite event specification in active databases: Model & implementation. In Proceedings of the 18th VLDB Conference, pages 327-38, 1992.
14. GMS92.H. Garcia-Molina and K. Salem. Main memory database systems: an overview. IEEE Transactions on Knowledge and Data Engineering, 4(6):509-16, 1992.
15. 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.
16. Leh86.T. Lehman. Design and performance evaluation of a main memory relational database system. PhD thesis, University of Wisconsin-Madison, 1986.
17. New94.New York Stock Exchange, Inc. The TA Q database, 3.0 edition, June 1994.
18. PTV90.P. Pucheral, J. Th~venin, and P. Valduriez. Efficient main memory data management using the D BGraph storage model. In Proceedings of the 16th VLDB Conference, pages 683-95, 1990.
19. Ram93.K. Ramamritham. Real-time databases. Distributed and Parallel Databases, 1(2):199-226, 1993.
20. Rou82.N. Roussopoulos. View indexing in relational databases. A CM Transactions on Database Systems, 7(2):258-90, 1982.
21. WC96.J. Widom and S. Ceri. Active database systems. Morgan Kaufmann, 1.0 edition, 1996.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

  • Machine learning

    • Machine learning approaches

      • Rule learning

• Information systems

  • Data management systems

    • Database management system engines

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

• Theory of computation

  • Formal languages and automata theory