Deducing Certain Fixes to Graphs

This paper proposes to deduce certain fixes to graphs G based on data quality rules Sigma and ground truth Gamma (i. e. , validated attribute values and entity matches). We fix errors detected by Sigma in G such that the fixes are assured correct as long as Sigma and Gamma are correct. We deduce certain fixes in two paradigms. (a) We interact with users and incrementally fix errors online. Whenever users pick a small set V-0 of nodes in G, we fix all errors pertaining to V-0 and accumulate ground truth in the process. (b) Based on accumulated Gamma, we repair the entire graph G offline; while this may not correct all errors in G, all fixes are guaranteed certain. We develop techniques for deducing certain fixes. (1) We define data quality rules to support conditional functional dependencies, recursively defined keys and negative rules on graphs, such that we can deduce fixes by combining data repairing and object identification. (2) We show that deducing certain fixes is Church-Rosser, i.e., the deduction converges at the same fixes regardless of the order of rules applied. (3) We establish the complexity of three fundamental problems associated with certain fixes. (4) We provide (parallel) algorithms for deducing certain fixes online and offline, and guarantee to reduce running time when given more processors. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of our methods.