Deducing Certain Fixes to Graphs

Summary: Proposes deducing certain, guaranteed-correct fixes to graphs from data quality rules Sigma and ground truth Gamma. Two regimes: online interactive fixes on a small vertex set V0, and offline full-graph repair with guaranteed correctness; uses conditional FDs, recursive keys, and negative rules; proves Church–Rosser convergence and offers parallel, scalable algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12003
Venue: VLDB
Year: 2019
Pagerank: 4.5311185e-05
Overall Rank: 8,363 | 41.88%
DOI: 10.14778/3317315.3317318

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,563	Big Graphs: Challenges and Opportunities	2022	VLDB	5.4328211e-05
8,145	Capturing Associations in Graphs	2020	VLDB	4.5724134e-05
9,354	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	4.3484715e-05
9,439	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	4.3389137e-05
9,489	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	4.3300131e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05
10,496	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.1905499e-05
11,019	Extending Graph Rules with Oracles	2024	VLDB	4.1905499e-05
11,101	Graph Association Analyses for Early Drug Discovery	2024	VLDB	4.1905499e-05
11,225	Splitting Tuples of Mismatched Entities	2023	SIGMOD	4.1905499e-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
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
268	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00029739054
686	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00018107664
830	Guided Data Repair	2011	VLDB	0.00016125759
1,160	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.0001358129
1,481	Automating Large-Scale Data Quality Verification	2018	VLDB	0.00011715754
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
2,417	Combining Quantitative and Logical Data Cleaning	2016	VLDB	8.8502556e-05
2,517	Dependencies for Graphs	2017	PODS	8.6058545e-05
2,728	Keys for Graphs	2015	VLDB	8.2228869e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
3,000	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	7.7447724e-05
3,478	Functional Dependencies for Graphs	2016	SIGMOD	7.0554625e-05
3,526	Distributed Data Deduplication	2016	VLDB	7.0056559e-05
3,570	Large-Scale Collective Entity Matching	2011	VLDB	6.9563715e-05
4,112	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	6.4329055e-05
5,881	Repairing Vertex Labels under Neighborhood Constraints	2014	VLDB	5.2872198e-05
6,119	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.1991813e-05
7,120	Discovering Graph Functional Dependencies	2018	SIGMOD	4.8200122e-05
7,587	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	4.6999342e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,450	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD	4.1905499e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
1,625	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB	0.0001109361
11,845	QFix: Demonstrating Error Diagnosis in Query Histories	2016	SIGMOD	4.1905499e-05
621	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018978331
5,454	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD	5.4967096e-05
10,406	User-Centric Property Graph Repairs	2025	SIGMOD	4.1905499e-05
1,160	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.0001358129
3,198	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD	7.4029546e-05