Strict and Flexible Rule-Based Graph Repairing

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, called Graph-Repairing Rules (GRRs). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called δ-GRR). We study three fundamental problems associated with both GRRs and δ-GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using GRRs or δ-GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.