VLDB 2026: IMFD researchers extend Basic Graph Patterns to temporal graphs, outperforming current methods
Research conducted by Diego Arroyuelo (DCC UC), Aidan Hogan (DCC UChile), Gonzalo Navarro (DCC UChile) and Juan Reutter (DCC UC and IMC UC) proposes a new way to query temporal graphs: incorporating the temporal dimension directly into the query pattern. The proposal was presented at Very Large Data Bases (VLDB) 2026, one of the leading international conferences on databases, held in Boston.
Very Large Data Bases (VLDB) 2026, an international conference bringing together researchers working in databases, data management, and large-scale information processing, was held in Boston, United States, from August 31 to September 4.
At this year’s conference, researchers from the Millennium Institute for Foundational Research on Data (IMFD) presented the paper “Worst-Case Optimal BGPs on Temporal Graphs,” which describes and tests a data structure that incorporates the temporal dimension directly into Basic Graph Patterns (BGP) queries on temporal graphs, offering stronger efficiency guarantees and faster results than existing methods.
The research was conducted by Department of Computer Science UC professor Diego Arroyuelo; Department of Computer Science UChile professors Aidan Hogan and Gonzalo Navarro; and DCC UC professor and researcher at the Institute of Mathematical and Computational Engineering (IMC UC), Juan Reutter, who is also director of the Millennium Institute for Foundational Research on Data (IMFD).
The problem addressed in the paper lies at the core of how graph databases work, specifically one of the structural components most widely used in queries through languages such as SPARQL and GQL: Basic Graph Patterns (BGP). This component records relationships between subjects and objects to identify which relationships exist, but not when they occurred or how they changed over time. The work of the four IMFD researchers addressed exactly that gap.
The Proposal
What the team did was extend that structure. To the original components, they added the temporal validity of each relation —an interval with a start and an end— and defined a temporal version of the query, called tBGP. In it, time can be indicated as a fixed value, left as a variable to be resolved, or related to other times through order clauses. This makes it possible to formulate questions that previously took much longer for this type of query.
The team’s proposal has the particularity of also addressing space efficiency, since it does not store the complete graph at every moment, but rather organizes it into intervals defined according to detected changes. The result is an index that grows proportionally to the number of relations, rather than to that number squared, as would happen if the graph were stored instant by instant.
Building on that index, the team adapted the Leapfrog Triejoin algorithm —usually employed on graphs without time— so that time became just another variable in the query. They demonstrated that the combination retains the property of being worst-case optimal: response time is proportional to the maximum number of results the query could return, without generating intermediate results that are later discarded.
“Using data structures to manage versions and new compressed representations of them, we managed to maintain linear space while also solving queries faster than the simple alternatives that existed,” explains DCC UChile academic Gonzalo Navarro.
The work includes an implementation that was tested on real data. The experiments used the Wikidata knowledge graph, with nearly a thousand queries drawn from real usage logs. The queries were resolved in milliseconds, with an index that takes up less than double the space required by an equivalent index without temporal information.
Reception at VLDB 2026
“I presented this paper first with a talk, and then with a poster. Since the line of research that led to this paper mixes elements from different disciplines within computing —data structures, databases, algorithms—, the paper drew a lot of interest. People wanted to learn about the techniques we used in our work,” explained the director of the Millennium Institute for Foundational Research on Data (IMFD), Juan Reutter.
Why is this research important?
Because the applications of this research make it possible to cover any type of graph that can be queried via BGP, now with the option of incorporating temporal validity intervals as an additional variable.
“Temporal information is central to many types of repositories. Think of databases on trips within a city, online transactions, contacts between virus carriers, and so on. It is necessary to design an appropriate query language, and an efficient implementation of that language, in order to properly exploit that information,” explains Navarro.
The research was funded by Chile’s National Agency for Research and Development (ANID), as part of the Millennium Science Initiative Program, with additional support from the National Fund for Scientific and Technological Development (Fondecyt).