Predictive dynamic load balancing of parallel and distributed rule and query processing

ABSTRACT

Expert Databases are environments that support the processing of rule programs against a disk resident database. They occupy a position intermediate between active and deductive databases, with respect to the level of abstraction of the underlying rule language. The operational semantics of the rule language influences the problem solving strategy, while the architecture of the processing environment determines efficiency and scalability.In this paper, we present elements of the PARADISER architecture and its kernel rule language, PARULEL. The PARADISER environment provides support for parallel and distributed evaluation of rule programs, as well as static and dynamic load balancing protocols that predictively balance a computation at runtime. This combination of features results in a scalable database rule and complex query processing architecture. We validate our claims by analyzing the performance of the system for two realistic test cases. In particular, we show how the performance of a parallel implementation of transitive closure is significantly improved by predictive dynamic load balancing.

REFERENCES

• 1: Serge Abiteboul , Eric Simon, Fundamental properties of deterministic and nondeterministic extensions of Datalog, Theoretical Computer Science, v.78 n.1, p.137-158, Jan. 21, 1991
• 2: David A. Brant , Daniel P. Miranker, Index support for rule activation, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.42-48, May 25-28, 1993, Washington, D.C., United States
• 3: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 4: Hasanat M. Dewan, Runtime reorganization of parallel and distributed expert database systems, Columbia University, New York, NY, 1994
• 5: H. M. Dewan, D. Ohsie, S.J. Stolfo, O. Wolfson, and S. DaSilva. Incremental Database Rule Processing in PARADISER. Journal of Intelligent Information Systems, 1:2, October 1992.
• 6: Hasanat M. Dewan , Salvatore J. Stolfo, System Reorganization and Load Balancing of Parallel Database Rule Processing, Proceedings of the 7th International Symposium on Methodologies for Intelligent Systems, p.186-197, June 15-18, 1993
• 7: H.M. Dewan and S.J. Stolfo. The Distributed Evaluation of Rules in PARADISER. Technical Report In Preparation, Department of Computer Science, Columbia University, May (expected) 1994.
• 8: Hasanat M. Dewan , Salvatore J. Stolfo , Leland Woodbury, Scalable parallel and distributed expert database systems with predictive load balancing, Journal of Parallel and Distributed Computing, v.22 n.3, p.506-522, Sept. 1994 [doi>10.1006/jpdc.1994.1107]
• 9: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 10: CORPORATE Tandem Performance Group, A benchmark of non-stop SQL on the debit credit transaction, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.337-341, June 01-03, 1988, Chicago, Illinois, United States
• 11: Eric N. Hanson, Rule condition testing and action execution in Ariel, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.49-58, June 02-05, 1992, San Diego, California, United States
• 12: 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
• 13: D.P. Miranker, D. Brant, B. Lofaso, and D. Gadbois. On the Performance of Lazy Matching in Productioa Systems. In Proceedings of the 1990 National Conference on Artificial Intelligence, pages 685-692, 1990.
• 14: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• 15: Daniel E. Neiman, Design and control of parallel rule-firing production systems, University of Massachusetts, Amherst, MA, 1992
• 16: A. Pasik. Improving Production System Performance on Parallel Architectures by Creating Constrained Copies of Rules. Technical Report CUCS-313-87, Department of Computer Science, Columbia University, 1987.
• 17: R. Ramakrishnan, P. Seshadri, D. Srivastave, and S. Sudarshan. An Overview of CORAL. Technical report, Department of Computer Science, University of Wisconsin-Madison, 1989.
• 18: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States
• 19: S J Stolfo , D M Miranker , R C Mills, A simple preprocessing scheme to extract and balance implicit parallelism in the concurrent match of production rules, Proc. of the IFIP TC 10 working conference on Fifth generation computer architectures, p.55-65, October 1986, Manchester, United Kingdom
• 20: S. J. Stolfo, H.M. Dewan, and O. Wolfson. The PARULEL parallel rule language. In Proceedings of the IEEE International Conference on Parallel Processing, pages II:36-45. IEEE, 1991.
• 21: Michael Stonebraker , Greg Kemnitz, The POSTGRES next generation database management system, Communications of the ACM, v.34 n.10, p.78-92, Oct. 1991 [doi>10.1145/125223.125262]
• 22: Shalom Tsur , Carlo Zaniolo, LDL: A Logic-Based Data Language, Proceedings of the 12th International Conference on Very Large Data Bases, p.33-41, August 25-28, 1986
• 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
• 24: Joel L. Wolf , Daniel M. Dias , Philip S. Yu , John Turek, Comparative performance of parallel join algorithms, Proceedings of the first international conference on Parallel and distributed information systems, p.78-89, December 1991, Miami, Florida, United States
• 25: Ouri Wolfson , Aya Ozeri, A new paradigm for parallel and distributed rule-processing, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.133-142, May 23-26, 1990, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages, Performance, Verification