VLDB 2026: Investigadores IMFD presentaron trabajo que agrega el tiempo a consultas BGP y que supera a métodos actuales
La investigación desarrollada por Diego Arroyuelo (DCC UC), Aidan Hogan (DCC UChile), Gonzalo Navarro (DCC UChile) y Juan Reutter (DCC UC e IMC UC), propone una nueva forma de realizar consultas sobre grafos temporales: incorporar la dimensión temporal directamente en el patrón de la consulta. La propuesta fue presentada en Very Large Data Bases (VLDB) 2026, una de las principales conferencias internacionales sobre bases de datos, realizada en Boston.
Entre el 31 de agosto y el 4 de septiembre se realizó en Boston, Estados Unidos, Very Large Data Bases (VLDB) 2026, conferencia internacional que reúne a investigadores que trabajan en bases de datos, gestión de datos y procesamiento de información a gran escala.
En la edición, investigadores del Instituto Milenio Fundamentos de los Datos (IMFD) presentaron el trabajo “Worst-Case Optimal BGPs on Temporal Graphs”, que describe y pone a prueba una estructura de datos que permite incorporar la dimensión temporal directamente en consultas BGP sobre grafos temporales con mejores garantías de eficiencia y resultados más rápidos que los métodos disponibles.
La investigación es del académico del Departamento de Ciencias de la Computación UC, Diego Arroyuelo; los académicos del Departamento de Ciencias de la Computación de UChile, Aidan Hogan y Gonzalo Navarro; y el profesor del DCC UC y del Instituto Instituto de Ingeniería Matemática y Computacional (IMC UC), Juan Reutter, también director del Instituto Milenio Fundamentos de los Datos (IMFD).
El problema que aborda el paper está en el centro de cómo funcionan las bases de datos de grafos, específicamente uno de los componentes estructurales más utilizados en consultas vía lenguajes como SPARQL y GQL: los Basic Graph Pattern (BGP). Dicho componente registra relaciones entre sujetos y objetos para identificar qué relaciones existen, pero no cuándo ocurrieron y/o cómo cambiaron dichas relaciones en el tiempo. El trabajo de los cuatro investigadores IMFD abordó justamente eso.
La propuesta
Lo que hizo el equipo fue extender esa estructura. A los componentes originales sumaron la validez temporal de cada relación —un intervalo con un inicio y un término— y definieron una versión temporal de la consulta, llamada tBGP. En ella, el tiempo puede indicarse como un valor fijo, dejarse como una variable a resolver, o relacionarse con otros tiempos mediante cláusulas de orden. Eso permite formular preguntas que antes tomaban mucho más tiempo para este tipo de consulta.
La propuesta del equipo tiene la particularidad de que además se hace cargo de la eficiencia de espacio, ya que no almacena el grafo completo en cada momento, sino que lo organiza por intervalos definidos según cambios detectados. El resultado es un índice que crece de forma proporcional al número de relaciones, y no a ese número elevado al cuadrado, como ocurriría al almacenar el grafo instante por instante.
Sobre ese índice, el equipo adaptó el algoritmo Leapfrog Triejoin —empleado usualmente en grafos sin tiempo— para que el tiempo pasara a ser una variable más de la consulta. Demostraron que la combinación mantiene la propiedad de ser worst-case optimal: el tiempo de respuesta es proporcional al máximo de resultados que la consulta podría arrojar, sin generar respuestas intermedias que después se descartan.
“Usando estructuras de datos para manejar versiones y nuevas representaciones comprimidas de ellas, logramos mantener espacio lineal, y a la vez resolver consultas más rápidamente que las alternativas simples que existían“, explica el académico del DCC UChile, Gonzalo Navarro.
El trabajo incluye una implementación que fue puesta a prueba sobre datos reales. Los experimentos usaron el grafo de conocimiento Wikidata, con casi mil consultas extraídas de registros de uso real. Las consultas se resolvieron en milisegundos, con un índice que ocupa menos del doble del espacio requerido por un índice equivalente sin información temporal.
Recepción en VLDB 2026
“Presenté este paper con una charla primero, y luego con un póster. Como la línea de investigación que condujo a este paper mezcla cosas de distintas disciplinas dentro de computación —estructuras de datos, bases de datos, algoritmos—, el paper despertó mucho interés. Las personas querían aprender sobre las técnicas que usamos en nuestro trabajo”, explicó el director del Instituto Milenio Fundamentos de los Datos, Juan Reutter.
¿Por qué esta investigación es importante?
Porque las aplicaciones de la investigación hacen posible abarcar cualquier tipo de grafo que pueda ser consultado vía BGP, ahora con la opción de incorporar intervalos de validez temporal como una variable más.
“La información temporal es central en muchos tipos de repositorios. Pensemos en bases de datos sobre viajes en una ciudad, transacciones online, contactos entre portadores de virus, etc. Se requiere diseñar un lenguaje de consulta adecuado, y una implementación eficiente de ese lenguaje, para poder explotar esa información adecuadamente“, explica Navarro.
La investigación fue financiada por la Agencia Nacional de Investigación y Desarrollo de Chile (ANID), como parte del Programa Iniciativa Científica Milenio, con apoyo adicional del Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt).