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

摘要

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