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: 12190
Venue: VLDB
Year: 2019
Pagerank: 5.4624971e-05
Overall Rank: 8,225 | 43.57%
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,608	Big Graphs: Challenges and Opportunities	2022	VLDB	6.1514145e-05
8,113	Capturing Associations in Graphs	2020	VLDB	5.484341e-05
9,437	GIDCL: A Graph-Enhanced Interpretable Data Cleaning Framework with Large Language Models	2024	SIGMOD	5.2687567e-05
9,627	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.2434488e-05
9,647	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	5.2430158e-05
10,523	Repairing Property Graphs under PG-Constraints	2026	VLDB	5.093636e-05
10,763	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	5.093636e-05
11,227	Extending Graph Rules with Oracles	2024	VLDB	5.093636e-05
11,304	Graph Association Analyses for Early Drug Discovery	2024	VLDB	5.093636e-05
11,424	Splitting Tuples of Mismatched Entities	2023	SIGMOD	5.093636e-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
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00026231189
714	Guided Data Repair	2011	VLDB	0.00014662041
866	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00013519288
998	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB	0.0001275238
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001179597
1,350	Automating Large-Scale Data Quality Verification	2018	VLDB	0.00011065626
2,041	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.2692538e-05
2,324	Dependencies for Graphs	2017	PODS	8.7506505e-05
2,398	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.631172e-05
2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.1280264e-05
2,893	Distributed Data Deduplication	2016	VLDB	7.983961e-05
2,973	Functional Dependencies for Graphs	2016	SIGMOD	7.9083516e-05
3,235	Large-Scale Collective Entity Matching	2011	VLDB	7.6139368e-05
3,251	Keys for Graphs	2015	VLDB	7.5963955e-05
3,496	Waldo: An Adaptive Human Interface for Crowd Entity Resolution	2017	SIGMOD	7.3634471e-05
5,519	Repairing Vertex Labels under Neighborhood Constraints	2014	VLDB	6.1885644e-05
5,878	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	6.0539311e-05
7,099	Discovering Graph Functional Dependencies	2018	SIGMOD	5.7043774e-05
7,393	Maverick: Discovering Exceptional Facts from Knowledge Graphs	2018	SIGMOD	5.6261241e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,721	Grafixer: Enabling User-Centric Repairs for Property Graphs	2025	SIGMOD
2	10,523	Repairing Property Graphs under PG-Constraints	2026	VLDB
3	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
4	1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
5	12,038	QFix: Demonstrating Error Diagnosis in Query Histories	2016	SIGMOD
6	533	Improving Data Quality: Consistency and Accuracy	2007	VLDB
7	10,681	User-Centric Property Graph Repairs	2025	SIGMOD
8	4,959	QFix: Diagnosing Errors through Query Histories	2017	SIGMOD
9	998	Towards Certain Fixes with Editing Rules and Master Data	2010	VLDB
10	2,981	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD