2022/11/01 by Larissa C. Shimomura, Shimomura, Larissa C., Nikolay Yakovets +3 · 1 citation
Computer Science · Decision Sciences · #Data Management and Algorithms #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #H.2 #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2211.00387
openalex publication_date 2022/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.