arXiv CSopen access

Worst-Case Optimal BGPs on Temporal Graphs

Worst-Case Optimal BGPs on Temporal Graphs Diego Arroyuelo

Aidan Hogan

Gonzalo Navarro

Juan Reutter

Pontificia Universidad Católica de Chile & IMFD, Chile [email protected]

DCC, Universidad de Chile & IMFD, Chile [email protected]

DCC, Universidad de Chile & IMFD, Chile [email protected]

Pontificia Universidad Católica de Chile & IMFD, Chile [email protected]

arXiv:2607.20356v1 [cs.DB] 22 Jul 2026

ABSTRACT We study how to evaluate basic graph patterns (BGPs) in a worstcase-optimal (wco) manner over temporal labeled graphs, where edges have an interval of temporal validity. We adopt a flexible query language in which users specify 𝑚 quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer is the set of all valid variable assignments, including time. We describe an index structure that, for a temporal graph with 𝑁 edges, requires 𝑂 (𝑁 ) space and can evaluate extended BGPs in wco time 𝑂 (𝑄 ∗𝑚 log 𝑁 ), where 𝑄 ∗ represents the maximum number of solutions for query 𝑄 over any temporal graph with the same number of instants of edge validity. We use our index to adapt Leapfrog Triejoin to the temporal graph setting under any variable evaluation ordering. Our index further yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with low space overhead. PVLDB Reference Format: Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro, and Juan Reutter. Worst-Case Optimal BGPs on Temporal Graphs. PVLDB, 19(11): X-X, 2026. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, extended version and/or other artifacts have been made available at https://github.com/darroyue/bgps-temporal-graphs

1

INTRODUCTION

A significant advance for solving Basic Graph Patterns (BGPs) was the discovery of the AGM bound [9] and worst-case-optimal (wco) joins. A graph database, in the simplest RDF-like format, is a labeled 𝑝

graph, where the edges 𝑠 → 𝑜 are seen as a set of triples (𝑠, 𝑝, 𝑜) for subject, predicate, and object. A BGP is a set of triple patterns (𝑠, 𝑝, 𝑜), where each component can be a constant or a variable. Solving a BGP returns all assignments of values to variables so that the triple patterns, when instantiated to triples, appear in the graph. A wco algorithm takes time proportional to the size of the output of the query on some graph, such as Leapfrog TrieJoin (LTJ) [51], This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 11 ISSN 2150-8097. doi:XX.XX/XXX.XX

which binds—i.e., finds all the possible values of—one variable, and for each value assigned to it, recurses on the remaining variables. Herein we consider temporal graphs with quads (𝑠, 𝑝, 𝑜, [ti, tf)) 𝑝

denoting that the graph edge 𝑠 → 𝑜 was valid from time ti (inclusive) to time tf (exclusive). Temporal graphs give relations a temporal range of validity (e.g., when a researcher was affiliated with a university), or a temporal instant (e.g., when a conference took place), and support querying complex relations (i.e., subgraphs, paths) with temporal ranges and instants (e.g., which researchers were affiliated with a university when a given conference was held). Temporal graph querying arises naturally in real-world systems where relations evolve over time. Examples include event modeling [25], cybersecurity systems [39], and AI applications [13, 14]. We aim at solving BGPs on temporal graphs. The simplest form of such BGP queries is the return all time points query, which looks to find all answers for the BGP that were valid at some point in time, together with the time where each of these answers exists in the database. A folklore way to solve this problem is a so-called joinfirst strategy: we first compute the answers of the BGP disregarding the time information, and then, for each solution to the BGP, we use the time information of the concrete edges to determine the points in time this solution is valid, if any. An advantage of joinfirst is that one is free to solve the BGP with any wco strategy [44, 45, 51], beyond-wco ones [1, 3, 33] and even combinations of wco and non-wco algorithms [23, 41, 53, 54]. Alternatively, Hu et al. [30] introduce a so-called time-first strategy, which sweeps over the time component and recomputes the BGP answer each time an event changes the set of edges present in the graph. Though they show good theoretical results for restricted kinds of BGPs, in the general case the whole BGP answer is recomputed for every event. We argue that these solutions suffer from two main limitations. First, on the usability side, the return all time points query may lack expressiveness in several applications. For example, the latest SQL 2011 standard recognizes the importance of returning answers that mix temporal constraints (e.g., joining two triples on the condition that one precedes a certain timestamp and the other comes after it) [37]. Second, while join-first strategies can handle such queries, they generate all solutions without considering time and only then filter by time, which is inefficient if the time filters are selective. Regarding LTJ, in particular, both time- and join-first algorithms translate to fixing particular variable binding orderings, where it is well known that choosing a good variable binding ordering is crucial for efficient query resolution, even if all orderings are theoretically optimal [51]. Hence, systems processing temporal graph queries would benefit from an approach that can effectively integrate time constraints within the core of a wco (or beyond-wco!) algorithm.

Carl Bob

[10:46,11:25) [16:11,17:03)

[09:51,10:40)

(3) We can answer point-in-time or interval queries that return all answers valid in a given timestamp or time period with stronger guarantees: we do it in wco time with respect to the graph restricted to that point or interval rather than the complete graph. This provides a further speedup for point-in-time or interval queries, which are key primitives of the versioning functionalities of the SQL 2011 standard and several graph database proposals [20, 27, 42, 47]. (4) We provide a prototype implementation and show that our improvements translate to practice, solving realistic temporal queries within milliseconds while using reasonable index space. It also clearly outperforms both join-first and time-first strategies, as well as two prominent solutions from previous work [30, 57].

Emma

B12

[06:45,07:22)

B6 [18:45,18:56)

[10:32,11:05)

[18:30,19:10)

Anna

Dick

Figure 1: A toy temporal graph about trips on buses. For simplicity the timestamps show only hours during some day.

Example 1. As a motivating example, consider a graph describing the bus trips over a year in a big city, with quads (𝑎, trip, 𝑏, [ti, tf)) indicating that person 𝑎 was on bus 𝑏 during time interval [ti, tf). Figure 1 shows a toy example (all the edges are labeled trip). A query looking for pairs of people that were together in a specific bus “B12” could ask to return all time points for the BGP {(𝑥, trip, B12), (𝑦, trip, B12)}. A join-first strategy would find all the pairs of people (𝑥, 𝑦) that had ever traveled in that bus, and only then filter who did so at the same time. If 𝑚 people take that bus at some time, each taking it 𝑣 times during the year, join-first involves a time complexity of 𝑂 (𝑚 2 𝑣). A time-first approach would, instead, consider each of the 𝑡 time instants of the year (at a granularity of, say, minutes) and, for each of those, get the pairs of 𝑏 people on that bus at that time, for a total time complexity of 𝑂 (𝑡𝑏 2 ). A better strategy would be to take each of the 𝑚 persons 𝑥 that take that bus, for each of them the 𝑣 times they took it (this should be once or twice a day), and then find the other 𝑏 persons on that same bus at that time, for a total time complexity of 𝑂 (𝑚𝑣𝑏), which should be close to the size of the final output and thus optimal. It is further expected that 𝑏 ≪ 𝑚 and 𝑚𝑣 ≪ 𝑡 (since 𝑚𝑣 is the total number of times bus B12 was taken, a fraction of the universe). As an example of the first limitation mentioned above, the timefirst strategy would have trouble finding pairs of people that were together in the bus for over an hour, or people that took the bus B12 before noon and then the bus B6 in the afternoon (those are beyond a simple return all time points query). □

2

RELATED WORK

Temporal query languages have been extensively studied in relational and graph databases, leading to temporal extensions of SQL:2011 [37] and to proposals for RDF and graph query languages such as T-SPARQL [27], stSPARQL [35], and SPARQL-ST [48]. Systems such as GLENDA [47] and RDF archives [20, 26] further support querying historical graph snapshots and tracking data evolution over time. Our work is complementary, focusing on efficient query evaluation rather than models or languages. Despite advances in temporal languages and data models, the body of work in algorithms supporting these query extensions is much thinner. Berberich et al. focus on temporal extensions to document databases (see e.g. [4, 10]), but these algorithms cannot be directly applied for graph patterns. Work on temporal constructs or temporal algebras, for relations or graphs, can lead directly to algorithms [11, 21, 42], and there is also body of work on extending traditional relational indexes to support temporal constructs such as duration or range (see e.g. [15, 36]), but all of these are based on traditional techniques and not wco joins. Relatedly, Khamis et al. [2] study the complexity of Boolean conjunctive queries with intersection joins, which conceptually align with temporal constraints that intersect time domains. Their techniques can be adapted to temporal joins, typically incurring an additional logarithmic indexing factor, while our work targets general temporal graph patterns in linear space. Finally, Khurana and Deshpande [34] and Hou et al. [29] propose fully-functional systems with support for evolving databases by storing over-time differences. However, their query engines are designed to exploit other components of relational systems such as data partitioning or cache optimization (under the assumption that temporal queries in practice often focus on recent data), which cannot be directly applied to wco strategies. Recent work on algorithms for temporal graph query processing focuses on evaluation under specific data-time constraints, such as retrieving BGPs that occur at the same time within an interval [57], answers that exist for a long period of time [38, 46], for the longest period [49], or answers where edges respect time constraints, in the sense that every match for (𝑠, 𝑝, 𝑜) must satisfy that 𝑠 exists before 𝑜 [24, 31]. Yet, none of these algorithms can be applied directly in our case because they are designed for specific time constraints. In contrast, our work focuses on answering arbitrary temporal graph patterns, which is a more general problem: all of these specific time constraints can be expressed as temporal graph patterns, whose expressive power goes well beyond these constraints.

We introduce a linear-space temporal graph representation that overcomes both limitations. Our index structure stores temporal graphs in terms of intervals defined by their updates, using an improvement of versioned binary trees that avoids a space blowup by taking advantage of compressed representations. Using these structures, we obtain the following contributions. (1) Our structure enables retrieving all time points of any given BGP (via LTJ), allowing any possible variable binding order, with (at least) the same complexity guarantees that time-first or join-first algorithms offer. This already improves the current state of the art with respect to worst-case optimal joins over temporal graphs. (2) We show that we can answer much more general queries. More precisely, we introduce temporal BGPs (tBGPs), which are a temporal analog to BGPs, and show how our data structure can process any tBGP query. This language allows time-aware pattern matching, retreiving different time intervals for different parts of the query, and applying filters to restrict these intervals. 2

is the predecessor of 𝑡 in T𝐺 . Queries can then be translated into valid tBGPs: clauses 𝑤 1 ≤ 𝑤 2 stay valid after mapping values of T to their predecessors in T𝐺 . We also assume that those clauses are satisfiable, and do not form cycles (like 𝑤 1 ≤ 𝑤 2 ≤ 𝑤 1 , as those are expressed by collapsing the variables in the cycle into one).

Our work is closest to that of Hu et al. [30], addressing join-first and time-first strategies for wco joins over temporal graphs. In comparison, our approach handles any variable binding ordering, more general queries, and interval or point queries with better guarantees. Their algorithm sweeps over the time domain, which takes Θ(𝑇 ) time over 𝑇 time instants. This corresponds, in our work, to a time-first strategy. Though we support all variable binding plans (including time-first), since Hu et al. first sweep over time and then process the query in two independent steps, they can use more sophisticated algorithms for the (non-temporal) query part, such as EmptyHeaded [1], which uses the Generalized Hypertree Decomposition (GHD) of queries. Moreover, as they show in their paper, their idea of only obtaining the solutions where the disappearing edge participates yields better results on hierarchical queries. Finally, their paper also proposes a cross between time-first and join-first combined with GHD-based algorithms, which again may work better or worse, depending on the instance, than our query plans. We discuss in the Conclusions how our algorithms can be adapted to work under GHD-like time guarantees as well.

3

Example 2. In Figure 1, U𝐺 = {Anna, Bob, Carl, Dick, Emma, B6, B12, trip} and T𝐺 ={06:45, 07:22, 09:51, 10:32, 10:40, 10:46, 11:05, 11:25, 16:11, 17:03, 18:30, 19:45, 18:56, 19:10}. We cannot write a pattern (𝑥, trip, B12, 10:50) because 10:50 is not in T𝐺 , but the answer is the same as for (𝑥, trip, B12, 10:46), where 𝑥 can be Anna or Carl. Only at 11:05 the answer changes: Anna is no longer a solution. □ The semantics of tBGPs is given by assignments, called solutions: values given to the tBGP variables so that all tuples occur in 𝐺. Definition 3. A solution to a tBGP with variables Vu and Vt over a temporal graph 𝐺 is an assignment 𝑓 : Vu → U𝐺 and 𝑓 : Vt → T𝐺 . Furthermore, assuming 𝑓 (𝑐) = 𝑐 for 𝑐 ∈ U𝐺 ∪ T𝐺 , for each tuple pattern (𝑥, 𝑦, 𝑧, 𝑤) in the tBGP, there must exist a tuple (𝑓 (𝑥), 𝑓 (𝑦), 𝑓 (𝑧), [ti, tf )) ∈ 𝐺 where ti ≤ 𝑓 (𝑤) < tf. Finally, for each clause 𝑤 1 ≤ 𝑤 2 it must hold 𝑓 (𝑤 1 ) ≤ 𝑓 (𝑤 2 ).

MODEL Note that the time component of our solutions must also belong to T𝐺 . This is a form of compacting the (possibly infinite) set of all the solutions in T : a solution with time 𝑡 ∈ T𝐺 stays valid for all the times 𝑡 ′′ ∈ T such that 𝑡 ≤ 𝑡 ′′ < 𝑡 ′ , where 𝑡 ′ follows 𝑡 in T𝐺 .

Here we describe temporal graphs, queries, and their AGM bound.

3.1

Temporal graphs and queries

As is usual in the literature, we regard a temporal graph 𝐺 as a set

Example 3. A tBGP for the first query of Example 1 is 𝑄 = {(𝑥, trip, B12, 𝑡), (𝑦, trip, B12, 𝑡)}, with Vu = {𝑥, 𝑦} and Vt = {𝑡 }. Two solutions are ⟨𝑓 (𝑥) = Anna, 𝑓 (𝑦) = Bob, 𝑓 (𝑡) = 10:32⟩ and ⟨𝑓 (𝑥) = Anna, 𝑓 (𝑦) = Carl, 𝑓 (𝑡) = 10:46⟩. The first is valid until 10:40 and the second until 11:05 (not inclusive). A tBGP for the last query is 𝑄 = {(𝑥, trip, B12, 𝑡 1 ), (𝑥, trip, B6, 𝑡 2 ), 𝑡 1 ≤ 12:00, 12:00 ≤ 𝑡 2 }. A solution is ⟨𝑓 (𝑥) = Anna, 𝑓 (𝑡 1 ) = 10:12, 𝑓 (𝑡 2 ) = 18:30⟩. □

𝑝

of labeled edges 𝑠 → 𝑜, or triples (𝑠, 𝑝, 𝑜), that exist during a given time interval [ti, tf ) (see, e.g., [27, 48]). Definition 1. Let U be any set of values and (T , ≤) a totally ordered time domain, disjoint from U. A temporal graph 𝐺 is a set of 𝑁 := |𝐺 | tuples (𝑠, 𝑝, 𝑜, [ti, tf )), where 𝑠, 𝑝, 𝑜 are elements from U, and ti, tf are elements from T , with ti < tf, so that [ti, tf ) represents an interval in the time domain. We also define, respectively U𝐺 := {𝑠, 𝑝, 𝑜 | ∃ti, tf, (𝑠, 𝑝, 𝑜, [ti, tf )) ∈ 𝐺 } and T𝐺 := {ti, tf | ∃𝑠, 𝑝, 𝑜, (𝑠, 𝑝, 𝑜, [ti, tf )) ∈ 𝐺 } as the set of elements and time instants mentioned in tuples of 𝐺.

Definition 4. Given a temporal graph 𝐺, the problem of solving a tBGP 𝑄 is that of computing the set 𝑄 (𝐺) of all the solutions to 𝑄. The selection of tBGPs as our language is justified as the key primitive of temporal relational calculus [19], the algebraic building block of most temporal database languages (see e.g. [27, 48, 50]). Hence, tBPGs are a fundamental querying functionality of temporal database languages per BGPs for (non-temporal) graph query languages. We compare tBGPs to other query languages in Section 3.4.

