OpenRuleBench: an analysis of the performance of rule engines

ABSTRACT

The Semantic Web initiative has led to an upsurge of the interest in rules as a general and powerful way of processing, combining, and analyzing semantic information. Since several of the technologies underlying rule-based systems are already quite mature, it is important to understand how such systems might perform on the Web scale. OpenRuleBench is a suite of benchmarks for analyzing the performance and scalability of different rule engines. Currently the study spans five different technologies and eleven systems, but OpenRuleBench is an open community resource, and contributions from the community are welcome. In this paper, we describe the tested systems and technologies, the methodology used in testing, and analyze the results.

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: 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
• 3: I. Balbin , G. S. Port , K. Ramamohanarao , K. Meenakshi, Efficient bottom-up computation of queries on stratified databases, Journal of Logic Programming, v.11 n.3-4, p.295-344, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90030-S]
• 4: Catriel Beeri , Raghu Ramakrishnan, On the power of magic, Journal of Logic Programming, v.10 n.3-4, p.255-299, April/May 1991 [doi>10.1016/0743-1066(91)90038-Q]
• 5: B. Bishop and F. Fischer. Iris -- integrated rule inference system. In International Workshop on Advancing Reasoning on the Web: Scalability and Commonsense (ARea 2008), June 2008.
• 6: F. Bry, N. Eisinger, T. Eiter, T. Furche, G. Gottlob, C. Ley, B. Linse, R. Pichler, and F. Wei. Foundations of Rule-Based Query Answering. In Proceedings of Summer School Reasoning Web 2007, Dresden, Germany (3rd--7th September 2007), volume 4634 of LNCS, pages 1--153. REWERSE, 2007.
• 7: Francesco Calimeri , Susanna Cozza , Giovambattista Ianni , Nicola Leone, Computable Functions in ASP: Theory and Implementation, Proceedings of the 24th International Conference on Logic Programming, December 09-13, 2008, Udine, Italy [doi>10.1007/978-3-540-89982-2_37]
• 8: The China benchmark suite, 2001. http://www.cs.unipr.it/China/Benchmarks/.
• 9: K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 292--322. Plenum Press, 1978.
• 10: C.L. Forgy. Rete: a fast algorithm for the many pattern/many object pattern match problem. Atrificial Intelligence, 19(1):17--37, September 1982.
• 11: Hector Garcia-Molina , Jeffrey D. Ullman , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall Press, Upper Saddle River, NJ, 2008
• 12: Logic programming and knowledge representation-the A-prolog perspective, Artificial Intelligence, v.138 n.1-2, p.3-38, June 2002 [doi>10.1016/S0004-3702(02)00207-2]
• 13: M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Logic Programming: Proceedings of the Fifth Conference and Symposium, pages 1070--1080, 1988.
• 14: Y. Guo, Z. Pan, and J. Heflin. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics, 2005.
• 15: Michael Kifer , Arthur Bernstein , Philip M. Lewis, Database Systems: An Application Oriented Approach, Complete Version (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 16: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 17: Michael Kifer , Eliezer L. Lozinskii, Implementing Logic Programs as a Database System, Proceedings of the Third International Conference on Data Engineering, p.375-385, February 03-05, 1987
• 18: O. Lassila and R.R. Swick (editors). Resource description framework (RDF) model and syntax specification. Technical report, W3C, February 1999. http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/.
• 19: L. Ma, Y. Yang, Z. Qiu, G. Xie, Y. Pan, and S. Liu. Towards a complete OWL ontology benchmark. In European Semantic Web Conference, pages 125--139, 2006.
• 20: Openrulebench web site, 2008. http://rulebench.projects.semwebcentral.org.
• 21: Prolog benchmarking, 1985. http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/code/bench/0.html.
• 22: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 23: York Sure , Jürgen Angele , Steffen Staab, OntoEdit: Guiding Ontology Development by Methodology and Inferencing, On the Move to Meaningful Internet Systems, 2002 - DOA/CoopIS/ODBASE 2002 Confederated International Conferences DOA, CoopIS and ODBASE 2002, p.1205-1222, October 30-November 01, 2002
• 24: Terrance Swift , David S. Warren, An abstract machine for SLG resolution: definite programs, Proceedings of the 1994 International Symposium on Logic programming, p.633-652, November 1994, Symposia, Melbourne
• 25: H.J. ter Horst. Combining RDF and part of OWL with rules: Semantics, decidability, complexity. In International Semantic Web Conference (ISWC), pages 668--684, November 2005.
• 26: G. Terracina , N. Leone , V. Lio , C. Panetta, Experimenting with recursive queries in database and logic programming systems, Theory and Practice of Logic Programming, v.8 n.2, p.129-165, March 2008 [doi>10.1017/S1471068407003158]
• 27: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 28: Allen Van Gelder, The alternating fixpoint of logic programs with negation, Journal of Computer and System Sciences, v.47 n.1, p.185-221, Aug. 1993
• 29: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 30: David S. Warren, Memoing for logic programs, Communications of the ACM, v.35 n.3, p.93-111, March 1992 [doi>10.1145/131295.131299]
• 31: D.S. Warren. Programming in tabled prolog. Manuscript. http://www.cs.sunysb.edu/ warren/xsbbook/, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Rule-based databases

General Terms:
Experimentation, Languages, Performance

Keywords:
benchmark, openrulebench, rule systems, semantic web