Data distribution and algorithms for asynchronous parallel processing of object-oriented knowledge bases
Arun K. Thakore · 1991
Sophisticated management and reasoning about large quantities of complex data are essential in advanced application areas. Several Object-Oriented (OO) databases/knowledge bases have been developed to effectively capture the complex domain knowledge. However, due to the enormity and the intricacy of the data, and the generality of the functions implemented by the OO databases/knowledge bases, the existing implementations operate inefficiently. In this dissertation, we study several issues related to the efficient parallel implementation of OO knowledge bases. The physical organization of the data across the processing nodes of a parallel system plays an important role in determining the execution time. We present several techniques for efficiently partitioning large quantities of OO data across the processing nodes of the parallel system. The techniques take advantage of the structure and the semantic property of OO data in localizing manipulation and reducing the overall communication costs during query processing. Further, we present parallel algorithms for the processing of non-deductive and deductive queries against a large OO knowledge base. The algorithms are developed for various query complexities. During processing, the algorithms avoid the execution of time-consuming join operations by retrieving the explicitly stored relationships, among the various object instances, based on patterns of object associations. Generation of large quantities of temporary data is avoided by marking object instances using their identifiers and by employing a two-phase query processing strategy. A query is processed by concurrent multiple wavefronts, thereby improving parallelism and avoiding the complexities introduced in their sequential implementation. The suitability of the data partitioning techniques and the correctness and the performance of the parallel algorithms have been tested and analyzed by running parallel programs on the IBM's distributed message passing system Victor. Benchmark queries of different semantic complexities are generated and their performance is analyzed for various data and system parameters. The performance of several application domains characterized by specific mixes of the benchmark queries is also analyzed.