A tuple (𝑠, 𝑝, 𝑜, [ti, tf )) represents that the triple (𝑠, 𝑝, 𝑜) is valid in any time 𝑡 such that ti ≤ 𝑡 < tf. We assume that temporal graphs do not have redundant tuples: if 𝐺 has tuples (𝑠, 𝑝, 𝑜, [ti, tf )) and (𝑠, 𝑝, 𝑜, [ti ′, tf ′ )), then [ti, tf) and [ti ′, tf ′ ) must be disjoint. This enforces a unique way to represent temporal graphs. Furthermore, since U ∩ T = ∅, node identifiers and labels cannot be time instants. We focus on graph patterns, which are the foundation of most query languages used in industry, like SPARQL, CYPHER and GQL [5, 22]. Graph patterns are sets of tuples with constants and variables, which must be found in 𝐺. To support temporal operations, we add temporal variables to patterns, and temporal filters.

3.2

Temporal worst-case optimal algorithms

The AGM bound refers to cardinalities of relations. To extend the concept to temporal graphs, we use the following notion. Definition 5. The point-based representation of 𝐺 is 𝐺ˆ = {(𝑠, 𝑝, 𝑜, 𝑡) | ∃ti, tf, (𝑠, 𝑝, 𝑜, [ti, tf )) ∈ 𝐺, 𝑡 ∈ [ti, tf ) ∩ T𝐺 }. The times 𝑡 present in 𝐺ˆ are only those constants ti, tf ∈ T that appear as interval extremes in 𝐺 (possibly on another triple); see Figure 2. As explained, we need not consider other times in the domain where 𝐺 does not change. As a result, we have the bound |𝐺ˆ | ≤ |𝐺 | · |T𝐺 | ∈ 𝑂 (𝑁 2 ), which is tight when the edges are valid for long time intervals and many different time instants exist in 𝐺. We define the AGM bound of query 𝑄 over temporal graph 𝐺 as the maximum number of solutions of 𝑄 over any temporal graph ˆ 𝐺 ′ whose point-wise representation has as many tuples as 𝐺.

Definition 2. Let Vu , Vt be two disjoint sets of variable symbols, additionally disjoint from U and T . A temporal basic graph pattern (tBGP) is a set of tuple patterns (𝑥, 𝑦, 𝑧, 𝑤), where each 𝑥, 𝑦, and 𝑧 are in U𝐺 ∪ Vu , and 𝑤 is in T𝐺 ∪ Vt , plus optional comparison clauses of the form 𝑤 1 ≤ 𝑤 2 , where 𝑤 1, 𝑤 2 ∈ T𝐺 ∪ Vt . We note, in particular, that tBGPs can only mention time instants that exist in T𝐺 . This is not really a restriction since the edges of 𝐺 at a time 𝑡 ∈ T are exactly the same as those at time 𝑡 ′ , where 𝑡 ′ 3

Carl Bob

A point-in-time query amounts to solving classic BGP pattern matching on graph 𝐺𝑡 , and a point-in-interval query requires matching BGPs on 𝐺𝑡𝑡12 , with 𝑡, 𝑡 1, 𝑡 2 given at query time. Our data structure can evaluate these queries in wco time with respect to the sizes of 𝐺𝑡 or 𝐺𝑡𝑡12 , i.e., the best one can hope for: the algorithm is wco on the labeled graph that has exactly the triples we need to consider. This improves the time of Theorem 4 since all such graphs are smaller ˆ Concretely, we show the following in Section 7. than 𝐺.

Emma

10:46 11:05

09:51

16:11

06:45

10:32

B12

18:30 10:46

10:32

B6 18:45

18:45

10:40

18:56

Anna

Dick

Theorem 6. Let 𝐺 be a temporal graph with 𝑁 tuples. Then, there is a data structure using 𝑂 (𝑁 ) space that allows the following: • Answer BGPs 𝑄 with 𝑚 tuples on the labeled graph 𝐺𝑡 for any time instant 𝑡 given with 𝑄, in 𝑂 (𝑄𝑡∗ 𝑚 log 𝑁 ) time, where 𝑄𝑡∗ is the maximum number of solutions for 𝑄 in some labeled graph with at most |𝐺𝑡 | triples, and • Answer BGPs 𝑄 with 𝑚 tuples on the labeled graph 𝐺𝑡𝑡12 for any time interval [𝑡 1, 𝑡 2 ) given with 𝑄, in 𝑂 (𝑄𝑡𝑡12 ∗ 𝑚 log 𝑁 ) time, where 𝑄𝑡𝑡12 ∗ is the maximum number of solutions for 𝑄 in some labeled graph with at most |𝐺𝑡𝑡12 | triples.

Figure 2: Point-based representation of the graph of Figure 1.

Definition 6. The AGM bound 𝑄 ∗ of a tBGP 𝑄 for a temporal graph 𝐺 is 𝑄 ∗ := max{|𝑄 (𝐺 ′ )|, |𝐺ˆ′ |≤|𝐺ˆ |}, over temporal graphs 𝐺 ′ . An algorithm computing 𝑄 (𝐺) is worst-case optimal (wco) if it takes time 𝑂 (𝑄 ∗ ), possibly with data-agnostic and polylog factors of |𝐺 |. The following theorem then states our main result. Theorem 4. Let 𝐺 be a temporal graph with 𝑁 tuples. Then, there exists a data structure using 𝑂 (𝑁 ) space that can compute 𝑄 (𝐺) for every tBGP 𝑄 with 𝑚 tuples in wco time, 𝑂 (𝑄 ∗𝑚 log 𝑁 ).

In Section 7 we also show that our data structure leads to instanceoptimal algorithms when matching a single triple pattern, and can also be used to list all time intervals where these matches existed. Next are duration queries, with two flavors. First, we can specifically input a BGP and time points 𝑡 1, 𝑡 2 at query time, and require all tuples that existed during the whole interval, or, in other words, to query graph 𝐺 [𝑡1 ,𝑡2 ) . We can also input a duration 𝛿 instead of the interval, in which case we want to look for answers that are valid for at least 𝛿 time. We show the following in Section 7.2.

The wco algorithm in Theorem 4 can be easily obtained by runˆ interpreting the tuples of the ning a wco algorithm directly on 𝐺, tBGP 𝑄 as quad-patterns (let us disregard the time clauses for simplicity in this discussion). The disadvantage is, of course, that 𝐺ˆ is a bloated representation of 𝐺, which can require quadratic space. We could, alternatively, build 𝐺ˆ from 𝐺 and index it on the fly at query time, but this translates the 𝑂 (𝑁 2 ) factor to the query time and working space. This is unacceptable in most practical cases. Our representation of Theorem 4 actually simulates the use of ˆ but uses 𝐺 in native form within 𝑂 (𝑁 ) the LTJ algorithm [51] on 𝐺, ˆ Our algorithm is not only wco, space, without converting it to 𝐺. but can also simulate LTJ with any desired variable elimination ˆ Choosing specific VEOs is key order (VEO), exactly as if run on 𝐺. for practical performance even if all VEOs are wco in theory [51].

3.3

Theorem 7. Let 𝐺 be a temporal graph with 𝑁 tuples. Then, there is a data structure using 𝑂 (𝑁 ) space that allows the following: • Solve BGPs 𝑄 with 𝑚 triples on the labeled graph 𝐺 [𝑡1 ,𝑡2 ) for any time interval [𝑡 1, 𝑡 2 ) given with 𝑄, in 𝑂 (𝑄 ∗[𝑡1 ,𝑡2 ) 𝑚 log 𝑁 ) time, where 𝑄 ∗[𝑡1 ,𝑡2 ) = min𝑡1 ≤𝑡 <𝑡2 𝑄𝑡∗ . • Solve BGPs 𝑄 with 𝑚 triples, reporting all the time intervals of length at least 𝛿 where 𝑄 holds in 𝐺 for any duration 𝛿 given with 𝑄, in time 𝑂 (𝑄𝛿∗ 𝑚 log 𝑁 ), where 𝑄𝛿∗ is the maximum number of solutions for this query in the subgraph of 𝐺 formed by all tuples with duration 𝛿 or more.

Point & interval queries: better guarantees

We obtain even stronger bounds for point-in-time and point-ininterval queries, which ask for all answers of a BGP valid at a given time point 𝑡 or at some point in the interval [ti, tf ). We can also query for answers valid along a whole time interval. To state these results, we define some (non-temporal) labeled graphs, derived from slicing a temporal graph across the time domain. We use |𝐺 | to denote the number of triples in a non-temporal graph.

3.4

On the choice of temporal BGPs

Temporal BGPs play a role for temporal graphs analogous to conjunctive queries (CQs) for relational data: they form the patternmatching core underlying richer temporal query languages [19]. The study of tBPGs is further justified by the fact that algorithms for standard conjunctive query evaluation cannot be directly translated to the temporal setting, because the language of tBGPs can be more expressive than CQs over a standard relational encoding of temporal graphs (see Appendix A in the extended version). The appendix also shows that, if 𝐺 is expanded into its point-based ˆ then every tBGP corresponds to a CQ with inrepresentation 𝐺, ˆ This further justifies tBGPs as the CQ equalities evaluated over 𝐺. ˆ for a graph 𝐺 with 𝑁 analog in our setting. Since the size of 𝐺, tuples, can be of order 𝑁 · |T𝐺 |, materializing 𝐺ˆ to process tBGPs as relational CQs is infeasible. Notice that our index structures can correctly evaluate tBGPs over 𝐺ˆ using only 𝑂 (𝑁 ) space.

Definition 7. For any 𝑡 ∈ T𝐺 , 𝐺𝑡 is the set of triples (𝑠, 𝑝, 𝑜) such that there exists a tuple (𝑠, 𝑝, 𝑜, [ti, tf )) in 𝐺 with ti ≤ 𝑡 < tf. For any 𝑡 1 < 𝑡 2 in T𝐺 , 𝐺 [𝑡1 ,𝑡2 ) is the set of triples (𝑠, 𝑝, 𝑜) such that there exists a tuple (𝑠, 𝑝, 𝑜) in 𝐺𝑡 for every 𝑡 ∈ T𝐺 with 𝑡 1 ≤ 𝑡 < 𝑡 2 , and 𝐺𝑡𝑡12 is the set of triples (𝑠, 𝑝, 𝑜) such that there exists a tuple (𝑠, 𝑝, 𝑜) in 𝐺𝑡 for some 𝑡 ∈ T𝐺 with 𝑡 1 ≤ 𝑡 < 𝑡 2 . Example 5. Let 𝐺 be the graph of Figure 1. Then 𝐺 10:32 contains the edges (Anna, trip, B12) and (Bob, trip, B12), 𝐺 [10:32,10:46) con10:46 contains the edges tains only the edge (Anna, trip, B12), and 𝐺 10:32 (Anna, trip, B12), (Bob, trip, B12), and (Carl, trip, B12). □ 4

𝜏𝑖 must be the trie of the order pos shown in Figure 3 (this is why LTJ needs the tries in various orders). Its first level corresponds to p = trip, the second to o = 𝑧, and the third to s = 𝑥. □

trip B6

Anna

Dick

Emma

B12

Anna

Bob

The first step of LTJ is to descend, from the root of each trie 𝜏𝑖 , by the constants of 𝑡𝑖 . It then starts the variable elimination step. Say that the chosen VEO is 𝑥 1, . . . , 𝑥 𝑣 . LTJ then finds each value 𝑐 that appears as a child of the current node in every trie 𝜏𝑖 whose next level corresponds to variable 𝑥 1 . For each such 𝑐, LTJ binds 𝑥 1 := 𝑐, descends by 𝑐 in all the corresponding tries 𝜏𝑖 , and goes on recursively with 𝑥 2 . Once we have bound all variables in this way, the set of bindings for 𝑥 1, . . . , 𝑥 𝑣 is a new solution for 𝑄. The values 𝑐 are found by intersecting the children of the current nodes 𝑣𝑖 in all the suitable tries 𝜏𝑖 ; see Algorithm 1 in Appendix B of the extended version. LTJ cycles over all the involved tries looking for the smallest 𝑥 ′ ≥ 𝑥, where 𝑥 is its next candidate, within the children of the current node 𝑣𝑖 in each trie 𝜏𝑖 . When all tries find the same 𝑥, this is the next output of the intersection. The key primitive used, leap(𝑣𝑖 , 𝑥), finds that smallest 𝑥 ′ ≥ 𝑥 within the children of 𝑣𝑖 . If leap is executed in 𝑂 (log 𝑁 ) time (e.g., using binary search) then LTJ obtains the wco time complexity 𝑂 (𝑄 ∗𝑚 log 𝑁 ).

Carl

Figure 3: The LTJ trie of order pos for the graph of Figure 1 devoided of temporal annotations.

4

OVERVIEW OF OUR SOLUTION

Our solution is to build a data structure for temporal graphs in which we can run the Leapfrog TrieJoin algorithm with any variable ordering to compute joins in wco time, and where the total space is linear with respect to the number of tuples of the temporal graph. For a temporal graph 𝐺, we replace the ti and tf components in 𝐺 by their rank in T𝐺 , turning them into integers in [0,𝑇 ) where 𝑇 = |T𝐺 | (we also maintain a dictionary to enable switching between actual time constants and integers in [0,𝑇 )). We further map the set of node identifiers and labels to the integer interval [0, 𝑈 ), where 𝑈 = |U𝐺 |. We handle those numeric identifiers using binary tries. We now define the Leapfrog TrieJoin algorithm and (versioned) binary tries: the two building blocks of our solution. In Section 5, we construct a data structure from these two building blocks that achieves the desired wco optimality, but with 𝑂 (𝑁 log 𝑁 ) space. Section 6 explains how to further reduce this to a structure using linear space, and how to use this structure for querying.

4.1

4.2

Binary Tries

Assume that we aim to represent each 𝐺𝑡 as a labeled graph, for the consecutive values 𝑡 ∈ [0,𝑇 ). We now describe a technique inspired by versioned data structures, beginning with binary tries. A binary trie (BT) is a binary tree that represents a set of binary strings, each string being a root-to-leaf path in the trie. If the sequence of left-right turns from to root to the leaf are interpreted as 0 and 1, respectively, we obtain the string represented by the leaf. We assume no binary string is a prefix of another. We use BTs to encode the sets of children of nodes of the LTJ tries. Those children are numbers in [0, 𝑈 ) interpreted as binary strings of length ℓ = ⌈log2 𝑈 ⌉, reading from most to least significant digit. Figure 4 (left) illustrates the BT for a toy LTJ trie node. BTs can simulate the search for the first child of 𝑣 with value ≥ 𝑥 in 𝑂 (ℓ) = 𝑂 (log 𝑁 ) time, as follows. We start at the BT root, with height ℎ := ℓ. If the ℎ-th highest bit of 𝑥 (an ℓ-bit number) is 1, we continue recursively by the right child of the BT, decrementing ℎ. Otherwise, we proceed as follows. First, we try to find the answer on the left branch, also decrementing ℎ. If that search returns an answer, we return it too. If not, we return the leftmost leaf of the right child of the node. When we arrive at a leaf, its string represents the first value ≥ 𝑥 in the trie. This takes 𝑂 (ℓ) time because it can descend by both children of a node only once in the whole process. For pseudocode see the extended version (Algorithm 2 in Appendix B). BTs then support the LTJ leap operation within the same 𝑂 (log 𝑁 ) time factor penalty of binary searches. As a consequence, we can use a BT as a local structure to represent the set of children of every LTJ trie node (instead of just a plain array of increasing identifiers), and retain the same wco time 𝑂 (𝑄 ∗ log 𝑁 ) on labeled graphs.

Leapfrog Triejoin

We describe the Leapfrog Triejoin (LTJ) algorithm [51], in the version that is adapted for solving BGPs on labeled graphs [28]. LTJ requires that the triples (𝑠, 𝑝, 𝑜) are represented as tries, which we will call LTJ tries, in the 6 possible orders of the components s, p, and o. Tries are labeled trees where no two children of a node have the same label, and represent all the strings that can be read by concatenating the labels of their root-to-leaf paths. Each LTJ trie stores the components s,p,o in some order, as strings of length 3. We call these orders spo, sop, pos, pso, osp, and ops. For example, the trie for the order pos has one root-to-leaf path with consecutive labels 𝑝, 𝑜, 𝑠 for each triple (𝑠, 𝑝, 𝑜) in the graph (see Figure 3). Each LTJ trie has height 3 and exactly 𝑁 leaves. Let 𝑄 = {𝑡 1, . . . , 𝑡𝑚 } be a BGP (i.e., a set of triple patterns) and {𝑥 1, . . . , 𝑥 𝑣 } its set of variables. LTJ carries out 𝑣 iterations, “eliminating” one variable at a time. The order LTJ chooses to eliminate the variables is known as the variable elimination order (VEO). Each triple pattern 𝑡𝑖 is associated with one of six tries, say 𝜏𝑖 . A level ℓ of 𝜏𝑖 corresponds to a constant 𝑐 (or variable 𝑥) if 𝑡𝑖 contains 𝑐 (or 𝑥) at the position corresponding to level ℓ in 𝜏𝑖 . To be a valid trie for 𝑡𝑖 , the first levels of 𝜏𝑖 (i.e., levels closest to the root) must correspond to constants of 𝑡𝑖 , and the subsequent levels must correspond to the variables of 𝑡𝑖 , consistently with the VEO.

