刘 波，周健昌

（暨南大学信息科学技术学院，广东广州510632）

条件函数依赖的增量计算

刘 波，周健昌

（暨南大学信息科学技术学院，广东广州510632）

条件函数依赖是对传统函数依赖的扩展，它通过引入条件模式，使其语义比函数依赖更精确、表达能力更强。然而，条件函数依赖的计算需要消耗较多的时间，为了提高条件函数依赖挖掘的效率，研究了条件函数依赖增量维护方法。针对数据集增加、删除、修改3种情况分别分析了条件函数依赖集变化规律，提出了条件函数依赖的增量计算算法，从而能够在数据库变化情况下，高效、动态地维护条件函数依赖。同时，在理论上对算法中关键步骤的正确性进行了论证，并通过实验验证了算法的有效性。

增量计算；条件函数依赖；数据挖掘

0 引 言

传统的函数依赖（functional dependencies，FDs）主要用于数据库模式设计，但对于刻画数据值的特征还不够精确，其语义约束过于严格而往往脱离现实情况。Bohannon P等在FDs的基础上，通过引入“条件模式”［1］，放宽了这种约束，形成条件函数依赖（conditional functional dependencies，CFDs）（在下文中，CFD表示一条条件函数依赖，CFDs表示多条条函数依赖），从而使描述的语义信息更精确，能够表达在局部范围内成立的函数依赖。

目前对FDs及CFDs的研究主要都是基于静态数据集的。算法TANE［2］和算法Fast FDs［3］是最具代表性的FDs挖掘方法。近些年，在CFDs挖掘方面，也提出一些卓有成效的算法，如Fan W F等提出了3个发现最小CFDs集的算法［4］：①CFDMiner，用基于闭数据项集的挖掘方法，挖掘常量CFDs；②CTane，基于层次的算法，是对算法TANE的扩展；……