• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2013, Vol. 35 ›› Issue (8): 149-155.

• 论文 • 上一篇    下一篇

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

李丁月1,刘建勋2,翟海军2   

  1. (1.湘潭大学信息工程学院,湖南 湘潭 411100;
    2.湖南科技大学知识处理与网络化制造湖南省教育厅重点实验室,湖南 湘潭 411100)
  • 收稿日期:2012-06-25 修回日期:2012-08-31 出版日期:2013-08-25 发布日期:2013-08-25
  • 基金资助:

    湖南省杰出青年基金资助项目(11JJ1011);国家自然科学基金资助项目(61272063);教育部新世纪人才项目(NCET100140);湖南省教育厅资助项目(09K085);湖南省教育厅一般项目(09C401)

An incremental discovering algorithm
for conditional functional dependencies       

LI Dingyue1,LIU Jianxun2,ZHAI Haijun2   

  1. (1.School of Information Engineering,Xiangtan University,Xiangtan 411100;
    2.Key Laboratory of Knowledge Processing and Networked Manufacturing,
    Hunan University of Science and Technology,Xiangtan 411100,China)
  • Received:2012-06-25 Revised:2012-08-31 Online:2013-08-25 Published:2013-08-25

摘要:

数据库频繁更新会导致满足条件的条件函数依赖(CFDs)发生变化,为获取准确的条件函数依赖,可以在更新后的数据库上重新执行发现过程,但这种方法会导致大量时间都浪费在对原始数据集的重复处理上。针对这种情况,在CFINDER算法基础上,提出了一个增量发现条件函数依赖的算法CFUP。当数据库中增加新数据集时,CFUP在已有的CFDs的基础上,去掉不满足条件的CFDs,发现满足条件的新CFDs。实验表明,该算法能有效地进行条件函数依赖的增量式更新,与重新运行CFINDER算法相比,减少了原始数据集的扫描次数,提高了更新CFDs的效率。

关键词: 条件函数依赖, 增量式算法, 数据库

Abstract:

If the database is updated frequently, Conditional Functional Dependencies (CFDs) that have met the conditions may changes.. In order to obtain accurate CFDs, we can rerun the discovering process over the updated database. However, it spends a lot of time on dealing with the original dataset. Aiming at this problem, based on CFINDER algorithm, the paper proposed an incremental discovering algorithm for CFDs, which is named as CFUP. When a batch of new data is added to the database, the CFUP algorithm scans dataset to decide whether existing CFDs is valid or not, and the new data produces new CFDs, to achieve an incremental update for CFDs. Experiments show that the CFUP algorithm can effectively find CFDs by using information from the last discovering process. Compared with the rerun of the CFINDER algorithm, it can reduce the scanning number to original dataset and improve the efficiency of discovering CFDs.

Key words: conditional functional dependencies;incremental algorithm;database