Naturally Embedded Query Languages

Val Tannen, Peter Buneman, Limsoon Wong

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


We investigate the properties of a simple programming language whose main computational engine is structural recursion on sets. We describe a progression of sublanguages in this paradigm that (1) have increasing expressive power, and (2) illustrate robust conceptual restrictions thus exhibiting interesting additional properties. These properties suggest that we consider our sublanguages as candidates for “query languages”. Viewing query languages as restrictions of our more general programming language has several advantages. First, there is no “impedance mismatch” problem; the query languages are already there, so they share common semantic foundation with the general language. Second, we suggest a uniform characterization of nested relational and complex-object algebras in terms of some surprisingly simple operators;and we can make comparisons of expressiveness in a general framework. Third, we exhibit differences in expressive power that are not always based on complexity arguments, but use the idea that a query in one language may not be polymorphically expressible in another. Fourth, ideas of category theory can be profitably used to organize semantics and syntax, in particular our minimal (core) language is a well-understood categorical construction: a cartesian category with a strong monad on it. Finally, we bring out an algebraic perspective, that is, our languages come with equational theories, and categorical ideas can be used to derive a number of rather general identities that may serve as optimizations or as techniques for discovering optimizations.
Original languageEnglish
Title of host publicationDatabase Theory — ICDT '92
Subtitle of host publication4th International Conference Berlin, Germany, October 14–16, 1992 Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-47360-2
ISBN (Print)978-3-540-56039-5
Publication statusPublished - 1992


Dive into the research topics of 'Naturally Embedded Query Languages'. Together they form a unique fingerprint.

Cite this