The Power of Methods With Parallel Semantics
Karl Denninghoff, Victor Vianu · 1991
A model capturing the data manipulation ca-pabilities of a large class of methods in ohject-oriented databases is proposed and investsi-gated. The model uses a deterministic, par-allel synchronous semantics with concurrent-read and concurrent-write. The results fo-cus on the expressive power of methods and help understand various constructs and se-mantics associated with methods. Restric-tions of methods providing va.rious tract,ability guarantees are also discussed. The restrictions correspond closely to well-known relational query languages such aa relational calculus, Datalog, the fixpoint queries, and the while queries. They provide complexity bounds such as constant parallel time, PTIMF, and PSPACE. Exact characterizations for some complexity classes are also obGncd under cer-tain assumptions. Our methods provide a model of database parallel computation which makes explicit the potential parallelism in databases. We compare our model to tra-ditional parallel computation models such as PRAMS and Hardware Modif?cal,ion Ma.chincs and show mutual simulation results with rca-sonable cost. We also compare methods t,o a newer model of generic computation involving parallelism. We show that certain complex-ity classes defined using the two models are the same, which suggests that methods cap-ture database parallel computaf,ion in a nat,u-ral and robust fashion. 1