Normalizing Property Graphs

Summary: Defines a class of functional dependencies for property graphs with linear-time implication checking and a flexible, label/property-targeted normalization procedure that yields BCNF when possible and guarantees 3NF otherwise. Empirically removes redundancy, detects inconsistencies via dependency violations, cuts update costs by orders of magnitude, and speeds up aggregate queries significantly. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13142
Venue: VLDB
Year: 2023
Pagerank: 5.2768691e-05
Overall Rank: 5,910 | 58.89%
DOI: 10.14778/3611479.3611506

Incoming Non-self Citations Over Time

Authors

1. Philipp Skavantzos
2. Sebastian Link

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,037	Transforming Property Graphs	2024	VLDB	4.4039656e-05
10,250	Structural Normalization of Property Graphs	2026	VLDB	4.1945683e-05
10,376	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.1945683e-05
10,508	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	4.1945683e-05
10,839	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	4.1945683e-05
11,010	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.1945683e-05
11,095	DTGraph: Declarative Transformations of Property Graphs	2024	VLDB	4.1945683e-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
356	Synthesizing Independent Database Schemas	1979	SIGMOD	0.00026034713
1,047	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014459715
1,785	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010560236
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
3,306	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.2437997e-05
3,818	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	6.7300958e-05
6,703	Discovering Graph Functional Dependencies	2018	SIGMOD	4.9555163e-05
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
8,085	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	4.5902231e-05
11,173	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	4.1945683e-05
11,490	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	4.1945683e-05
11,854	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,799	Normalizing Incomplete Databases	1995	PODS	4.1945683e-05
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
4,752	Normalization and Optimization of Schema Mappings	2009	VLDB	5.9481448e-05
6,180	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.1686632e-05
11,490	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	4.1945683e-05
12,486	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS	4.1945683e-05
1,813	A Unified Approach to Functional Dependencies and Relations	1975	SIGMOD	0.00010464576
10,508	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	4.1945683e-05
11,854	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD	4.1945683e-05
10,250	Structural Normalization of Property Graphs	2026	VLDB	4.1945683e-05