El galardón distingue los artículos de mayor impacto presentados durante la última década en la Conferencia Internacional sobre Teoría de Bases de Datos, ya sea en términos de investigación, metodología, contribuciones conceptuales o aplicaciones prácticas. El paper seleccionado este año se titula “Regular Queries on Graph Databases” y, además de Reutter (DCC UC / IMC UC), tiene como autores a Miguel Romero (DCC UC) y Moshe Y. Vardi (Universidad Rice, EE.UU.)
Hace 22 años, la Conferencia Internacional sobre Teoría de Bases de Datos (ICDT) comenzó a otorgar el premio ICDT Test of Time (ToT) para reconocer un paper, o un pequeño número de artículos, presentados en la ICDT al menos una década antes y que hayan superado mejor la "prueba del tiempo". Cabe destacar que la conferencia se lleva a cabo desde 1986 y se ha convertido en una de las más prestigiosas del área.
El premio ICDT ToT de este año se entregará durante la Conferencia Conjunta EDBT/ICDT 2025, que se desarrollará del 25 al 28 de marzo en Barcelona, España. En esta ocasión el Comité del galardón -compuesto por Xiao Hu (Universidad de Waterloo), Graham Cormode (Universidad de Warwick) y Marcelo Arenas (Departamento de Ciencia de la Computación UC/Instituto de Ingeniería Matemática y Computacional e investigador del Instituto Milenio Fundamentos de los Datos)- se encargó de analizar los artículos con mayor impacto de las actas de la ICDT 2015 en términos de investigación, metodología, contribuciones conceptuales o aplicaciones prácticas durante la última década.
Tras una meticulosa revisión, el comité seleccionó el artículo “Regular Queries on Graph Databases” como ganador del premio 2025. Sus autores son Juan Reutter (DCC UC/IMC UC y director del IMFD), Miguel Romero (DCC UC) y Moshe Y. Vardi (Universidad Rice, EE.UU.). De acuerdo con la organización a cargo del premio, las bases de datos de grafos se han convertido en un “modelo de datos clave, que se distingue por su énfasis en las consultas de navegación que descubren conexiones entre nodos en función de expresiones de navegación específicas. En este trabajo seminal, los autores introdujeron el lenguaje de consulta ‘Consultas regulares’ (RQ), un formalismo que extiende los lenguajes de consulta de grafos bien conocidos, como UC2RPQ y UCN2RPQ, al incorporar reglas de cierre transitivo en Datalog no recursivo. Aunque este lenguaje ya se había considerado antes, sus propiedades algorítmicas no se entendían bien”.
Juan Reutter
Una contribución importante de este artículo, agrega la organización, es demostrar que el “problema de contención de las Consultas regulares es 2EXPSPACE-completo, un resultado fundamental para comprender su complejidad computacional. Este estudio posicionó a RQ como un fragmento expresivo pero computacionalmente manejable, que conecta los avances teóricos con las aplicaciones prácticas e influye tanto en la teoría como en la práctica de las bases de datos”.
El trabajo realizado por Reutter y sus colegas ha inspirado investigaciones posteriores sobre lenguajes de consulta de grafos, incluidos los nuevos lenguajes estándar GQL y SQL/PGQ para bases de datos de grafos. Trabajos posteriores han explorado más a fondo el poder expresivo y la utilidad de las consultas regulares en áreas como el procesamiento de consultas de grafos en tiempo real, el mantenimiento de vistas de grafos con Regular Datalog y el desarrollo de taxonomías de lenguajes de consulta de grafos, lo que “demuestra la amplia influencia de este marco en dominios tanto teóricos como prácticos”.