Conditional functional dependencies for capturing data inconsistencies
Conditional functional dependencies for capturing data inconsistencies
复制标题
捕捉数据不一致性的条件功能依赖性
DOI：
10.1145/1366102.1366103
复制
发表时间：
2008-06-01
影响因子：
1.8
通讯作者：
Kementsietsidis, Anastasios
中科院分区：
文献类型：
--
作者：
Fan, Wenfei;Geerts, Floris;Kementsietsidis, Anastasios
我们为关系数据库提出了一类完整性约束，称为条件功能依赖性（CFD），并研究其在数据清洁中的应用。与主要用于模式设计开发的传统功能依赖关系（FDS）相反，CFD旨在通过实施语义相关值的绑定来捕获数据的一致性。对于CFD的静态分析，我们研究了一致性问题，即确定是否存在满足给定CFD的非空数据库以及含义问题，即确定一组CFD是否需要另一个CFD。我们表明，尽管任何一组过渡FD在微不足道的一致性上都是一致的，但一致性问题对于CFD来说是NP库，但是在PTIME中，当数据库架构被预定义或CFD中涉及的属性都有有限域时。对于CFD的含义分析，我们提供了类似于Armstrong的FD的推理系统，并表明，与传统对应物的线性时间复杂性相比，CFD的含义问题对于CFD来说是完整的。我们还提出了一种用于计算一组CFD的最小覆盖的算法。由于CFD允许数据绑定，因此在某些情况下，CFD可能在物理上很大，从而使违规的检测变得复杂。我们开发了用于检测SQL中CFD违规的技术，以及通过单个查询检查多个约束的新技术。我们还提供了用于检查数据库更改的CFD的增量方法。我们通过实验验证基于CFD的方法对于不一致检测的有效性。这项工作不仅对CFD产生了约束理论，而且还是迈向改善数据质量的实用约束方法的一步。
We propose a class of integrity constraints for relational databases, referred to as conditional functional dependencies (CFDs), and study their applications in data cleaning. In contrast to traditional functional dependencies (FDs) that were developed mainly for schema design, CFDs aim at capturing the consistency of data by enforcing bindings of semantically related values. For static analysis of CFDs we investigate the consistency problem, which is to determine whether or not there exists a nonempty database satisfying a given set of CFDs, and the implication problem, which is to decide whether or not a set of CFDs entails another CFD. We show that while any set of transitional FDs is trivially consistent, the consistency problem is NP-complete for CFDs, but it is in PTIME when either the database schema is predefined or no attributes involved in the CFDs have a finite domain. For the implication analysis of CFDs, we provide an inference system analogous to Armstrong's axioms for FDs, and show that the implication problem is coNP-complete for CFDs in contrast to the linear-time complexity for their traditional counterpart. We also present an algorithm for computing a minimal cover of a set of CFDs. Since CFDs allow data bindings, in some cases CFDs may be physically large, complicating the detection of constraint violations. We develop techniques for detecting CFD violations in SQL as well as novel techniques for checking multiple constraints by a single query. We also provide incremental methods for checking CFDs in response to changes to the database. We experimentally verify the effectiveness of our CFD-based methods for inconsistency detection. This work not only yields a constraint theory for CFDs but is also a step toward a practical constraint-based method for improving data quality.