标题： 时间路径查询的紧凑答案 显示英文标题

标题： Compact Answers to Temporal Path Queries

摘要： 我们研究基于路径的图查询，除了通过边进行导航外，还通过时间进行导航。 这使得可以提出关于网络动态的问题，如交通流动、因果关系或疾病的传播。 在这种情况下，图由带有有效区间注释的三元组组成，查询生成节点对，每个对与一个随时间变化的二元关系相关联。 例如，这样的对可以是两个机场，时间关系可以将可能的出发时间映射到可能的到达时间。 一个开放性问题是如何以紧凑的形式表示这种关系，并在查询评估过程中保持这一特性。 我们研究了四种针对此类查询答案的紧凑表示方法，这些方法基于编码区间集合的不同方式。 我们讨论了它们在简洁性、唯一性和计算成本方面的优缺点。 值得注意的是，最精细的编码保证了对密集时间的查询答案可以有限表示。 显示英文摘要

摘要： 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. We investigate four compact representations of answers to a such queries, which are based on alternative ways to encode sets of intervals. 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.