Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases

Abstract

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.