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.3198062e-05
Overall Rank: 8,420 | 43.56%
DOI: 10.14778/3317315.3317318
PDF: Download (CC BY-NC-ND 4.0)

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 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,496	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0944008e-05
7,892	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	5.4156936e-05
8,313	Capturing Associations in Graphs	2020	VLDB	5.3410298e-05
9,634	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.1354312e-05
9,847	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1064323e-05
10,390	Detecting Contradictions Within and Across Documents	2027	SIGMOD	4.9605343e-05
10,778	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.9605343e-05
11,254	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9605343e-05
11,618	Extending Graph Rules with Oracles	2024	VLDB	4.9605343e-05
11,676	Graph Association Analyses for Early Drug Discovery	2024	VLDB	4.9605343e-05
11,788	Splitting Tuples of Mismatched Entities	2023	SIGMOD	4.9605343e-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
100	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033951027
190	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025812169
717	Guided Data Repair	2011	VLDB	0.00014531658
890	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00013212032
988	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.00012643318
1,180	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011600363
1,278	Automating Large-Scale Data Quality Verification	2018	VLDB	0.00011208469
2,056	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.10022e-05
2,269	Dependencies for Graphs	2017	PODS	8.711418e-05
2,429	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4657925e-05
2,785	Interaction between Record Matching and Data Repairing	2011	SIGMOD	7.9995952e-05
2,894	Functional Dependencies for Graphs	2016	SIGMOD	7.8870146e-05
2,954	Distributed Data Deduplication	2016	VLDB	7.8045942e-05
3,280	Large-Scale Collective Entity Matching	2011	VLDB	7.4495028e-05
3,329	Keys for Graphs	2015	VLDB	7.4086832e-05
3,414	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3058225e-05
5,659	Repairing Vertex Labels under Neighborhood Constraints	2014	VLDB	6.0309201e-05
5,968	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.9135528e-05
6,454	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	5.7623501e-05
7,263	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5557683e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,778	Repairing Property Graphs under PG-Constraints	2026	VLDB
2	2,785	Interaction between Record Matching and Data Repairing	2011	SIGMOD
3	1,354	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
4	12,382	QFix: Demonstrating Error Diagnosis in Query Histories	2016	SIGMOD
5	527	Improving Data Quality: Consistency and Accuracy	2007	VLDB
6	10,385	Budgeted Interactive Property Graph Repair with GNN	2027	SIGMOD
7	11,190	User-Centric Property Graph Repairs	2025	SIGMOD
8	4,852	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD
9	988	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB
10	2,958	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD