Repairing Property Graphs under PG-Constraints

Summary: Studies repair of property graphs under PG-Constraints, a recursive denial-constraint fragment amenable to automata-based error analysis. Proposes topology/label-deletion repair pipeline and compares ILP, naive, and LP-guided greedy strategies; labels cut deletions 59%, greedy matches ILP quality with up to 97% faster runtime. (summarized by gpt-5.4-mini on Apr 12 2026)

Paper ID: hd34eef4c50b86cb9
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,707 | 28.02%
DOI: 10.14778/3797919.3797929

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Christopher Spinrath (CNRS; University of Lyon)
2. Angela Bonifati (CNRS; Institut Universitaire de France; University of Lyon)
3. Rachid Echahed (CNRS; Université Grenoble Alpes)

BibTeX Citation

@article{spinrath_vldb26,
        title = {{Repairing Property Graphs under PG-Constraints}},
        author = {Spinrath, Christopher and Bonifati, Angela and Echahed, Rachid},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {6},
        pages = {1212--1225},
        doi = {10.14778/3797919.3797929},
        url = {https://doi.org/10.14778/3797919.3797929},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,970	PGShield: Maintaining Path Constraints in Property Graphs	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049349003
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025872962
500	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017280722
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
1,043	Data Cleaning: Overview and Emerging Challenges	2016	SIGMOD	0.00012335114
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010566509
1,482	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010538703
1,494	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	0.00010502195
2,831	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9602632e-05
4,965	GPC: A Pattern Calculus for Property Graphs	2023	PODS	6.3360914e-05
7,226	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5810344e-05
7,359	Schema Mappings for Data Graphs	2017	PODS	5.5428964e-05
7,627	When is the Evaluation of Extended CRPQ Tractable?	2022	PODS	5.4814676e-05
8,362	Conjunctive Regular Path Queries under Injective Semantics	2023	PODS	5.3473243e-05
8,398	Deducing Certain Fixes to Graphs	2019	VLDB	5.3399392e-05
9,004	The Cost of Representation by Subset Repairs	2025	VLDB	5.2389669e-05
9,801	Incremental Detection of Denial Constraint Violations	2025	VLDB	5.1257999e-05
9,806	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1257999e-05
11,121	User-Centric Property Graph Repairs	2025	SIGMOD	4.9793485e-05
11,153	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,803	Efficient Query Repair for Aggregate Constraints	2026	VLDB
2	11,153	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD
3	8,398	Deducing Certain Fixes to Graphs	2019	VLDB
4	11,428	Versatile Property Graph Transformations	2025	VLDB
5	5,798	Normalizing Property Graphs	2023	VLDB
6	5,779	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
7	5,645	Repairing Vertex Labels under Neighborhood Constraints	2014	VLDB
8	10,970	PGShield: Maintaining Path Constraints in Property Graphs	2026	VLDB
9	188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD
10	11,121	User-Centric Property Graph Repairs	2025	SIGMOD