Paper Info
Title
Multiple wavefront algorithms for pattern-based processing of object-oriented databases
Abstract
The newly developed object-oriented database management systems provide rich facilities for the modeling and processing of structural as well as behavioral properties of complex application objects. However, due to the generality and high functionality of these systems, efficiency in processing large object-oriented databases is difficult to achieve using conventional computer systems. Efficient parallel algorithms and architectures are needed to solve this efficiency problem. In our previous work, we have shown that processing OODBs can be viewed as the manipulation of patterns of object associations. Parallel, multiple wavegront algorithms based on an identification approach for verifying association patterns have been introduced. In this paper, we present another approach for processing OODBs, i.e., an elimination approach which eliminates objects that do not satisfy an association pattern specification given in a query instead of identifying objects that satisfy the specification. 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 in this paper. Some simulation results are also provided to compare the performance of the identification approach with the elimination approach.
Year
DOI
Venue
1991
10.1109/PDIS.1991.183066
Miami Beach, FL
Keywords
Field
DocType
association pattern specification,processing tree query,multiple wavefront algorithm,efficiency problem,pattern-based processing,parallel elimination algorithm,efficient parallel algorithm,new approach,query processing,elimination approach,large object-oriented databases,identification approach,performance,computer aided manufacturing,database systems,design automation,parallel programming,parallel processing,concurrency,parallel algorithms
Computer-aided manufacturing,Wavefront,Concurrency,Degree of parallelism,Parallel algorithm,Computer science,Correctness,Algorithm,Theoretical computer science,Electronic design automation,Formal proof
Conference
ISBN
Citations 
PageRank 
0-8186-2295-4
5
1.94
References 
Authors
20
3
Name
Order
Citations
PageRank
Stanley Y. W. Su116221403.92
Yaw-Huei Chen25714.22
Herman Lam330591.31