Translating relational queries into iterative programs (Q1801247)

This book investigates the problem of translating set-oriented query specifications into iterative programs. The translation uses techniques of functional programming and program transformation. The first part presents two algorithms which generate iterative programs from algebra-based query specifications. The first algorithm initially translates query specifications into recursive programs. Those are simplified by sets of transformation rules before the last step of the algorithm generates the final iterative form. The second algorithm uses a two level translation which generated iterative programs faster than the first algorithm. On the first level a small set of transformation rules performs structural simplification before the functional combination on the second level yields the final iterative form. In the second part the same techniques are used to generate efficient programs for the evaluation of aggregate functions. One possible evaluation strategy is to sort the relation before applying the aggregate function, or better yet, to perform aggregation while sorting. Several transformation steps systematically generate these more efficient programs from separate specifications for the sort algorithm and the aggregate function. Finally, the third part investigates the Lisp-dialect T as a possible implementation language for database systems.