Knowledge graphs have soared in popularity by supporting different types of applications and domains. In this context, the property graph data model has become an emerging standard in industry and academia. With its widespread use, there is also an increasing interest in investigating constraints for property graph data and their applications in data profiling. Graph Generating Dependencies (GGDs) are a class of property graph data dependencies that can express constraints on topology and properties of nodes and edges of the graph, making them a suitable candidate to expose an overview of the property graph to the user (profile graph data). However, GGDs can be difficult to set manually. To solve this issue, we propose a framework for discovering GGDs automatically from the property graph to profile graph data. Our framework has three main steps: (1) pre-processing, (2) candidate generation, and, (3) GGD extraction. Our results show that the discovered set of GGDs can give an overview of the input graph, including schema-level information between the graph patterns and attributes.

Data dependencies are a key concept in data management and have been researched in data integration, data quality and query optimization. With the increasing use of graph-structured data in diverse applications, there is also an increasing interest in the study of graph data dependencies. In this scenario different classes of graph data dependencies have been proposed in the literature. In this work we study the class of Graph Generating Dependencies (GGDs). 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). While most of previously proposed classes of graph data dependencies focus on generalizing equality-generating dependencies for graph data, Graph Generating Dependencies (GGDs) can express tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. Given this new class of dependency, in this paper, we discuss the reasoning behind GGDs on Property Graphs. We propose algorithms to solve three main reasoning problems: the satisfiability, implication, and validation problems for GGDs and analyze their complexity. By studying these problems, we can understand the expressiveness and the limitations of GGDs in practical applications. To demonstrate the practical use of GGDs, we propose an algorithm that 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.

We propose Graph Generating Dependencies (GGDs), a new class of dependencies for property graphs. Extending the expressivity of state of the art constraint languages, GGDs can express both tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. We provide the formal definition of GGDs, analyze the validation problem for GGDs, and demonstrate the practical utility of GGDs.