Index support for rule activation

ABSTRACT

Integrated rule and database systems are quickly moving from the research laboratory into commercial systems. However, the current generation of prototypes are designed to work with small rule sets involving limited inferencing. The problem of supporting large complex rule programs within database management systems still presents significant challenges. The basis for many of these challenges is providing support for rule activation. Rule activation is defined as the process of determining which rules are satisfied and what data satisfies them. In this paper we present performance results for the DATEX database rule system and its novel indexing technique for supporting rule activation. Our approach assumes that both the rule program and the database must be optimized synergistically. However, as an experimental result we have determined that DATEX requires very few changes to a standard DBMS environment, and we argue that these changes are reasonable for the problems being solved. Based on the performance of DATEX we believe we have demonstrated a satisfactory solution to the rule activation problem for complex rule programs operating within a database system.

REFERENCES

• 1: D. S. Batory , J. R. Barnett , J. F. Garza , K. P. Smith , K. Tsukuda , C. Twichell , T. E. Wise, GENESIS: An Extensible Database Management System, IEEE Transactions on Software Engineering, v.14 n.11, p.1711-1730, November 1988 [doi>10.1109/32.9057]
• 2: David A. Brant , Timothy Grose , Bernie Lofaso , Daniel P. Miranker, Effects of Database Size on Rule System Performance: Five Case Studies, Proceedings of the 17th International Conference on Very Large Data Bases, p.287-296, September 03-06, 1991
• 3: Forgy, C. {1981}, "OPS5 User's Manual", Tech. Rep. CMU-CS- 81-135, Carnegie-Mellon University.
• 4: Forgy, C. {1982}, "RETE: A Fast Match Algorithm for the Many PatternlMany Object Pattern Match Problem," Artificial Intelligence, 19, pp. 17-37.
• 5: Anoop Gupta, Parallelism in Production Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 6: Hanson, E. { 1991}, "The Design and Implementation of the Ariel Active Database Rule System," Tech. Rep. WSU-CS-91- 06, Wright State University.
• 7: INGRES { 1990}, INGRES Version 6.3 Reference Manual, INGRES Products Division, Alameda, CA.
• 8: Kerschberg, L. {1987}, (ed.) Proceedings of the First International Conference on Expert Database Systems, Benjamin/ Cummings Publishing Company, Inc.,Menlo Park CA.
• 9: Kerschberg, L. {1988}, (ed.) Proceedings of the Second International Conference on Expert Database Systems, Benjamin/Cummings Publishing Company, Inc.,Menlo Park CA.
• 10: Kou, C.M., D.P. Miranker, and J.C. Browne {1991}, "On the Performance of the CREL System," Journal of Parallel and Distributed Computing, 13:4, pp. 424-441.
• 11: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• 12: McDermott J., A. Newell, and J. Moore {1978}, "The Efficiency of Certain Production System Implementations," In Pattern-directed Inference Systems, D. Waterman and F. Hayes-Roth (eds.), Academic Press.
• 13: Daniel P. Miranker, TREAT: a new and efficient match algorithm for AI production systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 14: Miranker, D.P., D. Brant, B. Lofaso, and D. Gadbois {1990}, "On the Performance of Lazy Matching in Production Systems," Proceedings of the 1990 National Conference on Artificial Intelligence, pp. 685-692.
• 15: Daniel P. Miranker , David A. Brant, An Algorithmic Basis for Integrating Production Systems and Large Databases, Proceedings of the Sixth International Conference on Data Engineering, p.353-360, February 05-09, 1990
• 16: D. P. Miranker , B. J. Lofaso, The Organization and Performance of a TREAT-Based Production System Compiler, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.3-10, March 1991 [doi>10.1109/69.75882]
• 17: Nishyama, S., K. Goolsbey, and D.P. Miranker {1992}, "Optimizing Constant Tests in a Production System Environment," Tech. RED., Dept. of Computer Sciences, University of Texas at Austin.
• 18: T. Sellis , C. Lin , L. Raschid, Data intensive production systems: the DIPS approach, ACM SIGMOD Record, v.18 n.3, p.52-58, Sep. 1989 [doi>10.1145/71031.71038]
• 19: M. Stonebraker , L. A. Rowe , M. Hirohama, The Implementation of POSTGRES, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.125-142, March 1990 [doi>10.1109/69.50912]
• 20: M. Stonebraker, The Integration of Rule Systems and Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.415-423, October 1992 [doi>10.1109/69.166984]
• 21: Sybase {1990}, Sybase V4.0 Reference Manual, Sybase Corp., Emeryville, CA.
• 22: Wang, Y-W, and E. Hanson { 1990}. "A Performance Comparison of the Rete and TREAT Algorithms for Testing Database Rule Conditions," Tech. Rep. WSU-CS-90-18, Dept. of Computer Science and Engineering, Wright State University.
• 23: Jennifer Widom , Roberta Cochrane , Bruce G. Lindsay, Implementing Set-Oriented Production Rules as an Extension to Starburst, Proceedings of the 17th International Conference on Very Large Data Bases, p.275-285, September 03-06, 1991

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Design, Performance