4.3

Versioned Binary Tries

We aim to represent all the graphs 𝐺𝑡 with the same tries. When representing 𝐺𝑡 , we will have LTJ trie nodes 𝑣 that will be very similar to the node 𝑣 for 𝐺𝑡 −1 : the node 𝑣 in 𝐺𝑡 may have a few inserted or deleted children with respect to the node 𝑣 in 𝐺𝑡 −1 . To

Example 8. For illustration, consider the graph of Figure 1 devoid of temporal annotations (and thus with only one edge from Carl to B12). If 𝑡𝑖 = (𝑥, trip, 𝑧) and the VEO eliminates 𝑧 and then 𝑥, then 5

v 2

3

6

v2

v1

2

v3

v1

3

v 0

0

2

v3

1

1

0

0

0

v3

4

6

v3

v4

v1

v

0

1

v2

6

v4 v

1

1

v1

4

v2

particular, consider a tBGP where the time component is a single constant 𝑡 for all the triple patterns. Then, using an LTJ trie with an order that starts with 𝑡, we descend by the child 𝑡 of the root and can solve the tBGP in time 𝑂 (𝑄𝑡∗ log 𝑁 ), where 𝑄𝑡∗ is the AGM bound for the corresponding BGP on the graph 𝐺𝑡 . As another example, consider the same tBGP where now 𝑡 is a variable. By solving it on an LTJ trie that starts with the 𝑡 component, we can mimic the so-called “time-first” approach in previous work [30]; by using a trie that ends with the 𝑡 component, we mimic the so-called “join-first” strategy. We can use more general strategies, however, by putting the time component elsewhere in the order. In this scenario, the clauses 𝑤 1 ≤ 𝑤 2 are handled as follows. If 𝑤 1 is bound before 𝑤 2 , then it will have assigned a value 𝑓 (𝑤 1 ) = 𝑡 1 each time 𝑤 2 is bound. At this moment we restrict the LTJ intersections for 𝑤 2 so that the values stay within [𝑡 1,𝑇 ). If, instead, 𝑤 2 is bound to 𝑓 (𝑤 2 ) = 𝑡 2 before 𝑤 1 , we enforce that the values of 𝑤 1 be within [0, 𝑡 2 ]. This is still wco, as it is equivalent to materializing a table with all the pairs (𝑤 1, 𝑤 2 ) with 𝑤 1 ≤ 𝑤 2 and including it in the LTJ algorithm. Since all the time instants appear in both columns, LTJ will not restrict the first bound variable; the second one will be restricted exactly as described. To do all this within 𝑂 (𝑁 log 𝑁 ) space, we introduce a special representation for the LTJ tries. Their abstract form will still be a trie of height 4, with one level per tuple component. The difference is in the way we represent the children of the nodes. Given a particular permutation, say (𝑠, 𝑡, 𝑝, 𝑜), we distinguish the levels before the time component (in our example, the first level, 𝑠), the time level, and the levels after the time component (levels 3 and 4, 𝑝 and 𝑜, in our example). Note that which levels are before and after the time level depends on the permutation we are storing. The levels before the time level can be implemented in traditional form, e.g., as an array of increasing child values. We now describe our implementation of the time level and its subsequent levels.

v

v

0

1

1

1

0

v4

Figure 4: At the top, three consecutive versions of an LTJ trie node 𝑣. The leftmost one has three children: values 2, 3, and 6. It is represented (below) with a BT using ℓ = 3 bits, which stores the binary strings 2 = 0102 , 3 = 0112 , and 6 = 1102 . The root of the BT is 𝑣 and its leaves are the corresponding children of 𝑣 in the LTJ trie. The center and right trie are successive versions of the leftmost one: the value 4 appears in the second version, whereas 3 disappears in the third. Both are represented (below) as VBTs: the pointers to preceding versions are shown with dashed lines; note in particular the pointer from the third to the first version.

efficiently represent the children of those LTJ trie nodes 𝑣, we use versioned binary tries (VBTs). A VBT represents a BT as a set of updates with respect to a reference BT. Instead of explicitly storing all the nodes of the BT it represents, the VBT records only the rootto-leaf paths that change with respect to the reference BT. Changes refer to newly inserted or deleted binary strings. The BT subtrees that do not change, instead of being duplicated, are pointed to from the corresponding nodes in the newly created paths to the reference BT. Figure 4 illustrates successive versions of the leftmost subtrie. Note that a top-down traversal on a VBT is identical to that on a standard BT, so we can run the LTJ intersections on the VBTs as well, in 𝑂 (log 𝑁 ) time per leap. Note how, in Figure 4, we can traverse the VBT of the third version exactly as if it were a BT. We use VBTs to represent a sequence of versions of a node’s children. The first version in time is represented as a standard BT. Each new version is a VBT encoded with respect to the preceding BT. From the third VBT onwards, the preceding BT is also represented as a VBT, so pointing to a subtree of the preceding BT may actually correspond to pointing to an earlier BT pointed to by the preceding VBT. This is shown on the third version in Figure 4. Since the paths are of length 𝑂 (log 𝑁 ), it follows that VBTs require 𝑂 (log 𝑁 ) space per update they record with respect to a previous BT. VBTs will be part of our solution, as described next.

5

5.1

The time level

The time level will be represented in a form closer to the tuples of 𝐺 (with the times already converted to integers in [0,𝑇 )) than ˆ This level will be an ordered sequence of to the set of quads of 𝐺. disjoint time intervals, stored in classical form (e.g., an array). Let 𝑣 be an LTJ trie node whose children belong to the time level, and [ti1, tf 1 ), [ti2, tf 2 ), . . . be the time intervals of all the tuples stored in the LTJ subtrie of 𝑣 (this is a subset of all the time intervals in 𝐺 and they can overlap). Then consider the list ⟨𝑡 1, 𝑡 2, . . .⟩ containing all the values ti𝑘 and tf𝑘 , sorted in increasing order and with equal values removed. The intervals forming the children of 𝑣 are then in principle [𝑡 1, 𝑡 2 ), [𝑡 2, 𝑡 3 ), . . ., which covers the whole universe [0,𝑇 ). We remove, however, intervals with no descending tuples. The surviving intervals are then of the form [ts1, te1 ), [ts2, te2 ), . . ., where each [ts𝑖 , te𝑖 ) is equal to some [𝑡𝑘 , 𝑡𝑘+1 ).

OUR REPRESENTATION

In abstract terms, we regard each tuple (𝑠, 𝑝, 𝑜, [ti, tf )) of 𝐺 as if it were tf − ti standard quads (𝑠, 𝑝, 𝑜, 𝑡), one per integer 𝑡 ∈ [ti, tf ); ˆ which as explained recall that we have mapped T to [0,𝑇 ). This is 𝐺, may have Θ(𝑁 2 ) quads, but we will manage to represent them all within 𝑂 (𝑁 log 𝑁 ) space (later, we will reduce the space to 𝑂 (𝑁 )). With the quads model, the tBGPs can be solved directly by using the LTJ algorithm on the LTJ tries storing the 4! permutations of {𝑠, 𝑝, 𝑜, 𝑡 }. The algorithm is then wco with respect to this model. In

Example 9. Consider the otps trie for Figure 1. The intervals [ti𝑖 , tf𝑖 ) for the node B12 are {[9:51,10:40),[10:32,11:05),[10:46,11:25), [16:11,17:03)}. The corresponding sorted list of times 𝑡𝑖 is then ⟨9:51,10:32,10:40,10:46,11:05,11:25,16:11,17:03⟩. A consecutive pair forms an interval [ts𝑖 , te𝑖 ), except for [11:25, 16:11), in which there are no tuples. Figure 5 illustrates the different levels in this trie. □ 6

B6

Before time level

Time level

[06:45,07:22)

[18:30,18:45)

trip

After time level

Emma

[18:45,18:56)

trip

Anna

trip

Anna

Dick

B12

[18:56,19:10)

[09:51,10:32)

trip

trip

Anna

Bob

[10:32,10:40)

[10:40,10:46)

trip

Anna

Bob

[10:46,11:05)

trip

Anna

trip

Anna

Carl

[11:05,11:25)

[16:11,17:03)

trip

trip

Carl

Carl

Figure 5: The otps trie corresponding to the graph of Figure 1.

5.2

We create new paths in the VBT of [ts2, te2 ) as described in Section 4.2, to account for those events. Each event requires creating 𝑂 (log 𝑁 ) nodes in the BTs or the VBTs. Note that each graph tuple (𝑠, 𝑝, 𝑜, [ti, tf )) generates two events: the insertion of (𝑠, 𝑝, 𝑜) at ti and its deletion at tf. Therefore, the trie represents at most 2𝑁 events, each of which induces 𝑂 (log 𝑁 ) new nodes in the VBTs. The total space is thus 𝑂 (𝑁 log 𝑁 ).

Levels after the time component

We will use BTs and VBTs to represent the children of all LTJ trie nodes below the time level. Consider an LTJ trie node 𝑣 whose children, at the time level, are [ts1, te1 ), [ts2, te2 ), . . . We will concatenate all the binary strings corresponding to all the levels that follow the time level. In the otps trie of Figure 5, the descendants of each node [ts𝑖 , te𝑖 ) will be arranged in a single BT (or VBT) holding binary strings of length 2ℓ, formed by concatenating the 𝑝 and the 𝑠 values (i.e., 𝑝 : 𝑠 := 2ℓ 𝑝 + 𝑠) of all the tuples that must be stored below 𝑣 and exist at time ts𝑖 . Per our construction, this set of tuples does not vary within the time interval [ts𝑖 , te𝑖 ). Figure 6 shows hypothetical values 𝑝 : 𝑠 descending from some node 𝑣. Note that concatenating the components is almost immaterial with respect to using different BTs for the children of every LTJ trie node. The BT node representing each prefix 𝑝 (at depth ℓ) becomes the root of the subtrie representing each component 𝑠 of the concatenations 𝑝 : 𝑠. We can then interpret the node of 𝑝 as the LTJ trie node obtained by descending by 𝑝 from 𝑣, and the subtrie with the 𝑠 components as the BT of its children. Our arrangement, however, is more convenient for the versioning we require next. Let us consider how we store the elements formed by concatenating the remaining attributes of the tuples below 𝑣. We first build the basic BT for the node [ts1, te1 ), containing all the elements whose tuples exist in time ts1 . This set of tuples does not vary until time te1 . This BT is the child of the node [ts1, te1 ) of the time level. Now consider the next interval, [ts2, te2 ). If ts2 > te1 + 1, then the intervals spanning [te1, ts2 ) were empty, and we simply build a new BT for [ts2, te2 ) containing only the new elements that appear at time ts2 . Otherwise, there exists a nonempty BT that precedes the BT for [ts2, te2 ), so we represent this BT as a VBT, whose reference is the BT for [ts1, te1 ). This VBT must represent two events:

Example 11. In the trie otps of Example 9, the tuple (Anna, trip, B12, [10:32,11:05)) will generate, below the node B12, a time ti = 10:32 where we will insert trip:Anna, and a time tf = 11:05 where we will delete trip:Anna. Because we use VBTs for intermediate intervals (in this case, for the intervals [10:40,10:46) and [10:46,11:05)), trip:Anna will not be explicitly represented in those. □

5.3

The intersections

(1) Consider a tuple (𝑠, 𝑝, 𝑜, [ti, tf )) of 𝐺 where (𝑠, 𝑝, 𝑜) must be inserted below the LTJ trie node 𝑣 and such that ti = ts2 . This tuple must be added to the VBT. (2) Similarly, each tuple (𝑠, 𝑝, 𝑜, [ti, tf )) belonging to the subtrie of 𝑣 and such that tf = ts2 must be removed from the VBT.

Intersections work exactly as in LTJ over BTs, except at the time level. At this level, each node represents an interval, which must be handled during intersection: each interval [ts𝑖 , te𝑖 ) stands for all the time instants ts𝑖 ≤ 𝑡 < te𝑖 . We modify the list intersection algorithm of LTJ so as to assume that all those time instants 𝑡 are explicitly represented and that copies of the BT of [ts𝑖 , te𝑖 ) descend from all those implicit time instants 𝑡. To find the first time 𝑡 ∗ ≥ 𝑡 0 , we look for 𝑡 0 and, (1) if we find some ts𝑖 ≤ 𝑡 0 < te𝑖 , we answer 𝑡 ∗ := 𝑡 0 ; (2) if we find some te𝑖 ≤ 𝑡 0 < ts𝑖+1 , we answer 𝑡 ∗ := ts𝑖+1 . We can avoid recomputing the same answers for all the time instants 𝑡 of an interval: Rather than returning each time instant, we return the range [𝑡 0, te𝑖 ) in case (1) above, and [ts𝑖+1, te𝑖+1 ) in case (2). We then modify the intersection algorithm to record the maximum interval starting at 𝑡 ∗ that is included in all the intersected lists. The instantiation of the corresponding time variable is then a whole interval where the instantiated BGP will not change. See pseudocode in the extended version (Algorithm 3 in Appendix B). Thus we can return solutions to BGPs with ranges of values for the time-bound variables. This is a form of compacting the output, but we cannot ensure we return it in the optimally compacted form.

Example 10. In Figure 5, below node B6, the interval [07:22,18:30)] disappears as it contains no tuples, and thus we start a new BT with root [18:30,18:45) containing Anna. The next interval, [18:45,18:56), modifies the previous one by adding Dick, represented as a VBT with respect to the previous one. The last interval, [18:56,19:10), removes Dick again, and is again represented by a VBT. □

The base version we have described implements leap in 𝑂 (log 𝑁 ) time and 𝑂 (𝑁 log 𝑁 ) space. This space is worrisome for large graphs. We now describe a more sophisticated storage mechanism that achieves linear space with no penalty in time complexity.

6

7

LINEAR SPACE

v

v

v

0

2

3

v2

5

4

0

1

6 0

v1

1

v3

v1

1 1

0

v2

1

v3

1

1

1

1 0

1 1

0

v3 1

5

4

6

0

0

u2

u3

u4

u5

1

0

7 1

u1

0

u6

0

u1

1

u2

0

u3

u4

0

u5

1

1

u6

u7

Figure 6: On the left, the two final levels of an LTJ trie node rooted at 𝑣. In the middle, the BT representation of the corresponding children. Note that we can also regard all the BTs as a single BT on the concatenation of the path labels, 2 : 5, 3 : 4, 3 : 5, 6 : 4, 6 : 6, and 6 : 7. On the right, a VBT representing two edits: the removal of 2 : 5 and the insertion of 6 : 1.

6.1

must hold Ω(log 𝑁 ) bits if it can address Θ(𝑁 ) tuples in constant time; therefore this number of bits amounts to 𝑂 (𝐿) words of space. Since the sum of the lengths 𝐿 of all the nodes below the time level amounts to the 2𝑁 updates in the graph, those 𝑂 (𝐿) words amount to 𝑂 (𝑁 ) over the whole LTJ trie. We still have 𝑂 (𝐿 log 𝑁 ) space to store the topology of 𝑉 , however, as it stores 𝐿 paths of length 𝑏ℓ = 𝑂 (log 𝑁 ). We avoid the need to store those pointers by concatenating all the bitvectors 𝑣.𝐵 (and, similarly, 𝑣.𝐸) levelwise, left to right. Note that the total length of the bitvectors 𝑣.𝐵 or 𝑣.𝐸 in a given level is always 𝐿, so we have 𝑏ℓ bitvectors 𝐵𝑑 [1, 𝐿], for 𝑑 ∈ [0, 𝑏ℓ − 1] that can be stored as a large concatenated bitvector of length 𝐿𝑏ℓ (similarly, 𝐸𝑑 for 𝑑 ∈ [0, 𝑏ℓ], where the level 𝑑 = 𝑏ℓ can be made implicit, as explained). Those bitvectors are shown at the bottom-right of Figure 7.

Data Structure

