Predictive Dynamic Load Balancing of Parallel and Distributed Rule and Query Processing.

@inproceedings{DBLP:conf/sigmod/DewanSHH94,
  author    = {Hasanat M. Dewan and
               Salvatore J. Stolfo and
               Mauricio A. Hern{\'a}ndez and
               Jae-Jun Hwang},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Predictive Dynamic Load Balancing of Parallel and Distributed
               Rule and Query Processing},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {277-288},
  ee        = {http://doi.acm.org/10.1145/191839.191893, db/conf/sigmod/DewanSHH94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Eric Simon: Fundamental Properties of Deterministic and Nondeterministic Extensions of Datalog. Theor. Comput. Sci. 78(1): 137-158(1991)

[2]

David A. Brant, Daniel P. Miranker: Index Support for Rule Activation. SIGMOD Conference 1993: 42-48

[3]

George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108

[4]

...

[5]

Hasanat M. Dewan, David Ohsie, Salvatore J. Stolfo, Ouri Wolfson, Sushil Da Silva: Incremental Database Rule Processing In PARADISER. J. Intell. Inf. Syst. 1(2): 177-209(1992)

[6]

Hasanat M. Dewan, Salvatore J. Stolfo: System Reorganization and Load Balancing of Parallel Database Rule Processing. ISMIS 1993: 186-197

[7]

...

[8]

...

[9]

David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992)

[10]

The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341

[11]

Eric N. Hanson: Rule Condition Testing and Action Execution in Ariel. SIGMOD Conference 1992: 49-58

[12]

Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224

[13]

Daniel P. Miranker, David A. Brant, Bernie J. Lofaso, David Gadbois: On the Performance of Lazy Matching in Production Systems. AAAI 1990: 685-692

[14]

Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568

[15]

...

[16]

...

[17]

...

[18]

Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121

[19]

...

[20]

...

[21]

Michael Stonebraker, Greg Kemnitz: The Postgres Next Generation Database Management System. Commun. ACM 34(10): 78-92(1991)

[22]

Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41

[23]

Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285

[24]

Joel L. Wolf, Daniel M. Dias, Philip S. Yu, John Turek: Comparative Performance of Parallel Join Algorithms. PDIS 1991: 78-88

[25]

Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142

Referenced by

1. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
   Contents