9313847 Stolfo We study solutions to the performance bottleneck in expert databases using the PARADISER 10 distributed rule processing environment as our testbed. We purpose an approach that combines statically computed restrictions on the rules of a rule program for partitioning the workload of rule evaluation among an arbitrary number of rule program replicas evaluated at distinct processing sites, and dynamic load balancing protocols that update and reorganize the distribution of workload by modifying the restrictions at runtime. (Rules are not redistributed.) Our techniques utilize one form of "meta-data", namely, statistics gathered on the attribute values and size of relations of the underlying database (e.g., number of distinct values of an attribute, number of tuples in a relation etc.) in the algorithms that compute the restrictions on the rules. We analyze the dynamic load balancing protocols in terms of efficiency and scalability criteria, which provide guidance on the expected behavior of the protocols with increasing database size. The proposed research falls into three main categories: (a) workload distribution paradigms among processing sites to ameliorate the performance degradation resulting from scaling up of database size, (b) a suite of load balancing protocols for dynamic "logical" reorganization of the underlying database, and their scaling characteristics, and , (c) experimental validation in the PARADISER expert database environment, using a suite of benchmark rule programs. A fully operational and transferable rule processing environment will be constructed that embodies these results.
