A Parallel Navigation Algorithm with Dynamic Load Balancing for OODBMSs

概要

論文の詳細を見る
High-performance navigational access to objects is crucial if the demands of object-oriented database management system (OODBMS) target application areas are to be met. We propose an algorithm to navigate, in parallel, objects in a parallel OODBMS for a shared-nothing environment. The algorithm exploits, among others, qualified path expressions and the setvalued nature of OODBMS attributes to generate independent paths, that can be traversed in parallel if the objects referenced therein are declustered across multiple nodes. We also propose a decentralised dynamic load balancing algorithm based on the premise that the cost of arbitrary user-defined functions (UDF) in the predicates of qualified path expressions can be estimated accurately by an average calculated over time and used in determining the load at each node in a shared-nothing system. Analytical and simulation results are presented which show that our navigation and load balancing strategies can improve query response time significantly. Simulation shows that if objects are uniformly partitioned across system nodes, our algorithm can achieve a speedup of up to 13.1 from 2 to 32 nodes. If the data is skewed, dynamic load balancing decreases the response time for navigating a seven level path expression by up to 34 %.
一般社団法人情報処理学会の論文
1999-05-15