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: hf9c83539848db5b5
Venue: VLDB
Year: 2019
Pagerank: 5.3399392e-05
Overall Rank: 8,398 | 43.54%
DOI: 10.14778/3317315.3317318

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; Shenzhen University; University of Edinburgh)
2. Ping Lu (Beihang University)
3. Chao Tian (Alibaba)
4. Jingren Zhou (Alibaba)

BibTeX Citation

@article{fan_vldb19,
        title = {{Deducing Certain Fixes to Graphs}},
        author = {Fan, Wenfei and Lu, Ping and Tian, Chao and Zhou, Jingren},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {7},
        pages = {752--765},
        doi = {10.14778/3317315.3317318},
        url = {https://doi.org/10.14778/3317315.3317318},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,513	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0986544e-05
7,872	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	5.4362062e-05
8,293	Capturing Associations in Graphs	2020	VLDB	5.3612871e-05
9,616	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.1510548e-05
9,806	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1257999e-05
10,707	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.9793485e-05
11,186	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9793485e-05
11,563	Extending Graph Rules with Oracles	2024	VLDB	4.9793485e-05
11,623	Graph Association Analyses for Early Drug Discovery	2024	VLDB	4.9793485e-05
11,738	Splitting Tuples of Mismatched Entities	2023	SIGMOD	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
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025872962
716	Guided Data Repair	2011	VLDB	0.00014553463
888	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00013255989
989	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.0001265344
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011627329
1,308	Automating Large-Scale Data Quality Verification	2018	VLDB	0.0001107886
2,055	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.1128336e-05
2,364	Dependencies for Graphs	2017	PODS	8.5665938e-05
2,423	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4877894e-05
2,784	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.018482e-05
2,948	Distributed Data Deduplication	2016	VLDB	7.8230494e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
3,273	Large-Scale Collective Entity Matching	2011	VLDB	7.471033e-05
3,317	Keys for Graphs	2015	VLDB	7.436464e-05
3,409	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3264601e-05
5,645	Repairing Vertex Labels under Neighborhood Constraints	2014	VLDB	6.0533594e-05
5,953	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.9359492e-05
6,440	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	5.7842039e-05
7,243	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5768239e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,153	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD
2	10,707	Repairing Property Graphs under PG-Constraints	2026	VLDB
3	2,784	Interaction between Record Matching and Data Repairing	2011	SIGMOD
4	1,348	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
5	12,333	QFix: Demonstrating Error Diagnosis in Query Histories	2016	SIGMOD
6	526	Improving Data Quality: Consistency and Accuracy	2007	VLDB
7	11,121	User-Centric Property Graph Repairs	2025	SIGMOD
8	4,827	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD
9	989	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB
10	2,964	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD