I apologize for the double-post, but I sent out a version in which one crucial piece of information was missing: the Test of Time Award winning paper appeared at ICDT 1992.

Sorry, again!

Thomas Schwentick


ICDT 2014 Test of Time Award


In 2013, the International Conference on Database Theory (ICDT) began awarding the ICDT test-of-time (ToT) award, with the goal of recognizing one paper, or a small number of papers, presented at ICDT from at least a decade earlier that have best met the "test of time". The ICDT ToT award for 2014 will be presented during the EDBT/ICDT 2014 Joint Conference, March 24-27, 2014 in Athens, Greece.

The ICDT 2014 ToT Award Committee consists of Ronald Fagin (chair), Michael Benedikt, and Wim Martens. The committee was charged with selecting a paper or a small number of papers from the ICDT 1986 - 1992 proceedings that has had the most impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. After careful consideration, we have decided to select the following paper as the award winner for 2014:

Naturally Embedded Query Languages, by Val Breazu-Tannen (now Tannen), Peter Buneman, and Limsoon Wong

This seminal paper (which appeared in ICDT 1992) strongly contributed to the establishment of the complex-object data model and its accompanying query languages. The paper had a significant influence on many important query- and programming languages. For example, LINQ and its monadic semantics finds its roots in this work, as do many language proposals following the map-reduce paradigm. XQuery, one of the most important languages for querying XML, is strongly based on the Nested Relational Calculus, which was introduced in this paper.

The paper identifies structural recursion over collection types (which generalize sets, bags, and lists) as the single computational device to explain the semantics of iteration, aggregation, quantification, filtering, joins, transitive closure, nesting and unnesting, and thus the core building blocks of rich query and collection-oriented programming languages.  It is remarkable that structural recursion and the associated notion of monad also serve as a syntactic guideline: comprehensions, in various forms, have been at the heart of collection-oriented languages to this day. The authors identify restrictions that render the general recursion scheme as expressive as previously-defined languages for nested data structures, including the nested algebra or complex objects algebra.

The paper has approximately 200 citations to this date and its journal version, called "Principles of Programming with Complex Objects and Collection Types", with additional author Shamim Naqvi, has another 260 citations.  It continues to spur interconnection between the database and functional programming communities.