Paper by Juan Reutter receives ICDT Test of Time 2025 Award

The award honors the papers with the greatest impact presented during the last decade at the International Conference on Database Theory, either in terms of research, methodology, conceptual contributions or practical applications. The paper selected this year is entitled "Regular Queries on Graph Databases" and, in addition to Juan Reutter, academic of the Department of Computer Science UC, of the Institute of Mathematical and Computational Engineering UC and director of the Millennium Institute Foundational Research on Data, has as authors Miguel Romero (DCC UC) and Moshe Y. Vardi (Rice University, USA).

Twenty-two years ago, the International Conference on Database Theory(ICDT) began awarding the ICDT Test of Time (ToT) award to recognize a paper, or a small number of papers, presented at ICDT at least a decade earlier that have best passed the "test of time". It should be noted that the conference has been held since 1986 and has become one of the most prestigious in the field.

This year's ICDT ToT Award will be presented during the EDBT/ICDT 2025 Joint Conference, to be held from March 25-28 in Barcelona, Spain. On this occasion, the award committee - composed of Xiao Hu(University of Waterloo), Graham Cormode(University of Warwick) and Marcelo Arenas (DCC UC-IMC UC and IMFD researcher) - was in charge of analyzing the papers with the highest impact of the ICDT 2015 proceedings in terms of research, methodology, conceptual contributions or practical applications during the last decade.

After a meticulous review, the committee selected the paper "Regular Queries on Graph Databases" as the winner of the 2025 award. Its authors are Juan Reutter, Miguel Romero and Moshe Y. Vardi. According to the award organization, graph databases have become a "key data model, distinguished by their emphasis on navigational queries that discover connections between nodes based on specific navigational expressions. In this seminal work, the authors introduced the query language 'Regular Queries' (RQ), a formalism that extends well-known graph query languages, such as UC2RPQ and UCN2RPQ, by incorporating transitive closure rules in non-recursive Datalog. Although this language had been considered before, its algorithmic properties were not well understood."

An important contribution of this paper, the organization adds, is to demonstrate that the "regular Query containment problem is 2EXPSPACE-complete, a fundamental result for understanding its computational complexity. This study positioned RQ as an expressive yet computationally tractable fragment that connects theoretical advances with practical applications and influences both database theory and practice."

The work done by Reutter and his colleagues has inspired subsequent research on graph query languages, including the new standard GQL and SQL/PGQ languages for graph databases. Subsequent work has further explored the expressive power and utility of regular queries in areas such as real-time graph query processing, maintaining graph views with Regular Datalog, and developing taxonomies of graph query languages, which "demonstrates the broad influence of this framework in both theoretical and practical domains."

Source: IMC UC