Repairing Entities using Star Constraints in Multirelational Graphs
Repairing Entities using Star Constraints in Multirelational Graphs
复制标题
DOI：
10.1109/icde48307.2020.00027
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Peng Lin;Qi Song;Yinghui Wu;Jiaxing Pi
中科院分区：
文献类型：
--
作者：
Peng Lin;Qi Song;Yinghui Wu;Jiaxing Pi
本文研究了一类邻域约束来刻画和修复多关系图数据中的错误实体信息。(1)提出了一类称为星函数依赖(StarFDs)的约束。与传统的完整性约束不同，StarFD强制实施由实体及其相关邻居限定的值依赖关系，这些实体及其相关邻居由合并了合取规则路径查询的星形模式标识。StarFDs在表现力和复杂性之间取得了平衡：StarFDs的验证是易处理的，StarFDs的可满足性和蕴涵分别是NP-完全和coNP-完全。(2)给定一个StarFD集Σ和一个图G，实体修复问题是用最少的变化量执行Σ来计算G的最小修复。虽然这个问题是NP-完全的，很难逼近，但我们证明了在大型图中计算修复是可行的。我们的方法(A)尽可能用最优的、可逼近的和成本有界的解决方案区别地检测和解决错误，并且(B)对于所有情况，产生由Σ和不一致的大小确定的时间成本。使用真实世界的数据，我们展示了基于StarFD的技术有效地识别和修复错误。我们还表明，我们的修复算法有利于其他任务，如事实检查。
This paper studies a class of neighborhood con-straints to characterize and repair erroneous entity information in multi-relational graph data. (1) We propose a class of constraints called star functional dependencies (StarFDs). Unlike conventional integrity constraints, a StarFDenforces value dependencies conditioned by entities and their relevant neighbors, which are identified by a star pattern that incorporates conjunctive regular path queries. StarFDsachieve a balance between expressiveness and complexity: the validation of StarFDsis tractable, and the satisfiability and implication of StarFDsare NP-complete and coNP-complete, respectively. (2) Given a set of StarFDsΣ and a graph G, the entity repair problem is to compute a minimum repair of G by enforcing Σ with the smallest amount of changes. Although this problem is NP-complete and hard to approximate, we show it is feasible to compute repairs in large graphs. Our approach (a) discriminately detects and resolves errors with optimal, approximable and cost-bounded solutions whenever possible, and (b) incurs a time cost determined by Σ and the size of inconsistencies, for all cases. Using real world data, we show that StarFD-based techniques effectively identify and repair errors. We also show that our repairing algorithms benefit other tasks such as fact checking.