Structural Normalization of Property Graphs

A property graph stores information in the form of a network of nodes and edges, annotated with labels and properties (i.e. attributes). Even though various forms of functional dependencies, uniqueness constraints, and keys have been proposed for graph data, no study has been hitherto undertaken that builds upon and utilizes these concepts to assemble a comprehensive proposal for graph normalization. An elementary proposal merely maps the nodes in the graph schema to a relational schema and deploys relational normalization techniques. Unfortunately, this proposal disregards the graph structure and thereby forfeits the opportunity for structural normalization. In this paper, we define five structural graph normal forms that extend relational normal forms building on concepts of keys and graph functional dependencies. Based on acyclic graph patterns, these normal forms apply to any data graph, address previously overlooked sources of inconsistency, and support structure-aware integrity preservation beyond node attributes. We showcase the applicability and effectiveness of these normal forms through experimentation.