论文标题
RPQ的基于运行的语义
Run-Based Semantics for RPQs
论文作者
论文摘要
RPQS（常规路径查询）的形式主义是图形数据库的大多数查询语言的重要组成部分。通常在同态语义下评估RPQ；特别是仅返回匹配步行的端点。实际应用通常需要进行完整的步行以计算汇总值。在这种情况下，同态语义不合适，因为匹配的步行数量可能是无限的。因此，图形数据库引擎适应了RPQ的语义，通常会忽略理论危险信号。例如，流行的查询语言Cypher使用TRAIL语义，从而确保其结果是有限的，以使计算问题变得棘手。 我们为RPQ提出了一种新的语义，包括简单运行和结合轨道语义，作为将理论考虑与实际愿望调和的候选人。两者都确保输出以与同态语义相兼容的方式是有限的：端点上的投影与同态语义相吻合。因此，测试结果的空虚是可探讨的，并且很容易应用已知的方法。此外，简单运行和绑定 - 轨道语义语义支持袋语义，以及结果袋的列举是可行的
The formalism of RPQs (regular path queries) is an important building block of most query languages for graph databases. RPQs are generally evaluated under homomorphism semantics; in particular only the endpoints of the matched walks are returned. Practical applications often need the full matched walks to compute aggregate values. In those cases, homomorphism semantics are not suitable since the number of matched walks can be infinite. Hence, graph-database engines adapt the semantics of RPQs, often neglecting theoretical red flags. For instance, the popular query language Cypher uses trail semantics, which ensures the result to be finite at the cost of making computational problems intractable. We propose a new kind of semantics for RPQs, including in particular simple-run and binding-trail semantics, as a candidate to reconcile theoretical considerations with practical aspirations. Both ensure the output to be finite in a way that is compatible with homomorphism semantics: projection on endpoints coincides with homomorphism semantics. Hence, testing the emptiness of result is tractable, and known methods readily apply. Moreover, simple-run and binding-trail semantics support bag semantics, and enumeration of the bag of results is tractable
