Abstract
We study path-based graph queries that, in addition to navigation through edges, also perform navigation through time. This allows asking questions about the dynamics of networks, like traffic movement, cause-effect relationships, or the spread of a disease. In this setting, a graph consists of triples annotated with validity intervals, and a query produces pairs of nodes where each pair is associated with a binary relation over time. For instance, such a pair could be two airports, and the temporal relation could map potential departure times to possible arrival times. An open question is how to represent such a relation in a compact form, and maintain this property during query evaluation. To address this, we investigate four compact representations of answers to a such queries. We discuss their respective advantages and drawbacks, in terms of conciseness, uniqueness, and computational cost. Notably, the most refined encoding guarantees that query answers over dense time can be finitely represented.