Chen's Entity/Relationship (E/R) framework is a lingua franca for well-designed databases. We define E/R graphs as property graphs that are instances of E/R diagrams. As the latter are a subclass of PG-Schema, E/R modeling constitutes a methodology for designing graph databases that guarantee data integrity, the absence of data redundancy and update anomalies. In addition, E/R graphs provide the first graph semantics for E/R diagrams. Further to the unification of conceptual and graph data modeling, referential integrity for E/R graphs can be managed by directed edges, called E/R links, between nodes. As a consequence, redundancy and sources of potential inconsistency can be eliminated, minimizing update maintenance. This is achieved by E/R keys that use properties and E/R links to enforce entity integrity, in contrast to property keys that rely exclusively on properties to enforce entity integrity. We use the TPC-H benchmark as running example and for extensive experiments that quantify the effort for i) managing entity integrity using property keys or E/R keys, ii) managing referential integrity using property redundancy or E/R links, iii) query evaluation. In summary, E/R diagrams form a principled core of PG-Schema for well-designed property graphs, while E/R keys constitute an efficient core of PG-Key for data integrity management.

This tutorial shows how traditional Entity/Relationship modeling and modern graph data modeling can be combined to bring forward well-designed graph data models that process workloads and maintain data integrity efficiently.

Abstract Normalization minimizes sources of potential data inconsistency and costs of update maintenance incurred by data redundancy. For relational databases, different classes of dependencies cause data redundancy and have resulted in proposals such as Third, Boyce–Codd, Fourth and Fifth Normal Form. Features of more advanced data models make it challenging to extend achievements from the relational model to missing, non-atomic, or uncertain data. We initiate research on the normalization of graph data, starting with a class of functional dependencies tailored to property graphs. We show that this class captures important semantics of applications, constitutes a rich source of data redundancy, its implication problem can be decided in linear time, and facilitates the normalization of property graphs flexibly tailored to their labels and properties that are targeted by applications. We normalize property graphs into Boyce–Codd Normal Form without loss of data and dependencies whenever possible, but guarantee Third Normal Form in general. Experiments on real-world property graphs quantify and qualify various benefits of graph normalization: (1) removing redundant property values as sources of inconsistent data, (2) detecting inconsistency as violation of functional dependencies, (3) reducing overheads for updates by orders of magnitude, and (4) significant speed ups of queries.

Normalization aims at minimizing sources of potential data inconsistency and costs of update maintenance incurred by data redundancy. For relational databases, different classes of dependencies cause data redundancy and have resulted in proposals such as Third, Boyce-Codd, Fourth and Fifth Normal Form. Features of more advanced data models make it challenging to extend achievements from the relational model to missing, non-atomic, or uncertain data. We initiate research on the normalization of graph data, starting with a class of functional dependencies tailored to property graphs. We show that this class captures important semantics of applications, constitutes a rich source of data redundancy, its implication problem can be decided in linear time, and facilitates the normalization of property graphs flexibly tailored to their labels and properties that are targeted by applications. We normalize property graphs into Boyce-Codd Normal Form without loss of data and dependencies whenever possible for the target labels and properties, but guarantee Third Normal Form in general. Experiments on real-world property graphs quantify and qualify various benefits of graph normalization: 1) removing redundant property values as sources of inconsistent data, 2) detecting inconsistency as violation of functional dependencies, 3) reducing update overheads by orders of magnitude, and 4) significant speed ups of aggregate queries.