Structural Recursion as a Query Language

Peter Buneman, Val Tannen, S. Naqvi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose a programming paradigm that tries to get close to both the semantic simplicity of relational algebra, and the expressive power of unrestricted programming languages. Its main computational engine is structural recursion on sets. All programming is done within a "nicely" typed lambda calculus, as in Machiavelli [OBB89]. A guiding principle is that how queries are implemented is as important as whether they can be implemented. As in relational algebra, the meaning of any relation transformer is guaranteed to be a total map taking finite relations to finite relations. A naturally restricted class of programs written with structural recursion has precisely the expressive power of the relational algebra. The same programming paradigm scales up, yielding query languages for the complex-object model [AB89]. Beyond that, there are, for example, efficient programs for transitive closure and we are also able to write programs that move out of sets, and then perhaps back to sets, as long as we stay within a (quite flexible) type system. The uniform paradigm of the language suggests positive expectations for the optimization problem. In fact, structural recursion yields finer grain programming therefore we expect that lower-level, and therefore better optimizations will be feasible.
Original languageEnglish
Title of host publicationProceedings of 3rd International Workshop on Database Programming Languages
PublisherMorgan Kaufmann
Number of pages11
ISBN (Print)1-55860-242-9
Publication statusPublished - Aug 1991


Dive into the research topics of 'Structural Recursion as a Query Language'. Together they form a unique fingerprint.

Cite this