Consider the sequence of updates that occur in the time-level children [ts1, te1 ), [ts2, te2 ), . . . of a particular LTJ trie node. Instead of creating a sequence of VBTs 𝑣 1, 𝑣 2, . . ., we create a single BT 𝑉 where we insert all the paths corresponding to those updates; each VBT (or BT) 𝑣𝑙 corresponds to a sequence of insertions/deletions of tuples (just insertions in case of BTs). If there are 𝑏 levels after the time level, for 1 ≤ 𝑏 ≤ 3, each such path is of length 𝑏ℓ. Updates consisting of insertions correspond to a path of length 𝑏ℓ. Updates consisting of deletions are also paths of length 𝑏ℓ, plus a deletion mark. Note this differs from the way we represented deletions in VBTs; see Figure 6. If a given tuple is inserted and deleted several times, its leaf will correspond to several updates. We will record the timestamps of those updates. If 𝑉 represents 𝐿 updates, they are numbered 1 to 𝐿. Each node [ts𝑙 , te𝑙 ) stores the value 𝑝𝑙 ∈ [1, 𝐿] for its last update. This means that its BT corresponds to executing the updates [1, 𝑝𝑙 ] on an empty trie. We store the timestamps, however, in a way that will enable fast navigation. Each node 𝑣 of 𝑉 will conceptually store the subsequence 𝑣.𝑇 of [1, 𝐿] corresponding to the updates that occur below 𝑣. The subsequence is 𝑣 .𝑇 = ⟨1, 2, . . . , 𝐿⟩ if 𝑣 is the root of 𝑉 . If 𝑣 is a leaf, then 𝑣 .𝑇 contains the timestamps where its particular tuple was created or removed. Figure 7 shows an example (see only the top and bottom-left parts for now). Instead of storing 𝑣.𝑇 [1, 𝐿𝑣 ] explicitly, we will store only a bitvector 𝑣 .𝐵 [1, 𝐿𝑣 ], where 𝑣.𝐵 [𝑖] = 0 iff 𝑣.𝑇 [𝑖] appears below the left child of 𝑣, and 𝑣 .𝐵 [𝑖] = 1 if it appears below the right child. To efficiently support operation leap, we also store a bitvector 𝑣.𝐸 [1, 𝐿𝑣 ], where 𝑣 .𝐸 [𝑖] = 1 iff at timestamp 𝑣.𝑇 [𝑖] there exists some tuple below 𝑣 whose last update was an insertion (i.e., the tuple exists at timestamp 𝑖). The leaves of 𝑉 store only their bitvector 𝑣.𝐸, not 𝑣.𝐵.

6.2

Navigation

To navigate 𝑉 without pointers, we must know the ranges 𝐵𝑑 [𝑠 𝑣 , 𝑒 𝑣 ] and 𝐸𝑑 [𝑠 𝑣 , 𝑒 𝑣 ] where the bitvectors 𝐵 𝑣 [1, 𝐿𝑣 ] and 𝐸 𝑣 [1, 𝐿𝑣 ] are stored, for any node 𝑣 of depth 𝑑. For the root, these are just 𝐵 0 [1, 𝐿] and 𝐸 0 [1, 𝐿]. For the rest, we make use of the function 𝑟𝑎𝑛𝑘 (𝐵, 𝑖, 𝑗), which counts the number of 1s in 𝐵 [𝑖, 𝑗]. This operation can be computed in constant time by storing just 𝑜 (|𝐵|) additional bits [17, 43]. Assume 𝐵𝑑 [𝑠 𝑣 , 𝑒 𝑣 ] is the area of 𝐵𝑑 corresponding to 𝑣 .𝐵. Then, letting 𝑟 := 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠 𝑣 , 𝑒 𝑣 ), the area for the left child of 𝑣 .𝐵 is 𝐵𝑑+1 [𝑠 𝑣 , 𝑒 𝑣 − 𝑟 ], and the area for its right child is 𝐵𝑑+1 [𝑒 𝑣 − 𝑟 + 1, 𝑒 𝑣 ]. We know we have reached a null pointer 𝑣 in 𝑉 when 𝑠 𝑣 > 𝑒 𝑣 . Example 13. Let us start at the root in Figure 7, with 𝐵 0 [1, 6] = 001010. To go to its left child, we compute 𝑟𝑎𝑛𝑘 (𝐵 0, 1, 6) = 2; thus its left child corresponds to 𝐵 1 [1, 4] = 1111. If we want to go left again, we compute 𝑟𝑎𝑛𝑘 (𝐵 1, 1, 4) = 4, and find that its left child is null because it corresponds to 𝐵 2 [1, 0]. □

Example 12. At the bottom of Figure 7, the root’s left child has 𝐸 [4] = 0 since the node does not exist at timestamp 𝑇 [4] = 6. Its right child has 𝐵 = 0101 since timestamps 𝑇 [1] = 1 and 𝑇 [3] = 4 go to its left child, whereas 𝑇 [2] = 2 and 𝑇 [4] = 6 go to the right. □

Until now, our structure is a variant of the wavelet matrix [18], but the bitvectors 𝐸𝑑 extend it so that we can traverse 𝑉 as if it were the VBT at some timestamp 𝑝𝑙 ∈ [1, 𝐿]. We start at the root of 𝑉 (i.e., 𝑑 := 0 and [𝑠 𝑣 , 𝑒 𝑣 ] := [1, 𝐿]) with the local offset 𝑝 := 𝑝𝑙 − 𝑠 𝑣 for 𝑝𝑙 . If 𝐸𝑑 [𝑠 𝑣 + 𝑝] = 0, then the VBT node was null at this time instant. Otherwise, we can go left or right. The timestamp 𝑝 becomes 𝑝 − 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠 𝑣 , 𝑠 𝑣 + 𝑝) on the left child and 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠 𝑣 , 𝑠 𝑣 +𝑝) −1 on the right child. Note that 𝑝 cannot become negative, since that would mean that there have been no updates

Note that every update induces 2𝑏ℓ + 1 bits in 𝑉 : one in the bitvectors 𝑣 .𝐵 of the proper ancestors 𝑣 of its leaf and one in the bitvectors 𝑣.𝐸 of those nodes and the leaf itself. We can actually avoid storing 𝑣 .𝐸 at leaves 𝑣 because it is always an alternating sequence of 1s and 0s. Therefore, the total number of bits in 𝑣.𝐵 and 𝑣.𝐸 bitvectors of 𝑉 is 𝐿 · 2𝑏ℓ = 𝑂 (𝐿 log 𝑁 ). The machine word 8

1

0

2

0

1

1

0

1

1

v2

v1

1

0

V

1

1

T=5

1

T = 1,4*

1

0 T = 1,2,4,6

0

v2

v3 T=5

v1

E = 10

v4

1

B = 10 E = 11 0

1

v2

v4

E= 1

v4

E= 1

0

v3

B0 = 001010 E0 = 111111 1 B= 0 E= 1 0

B= 0 E= 1 0

1

0

V 1

E = 10

0

0

v3

0

B = 0101 E = 1110 0

T=3

0

v4 T = 2,6*

v2

1

1

0

B = 1111 E = 1110

T = 3,5

1

0 1

v3

v2

6

1

1

0

B = 001010 E = 111111

T = 1,2,4,6

v1

1 1

v3

5

0

T = 1,2,3,4,5,6

0

0

1

1

0

v2

v1

4

0

1

0

v1

3

0

v3

B1 = 111110 E1 = 111011 B2 = 010100 E2 = 111011 E3 = 101011

T=3

Figure 7: On the top, the BTs of six consecutive timestamps, corresponding to inserting 𝑣 1 with value 0102 = 2, then 𝑣 2 with value 0112 = 3, and 𝑣 3 with value 1102 = 6. The leaf 𝑣 1 is then removed, 𝑣 4 is inserted with value 1002 = 4, and finally 𝑣 2 is removed. On the bottom left, our conceptual trie 𝑉 representing all the events, with the 𝑣.𝑇 sequences of timestamps besides each node 𝑣; the deletions are marked with a ∗ at the leaves. On the right, the actual compact representation of 𝑉 , first still with the tree topology and then just like the bitvectors 𝐵𝑑 and 𝐸𝑑 . Bitvector 𝐸 3 can be made virtual, as explained.

7.1

on the subtree of 𝑉 since the beginning, and thus the node would be null at timestamp 𝑝 (which we detect before entering the node). Example 14. Assume we want to go to the left child of the root at timestamp 𝑝𝑙 = 6 in Figure 7. Though 𝑉 has such a node, which is 𝐵 1 [1, 4], we see that it did not exist at timestamp 6 since 𝐸 1 [1+3] = 0. This position 3 is where we map the relative value 𝑝 = 𝑝𝑙 − 1 = 5 at the root to relative value 𝑝 − 𝑟𝑎𝑛𝑘 (𝐵 0, 1, 6) = 3 at its left child. □ With those operations, we can traverse any VBT top-down in constant time per movement to children, while the total space used by 𝑉 is 𝑂 (𝐿) and the total space is 𝑂 (𝑁 ) per LTJ trie. To support leap on this representation, recall that leap is applied on an LTJ trie node [ts𝑙 , te𝑙 ) of the time level, and aims to traverse its VBT (or BT) from its root 𝑣. Previously we describe this on a VBT of height ℓ, as we always perform leap on a single attribute, but now we have concatenated 𝑏 attributes in VBTs of height 𝑏ℓ. However, since we can start at any node whose depth is a multiple of ℓ, the procedure remains unchanged over blocks of ℓ elements. When run on 𝑉 , we are only interested in the timestamps [1, 𝑝𝑙 ], which represent the VBT of [ts𝑙 , te𝑙 ). We use 𝑣.𝐸 as before to determine if a node is null at timestamp 𝑝𝑙 . See pseudocode in the extended version (Algorithm 4). This completes the proof of Theorem 4.

7

Point-in queries

To answer a query 𝑄 over 𝐺𝑡 , we transform it into a temporal BGP by adding the constant 𝑡 as the fourth component in all the triples. Interestingly, if we force the variable order to descend first by the attribute t = 𝑡 we can show that the resulting algorithm takes exactly the same amount of steps that the normal LTJ algorithm on 𝑄 would take, immediately giving us worst-case optimality over 𝐺𝑡 . This proves the first part of Thm. 6. For the case of 𝐺𝑡𝑡12 , we must extend the navigation of 𝐺𝑡 using VBTs, described in Section 6.2, to intervals [𝑡 1, 𝑡 2 ). The key idea is that if 𝑡 1 and 𝑡 2 are represented by 𝑝 1 and 𝑝 2 + 1 at some node [𝑠 𝑣 , 𝑒 𝑣 ], then 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠 𝑣 + 𝑝 1, 𝑠 𝑣 + 𝑝 2 ) = 0 iff the node 𝑠 𝑣 did not exist along the whole period between the local offsets 𝑝 1 and 𝑝 2 , that is, it did not exist in 𝐺𝑡𝑡12 . Hence, we can quickly find the time intervals that overlap or are contained in [𝑡 1, 𝑡 2 ), and continue the LTJ algorithm while keeping track of these intervals. This yields the second part of Thm. 6; details in the extended version (Appendix C). We note that the so-called “join-first” strategy, which solves 𝑄 on the labeled graph 𝐺 all = 𝐺𝑇1 of all the tuples that ever existed and then filters the results by time, can offer the AGM bound only on |𝐺 all |, whereas our result bounded by |𝐺𝑡𝑡12 | is the best one can hope for: the algorithm is wco on the labeled graph that has exactly the triples we want to consider. Given a single triple pattern (𝑠, 𝑝, 𝑜), our algorithm lists all matches that existed during the interval [𝑡 1, 𝑡 2 ) in instance-optimal time: 𝑂 (log 𝑁 ) per reported triple. We can also list all the maximal intervals where each such match existed during [𝑡 1, 𝑡 2 ), each in 𝑂 (log 𝑁 ) time. This also permits tracking the differences between 𝐺𝑡1 −1 and 𝐺𝑡2 −1 : an important operation on versioned graphs. Neither “join-first” nor “time-first” strategies can handle these queries near-optimally. Full proof in the extended version (Appendix C).

QUERYING FOR POINTS AND INTERVALS

Definition 7 introduces several labeled graphs derived from a temporal graph 𝐺, in which it is of interest to answer standard BGPs. We now show how our linear-space data structure on 𝐺 can be used to answer BGPs over these graphs. We start with point-in-time and point-in-interval queries, corresponding to querying graphs 𝐺𝑡 and 𝐺𝑡𝑡12 , where 𝑡, 𝑡 1 , and 𝑡 2 are given at query time (Theorem 6). We finish with 𝐺 [𝑡1 ,𝑡2 ) and queries with duration. (Theorem 7).

Theorem 15. Let 𝐺 be a temporal graph with 𝑁 tuples. Then, there is a data structure using 𝑂 (𝑁 ) space that can report all the 9

Table 1: The datasets we use, including space in bytes per tuple and construction time in microseconds per edge.

𝑜𝑐𝑐 occurrences of a single-triple-pattern query 𝑄 = {(𝑠, 𝑝, 𝑜)} in the labeled graph 𝐺𝑡𝑡12 , for any time interval [𝑡 1, 𝑡 2 ) given with 𝑄, in time 𝑂 ((1 + 𝑜𝑐𝑐) log 𝑁 ). It can also list each maximal time interval where each occurrence appears in time 𝑂 (log 𝑁 ).

7.2

Dataset

Queries with duration

In some cases we are interested in requiring that the solutions to the queries last for some time. We consider two cases of such queries. The first establishes a time interval and looks for solutions that always hold during this interval. According to our definitions, this amounts to running the query over 𝐺 [𝑡1 ,𝑡2 ) ; recall Definition 7. A second case does not fix the exact times, but sets a minimum duration 𝛿 along which the reported solutions must hold [30]. In order to query 𝐺 [𝑡1 ,𝑡2 ) in optimal time, we can reuse some of the ideas used to query 𝐺𝑡𝑡12 . Indeed, we have that 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠 𝑣 + 𝑝 1, 𝑠 𝑣 + 𝑝 2 ) = 𝑝 2 − 𝑝 1 + 1 iff the node 𝑠 𝑣 exists throughout the whole period between the local offsets 𝑝 1 and 𝑝 2 . Therefore, we can use Algorithm 5 with a single change to require that all the bits in the area of 𝐸𝑑 are 1s, not just one of them. This may not be optimal in the size of 𝐺 [𝑡1 ,𝑡2 ) , because we may be stuck exploring a BT node that existed all along [𝑡 1, 𝑡 2 ), while none of its children did. However, the algorithm is still wco with respect to the size of 𝐺𝑡 for any 𝑡 ∈ [𝑡 1, 𝑡 2 ): if the subtree of a node 𝑣 at depth 𝑑 does not exist in 𝐺𝑡 , then the corresponding bit 𝐸𝑑 will be zero and the algorithm will not attempt to explore it. Instead of satisfying the AGM bound on |𝐺 [𝑡1 ,𝑡2 ) | = | ∩𝑡 ∈ [𝑡1 ,𝑡2 ) 𝐺𝑡 |, we satisfy it in terms of min𝑡 ∈ [𝑡1 ,𝑡2 ) |𝐺𝑡 |. This proves the first part of Thm. 7. For the case where we look for solutions of a query 𝑄 that hold over a minimum duration 𝛿, we first solve the query on 𝐺, adding the same variable 𝑡 as the fourth component of all the triple patterns, and use the LTJ tries where the time component t is at the end, as in join-first approaches. For the time level we use a more sophisticated data structure, based on geometric grids, that allows us to quickly discard time intervals smaller than 𝛿 while at the same time storing the children of each LTJ trie node 𝑣 in an efficient way; see the extended version (Appendix D). This is the second part of Thm. 7.

8

|U𝐺 |

844,172,299 116,145,285 15,943,638 9,384,937

Divvy Yellow Caida

21,243,344 30,003,832 15,792,089

|T𝐺 |

Space Time

155,956 155,956

241 230

38.0 34.7

7,158 20,673,270 8,552 20,797,780 110,704 336

190 194 141

25.0 29.1 20.8

annotations, further providing a comprehensive log of (5) realworld queries [40]. As per many real-world temporal graphs, some relations include temporal annotations, while others are asserted without temporal qualification (and considered universally valid). We extract the temporal graph from Wikidata considering all 844 million triples (see Table 1) consisting of items and properties. We extract temporal qualifiers on Wikidata statements, where available, for start time (ti), end time (tf), and point in time (ti and tf). In the resulting temporal graph, about 16 million triples have non-trivial temporal annotations. The graph features 12,894 distinct predicates. We extract 1000 BGPs from the real-world query logs published for Wikidata [40]; more details are given in the extended version (Appendix F.1). We filter queries whose constants do not occur in the graph, resulting in 974 queries. We run queries with a result limit of 1,000 and a timeout of 600 seconds. Indexing. Table 1 shows that our index (Wiki) uses 241 bytes per edge, or 60 32-bit words. This is 12 times the space needed to store the edges in plain form (as five 32-bit integers). For comparison, a standard index on non-temporal graphs uses 157 bytes per edge [7]. From the total space, 84% is used by the 6 tries starting with the time component, with tspo, tpos, and tosp being the largest tries (see the extended version, Appendix E). Indexing took 9 hours, growing linearly with the data size (verified by indexing increasing subsets). About 9% of the time was for building the 12 regular tries; the rest is used to build the 6 tries starting with the time component: building the linear-space data structure we designed in Section 6 requires sorting the data ⌈log2 |U𝐺 |⌉ = 28 times per level, not just once per the standard tries (those use faster radix-sorts, however). Our construction runs essentially in-place, using no more space than the final index.

