Fast interval joins for temporal SPARQL queries

Knowledge graphs enriched with temporal information are becoming more and more common. As an example, the Wikidata KG contains millions of temporal facts associated with validity intervals (i.e., start and end time) covering a variety of domains. While these facts are interesting, computing temporal relations between their intervals allows to discover temporal relations holding between facts (e.g., “football players that get divorced after moving from a team to another"). In this paper we study the problem of computing different kinds of interval joins in temporal KGs. In principle, interval joins can be computed by resorting to query languages like SPARQL. However, this language is not optimized for such a task, which makes it hard to answer real-world queries. For instance, the query “find players that were married while being member of a team" times out on Wikidata. We present efficient algorithms to compute interval joins for the main Allen's relations (e.g., before, after, during, meets). We also address the problem of interval coalescing, which is used for merging contiguous or overlapping intervals of temporal facts, and propose an efficient algorithm. We integrate our interval joins and coalescing algorithms into a light SPARQL extension called iSPARQL. We evaluated the performance of our algorithms on real-world temporal kgs.