一种增量发现条件函数依赖的算法＊

李丁月，刘建勋，翟海军

（1.湘潭大学信息工程学院，湖南 湘潭411100；2.湖南科技大学知识处理与网络化制造湖南省教育厅重点实验室，湖南 湘潭411100）

1 引言

随着信息技术的快速发展，人类社会累积的数据每年都在呈指数上涨，这些数据中存在大量错误、不一致以及冗余的数据，即“脏数据”［1］。“脏数据”从各个方面影响组织的运作、收入和效率。据估计，美国政府每年在改善数据质量方面的花费达到了近600亿美元［2］。数据清除的目的是解决“脏数据”问题，检测和修改数据中的错误、不一致和重复数据，从而提高数据质量［3］。

数据质量的主要评价指标包括以下几个方面：一致性（Consistency）、正确性（Correctness）、完整性（Completeness）和最小性（Minimality）［1］。其中，如何解决数据的不一致性问题是近年数据库研究领域的一个热门课题。早期，研究人员主要采用函数依赖FDs（Functional Dependencies）来检测和修改不一致数据。其中，文献［4～6］提出了一些自动从关系数据库中发现函数依赖的方法。函数依赖可以有效地进行模式发现，然而，其在抓取数据中的语义方面往往无能为力。表1描述的记录出自1994年美国Adult Census数据库，其中包括work class（WC）、education（ED）、marital status（MS）、occupation（OCC）、relationship（REL）、sex（SEX）、native－country（NC）七个属性。表1中存在一些不一致数据。例如，在Tuple为t5的记录中，REL属性的取值是 Wife，SEX属性的取值是Male。很明显，这条记录中存在不一致数据，SEX属性的正确取值应是female。类似于表1中的这种数据不一致情形在现实数据中大量地存在，但是利用函数依赖无法有效检测出这些不一致的数据。找到一种能够自动检测和修改不一致数据的方法成为急需解决的问题。……