Design Foundations of Graph Databases

The property graph model and graph database management systems such as Neo4j have become increasingly popular. Naturally, questions around graph data modelling best practices arise. Graph databases are perceived as very intuitive and our research will provide evidence to showcase their benefits. One of our main contributions is formalising the observation that hierarchical property graphs provide a graph semantics to the Entity-Relationship model (E/R model) and vice versa Entity-Relationship diagrams (E/R diagrams) impart a schema framework to hierarchical property graphs. While the E/R model is well-established with comprehensive research that spans more than 40 years, surprisingly this observation has not been stated or formalised so far. Moreover, hierarchical property graphs constitute a natural graph semantics for E/R diagrams, namely in the form of homomorphisms on E/R diagrams. We will call such property graphs E/R graphs. This outlines how graphs unify conceptual and logical data modelling which showcases an opportunity to overcome shortcomings of the relational data model for integrity management. One fundamental goal in database design is to eliminate redundancy, yet even Inclusion Dependency Normal Form relies on attribute duplication introduced through foreign keys to establish referential integrity. Interestingly, edges in property graphs can avoid such attribute redundancy completely. Furthermore, we introduce E/R keys, an expressive yet efficient subclass of the previously proposed PG-Keys and demonstrate how they improve entity and referential integrity management. Another major contribution is the first ever establishment of a normalisation framework that accommodates any interpretation of missing data in response to the data variety dimension graph databases are expected to handle as No-SQL databases. To this end, we introduce redundancy-causing graph functional dependencies that are transformed into graph uniqueness constraints that avoid redundancy. These dependencies strike a great balance between expressiveness and tractability as required for a normalisation framework. Despite the major challenge of property graphs not necessarily having a schema, our functional dependencies and uniqueness constraints also enable us to extend the entire classical relational normalisation framework of Boyce-Codd and Third Normal Forms to property graphs.

Name thesis:degree_name

PhD

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

ResearchSpace@Auckland

Year dc:date.issued

2025

Author dc:creator

• Skavantzos, Philipp

Advisors dc:contributor.advisor

• Link, Sebastian
• Zhao, Kaiqi

• Database Design
• Graph Database
• Integrity Constraints

Statement dc:rights

• Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Licence dc:rights.uri

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Handle dc:identifier.uri

https://hdl.handle.net/2292/71411

OAI identifier oai:identifier

oai:researchspace.auckland.ac.nz:2292/71411