一种扩展条件函数依赖的发现算法

被引：5

作者：

刘显敏

李建中

机构：

[1] 哈尔滨工业大学

来源：

计算机研究与发展 | 2015年 / 52卷 / 01期

关键词：

扩展条件函数依赖; 发现算法; 搜索算法; 剪枝策略; 冗余;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

扩展条件函数依赖(extended conditional functional dependency,eCFD)是一种描述数据一致性的语义规则,是条件函数依赖(conditional functional dependency,CFD)的扩展.相比于CFD,eCFD能够描述更多的模式从而表达更丰富的语义信息.然而,关注eCFD的研究工作并不多.从给定数据中发现eCFD规则是一个重要问题,据笔者所知,目前还没有这方面的工作.该问题的难点在于,给定数据中所有合法的eCFD规则之间存在不一致的情况,且包含大量冗余,而CFD和传统的函数依赖规则并没有这样的问题.为避免不一致,同时尽可能地消除冗余,定义了"强合法eCFD"和"近似无冗余eCFD".基于这些概念给出了eCFD发现问题的形式化定义,并给出了MeCFD算法.利用划分属性的方法,MeCFD首先生成所有的基本eCFD,然后,通过合并基本eCFD来构造"组合eCFD".使用先深序来搜索候选空间,使得MeCFD仅用常数的存储空间来维护数据划分,节省了大量的空间开销,有效的剪枝策略被用来改进MeCFD的性能.真实数据集上的实验结果显示出MeCFD良好的可扩展性以及剪枝策略和优化方法的有效性.

引用

收藏

页码：130 / 140

页数：11

相关论文

共 3 条

[1] Conditional functional dependencies for capturing data inconsistencies
Fan, Wenfei
Geerts, Floris
Jia, Xibei
Kementsietsidis, Anastasios
[J]. ACM TRANSACTIONS ON DATABASE SYSTEMS, 2008, 33 (02):
[2] Discovering data quality rules .2 Fei Chiang,Renée J. Miller. Proceedings of the VLDB Endowment . 2008
[3] Propagating functional dependencies with conditions .2 Wenfei Fan,Shuai Ma,Yanli Hu,Jie Liu,Yinghui Wu. Proceedings of the VLDB Endowment . 2008