Efficient processing of relational calculus expressions using range query theory
Dan E. Willard · 1984
In this paper we define a language based on a broad subset of the relational calculus and show all expressions in this language can be evaluated in space O(N) and time O(N logdN), where d is a small constant whose value depends on the particular predicate and where N is the number of records stored in the data base. We currently have no hard statistics, but a reasonable guess seems to be that a standard sequential random access machine can handle 95% or more of commercial requests in time O(N log N) and memory O(N) using this technique.