EXPERIMENTS

Appendix E, in the extended version, gives details on the implementation of our index. In this section we evaluate its empirical performance over real temporal graphs, in two scenarios. First, we evaluate our index on a temporal graph and real queries from Wikidata, aiming to assess its practicality and the advantage of being able to bind the time at any point, not just at the beginning (time-first) or at the end (join-first). Second, we compare our index with two other systems that offer comparable functionality [30, 57] over real temporal graphs with synthetic queries. We ran our experiments on a 16-core Intel Xeon Silver 4110 with Debian 5.10.127-2, clocked at 2.1 GHz, with 768 GB of RAM and 10 MB cache. Our C++ code was compiled with -Ofast. Our benchmark, code and datasets are available on Github.

8.1

𝑁

Wiki WikiT

Variable elimination. A standard LTJ strategy [28] is to choose as the next variable the one whose trie nodes have the least amount of children among those (if possible) that are connected to a previously bound variable. Lonely variables (i.e., those appearing once in the BGP) are bound at the end. For temporal graphs we modify this strategy in three ways: join-first (JF) leaves the temporal variables to the end, time-first (TF) binds the temporal variables first, and least-children (LC) treats the time as any other variable (the ability to do this distinguishes our index from previous work). For nodes at the level t, we divide the total temporal span divided by their number of children, to estimate the number of children of its nodes.

Wikidata with real query logs

Benchmark. We perform experiments over the Wikidata knowledge graph [52]. We choose Wikidata as it provides a (1) large-scale, (2) real-world, (3) diverse knowledge graph featuring (4) temporal

Results. Figure 8 shows boxplots of query times, along with averages and number of queries for which one approach is faster than 10

milliseconds

106

JF – 425 675 2.18

JF< TF< LC< Avg

103 100 10−3 JF

LC

TF 549 – 620 8,010

Comparison with previous work. Figure 9 (right) compares the time to solve point-in-time queries using our index and that of Hu et al. [30]. That index implements queries with duration 𝛿, which for 𝛿 = 1 are point-in-time queries. We chose the strategies that performed best: generic join for cyclic queries and their acyclic baseline for the rest. As they do not limit the output size, we run both systems in that mode over a reduced Wikidata graph having only the triples with non-trivial time annotations; see WikiT in Table 1. We only report on the 76 BGPs that are supported by the code of Hu et al., that is, with variable subject and object. It can be seen that JF and LC outperform Hu et al. by orders of magnitude, which shows that our index has a competitive advantage over stateof-the-art solutions. TF is much slower in this case (still with better median but with worse distribution than Hu et al.); we consider next a scenario where TF is more competitive.

LC 299 354 – 1.06

TF

milliseconds

Figure 8: Left: Boxplots of runtimes in msec. Right: number of queries for which the approach in the row runs faster than that in the column, with average times at the bottom.

106

102

103

100

100

8.2

10−2

Other datasets with synthetic queries

10−3 JF

LC

JF

LC

Zhu et al. [57] study BGPs with fixed topologies (stars, chains, cycles, diamonds, cliques of various sizes) on various datasets. Table 1 describes the datasets we use; Appendix F.2 (extended version) gives more details. For each topology, they generate 100 pointin-time queries where all nodes are variables and edge labels are assigned a random constant so that the tBGP occurs at least once in the graph. We evaluate our system and related work on this setting.

TF Hu et al.

Figure 9: Left: boxplots of runtimes in msec for the query with clause 𝑡 1 ≤ 𝑡 2 . Right: comparison with Hu et al. [30] for point-in-time queries on WikiT.

Hu et al. Table 2 shows the times of Hu et al. [30] on Divvy, with a 60-second timeout, compared with our system using LC and TF, and no output size limit. On the acyclic queries (stars and chains), TF is 1.7 to 4.5 times faster than Hu et al.; on the cyclic queries it is up to 50 times faster (and more in the shapes where Hu et al. have many timeouts). LC outperforms TF on the stars, but it is (sometimes much) slower in the other shapes. As choosing good VEOs makes a sharper difference on cyclic queries, this suggests that we take advantage from the freedom to choose good query plans. But it also shows that finding the best plan can be challenging.

another. Our LC strategy is on average twice as fast as JF and orders of magnitude faster than TF. The boxplots of LC and JF seem comparable, yet JF is 20% slower in the median. The boxplots and the averages show that TF has many bad cases, making it an unstable strategy. By not always binding the temporal variables at the start (per TF) nor at the end (per JF), the LC strategy outperforms TF in 64% of the queries and JF in 69%. The average of the query-wise minima of the three times is 0.94 msec, just 11% faster than LC. Discussion. The results show that our index is practical on reallife scenarios: using less than twice the space needed for a nontemporal graph, we answer realistic queries within a millisecond. We also conclude that it is often highly beneficial to allow temporal variables to be eliminated at any point: LC is the fastest strategy in the majority of the queries, clearly outperforming JF and TF. This highlights the relevance of a unique capability of our index, and leaves room for designing better heuristics along the lines of LC.

Zhu et al. This paper implements point-in-time queries restricted to a time window [𝑡𝑠 , 𝑡𝑒 ] given with the query; this corresponds in our language to adding the same temporal variable 𝑡 to all BGPs and adding constraints 𝑡𝑠 ≤ 𝑡 and 𝑡 ≤ 𝑡𝑒 . They restrict the results to random time windows that cover a fraction of the time domain, set an output size limit, and set the timeout to 60 seconds. While they do not offer public code, we follow their descriptions to perform similar experiments on Divvy, which is close to their description in size and other parameters. Their TSRJoin index (the one that performs best) takes 483 bytes per tuple (2.5 times our space) and is built 4 times faster than ours in their machine (which is clocked at 2.9 GHz, but its architecture is older). Table 2 compares query performance with a time window of 10% of the domain and limiting the results to 100,000, which is the only configuration where we can compare all query shapes. We show their best time (TSRJoin). Our approach, using only TF strategy this time, is 2–100 times faster than TSRJoin. While the 2–4 speedup factors on star shapes can be attributed to our more modern machine1 , we are 1–2 orders of magnitude faster on the other shapes. We conjecture that this is

A more complex query. Our index solves more than just pointin-time queries. We demonstrate its performance on more complex queries by using now two time variables, 𝑡 1 and 𝑡 2 , and randomly assigning 𝑡 1 or 𝑡 2 (but at least once each) to the BGP triples in order to build the tBGP, and complete the query with a clause 𝑡 1 ≤ 𝑡 2 . We convert the 825 BGPs having more than one triple. Figure 9 (left) shows the distribution of times using JF and LC; note that the TF strategy is very inefficient when there are two (or more) time variables, as it would lead to Ω(𝑇 2 ) query time. In this case, LC and JF perform similarly, with a distribution close to that of the simpler point-in-time query. For example, the median of LC is 65 microseconds, just 30% higher than the median of the point-in-time queries (50 microseconds). This shows that our index can efficiently solve more complex queries as well.

1 According to Gemini, our hardware should be from 25%–35% faster for pure-CPU

calculations, to 3 times faster for computations bounded by RAM transfers. 11

3-star

4-star

5-star

3-chain

4-chain

5-chain

3-circle

4-circle

5-circle

diamond

4-clique

5-clique

100%

Hu et al. [30] Ours (LC) Ours (TF)

250 100 146

349 116 169

454 138 195

180 57 46

206 85 53

235 1,054 52

262 17 47

2,382 213 50

* 3,263 56

3,614 150 96

1,389 62 55

* 638 63

1% 10%

Table 2: Average time in msec to solve the different shapes on Divvy, with different windows of the time domain (100%, 10%, 1%) and limiting results to 100,000 (except on the 100% windows, which set no limit to match Hu et al. [30]). Times from Zhu et al. [57] are approximated from their plots. (*): Early termination due to many queries exceeding the 60,000 msec timeout. System

Zhu et al. [57] Ours (TF)

50 12.9

50 23.9

50 18.4

50 4.30

50 6.04

70 4.52

150 4.36

150 4.39

70 4.98

100 8.60

300 4.39

700 6.58

Ours (TF)

2.22

4.22

2.39

0.97

1.07

0.83

0.80

0.86

1.04

2.06

1.18

1.13

Table 3: Average time in msec on three collections with our system. We use a 10% time window and limit the results to 100,000 Dataset

3-star

4-star

5-star

3-chain

4-chain

5-chain

3-circle

4-circle

5-circle

diamond

4-clique

5-clique

Divvy Yellow Caida

12.9 0.23 230

23.9 0.12 240

18.4 0.47 234

4.30 2.80 236

6.04 20.7 242

4.52 401 247

4.36 17.0 224

4.39 346 1,416

4.98 13,913 3,032

8.60 197 762

4.39 204 868

6.58 34.6 4,203

mainly due to our ability to choose arbitrary VEOs for the other variables: we outperform TSRJoin more sharply on the queries where it is not trivial to find the best VEO. On the star queries, instead, there is only one join variable apart from time.

the generalized hypertree width of the query [1], which is never larger than its fractional hypertree width (the AGM bound). This can be done by optimally partitioning the query into a tree of cyclic queries, using our wco algorithm to solve each cyclic component, and then applying Yannakakis’ algorithm [56] to solve the resulting acyclic join of intermediate results. A problem is that those intermediate results might be obtained with the bindings of the time variables in non-compacted form (akin to representing 𝐺ˆ instead of 𝐺), and then they might require a lot of space. A solution would be to represent the intermediate results optimally using time intervals, yet finding the minimal set of hyperrectangles covering all the instantiations of the temporal variables seems difficult. A related challenge is to choose the most efficient VEOs. As seen in Figure 8, which approach works best depends on the query. The least-children (LC) strategy—akin to greedy optimization on cardinality estimates—works well in many cases, but there is room for better heuristics, including adaptive VEOs [7]. Another line of future work is to extend the language of the temporal clauses. For example, we may include timestamp arithmetic like 𝑤 1 ≤ 𝑤 2 + 3 if T is numeric, which requires representing the original time domain T (rather than T𝐺 ). In this case, the point graph 𝐺ˆ is only bounded by 𝑁 · |T |, which can even be infinite, and worst-case optimality must be reconsidered. Still, our structures would work without many changes, yet it will be crucial to always bind temporal variables to ranges, as discussed in Section 5.3. Finally, wco algorithms can be deployed for standard DBMS [23], which suggests our techniques could be deployed in a broader setting. This may include temporal path languages [6, 55] or even becoming part of temporal DBMS pipelines [29].

More on our performance. By looking at the “Ours” rows in the areas 100%, 10%, and 1% of Table 2, we can see that the time window sensitivity has a significant impact on the query time of our index, showing that it filters effectively using the time component. Table 3 measures our times on other datasets mentioned in Zhu et al.’s paper [57] (but much larger than their versions, so the results are not comparable): Yellow and Caida. We use a 10% time window and limit the results to 100,000. The differences in performance are explained mostly by the distribution of predicates: there are a few thousand in Divvy and Yellow, but those in Yellow are considerably skewed, while those in Divvy distribute uniformly. Caida, instead, has just one predicate. Since queries fix a predicate at random and leave all nodes as variables, the times in Caida are high and relatively uniform, growing as larger structures are reported: essentially we are generating all the ways a shape appears in the graph. Predicates help filter edges on Divvy, which yields low and relatively uniform times. On Yellow, with a skewed distribution, filtering is effective for most predicates, but the high times obtained on the larger structures when using a popular predicate dominate the average.

9

CONCLUSIONS

We have described a data structure that enables processing temporal BGPs in wco time, and provides further guarantees for other key applications such as point-in-time queries or queries with duration. Our experiments show that we solve realistic queries on large graphs within milliseconds, and that our strategy clearly outperforms simple solutions, as well as previous work. Although our index is static, we describe in Appendix G how to support adding new events (i.e., edge insertions and deletions) to the graph. One interesting challenge for future work is to obtain beyondwco query times. For example, we can easily obtain time related to

ACKNOWLEDGMENTS This work was supported by ANID – Millennium Science Initiative Program – Code ICN17_002. GN was also supported by Fondecyt Grant 1260080. 12

REFERENCES

Springer, 2018. [26] Fabio Grandi et al. Multi-temporal RDF ontology versioning. In IWOD@ ISWC, 2009. [27] Fabio Grandi et al. T-SPARQL: A TSQL2-like temporal query language for RDF. In ADBIS (local proceedings), volume 639, pages 21–30, 2010. [28] Aidan Hogan, Cristian Riveros, Carlos Rojas, and Adrián Soto. A worst-case optimal join algorithm for SPARQL. In Proc. 18th International Semantic Web Conference (ISWC), pages 258–275, 2019. [29] Jiamin Hou, Zhanhao Zhao, Wei Lu, Shiming Yang, Shuang Liu, Quanqing Xu, Chuanhui Yang, and Xiaoyong Du. An efficient and scalable graph database with built-in temporal support: J. hou et al. The VLDB Journal, 34(4):53, 2025. [30] Xiao Hu, Stavros Sintos, Junyang Gao, Pankaj K. Agarwal, and Jun Yang. Computing complex temporal join queries efficiently. In Proc. International Conference on Management of Data (SIGMOD), pages 2076–2090, 2022. [31] Chengying Huan, Heng Zhang, Yongchao Liu, Likang Chen, Xuran Wang, Yongchun Jiang, Shaonan Ma, and Yanjun Wu. TeMatch: A fast temporal subgraph matching framework with temporal-aware subgraph matching algorithms. In 2025 IEEE 41st International Conference on Data Engineering (ICDE), pages 1029–1042, 2025. [32] Guy Jacobson. Space-efficient static trees and graphs. In Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pages 549–554, 1989. [33] Mahmoud A. Khamis, Hung Q. Ngo, Cristopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems, 41(4):22, 2016. [34] Udayan Khurana and Amol Deshpande. Storing and analyzing historical graph data at scale. In International Conference on Extending Database Technology. OpenProceedings. org, 2016. [35] Manolis Koubarakis and Kostis Kyzirakos. Modeling and querying metadata in the semantic sensor web: The model stRDF and the query language stSPARQL. In Proc. Extended Semantic Web Conference, pages 425–439, 2010. [36] Hans-Peter Kriegel, Marco Pötke, and Thomas Seidl. Managing intervals efficiently in object-relational databases. In VLDB, volume 20, page 0, 2000. [37] Krishna Kulkarni and Jan-Eike Michels. Temporal features in SQL: 2011. ACM Sigmod Record, 41(3):34–43, 2012. [38] Faming Li, Zhaonian Zou, and Jianzhong Li. Durable subgraph matching on temporal graphs. IEEE Transactions on Knowledge and Data Engineering, 35(5):4713– 4726, 2022. [39] Min Lu, Qianzhen Zhang, and Xianqiang Zhu. Temporal multi-query subgraph matching in cybersecurity. Technologies, 13(8):335, 2025. [40] Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. Getting the most out of Wikidata: Semantic technology usage in Wikipedia’s knowledge graph. In Proc. 17th International Semantic Web Conference (ISWC), pages 376–394, 2018. [41] Amine Mhedhbi and Semih Salihoglu. Optimizing subgraph queries by combining binary and worst-case optimal joins. Proceedings of the VLDB Endowment, 12(11):1692–1704, 2019. [42] Vera Zaychik Moffitt and Julia Stoyanovich. Temporal graph algebra. In Proc. 16th International Symposium on Database Programming Languages, pages 1–12, 2017. [43] J. Ian Munro. Tables. In Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 37–42, 1996. [44] Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In Proc. 37th Symposium on Principles of Database Systems (PODS), pages 111–124, 2018. [45] Hung Q. Ngo, Ely Porat, Cristopher Ré, and Atri Rudra. Worst-case optimal join algorithms. In Proc. 31st Symposium on Principles of Database Systems (PODS), pages 37–48, 2012. [46] Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. In Proc. 10th ACM International Conference on Web Search and Data Mining (WSDM), pages 601–610, 2017. [47] Olivier Pelgrin, Ruben Taelman, Luis Galárraga, and Katja Hose. GLENDA: Querying RDF archives with full SPARQL. In Proc. European Semantic Web Conference (ESWC), pages 75–80, 2023. [48] Matthew Perry, Prateek Jain, and Amit P Sheth. SPARQL-st: Extending SPARQL to support spatiotemporal queries. In Geospatial Semantics and the Semantic Web: Foundations, Algorithms, and Applications, pages 61–86. Springer, 2011. [49] Konstantinos Semertzidis and Evaggelia Pitoura. Top-𝑘 durable graph pattern queries on temporal graphs. IEEE Transactions on Knowledge and Data Engineering, 31(1):181–194, 2018. [50] Richard Snodgrass. The temporal query language TQuel. ACM Transactions on Database Systems, 12(2):247–298, 1987. [51] Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory (ICDT), pages 96–106, 2014. [52] Denny Vrandecic and Markus Krötzsch. Wikidata: a free collaborative knowledgebase. Commun. ACM, 57(10):78–85, 2014. [53] Jialing Wang, Immanuel Trummer, Ahmet Kara, and Dan Olteanu. ADOPT: Adaptively optimizing attribute orders for worst-case optimal join algorithms

