  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.
