The relationship between polynomial and exponential time bounded relativized computations is investigated. It is shown that there exists an oracle X such that relative to X nondeterministic exponential computations yield only the languages in $\Sigma _2^{P,X} $ from the polynomial hierarchy. More informally, relative to that X two polynomial quantifiers are as powerful as one exponential quantifier.

In this paper a new method to increase parallelism in database systems is described. Use is made of the fact that for recovery reasons, we often have two values for one object in the database—the new one and the old one. Introduced and discussed in detail is a certain scheme by which readers and writers may work simultaneously on the same object. It is proved that transactions executed according to this scheme have the correct effect; i.e., consistency is preserved. Several variations of the basic scheme which are suitable depending on the degree of parallelism required, are described.