[1] Christopher R Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. Emptyheaded: A relational engine for graph processing. ACM Transactions on Database Systems, 42(4):1–44, 2017. [2] Mahmoud Abo Khamis, George Chichirim, Antonia Kormpa, and Dan Olteanu. The complexity of boolean conjunctive queries with intersection joins. In Proc. 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 53–65, 2022. [3] Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Proc. 36th ACM Symposium on Principles of Database Systems (PODS), pages 429–444, 2017. [4] Avishek Anand, Srikanta Bedathur, Klaus Berberich, and Ralf Schenkel. Index maintenance for time-travel text search. In Proc. 35th International ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 235–244, 2012. [5] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. Foundations of modern query languages for graph databases. ACM Computing Surveys, 50(5):1–40, 2017. [6] Marcelo Arenas, Pedro Bahamondes, Amir Aghasadeghi, and Julia Stoyanovich. Temporal regular path queries. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2412–2425. IEEE, 2022. [7] Diego Arroyuelo, Daniela Campos, Adrián Gómez-Brandón, Yuval Linker, Gonzalo Navarro, Carlos Rojas, and Domagoj Vrgoc. CompactLTJ: Space & time efficient Leapfrog Triejoin on graph databases. The Very Large Databases Journal, 34:article 67, 2025. [8] Diego Arroyuelo, Adrián Gómez-Brandón, Aidan Hogan, Gonzalo Navarro, Juan L. Reutter, Javiel Rojas-Ledesma, and Adriá Soto. The Ring: Worst-case optimal joins in graph databases using (almost) no extra space. ACM Transactions on Database Systems, 29(2):article 5, 2024. [9] Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737–1767, 2013. [10] Klaus Berberich, Srikanta Bedathur, Thomas Neumann, and Gerhard Weikum. A time machine for text search. In Proc. 30th Annual International ACM Conference on Research and Development in Information Retrieval (SIGIR), pages 519–526, 2007. [11] Michael H Böhlen, Christian S Jensen, and Richard Thomas Snodgrass. Temporal statement modifiers. ACM Transactions on Database Systems, 25(4):407–456, 2000. [12] Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and Robert Sedgewick. Resizable arrays in optimal time and space. In Proc. 6th International Symposium on Algorithms and Data Structures (WADS), pages 37–48, 1999. [13] Borui Cai, Yong Xiang, Longxiang Gao, He Zhang, Yunfeng Li, and Jianxin Li. Temporal knowledge graph completion: A survey. arXiv preprint arXiv:2201.08236, 2022. [14] Li Cai, Xin Mao, Yuhao Zhou, Zhaoguang Long, Changxu Wu, and Man Lan. A survey on temporal knowledge graph: Representation learning and applications. arXiv preprint arXiv:2403.04782, 2024. [15] Matteo Ceccarello, Anton Dignös, Johann Gamper, and Christina Khnaisser. Indexing temporal relations for range-duration queries. In Proceedings of the 35th International Conference on Scientific and Statistical Database Management, pages 1–12, 2023. [16] Timothy M. Chan, Kasper G. Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proc. 27th ACM Symposium on Computational Geometry (SoCG), pages 1–10, 2011. [17] David R. Clark. Compact PAT Trees. PhD thesis, University of Waterloo, Canada, 1996. [18] Francisco Claude, Gonzalo Navarro, and Alberto Ordóñez. The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems, 47:15–32, 2015. [19] Albert Croker and James Clifford. On completeness of historical relational data models. NYU Working Paper No. IS-89-002, 1989. [20] Ignacio Cuevas and Aidan Hogan. Versioned queries over RDF archives: All you need is SPARQL? In MEPDaW@ ISWC, pages 43–52, 2020. [21] Anton Dignös, Michael H Böhlen, and Johann Gamper. Temporal alignment. In Proc. ACM International Conference on Management of Data (SIGMOD), pages 433–444, 2012. [22] Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. A researcher’s digest of GQL. In Proc. 26th International Conference on Database Theory (ICDT), pages 1:1–1:22, 2023. [23] Michael J. Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann. Adopting worst-case optimal joins in relational database systems. Proceedings of the VLDB Endowment, 13(11):1891–1904, 2020. [24] Yunjun Gao, Tianming Zhang, Linshan Qiu, Qingyuan Linghu, and Gang Chen. Time-respecting flow graph pattern matching on temporal graphs. IEEE Transactions on Knowledge and Data Engineering, 33(10):3453–3467, 2020. [25] Simon Gottschalk and Elena Demidova. Eventkg: A multilingual event-centric temporal knowledge graph. In European semantic web conference, pages 272–287. 13

via reinforcement learning. Proceedings of the VLDB Endowment, 16(11):2805– 2817, 2023. [54] Yisu Remy Wang, Max Willsey, and Dan Suciu. Free Join: Unifying worst-case optimal and traditional joins. Proceedings of the ACM on Management of Data (SIGMOD), 1(2):150:1–150:23, 2023. [55] Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs. Proceedings of the VLDB Endowment, 7(9):721–732, 2014. [56] Mihalis Yannakakis. Algorithms for acyclic database schemes. In Proc. 7th International Conference on Very Large Databases (VLDB), pages 82–94, 1981. [57] Kaijie Zhu, George Fletcher, and Nikolay Yakovets. Leveraging temporal and topological selectivities in temporal-clique subgraph query processing. In Proc. 37th IEEE International Conference on Data Engineering (ICDE), pages 672–683, 2021.

14

A

ON THE EXPRESSIVE POWER OF TBGPS

Let us start with the comparison with CQs. To abstract from relational representations of temporal graphs, we consider a relational representation with a single relation 𝑇 of arity 5, with the first three positions reserved for triples, the fourth for the start of a time interval, and the fifth for the end of the interval. Then, each temporal graph 𝐺 is directly represented as an instance 𝐼𝐺 : for each tuple (𝑠, 𝑝, 𝑜, [ti, tf )) in 𝐺 we add to 𝐼𝐺 the atom (𝑠, 𝑝, 𝑜, ti, tf). In this context, one asks whether every tBGP can be expressed as a query in 𝐼𝐺 ; we say that a tBPG 𝑄 can be expressed as a conjunctive query over the relational representation of graphs if one can find a conjunctive query 𝑄 ′ such that the evaluation of 𝑄 over any temporal graph 𝐺 corresponds to the evaluation of 𝑄 ′ over 𝐼𝐺 . Proposition 16. There is a family of tBGPs that cannot be expressed as conjunctive queries over the relational representation of graphs, nor as conjunctive queries with inequalities. Proof. Assume towards contradiction that every tBGP can be expressed as a conjunctive query over the relational representation of temporal graphs, possibly extended with inequalities. Consider, for every 𝑛 ≥ 1, the tBGP 𝑄𝑛 consisting of a path of length 𝑛 required to hold at the same time instant: 𝑄𝑛 = {(𝑥 0, 𝑝, 𝑥 1, 𝑤), (𝑥 1, 𝑝, 𝑥 2, 𝑤), . . . , (𝑥𝑛−1, 𝑝, 𝑥𝑛 , 𝑤)}. Intuitively, 𝑄𝑛 asks for a path of length 𝑛 that exists simultaneously at some time point 𝑤. Suppose there exists a conjunctive query 𝑄𝑛′ over the relational encoding using the relation 𝑇 (𝑠, 𝑝, 𝑜, ti, tf) that expresses 𝑄𝑛 . Let 𝐻𝑛 be a static graph consisting of a path 𝑝

𝑝

𝑝

𝑎0 → − 𝑎1 → − ··· → − 𝑎𝑛 . We construct two temporal graphs that have the same frozen structure but different temporal behavior. Instance 𝐺 1 . For every edge (𝑎𝑖 , 𝑝, 𝑎𝑖+1 ) of 𝐻𝑛 , include the tuple (𝑎𝑖 , 𝑝, 𝑎𝑖+1, [𝑡 1, 𝑡 3 )) with 𝑡 0 < 𝑡 1 < 𝑡 2 < 𝑡 3 . Additionally, add one extra edge (𝑏, 𝑝 ′, 𝑏 ′, [𝑡 0, 𝑡 2 )). At time 𝑡 2 , all edges of the path are valid simultaneously, hence 𝑄𝑛 (𝐺 1 ) contains a solution witnessing time 𝑤 = 𝑡 2 . Since 𝑄𝑛′ expresses 𝑄𝑛 , there must be a homomorphism from the body of 𝑄𝑛′ into 𝐼𝐺 1 mapping the variable corresponding to 𝑤 to the value 𝑡 2 . Consequently, some atom of 𝑄𝑛′ must use 𝑡 2 as the value obtained from an interval endpoint appearing in position 5 (the interval end), because 𝑡 2 only occurs there. Instance 𝐺 2 . Now consider the temporal graph obtained by replacing the additional edge with (𝑏, 𝑝 ′, 𝑏 ′, [𝑡 2, 𝑡 4 )) for 𝑡 3 < 𝑡 4 , while keeping all path edges unchanged. Again, the frozen graph is identical to 𝐻𝑛 , and now the witnessing time belongs to the start of an interval, namely position 4. Hence, correctness of 𝑄𝑛′ implies that there must exist a homomorphism mapping the same time variable to position 4 of some atom. But we also need to map the atom mapping 𝑤 to the fifth position. As the value 𝑡 2 is not in the fifth position in any tuple in 𝐼𝐺 2 , it follows that there cannot be a homomorphism from 𝑄𝑛′ to 𝐼𝐺 2 , which is a contradiction. Therefore, no conjunctive query (even with inequalities) can express any of the tBGPs {𝑄𝑛 }𝑛≥1 . □ However, tBGPs do coincide with conjunctive queries (with inequalities) when we expand graphs into their point-based representation, which may be of quadratic size with respect to the original temporal graph. While materializing the point-based representation is therefore not feasible in practice, the following result provides a good justification for our language: by focusing on tBGPs we study the basing block of temporal query languages. To make this more precise, consider a different relational representation 𝐼𝐺 , which now stores a tuple (𝑠, 𝑝, 𝑜, 𝑡) ˆ Further, let us say that a tBGP is compatible with a graph 𝐺 if the time instants mentioned in 𝑄 are also in I𝐺 . for each (𝑠, 𝑝, 𝑜, 𝑡) ∈ 𝐺. Proposition 17. for every tBGP 𝑄 one can construct a conjunctive query 𝑄ˆ with inequalities, so that the answer of 𝑄 over a compatible ˆ and conversely, as long as the inequalities on the conjunctive query are only on variables temporal graph 𝐺 is the same as the answer of 𝑄ˆ over 𝐺, used in the fourth position of relations. Proof. Let 𝑄 be a tBGP. Observe that 𝑄 can be viewed syntactically as a conjunctive query of arity 4, possibly with comparison predicates between variables occurring in the fourth (temporal) position. Hence, 𝑄 can be directly evaluated over the point-based representation 𝐺ˆ as a standard conjunctive query with inequalities. We show that the answers coincide in both settings. Throughout the proof we consider only temporal graphs 𝐺 for which 𝑄 is well defined, that is, all constants appearing in 𝑄 belong to U𝐺 and all temporal constants belong to 𝐼𝐺 . (⇒) Let 𝑓 be a solution of 𝑄 over the temporal graph 𝐺. Consider any tuple pattern (𝑥, 𝑦, 𝑧, 𝑤) of 𝑄. Since 𝑓 is a valid assignment, there exists a tuple (𝑓 (𝑥), 𝑓 (𝑦), 𝑓 (𝑧), [ti, tf)) ∈ 𝐺 15

𝑥 ← 0;𝑙 ← 0; while 𝑡𝑟𝑢𝑒 do 𝑥 ← leap(𝑣𝑙 , 𝑥) ; 𝑖 ← (𝑙 + 1) mod 𝑘 ; while 𝑖 ≠ 𝑙 do 𝑥 ′ ← leap(𝑣𝑖 , 𝑥) ; if 𝑥 ′ > 𝑥 then 𝑥 ← 𝑥 ′ ; 𝑙 ← 𝑖 ; 𝑖 ← (𝑖 + 1) mod 𝑘 ; end if 𝑥 = +∞ thenbreak ; report 𝑥 ; 𝑥 ←𝑥 +1; end Algorithm 1: The LTJ iterator reports all common children of LTJ trie nodes 𝑣 0, . . . , 𝑣𝑘 −1 . leap(𝑣, 𝑥) returns the next value ≥ 𝑥 descending from LTJ trie node 𝑣, or +∞ if none exists. such that ti ≤ 𝑓 (𝑤) < tf. By definition of solutions, we may assume that 𝑓 (𝑤) ∈ T𝐺 . Then, by construction of the point-based representation, the tuple (𝑓 (𝑥), 𝑓 (𝑦), 𝑓 (𝑧), 𝑓 (𝑤)) ˆ Hence every atom of 𝑄 is satisfied in 𝐺, ˆ and all comparison predicates remain valid. Therefore 𝑓 is also a satisfying assignment belongs to 𝐺. ˆ of 𝑄 evaluated as a conjunctive query over 𝐺. ˆ Since tuples of 𝐺ˆ have the form (𝑠, 𝑝, 𝑜, 𝑡) obtained from intervals of 𝐺, for (⇐) Conversely, let 𝑓 be a satisfying assignment of 𝑄 over 𝐺. every atom (𝑥, 𝑦, 𝑧, 𝑤) of 𝑄 such that ˆ (𝑓 (𝑥), 𝑓 (𝑦), 𝑓 (𝑧), 𝑓 (𝑤)) ∈ 𝐺, there exists an interval [ti, tf) with (𝑓 (𝑥), 𝑓 (𝑦), 𝑓 (𝑧), [ti, tf)) ∈ 𝐺 and ti ≤ 𝑓 (𝑤) < tf. Hence the atom is satisfied under the semantics of tBGPs. Moreover, because the domain of values and the temporal domain are disjoint, variables occurring in the first three positions cannot be mapped to temporal values and vice versa. Thus comparison predicates involving temporal variables are preserved, and 𝑓 is a valid solution of 𝑄 over 𝐺. □ From Propositions 16 and 17, it follows that none of the techniques developed for relational conjunctive queries can be directly ported into our temporal graph setting, unless we first expand temporal graphs to their point-based representation, this, as we explained, is not feasible to do in practice.

B

PSEUDOCODES

We show pseudocode in Algorithms 1 to 4.

C

QUERYING THE GRAPHS 𝐺𝑡 AND 𝐺𝑡𝑡12 (EXTENDED VERSION)

