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.
翻译:图形产生依赖性(GGDs) 非正式地表达了两种(可能不同的)图形模式之间的制约,这些模式在图形数据(通过财产价值限制)及其结构(通过地形限制)上强制执行关系。 图表产生依赖性(GGDs)可以在财产图上表示图象和平等产生依赖性,两者在图形数据管理中都得到广泛应用。在本文中,我们讨论了GGGDs背后的推理。我们提出了各种算法,以解决GGGDs的可诉性、影响和验证问题,并分析其复杂性。为了展示GGGDs的实际用途,我们提出了一种算法,通过GGDs的验证发现数据中的不一致。我们的实验表明,即使GGDs的验证在计算上非常复杂,GGDs也可以在合成数据和现实世界数据的可行执行时间内找到数据不一致之处。