β Scribed by Dan Suciu; Val Tannen
No coin nor oath required. For personal study only.
We show that a form of divide and conquer recursion on sets, together with the relational algebra, expresses exactly the queries over ordered relational databases which are NC-computable. At a finer level, we relate k nested uses of recursion exactly to AC k , k 1. We also give corresponding results for complex objects.
π SIMILAR VOLUMES
More and more relational database systems for microcomputers are providing visual interfaces, such as query by example (QBE). At the same time, experimental studies are providing more support for the theory that the end users can perform better with the entity relationship (ER) model than with the r
Or-sets were introduced by Imielinski, Naqvi, and Vadaparty for dealing with limited forms of disjunctive information in database queries. Independently, Rounds used a similar notion for representing disjunctive and conjunctive information in the context of situation theory. In this paper we formula