This project aims to study the parallel architectures and algorithms for efficient processing of large object-oriented knowledge bases. The approach taken in this study is to represent a large knowledge base as a schema graph at the intensional level and as object graphs at the extensional level. Graph-based models are then used for OO (object-oriented) query processing and optimization, knowledge rule processing, and transaction management. A graph-based query processing model supports two parallel multiple wavefront algorithms, namely, identification and elimination algorithms. Query processing is divided into two phases. In the first phase, objects of interest or of no interest in the knowledge base are identified or eliminated depending on the algorithms used. In the second phase, system/user defined functions are executed on the objects selected during the first phase to produce the final result. In our research, the processing and optimization of multiple queries is being studied and heuristic rules are applied. In the graph-based rule processing model, a control graph models the variety of structural and semantic relationships and dependencies among rules. This provides a mechanism to process the triggered rules according to the application semantics and also clearly defines the scope of parallelism that can be exploited among rules. Compatible to the control graphs of rules, we also use a control graph representation for transactions. This representation of a transaction is more general and powerful than traditional flat and tree-based transaction models and can uniformly embed the rule control graphs as part of a transaction.
We have presented and proven the correctness of multiple wave-front algorithms for both tree-structured and cyclic queries. A unique data structure for supporting multiple wavefront algorithms has been designed and implemented. A parallel query processor has been implemented on a multiprocessor Transputer network. Based on the experience, we built a query processing evaluation system, which can process multiple queries, on a 64-node nCUBE2 parallel computer. We have implemented a graph-based parallel scheduling algorithm on the nCUBE2 parallel computer. Other supporting modules of the object-oriented knowledge base management system (query processor, transaction processor, lock manager, etc.) are simulated to create an environment for evaluating architectures and algorithms.
This project was initially supported by NSF with Prof. Stanley Su (su@cis.ufl.edu) as the Principal Investigator and Prof. Herman Lam (hlam@cis.ufl.edu) as the Co-Principal Investigator. It is presently supported by Fujitsu, Ltd., with Prof. Stanley Su as the Principal Investigator.