论文标题
表示图形数据库模式匹配中的路径
Representing Paths in Graph Database Pattern Matching
论文作者
论文摘要
现代的图形数据库查询语言，例如GQL，SQL/PGQ及其学术前任G-core，可以将符合常规路径查询的路径返回给用户，从而促进对一流公民的路径。这在效率方面带来了许多挑战，这是因为图形在给定节点对之间可以有大量路径。 我们介绍了路径多组表示（PMR）的概念，该表示可以以指数为简洁的方式表示路径的多集。在探索了PMR的最小化和等效测试之类的基本问题之后，我们探索了它们的使用如何在执行查询计划时导致大量时间和空间节省。我们表明，从计算复杂性的角度来看，PMR似乎特别适合代表常规路径查询的结果以及其涉及计数，随机抽样，工会和联接的结果。
Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that paths that match regular path queries can be returned to the user. This brings a number of challenges in terms of efficiency, caused by the fact that graphs can have a huge amount of paths between a given node pair. We introduce the concept of path multiset representations (PMRs), which can represent multisets of paths in an exponentially succinct manner. After exploring fundamental problems such as minimization and equivalence testing of PMRs, we explore how their use can lead to significant time and space savings when executing query plans. We show that, from a computational complexity point of view, PMRs seem especially well-suited for representing results of regular path queries and extensions thereof involving counting, random sampling, unions, and joins.
