Normalizing Property Graphs

Summary: Introduces functional dependencies for property graphs, with linear-time implication, enabling label/property-targeted normalization. Decomposes graphs losslessly into BCNF when possible (otherwise 3NF), reducing redundancy and update costs while exposing inconsistencies and accelerating aggregates. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13330
Venue: VLDB
Year: 2023
Pagerank: 6.1205402e-05
Overall Rank: 5,690 | 60.97%
DOI: 10.14778/3611479.3611506

Incoming Non-self Citations Over Time

Authors

1. Philipp Skavantzos (University of Auckland)
2. Sebastian Link (University of Auckland)

BibTeX Citation

@article{skavantzos_vldb23,
        title = {{Normalizing Property Graphs}},
        author = {Skavantzos, Philipp and Link, Sebastian},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {3031--3043},
        doi = {10.14778/3611479.3611506},
        url = {https://doi.org/10.14778/3611479.3611506},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,187	Transforming Property Graphs	2024	VLDB	5.3058708e-05
10,538	Structural Normalization of Property Graphs	2026	VLDB	5.093636e-05
10,665	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	5.093636e-05
10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD	5.093636e-05
11,064	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	5.093636e-05
11,221	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	5.093636e-05
11,301	DTGraph: Declarative Transformations of Property Graphs	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
540	Synthesizing Independent Database Schemas	1979	SIGMOD	0.0001686137
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
1,661	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010079134
2,324	Dependencies for Graphs	2017	PODS	8.7506505e-05
2,861	PG-Keys: Keys for Property Graphs	2021	SIGMOD	8.0212883e-05
2,973	Functional Dependencies for Graphs	2016	SIGMOD	7.9083516e-05
3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2602055e-05
7,099	Discovering Graph Functional Dependencies	2018	SIGMOD	5.7043774e-05
7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.6776392e-05
8,137	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.4809275e-05
11,379	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	5.093636e-05
11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.093636e-05
12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,993	Normalizing Incomplete Databases	1995	PODS
2	2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD
3	4,320	Normalization and Optimization of Schema Mappings	2009	VLDB
4	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
5	11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD
6	12,679	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
7	4,232	A Unified Approach to Functional Dependencies and Relations	1975	SIGMOD
8	10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD
9	12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
10	10,538	Structural Normalization of Property Graphs	2026	VLDB