Definition 7 gives some standard labeled graphs that can be derived from a temporal graph 𝐺, on which it is of interest to answer standard BGPs. We now show how we can use our linear-space data structure on 𝐺 to answer BGPs on 𝐺𝑡 and 𝐺𝑡𝑡12 , where 𝑡, 𝑡 1 , and 𝑡 2 are given together with the query, in wco time with respect to those graphs. The case of 𝐺 [𝑡1 ,𝑡2 ) will be discussed later. We can answer general BGPs 𝑄 on 𝐺𝑡 by converting them to BGPs on the temporal graph 𝐺, adding the constant 𝑡 as the fourth component in all the triples. A particularly interesting result, however, is obtained if we instead descend by the attribute t = 𝑡 in the 6 LTJ tries that start with attribute t. The subtries that descend from those nodes correspond to the LTJ tries for 𝐺𝑡 , on the attributes s, p, and o. For example, if we descend by 𝑡 in the trie tspo, the subtrie of the node we arrive at is isomorphic to the trie spo of 𝐺𝑡 . We can then run the normal LTJ algorithm for 𝑄 using those subtries, exactly as if they were the LTJ tries of 𝐺𝑡 . Since our 𝑂 (𝑁 ) space data structure simulates the operation leap on those subtries in 𝑂 (log 𝑁 ) time, the result follows easily. This proves the first part of Thm. 6. To obtain an analogous result for 𝐺𝑡𝑡12 , we must extend the navigation of 𝐺𝑡 using VBTs, described in Section 6.2, to intervals [𝑡 1, 𝑡 2 ). The key idea is that, if 𝑡 1 and 𝑡 2 are represented by 𝑝 1 and 𝑝 2 + 1 at some node [𝑠 𝑣 , 𝑒 𝑣 ], then 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠 𝑣 + 𝑝 1, 𝑠 𝑣 + 𝑝 2 ) = 0 iff the node 𝑠 𝑣 did not exist along the whole period between the local offsets 𝑝 1 and 𝑝 2 , that is, it did not exist in 𝐺𝑡𝑡12 . We start on the time level, where we find the first and last intervals, [ts𝑎 , te𝑎 ) and [ts𝑏 , te𝑏 ), that overlap or are contained in [𝑡 1, 𝑡 2 ) (it might be that 𝑎 = 𝑏, but the answer is empty if no such intervals exist). Let these intervals correspond to timestamps 𝑝𝑎 and 𝑝𝑏 in our linear-space data structure 𝑉 below the time level. We start at depth 𝑑 := 0, with interval [𝑠 𝑣 , 𝑒 𝑣 ] := [1, 𝐿] at the root 𝑣 of 𝑉 , and with local offsets 𝑝 1 := 𝑝𝑎−1 − 𝑠 𝑣 and 𝑝 2 := 𝑝𝑏 − 𝑠 𝑣 . If 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠 𝑣 + 𝑝 1 + 1, 𝑠 𝑣 + 𝑝 2 ) = 0, then the VBT node was null all along the time interval [𝑡 1, 𝑡 2 ); 16

leap(𝑣, 𝑥, ℎ) if 𝑣 = 𝑛𝑢𝑙𝑙 thenreturn +∞ ; if 𝑣 is a leaf thenreturn 0 ; if ⌊𝑥/2ℎ ⌋ = 1 then 𝑥 ← leap(𝑣.𝑟, 𝑥 − 2ℎ , ℎ − 1) ; else 𝑥 ← leap(𝑣 .𝑙, 𝑥, ℎ − 1) ; if 𝑥 ≠ +∞ thenreturn 𝑥 ; 𝑥 ← leftmost(𝑣.𝑟, ℎ − 1) ; end if 𝑥 ≠ +∞ then 𝑥 ← 𝑥 + 2ℎ ; return 𝑥 ; leftmost(𝑣, ℎ) if 𝑣 = 𝑛𝑢𝑙𝑙 thenreturn +∞ ; if 𝑣 is a leaf thenreturn 0 ; if 𝑣.𝑙 ≠ 𝑛𝑢𝑙𝑙 then return leftmost(𝑣.𝑙, ℎ − 1) ; return 2ℎ + leftmost(𝑣.𝑟, ℎ − 1) ; Algorithm 2: The implementation of leap using BTs (or, equivalently, VBTs). The function receives the LTJ trie node 𝑣 (which is identified with the BT root), the minimum desired value 𝑥, and the BT height ℎ = ℓ. The left and right children of BT node 𝑣 are 𝑣 .𝑙 and 𝑣.𝑟 , respectively. 𝑥 ← 0;𝑙 ← 0; while 𝑡𝑟𝑢𝑒 do [𝑥, 𝑦) ← leap(𝑣𝑙 , 𝑥) ; 𝑖 ← (𝑙 + 1) mod 𝑘 ; while 𝑖 ≠ 𝑙 do [𝑥 ′, 𝑦 ′ ) ← leap(𝑣𝑖 , 𝑥) ; if 𝑥 ′ > 𝑥 then [𝑥, 𝑦) ← [𝑥 ′, 𝑦 ′ ) ; 𝑙 ← 𝑖 ; else 𝑦 ← min(𝑦, 𝑦 ′ ) ; 𝑖 ← (𝑖 + 1) mod 𝑘 ; end if 𝑥 = +∞ thenbreak ; report [𝑥, 𝑦) ; 𝑥 ←𝑦 ; end Algorithm 3: The modified LTJ iterator to account for intervals when intersecting at the time level. The iterator now returns intervals [𝑥, 𝑦) where all the results will be the same.

that is to say, there are no elements of 𝐺𝑡𝑡12 descending from 𝑣. Otherwise, we can go left or right. We compute 𝑟 := 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠 𝑣 , 𝑒 𝑣 ) and ′ := 𝑟𝑎𝑛𝑘 (𝐵 , 𝑠 , 𝑠 + 𝑝 ′ 𝑝 1/2 𝑑 𝑣 𝑣 1/2 ). To descend left, we update 𝑒 𝑣 := 𝑒 𝑣 − 𝑟 and 𝑝 1/2 := 𝑝 1/2 − 𝑝 1/2 ; to descend right we update 𝑠 𝑣 := 𝑒 𝑣 − 𝑟 + 1 and ′ − 1. 𝑝 1/2 := 𝑝 1/2 A special case occurs in this process if 𝑝 1 and 𝑝 2 become equal. This means that the subtree of 𝑣 had no update during [𝑡 1, 𝑡 2 ), and therefore it has tuples below it during that period iff 𝐸𝑑 [𝑠 𝑣 + 𝑝 1 ] = 1, assuming 𝐸𝑑 [0] = 0. Algorithm 5 shows how to modify Algorithm 4 to perform leap on this simulated trie. Note that if the algorithm arrives at a node 𝑣, there exists at least one edge below 𝑣 during [𝑡 1, 𝑡 2 ); therefore we do not spend any time on nodes that do not exist in the LTJ trie of 𝐺𝑡𝑡12 . This yields the second part of Thm. 6. We note that the so-called “join-first” strategy, which solves 𝑄 on the labeled graph 𝐺 all = 𝐺𝑇1 of all the tuples that ever existed and then filters the results by time, can offer the AGM bound only on |𝐺 all |, whereas our result bounded by |𝐺𝑡𝑡12 | is the best one can hope for: the algorithm is wco on the labeled graph that has exactly the triples we want to consider. Triple patterns. Consider the case of a BGP formed by a single triple pattern (𝑠, 𝑝, 𝑜). Our algorithm will first descend in the time level, computing 𝑎 and 𝑏 with a binary search, and then descend in 𝑉 by the constants in (𝑠, 𝑝, 𝑜). For each node arrived at, there exists at least 17

leap(𝑑, 𝑠, 𝑒, 𝑝, 𝑥, ℎ) if 𝑠 + 𝑝 ∉ [𝑠, 𝑒] ∨ 𝐸𝑑 [𝑠 + 𝑝] = 0 thenreturn +∞ ; if ℎ = 0 thenreturn 0 ; 𝑟 ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑒) ; 𝑝 ′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝) ; if ⌊𝑥/2ℎ ⌋ = 1 then 𝑥 ← leap(𝑑 + 1, 𝑒 − 𝑟 + 1, 𝑒, 𝑝 ′ − 1, 𝑥 − 2ℎ , ℎ − 1) ; if 𝑥 ≠ +∞ thenreturn 𝑥 + 2ℎ ; return +∞; end else 𝑥 ← leap(𝑑 + 1, 𝑠, 𝑒 − 𝑟, 𝑝 − 𝑝 ′, 𝑥, ℎ − 1) ; if 𝑥 ≠ +∞ thenreturn 𝑥 ; if 𝑟 = 0 ∨ 𝐸𝑑+1 [𝑒 − 𝑟 + 𝑝 ′ ] = 0 thenreturn +∞ ; return 2ℎ + leftmost(𝑑 + 1, 𝑒 − 𝑟 + 1, 𝑒, 𝑝 ′ − 1, ℎ − 1) ; end leftmost(𝑑, 𝑠, 𝑒, 𝑝, ℎ) if ℎ = 0 thenreturn 0 ; 𝑟 ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑒) ; 𝑝 ′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝) ; if 𝑠 ≤ 𝑒 − 𝑟 ∧ 𝐸𝑑+1 [𝑠 + 𝑝 − 𝑝 ′ ] = 1 then return leftmost(𝑑 + 1, 𝑠, 𝑒 − 𝑟, 𝑝 − 𝑝 ′, ℎ − 1) end return 2ℎ + leftmost(𝑑 + 1, 𝑒 − 𝑟 + 1, 𝑒, 𝑝 ′ − 1, ℎ − 1) ; Algorithm 4: The implementation of leap on our linear-space representation. The function receives the LTJ trie node that corresponds to the range [𝑠, 𝑒] at level 𝑑 of our structure, the local timestamp of interest 𝑝 = 𝑝𝑙 − 𝑠, the minimum desired value 𝑥, and the BT height ℎ = ℓ. one triple in 𝐺𝑡𝑡12 , and the algorithm will descend by all left and right branches in the VBTs, reporting all the triples. The total time is instance-optimal, 𝑂 (log 𝑁 ) per reported triple. The existential query, that is, telling whether the triple pattern has a match or not in 𝐺𝑡𝑡12 , takes 𝑂 (log 𝑁 ) time. Even this simple query is not handled near-optimally with the “join-first” strategy: there could be many matches for (𝑠, 𝑝, 𝑜) out of [𝑡 1, 𝑡 2 ). It is also not handled well with “time-first”, which individually considers each time 𝑡 ∈ [𝑡 1, 𝑡 2 ) and solves the query on 𝐺𝑡 : the triple pattern may not appear in many time instants 𝑡. Listing time intervals. It is also possible to list all the maximal intervals where each match (𝑠, 𝑝, 𝑜) of the BGP existed during [𝑡 1, 𝑡 2 ), each in 𝑂 (log 𝑁 ) time. In the final level ℓ, each position in 𝐸 ℓ [𝑠 +𝑝 1 +1, 𝑠 +𝑝 2 ] corresponds to an event where the triple (𝑠, 𝑝, 𝑜) is successively inserted (1) and deleted (0). Those offsets 𝑝 1 < 𝑝 ≤ 𝑝 2 can be mapped to the corresponding time instants as we return from the recursive traversal of the VBT. Say that from our range in 𝐸𝑑 [𝑠, 𝑒] we went to the left child, thereby arriving at the range 𝐸𝑑+1 [𝑠, 𝑒 −𝑟 ] with 𝑟 := 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑒). Then, a position 𝐸𝑑+1 [𝑠 − 1 + 𝑝] corresponds to the position 𝐸𝑑 [𝑠 + 𝑠𝑒𝑙𝑒𝑐𝑡 0 (𝐵𝑑 , 𝑠, 𝑝)], where 𝑠𝑒𝑙𝑒𝑐𝑡𝑏 (𝐵𝑑 , 𝑠, 𝑝) is the position of the 𝑝th occurrence of bit 𝑏 ∈ {0, 1} in 𝐵𝑑 [𝑠..]. Analogously, if we went to the right child of 𝐸𝑑 [𝑠, 𝑒], arriving at the range 𝐸𝑑+1 [𝑒 − 𝑟 + 1, 𝑒], a position 𝐸𝑑+1 [𝑒 − 𝑟 + 𝑝] corresponds to the position 𝐸𝑑 [𝑠 + 𝑠𝑒𝑙𝑒𝑐𝑡 1 (𝐵𝑑 , 𝑠, 𝑝)]. Query 𝑠𝑒𝑙𝑒𝑐𝑡 is solved in constant time using 𝑜 (|𝐵𝑑 |) bits on top of 𝐵𝑑 [17, 43]. After 𝑂 (log 𝑁 ) steps we reach the root of 𝑉 , where the timestamp 𝑝 can be binary searched among the 𝑝𝑙 values assigned to the intervals [ts𝑙 , te𝑙 ) to convert it to time instants in T . Theorem 18. Let 𝐺 be a temporal graph with 𝑁 tuples. Then, there is a data structure using 𝑂 (𝑁 ) space that can report all the 𝑜𝑐𝑐 occurrences of a single-triple-pattern query 𝑄 = {(𝑠, 𝑝, 𝑜)} in the labeled graph 𝐺𝑡𝑡12 , for any time interval [𝑡 1, 𝑡 2 ) given with 𝑄, in time 𝑂 ((1 + 𝑜𝑐𝑐) log 𝑁 ). It can also list each maximal time interval where each occurrence appears in time 𝑂 (log 𝑁 ). Listing the time intervals where a triple pattern existed in [𝑡 1, 𝑡 2 ) also permits tracking the differences between 𝐺𝑡1 −1 and 𝐺𝑡2 −1 , an important operation on versioned graphs. This can go from tracking a single triple (𝑠, 𝑝, 𝑜) to listing all the changes in the graph.

D

QUERIES WITH DURATION (EXTENDED VERSION)

In some cases we are interested in requiring that the solutions to the queries last for some time. We consider two cases of such queries. A first one is to establish a time interval where the solution must always hold, so that we are interested only in that time interval. In other 18

leap(𝑑, 𝑠, 𝑒, 𝑝 1, 𝑝 2, 𝑥, ℎ) if 𝑠+𝑝 ∉ [𝑠, 𝑒] ∨ 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠+𝑝 1 +1, 𝑠+𝑝 2 )=0 thenreturn +∞ ; if ℎ = 0 thenreturn 0 ; 𝑟 ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑒) ; 𝑝 1′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝 1 ); 𝑝 2′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝 2 ) ; if ⌊𝑥/2ℎ ⌋ = 1 then 𝑥 ← leap(𝑑 + 1, 𝑒 − 𝑟 + 1, 𝑒, 𝑝 1′ − 1, 𝑝 2′ − 1, 𝑥 − 2ℎ , ℎ − 1) ; if 𝑥 ≠ +∞ thenreturn 𝑥 + 2ℎ ; return +∞ ; end else 𝑥 ← leap(𝑑 + 1, 𝑠, 𝑒 − 𝑟, 𝑝 1 − 𝑝 1′ , 𝑝 2 − 𝑝 2′ , 𝑥, ℎ − 1) ; if 𝑥 ≠ +∞ thenreturn 𝑥 ; if 𝑟 = 0 ∨ 𝑟𝑎𝑛𝑘 (𝐸𝑑+1, 𝑒 − 𝑟 + 𝑝 1′ + 1, 𝑒 − 𝑟 + 𝑝 2′ ) = 0 thenreturn +∞ ; return 2ℎ + leftmost(𝑑+1, 𝑒−𝑟 +1, 𝑒, 𝑝 1′ −1, 𝑝 2′ −1, ℎ−1) ; end leftmost(𝑑, 𝑠, 𝑒, 𝑝 1, 𝑝 2, ℎ) if ℎ = 0 thenreturn 0 ; 𝑟 ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑒) ; 𝑝 1′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝 1 ) ; 𝑝 2′ ← 𝑟𝑎𝑛𝑘 (𝐵𝑑 , 𝑠, 𝑠 + 𝑝 2 ) ; if 𝑠 ≤ 𝑒 − 𝑟 ∧ 𝑟𝑎𝑛𝑘 (𝐸𝑑+1, 𝑠 + 𝑝 1 − 𝑝 1′ + 1, 𝑠 + 𝑝 2 − 𝑝 2′ ) > 0 then return leftmost(𝑑 + 1, 𝑠, 𝑒 − 𝑟, 𝑝 1 − 𝑝 1′ , 𝑝 2 − 𝑝 2′ , ℎ − 1) ; end return 2ℎ + leftmost(𝑑 + 1, 𝑒 − 𝑟 + 1, 𝑒, 𝑝 1′ − 1, 𝑝 2′ − 1, ℎ − 1) ; Algorithm 5: The implementation of leap on our linear-space representation, simulating the graph 𝐺𝑡𝑡12 . The function receives the LTJ trie node that corresponds to the range [𝑠, 𝑒] at level 𝑑 of our structure, the local timestamps of interest 𝑝 1 = 𝑝𝑎−1 − 𝑠 and 𝑝 2 = 𝑝𝑏 − 𝑠, the minimum desired value 𝑥, and the BT height ℎ = ℓ. We assume that 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑖, 𝑖 − 1) returns 𝐸𝑑 [𝑖 − 1], assuming 𝐸𝑑 [0] = 0.

words, we must run the query on 𝐺 [𝑡1 ,𝑡2 ) ; recall Definition 7. A second one does not fix the exact times, but sets a minimum duration 𝛿 along which the reported solutions must hold [30].

D.1

Querying the Graph 𝐺 [𝑡1,𝑡2 )

