One-sided recursions

摘要

The performance of database systems with recursive query languages can be improved by recognizing simple, easily evaluable classes of recursions and using algorithms tailored to these classes whenever possible. In this paper we identify a useful subset of recursive definitions, the one-sided recursions. We show how to detect one-sided recursions, and give a schema to evaluate selections of the form “column = constant” on a relation defined by a one-sided recursion. Instantiating this schema produces evaluation algorithms that have simple termination conditions, maintain minimal state information, and use selections on the recursively defined relation to restrict the tuples examined during the evaluation. We show that there are no similar algorithms for many-sided recursions. We also prove that it is undecidable whether an arbitrary definition has an equivalent one-sided definition, but show that equivalence to a one-sided recursion is decidable for a large subset of recursions.