efficient processing of relational calculus expressions using range query theory
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 log d N), 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.
efficiency process relation express range queries theory paper language value space timing log records data base statistics standardization random access memorialized