The idea used to query 𝐺𝑡𝑡12 in optimal time can be extended to query 𝐺 [𝑡1 ,𝑡2 ) : 𝑟𝑎𝑛𝑘 (𝐸𝑑 , 𝑠 𝑣 + 𝑝 1, 𝑠 𝑣 + 𝑝 2 ) = 𝑝 2 − 𝑝 1 + 1 iff the node 𝑠 𝑣 exists throughout the whole period between the local offsets 𝑝 1 and 𝑝 2 . Therefore, we can use Algorithm 5 with the only change that we require that all the bits in the area of 𝐸𝑑 are 1s, not just one of them. This strategy does not yield worst-case time guarantees in terms of the size of 𝐺 [𝑡1 ,𝑡2 ) , however: it is possible that a BT node may have existed all along [𝑡 1, 𝑡 2 ), while none of its children have. We can therefore traverse large parts of the VBT just to find out that there are no matches of 𝑄 in 𝐺 [𝑡1 ,𝑡2 ) (which could even be empty). On the other hand, the algorithm is still wco with respect to the size of 𝐺𝑡 for any 𝑡 ∈ [𝑡 1, 𝑡 2 ): if the subtree of a node 𝑣 at depth 𝑑 does not exist in 𝐺𝑡 , then the corresponding bit 𝐸𝑑 will be zero and the algorithm will not attempt to explore it. Instead of satisfying the AGM bound on |𝐺 [𝑡1 ,𝑡2 ) | = | ∩𝑡 ∈ [𝑡1 ,𝑡2 ) 𝐺𝑡 |, we satisfy it in terms of min𝑡 ∈ [𝑡1 ,𝑡2 ) |𝐺𝑡 |. This proves the first part of Thm. 7.

D.2

Setting a minimum duration 𝛿

Consider the problem of solving a BGP on the triples (𝑠, 𝑝, 𝑜) of a temporal graph 𝐺 so that the BGP exists in 𝐺 during an interval of 𝛿 time units or more. We solve this query on 𝐺, adding the same variable 𝑡 as the fourth component of all the triple patterns, and use the LTJ tries where the time component t is at the end, as in join-first approaches. Note that those tries do not use the linear-space representation of Section 6. Instead, we will use a more sophisticated data structure to store the children of each LTJ trie node 𝑣 in order to obtain relevant time guarantees. Let 𝑢 1, . . . , 𝑢𝑘 be the children of node 𝑣, with increasing values 𝑥 1, . . . , 𝑥𝑘 . In addition to storing an array with the (values of) the nodes 𝑢 1, . . . , 𝑢𝑘 , we store 𝑘 points (𝑖, 𝛿𝑖 ) in a geometric grid, where 𝛿𝑖 is the longest duration of a tuple of 𝐺 stored below node 𝑢𝑖 (here we refer to the original durations of the tuples, before we mapped them to [0,𝑇 )). When it comes to solve leap(𝑣, 𝑥), we look for the point (𝑖, 𝛿𝑖 ) with minimum value 𝑖 such that 𝑥𝑖 ≥ 𝑥 and 𝛿𝑖 ≥ 𝛿. This is an orthogonal range geometric query in two dimensions, which a linear-space 19

P S

O

O O

S

P

T

T

O

S

S

T P

S S

O

P

P O

T

T

S

P

S

T

T

P

O

T

O

P

Figure 10: The meta-trie of all the LTJ tries we need to build.

data structure solves in 𝑂 (log 𝑁 ) time [16], thereby not affecting our complexities. Note that, as we represent times in T \ T𝐺 with their predecessors in T𝐺 , we work with the maximum possible durations and do not lose any solution. We leave variable 𝑡 to be bound at the end. When we reach the last level, t, in all the triple patterns of the BGP, we must intersect the 𝑚 time intervals, aiming again at finding time ranges of length at least 𝛿. In this level we also convert every node [ts𝑖 , tf𝑖 ) into a point (𝑖, 𝛿𝑖 ) of a two-dimensional grid, with 𝛿𝑖 the actual duration of the interval [ts𝑖 , tf𝑖 ). We can then run the intersection algorithm for the time level as described in Section 5.3 (precisely, the version with intervals of Algorithm 3), where leap(𝑣, 𝑡 0 ) is solved as follows. First we find 𝑖 such that (1) ts𝑖 ≤ 𝑡 0 < te𝑖 or (2) te𝑖 ≤ 𝑡 0 < ts𝑖+1 . In case (1), if the duration of [𝑡 0, te𝑖 ) is at least 𝛿,2 we return 𝑡 ∗ := 𝑡 0 . In any other case, the interval [ts𝑖 , te𝑖 ) is not useful and we search the grid for the point ( 𝑗, 𝛿 𝑗 ) with smallest coordinate 𝑗 such that 𝑗 > 𝑖 and 𝛿 𝑗 ≥ 𝛿. This yields the closest time interval to the right that contains an edge whose duration is long enough, and is found in 𝑂 (log 𝑁 ) time with the geometric data structure. It is easy to see that our search algorithm works exactly as if we had run the query on 𝐺, yet completely ignoring the edges shorter than 𝛿. This proves the second part of Thm. 7.

E

IMPLEMENTATION

Although our data structure uses linear space, the constant is high in practice because of the need to store 4! = 24 tries with all the possible orderings of {𝑠, 𝑝, 𝑜, 𝑡 }. Since each trie has 4 levels and all the tuples are mentioned once in every level before the time level and twice since the time level, a (slightly pessimistic) upper bound on the number of LTJ trie nodes stored is 156𝑁 for a temporal graph of 𝑁 tuples. Further, our representation for the trie levels requires two words per node (i.e., two events), and versioned tries after the time level require four words per node (i.e., each event induces ℓ in each bitvector 𝐵𝑑 and 𝐸𝑑 ), which sets the count to 228𝑁 words. The space for the trie pointers can in general be dismissed by using compact topology representations [32]. Considering that we need 5𝑁 words to represent the 𝑁 tuples (𝑠, 𝑝, 𝑜, [ti, tf ]) in raw form, the blowup factor in the space is 45.6. In order to reduce this overhead we make use of trie switching [8] and partial tries. Another space-saving device is the possibility of sharing trie prefixes. For example, the tries for spo and spto can share their first two levels; the nodes of the level sp concatenate two sequence of children: those of the trie that continues with o and those of the trie that continues with to. This can also be emulated with the succinct topology representations that do not use pointers [32], because we can simulate that they have a first child continuing with o and a second one with to. Our linear-space representation of Section 6 can be similarly adapted. Those fake pointers add up to 𝑂 (𝑁 ) bits of space. With these mechanisms, we can define a meta-trie that stores all the paths that are stored in the index; each path corresponds to a (possibly partial) LTJ trie. The shared paths in the meta-trie correspond to shared paths in the LTJ tries. Therefore, the number of nodes in the meta-trie correspond to the factor multiplying 𝑁 in our storage space, if multiplied by the appropriate factor: 1 for levels before time, 2 for the time level, 4 for the levels after time. Figure 10 contains a meta-trie that suffices to run LTJ on any instantiation order, and which uses just 76𝑁 , 15.2 times the space needed to store the raw data (our actual space in the experiments is 22% less because the higher trie levels have fewer than 𝑁 elements). To further reduce space, we use a recent compact trie representation [7] for the levels up to the time component; subsequent ones are implemented as described in Section 6.

F BENCHMARKS F.1 Generation of temporal intervals and tBGPs for Wikidata We convert the information of some qualifiers into temporal annotations for the corresponding triples. We distinguish 65 qualifiers of this kind. The ones leading to most timestamps are P580 (“start time”, 10,645,813 annotations), P582 (“end time”, 5,430,256 annotations), P585 (“point in time”, 3,023,126 annotations), and P577 (“publication date”, 1,408,894 annotations); the others produce from a few tens of thousand to as few as 2 annotations. Some qualifiers, like P580 and P582, are paired and used to produce a time interval (open to one side in case only one of the two qualifiers occurs; typically having only P580 implies that the triple is valid up to the present time); the others, like P585 and 2 How this is defined depends on how we model durations. For example, if T = N, we may understand that the interval [2, 3) has a duration of 1 (if we count the number of instants

it spans) or less than 1 (if we count its length on the real line). 20

P577, are used to produce an interval of only one time instant. All the granularities are uniformized to day-level. All the triples without temporal annotations are assumed to be valid for the whole universe of time instants; we say those temporal intervals are “trivial”. To generate tBGPs, we filter disconnected and duplicate BGPs (modulo graph isomorphism). In order to ensure that the BGPs we use for experiments are likely to touch the non-trivial temporal annotations, we define a score to prioritize BGPs with more triple patterns whose predicates have a higher ratio of triples with non-trivial temporal annotations. More specifically, for each predicate 𝑝𝑖 , in case it is a constant, we define 𝑟𝑖 as the ratio of triples with predicate 𝑝𝑖 that have non-trivial temporal annotations in the graph; otherwise, if 𝑝𝑖 is a variable, we Í define 𝑟𝑖 as 0. For each BGP extracted from the log of the form 𝑄 = {(𝑠 1, 𝑝 1, 𝑜 1 ), . . . , (𝑠𝑚 , 𝑝𝑚 , 𝑜𝑚 )}, we compute the score 𝑚 𝑖=1 𝑟 𝑖 . We then extract the top 1,000 BGPs from the query logs per this score. Further filtering BGPs with constants not appearing in the graph, we arrive at 972 queries. Finally, we extend each triple pattern with a shared temporal variable 𝑣 ∈ Vt to generate 𝑄 ′ = {(𝑠 1, 𝑝 1, 𝑜 1, 𝑣), . . . , (𝑠𝑚 , 𝑝𝑚 , 𝑜𝑚 , 𝑣)}.

F.2

Other datasets

We downloaded Divvy, Yellow and Caida datasets from Zhu et al. [57]. We have left the triple sets in our repository for reproducibility. Divvy records about 21 million trips of shared bikes in Chicago between 2013 and 2019, with start and end time: the source and target locations become the subject and object, and the type of bike is taken as the predicate, leading to 6,525 different predicates (and 633 nodes). We downloaded it from https://divvybikes.com/system-data. Yellow records about 33 million taxi trips in New York City from 2022, also with start and end time: the source and target locations become again the subject and object, but this time the predicate is chosen to be the distance travelled. This leads to 8,289 predicates (and 263 nodes). We downloaded it from TLC Trip Record Data, https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page (the “Yellow Taxi Trip Records” of 2022, in PARQUET format). Caida records about 16 million relations between autonomous systems on the Internet from 1998 to 2026. We downloaded it from The CAIDA AS Relationships Dataset, https://www.caida.org/catalog/datasets/as-relationships/, subdirectories serial-1/ and serial-2/. Edges have no labels (i.e., there is only one label) and span only one time instant; we join successive times of an edge into maximal ranges. The graph has 110,703 nodes.

G

DYNAMISM

Our data structure supports efficiently updating the graph with newer events, that is, insertion and removal of edges with progressively larger timestamps. The core data structure that must be updated is the linear-space one of Section 6. Adding a new event at time 𝐿 + 1 (e.g., at time 7 in Figure 7) for some 𝑣𝑖 implies appending a bit to the corresponding 𝑏ℓ bitvectors 𝑣.𝐵 [1, 𝐿𝑣 ] and 𝑣.𝐸 [1, 𝐿𝑣 ]. Let 𝑣 be the root node. We first increment 𝐿𝑣 . Now, if 𝑣𝑖 is stored in the left child of 𝑣 (i.e., the first of the 𝑏ℓ bits of 𝑣𝑖 is a 0), we set 𝑣.𝐵 [𝐿𝑣 ] ← 0 and continue recursively at the left child; otherwise we set 𝑣.𝐵 [𝐿𝑣 ] ← 1 and continue recursively at the right child. We continue descending, according to the following bits of 𝑣𝑖 , until reaching the leaves, where nothing is done. At the return of the recursion we set the values 𝑣 .𝐸 [𝐿𝑣 ]. As explained, a leaf is empty iff it holds an even number of events, whereas an internal node 𝑢 is empty iff 𝑢.𝐸 [𝐿𝑣 ] = 0. We then set 𝑣 .𝐸 [𝐿𝑣 ] ← 0 if both children of 𝑣 are empty or nonexistent, otherwise we set 𝑣.𝐸 [𝐿𝑣 ] ← 1. We must also update the data structures to compute 𝑟𝑎𝑛𝑘 (and 𝑠𝑒𝑙𝑒𝑐𝑡 if needed, see Appendix C), so as to account for the bits appended to 𝑣.𝐵 and 𝑣.𝐸. Those structures [17, 43] are arrays that summarize information on successive blocks of the bitvectors, so when the bitvectors grow, only a constant amount of work is needed to update the information on the last block or to append a new block. Overall, adding a new event in the linear-space data structure takes time 𝑂 (𝑏ℓ) = 𝑂 (log 𝑁 ). In the dynamic structure, we cannot concatenate all the bitvectors of each level 𝑑 into a single one, 𝐵𝑑 and 𝐸𝑑 , because appending bits to node bitvectors 𝑣 .𝐵 or 𝑣.𝐸 would require inserting bits in the middle of some 𝐵𝑑 or 𝐸𝑑 , and that cannot be done in constant time. Instead, we maintain separate bitvectors 𝑣.𝐵 and 𝑣.𝐸 for each node 𝑣. We had avoided this to prevent spending 𝑂 (𝐿 log 𝑁 ) space for node data, as there can be up to 𝐿 · 𝑏ℓ nodes overall. Another bound to the number of nodes, however, is 𝑁 , because there are at most 𝑁 distinct leaves and thus 𝑂 (𝑁 ) internal nodes; the added space is then 𝑂 (𝑁 ) (i.e., 𝑂 (𝑁 log 𝑁 ) bits), which is also linear in the graph size. This works because, as shown in Figure 10, we will store only one copy of the linear-space data structure (the leftmost trie in the figure, with this structure at the root). The bitvectors 𝑣.𝐵 and 𝑣.𝐸, and their additional 𝑟𝑎𝑛𝑘 and 𝑠𝑒𝑙𝑒𝑐𝑡 data structures, can be stored as “extendible arrays” [12], which √︁ support accessing and extending them in constant worst-case time with an additional space overhead of only 𝑂 ( 𝐿 log 𝑁 + 𝑁 log 𝑁 ) bits. Given the current time range [0,𝑇 ), a new triple (𝑠, 𝑝, 𝑜) that is inserted or deleted at time 𝑇 (which expands the time range to [0,𝑇 + 1)) requires inserting 𝑠𝑝𝑜, 𝑠𝑜, 𝑝𝑜𝑠, 𝑝𝑠, 𝑜𝑠𝑝, and 𝑜𝑝 in the leftmost trie of Figure 10. Each such string represents the 𝑏ℓ-bit descriptions we insert in the linear-space data structure as discussed so far. We must also insert the triple in the other tries of Figure 10: 𝑝𝑡, 𝑝𝑜𝑡, 𝑝𝑜𝑠, 𝑝𝑠, 𝑜𝑡, 𝑜𝑠𝑡, 𝑜𝑠𝑝, 𝑜𝑝, 𝑠𝑡, 𝑠𝑝𝑡, 𝑠𝑝𝑜𝑡, and 𝑠𝑜. Note that some of those paths do not have a time component (e.g., 𝑝𝑜𝑠) and thus correspond to normal tries indicating which strings exist at some time instant. Those tries can be implemented as classic structures, turning the array of children of each node (that we used to binary search for the desired child) into balanced trees to allow insertions and searches in 𝑂 (log 𝑁 ) time. We never delete strings (e.g., 𝑝𝑜𝑠) in those tries, as all of them existed at some point; we only add new ones upon insertions. The remaining tries have the time component at their last level (e.g., 𝑝𝑜𝑡). In those last levels we store a sequence of time intervals [𝑡𝑠𝑖 , 𝑡𝑒𝑖 ), as described in Section 5.1. In the dynamic case, we must allow writing 𝑡𝑒𝑖 = +∞ in the last range so that it extends automatically to the 21

current last time when 𝑇 increases. For example, in the trie 𝑝𝑜𝑡, the time level stores the intervals in which each string 𝑝𝑜 existed in the graph. We must then include 𝑇 in this last level. When inserting (𝑠, 𝑝, 𝑜) at time 𝑇 , if the last range is of the form [𝑡𝑠𝑖 , 𝑡𝑒𝑖 ) with 𝑡𝑒𝑖 ≠ +∞, we add a new range [𝑇 , +∞). When deleting (𝑠, 𝑝, 𝑜) at time 𝑇 , then the last range [𝑡𝑠𝑖 , +∞) is converted to [𝑡𝑠𝑖 ,𝑇 ). Overall, we can retain the time complexities of the structure described in the paper, as well as its linear space, and can add new events at increasing timestamps in time 𝑂 (log 𝑁 ).

22

Related documents

• TrajectoryDB: A New Database for Agent Trajectories#673620
• Preserving contextual information in cultural heritage metadata through multidimensional knowledge graphs#673621
• X-DigCheck: Co-Evolving Application Profiles and Knowledge Graphs, Demonstrated on the RTI Documentation of Rupe Magna#673622
• Open Tabular Insight Extraction: Where Do We Stand, and Where Should We Go?#673623
• Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families#673624