Paper by Juan receives the ICDT Test of Time 2025 award

The award recognizes the most influential articles presented over the last decade at the International Conference on Database Theory, whether in terms of research, methodology, conceptual contributions, or practical applications. This year's selected paper is entitled "Regular Queries on Graph Databases" and, in addition to Juan , an academic at the UC Department of Computer Science, the UC Institute of Mathematical and Computational Engineering, and director of Millennium Institute Foundational Research on Data, its authors include 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) prize to recognize a paper, or a small number of articles, presented at the ICDT at least a decade earlier that have best stood 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 theEDBT/ICDT 2025 Joint Conference, which will take place from March 25 to 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 responsible for analyzing the articles with the greatest impact from the ICDT 2015 proceedings in terms of research, methodology, conceptual contributions, or practical applications over the last decade.

After a meticulous review, the committee selected the article "Regular Queries on Graph Databases"as the winner of the 2025 award. Its authors are Juan , Miguel Romero, and Moshe Y. Vardi. According to the organization in charge of the award, graph databases have become a "key data model, distinguished by its emphasis on navigation queries that discover connections between nodes based on specific navigation expressions. In this seminal work, the authors introduced the 'Regular Queries' (RQ) query language, 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 article, the organization adds, is to demonstrate that the "containment problem of regular queries is 2EXPSPACE-complete, a fundamental result for understanding their computational complexity. This study positioned RQ as an expressive but computationally manageable fragment, connecting theoretical advances with practical applications and influencing both database theory and practice."

The work done by Reutter and his colleagues has inspired further research on graph query languages, including the new standard languages GQL and SQL/PGQ 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