论文标题
与图形生成依赖关系的属性图上的推理
Reasoning on Property Graphs with Graph Generating Dependencies
论文作者
论文摘要
图生成依赖关系（GGD）在两个（可能不同）的图形模式之间非正式地表达约束，这些图形模式在图形数据（通过属性值约束）及其结构（通过拓扑约束）上都强化了关系。图生成依赖关系（GGD）可以表达对属性图的元组和等值的依赖性，这两者都在图数据管理中找到了广泛的应用。在本文中，我们讨论了GGD背后的推理。我们提出了算法来解决GGD的满意度，含义和验证问题并分析其复杂性。为了证明GGD的实际使用，我们提出了一种算法，该算法通过验证GGD发现数据不一致。我们的实验表明，即使GGD的验证具有较高的计算复杂性，GGD也可用于在合成和现实世界中可行的执行时间内找到数据不一致。
Graph Generating Dependencies (GGDs) informally express constraints between two (possibly different) graph patterns which enforce relationships on both graph's data (via property value constraints) and its structure (via topological constraints). Graph Generating Dependencies (GGDs) can express tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. In this paper, we discuss the reasoning behind GGDs. We propose algorithms to solve the satisfiability, implication, and validation problems for GGDs and analyze their complexity. To demonstrate the practical use of GGDs, we propose an algorithm which finds inconsistencies in data through validation of GGDs. Our experiments show that even though the validation of GGDs has high computational complexity, GGDs can be used to find data inconsistencies in a feasible execution time on both synthetic and real-world data.
