Multiple wavefront algorithms for pattern-based processing of object-oriented databases

The authors have show previously (1989, 1991) that processing OODBs can be viewed as the manipulation of patterns of object associations. Parallel, multiple wavefront algorithms based on an identification approach for verifying association patterns have been introduced. The current paper presents an elimination approach for processing OODBs. The new approach allows more processors to operate concurrently on a query, thus allowing a higher degree of parallelism in query processing. A formal proof of the correctness of the new approach is given, and a parallel elimination algorithm for processing tree queries is presented. Some simulation results are also provided to compare the performance of the identification approach with the elimination approach