條件函數(shù)依賴的增量計算

劉 波，周健昌

（暨南大學信息科學技術(shù)學院，廣東廣州510632）

條件函數(shù)依賴的增量計算

劉 波，周健昌

（暨南大學信息科學技術(shù)學院，廣東廣州510632）

條件函數(shù)依賴是對傳統(tǒng)函數(shù)依賴的擴展，它通過引入條件模式，使其語義比函數(shù)依賴更精確、表達能力更強。然而，條件函數(shù)依賴的計算需要消耗較多的時間，為了提高條件函數(shù)依賴挖掘的效率，研究了條件函數(shù)依賴增量維護方法。針對數(shù)據(jù)集增加、刪除、修改3種情況分別分析了條件函數(shù)依賴集變化規(guī)律，提出了條件函數(shù)依賴的增量計算算法，從而能夠在數(shù)據(jù)庫變化情況下，高效、動態(tài)地維護條件函數(shù)依賴。同時，在理論上對算法中關(guān)鍵步驟的正確性進行了論證，并通過實驗驗證了算法的有效性。

增量計算；條件函數(shù)依賴；數(shù)據(jù)挖掘

0 引 言

傳統(tǒng)的函數(shù)依賴（functional dependencies，F(xiàn)Ds）主要用于數(shù)據(jù)庫模式設(shè)計，但對于刻畫數(shù)據(jù)值的特征還不夠精確，其語義約束過于嚴格而往往脫離現(xiàn)實情況。Bohannon P等在FDs的基礎(chǔ)上，通過引入“條件模式”［1］，放寬了這種約束，形成條件函數(shù)依賴（conditional functional dependencies，CFDs）（在下文中，CFD表示一條條件函數(shù)依賴，CFDs表示多條條函數(shù)依賴），從而使描述的語義信息更精確，能夠表達在局部范圍內(nèi)成立的函數(shù)依賴。

目前對FDs及CFDs的研究主要都是基于靜態(tài)數(shù)據(jù)集的。算法TANE［2］和算法Fast FDs［3］是最具代表性的FDs挖掘方法。近些年，在CFDs挖掘方面，也提出一些卓有成效的算法，如Fan W F等提出了3個發(fā)現(xiàn)最小CFDs集的算法［4］：①CFDMiner，用基于閉數(shù)據(jù)項集的挖掘方法，挖掘常量CFDs；②CTane，基于層次的算法，是對算法TANE的擴展；③FastCFD，基于深度優(yōu)先的策略，是對算法Fast FD的擴展。文獻［5］、文獻［6］分別研究了頻繁常量CFDs、近似CFDs的發(fā)現(xiàn)方法。此外，在CFDs應(yīng)用方面的研究主要集中在數(shù)據(jù)清洗與重復檢測方面，如文獻［7- 13］。

但是，數(shù)據(jù)庫往往是變化的，因而CFDs也應(yīng)隨之更新。至今，未見基于變化數(shù)據(jù)更新CFDs的研究，相關(guān)的增量處理方法與本工作研究目標不同。文獻［14］研究的主體是FDs，而且針對插入元組采用增量方法計算FDs，但基于刪除元組采用非增量方法計算FDs。文獻［8］介紹了CFDs在違例元組的增量檢測方面的應(yīng)用，即在CFDs集保持不變的情況下，針對插入、刪除、修改元組增量檢查是否有違例元組出現(xiàn)。

本文主要創(chuàng)新點如下：①基于非增量計算算法CTane，針對數(shù)據(jù)表的增加、刪除、修改元組等不同操作，分別分析了在相應(yīng)情況下CFDs變化規(guī)律；②提出了增量計算CFDs算法CTane-IncProc，且分析并驗證了此算法的正確性與高效性。該研究工作與其他CFDs相關(guān)研究目標與方法不同，例如，文獻［4］主要研究非增量計算CFDs的方法，而本文針對變化的數(shù)據(jù)集研究增量計算方法。

1 問題描述與相關(guān)概念

1.1 問題描述

假設(shè)給定關(guān)系模式R的關(guān)系數(shù)據(jù)表r，且：

Δr：對r進行的增量操作元組集；

r′：增量操作發(fā)生后新關(guān)系數(shù)據(jù)表；

Partitions（r）：增量操作發(fā)生前r的劃分信息；

CFDs_old（r）：數(shù)據(jù)表r更新發(fā)生前的最小條件函數(shù)依賴集；

CFDs_new（r）：數(shù)據(jù)表r更新發(fā)生后的最小條件函數(shù)依賴集。

CFDs增量計算問題描述為：

給定：數(shù)據(jù)表r，由CTane算法［4］得到的最小條件函數(shù)依賴集CFDs_old（r），劃分信息Partitons（r），以及增量操作元組集Δr。

目標：增量計算變化后的數(shù)據(jù)表r′中最小條件函數(shù)依賴集CFDs_new（r）。

難點：

（1）如何保證CFDs_new（r）中的條件函數(shù)依賴是最小的；

（2）如何保持增量挖掘過程中的輔助信息的一致性狀態(tài)，使得這種增量計算不會引入錯誤，從而可以持續(xù)地用更新后的信息再進行下一次的增量挖掘。

1.2 相關(guān)概念

在下文中，R表示關(guān)系的模式；r為R的關(guān)系數(shù)據(jù)表；A、B、X、Y、Z分別為R的一個屬性或?qū)傩约希籥ttr（R）表示R的全體屬性集；Dom（A）表示r中屬性A的值域。

定義1CFD［4］：

R上的某CFD可以表示為

式中，X?attr（R），Y?attr（R）；X→Y是一個標準FD；tp［X∪Y］為定義在X∪Y上的模板，若A∈X∪Y，tp［A］為屬于Dom（A）的常量或變量值“－”。

設(shè)Y＝A1∪A2∪…∪An，根據(jù)阿姆斯特朗公理中的合并律，任何形式為（X→Y，tp［X］‖tp［Y］）的CFD都可由（X→A1，tp［X］‖tp［A1］）、（X→A2，tp［X］‖tp［A2］）、…、（X→An，tp［X］‖tp［An］）合成，故本文只討論并挖掘形式為（X→A，tp［X］‖tp［A］）的CFD，其中A僅包含一個屬性，這簡化了算法的復雜性。

定義2常量CFD、變量CFD［4］：

在CFD：（X→Y，tp［X］‖tp［Y］）中，tp［X∪Y］中不含變量“－”，則稱為常量CFD，否則就是變量CFD。

例如，按CFD的定義，從表1可得如下CFDs：

其中，1和2是變量CFDs，3是常量CFD。

表1 數(shù)據(jù)集示例

定義3模板間的泛化關(guān)系［4］：

為模板的變量值與常量值定義出一個關(guān)系符“?”，稱泛化。有如下兩種泛化：

（1）屬性值的泛化：?A∈attr（R），若n1、n2∈tp［A］且n1＝＝n2或n1是常量而n2是變量，則有n1?n2；

顯然，泛化程度的高低體現(xiàn)的是模板抽象、概括能力，即語義包含能力。泛化程度低的模板所蘊含的元組也必被泛化程度高的模板所蘊含。

定義4等價類［4］：

屬性集X的某一等價類［t］X是指在給定關(guān)系實例中，所有與元組t在X上取值對應(yīng)相等（簡稱與t在X上取值相等）的元組的集合。

定義5劃分［4］：

在TANE算法中，劃分πX被定義為X的所有等價類的集合。在CTane中擴展劃分定義π（X，SP）：是πX中比SP具體化的所有模板所包含的等價類集合，即π（X，SP）是符合SP約束的πX的子集。

定義6平凡CFD［4］：

定義7左歸約CFD［4］：

定義8最小CFD［4］：

例如，考慮如下CFD：

因存在（（Major）→（College），（－）‖（－）），所以4不是最小CFD。

本文研究的CFD計算即指最小CFD的計算。

2 CFDs集的增量計算

由于不同類型的增量操作對最小CFDs集的影響是不同的，因此增量計算最小CFD需要按操作類型分別研究。

表2是對表1的增量操作示例表，有如下特點：

（1）在屬性方面表2比表1多兩個字段：ID字段取值OPi表示第i個增量操作；OP字段表示增量操作的類型，其取值DEL表示刪除，INS表示增加，UPD表示修改元組。

（2）修改元組中的某些字段值，如“C，D”，表示將值C修改為值D。

（3）ID、TID字段僅是為方便描述而附加的字段，挖掘與更新均不涉及。

表2 增量操作示例表

2.1 新增元組與CFDs的增量計算

新增元組可能使原有CFDs失效，也可能導致原有CFDs仍然有效、或新增CFDs。

2.1.1 原有CFDs失效及有效的情況定理1在關(guān)系r中插入元組t，若

且在r＼｛t｝中存在t′，使t′［X］＝t［X］?tp［X］，t′［Y］≠t［Y］，則?CFDs_new（r）。

定理1可根據(jù)CFD的定義以及模板泛化的概念直接證得，這也是插入一個元組后判斷一條CFD是否成立的依據(jù)，插入的元組t若符合定理1中的條件，則失效。

例如，表2中的OP1操作后，原有的CFD：（（Group）→（Name），（A）‖（曾莉）），因符合定理1的條件而失效，故不應(yīng)加入CFDs_new（r）。

反過來看上述定理1，可得以下推論。推論1在關(guān)系r中插入元組t，若

（1）?t′∈r＼｛t｝，t′［X］＝t［X］?tp［X］，且t′［Y］＝t［Y］?tp［Y］；

（2）在r＼｛t｝中不存在t′，使t′［X］＝t［X］?tp［X］，而不論t′［Y］取何值。

例如，表2中的OP1操作后，（（Group）→（Major），（A）‖（通信））顯然因為符合條件（1）而保留。（（Group，Gender）→（Major），（A，－）‖（－））、（（Group，Gender）→（Name），（A，－）‖（－））都因為t7［Group，Gender］有新取值（A，Male）而保留，而不管t7［Major］、t7［Name］取何值。

2.1.2 新增CFDs的情況

插入一個元組不但可能會使CFDs失效，還可能會生成一些CFDs_old（r）中不存在的CFDs，即：（X→Y，tp［X］‖tp［Y］）?CFDs_old（r），但∈CFDs_new（r）。具體情況如下：

（1）在r＼｛t｝中?t′，使t′［X］＝t［X］?tp［X］，t′［Y］＝t［Y］?tp［Y］，且滿足這一條件的元組t′個數(shù)之和為k－1（k是CTane算法中設(shè)置的頻繁度閾值），而插入t后（t′［X］‖t′［Y］）的頻繁度達到k，故應(yīng)將插入到CFDs_new（r）；

在上述情況中，情況（1）是量的積累達到頻度k，從而新的CFD被檢測到；情況（2）是因為插入元組使泛化程度更高的′向低泛化的退化，且基于′產(chǎn)生多條。

例如，對于表2中的OP1，存在泛化退化的情況：在插入前存在的：（（Group，Major）→（Name），（－，－）‖（－）），由于插入t7后，對于滿足［Group，Major］＝（A，通信）的兩個元組t1與t7，在［Name］上取值不相同，所以不再成立，但它可以分解為以下泛化程度較低的CFDs：

2.1.3 最小CFDs集的更新

根據(jù)以上情況的分析，本研究采用以下方法對最小CFDs集進行更新。

假設(shè)新插入元組為t，r為修改前的新數(shù)據(jù)表，對CFDs_ old（r）中的每艘最小CFDs：（X→Y，tp［X］‖tp［Y］）進行如下檢測：

依據(jù)推論1中的條件（2），如果t在X的任一分量上出現(xiàn)新屬性值，則滿足在r＼｛t｝中不存在t′，使t′［X］＝t［X］?tp［X］，所以仍是最小CFD。

（2）若r′＝｛t′｜t′∈r，t′［X］＝t［X］｝為空，則t對無影響，將加入到CFDs_new（r）。

因為r′＝｛t′｜t′∈r，t′［X］＝t［X］｝為空，說明在t插入前，r中沒有以t［X］為X屬性值的元組，依據(jù)最小CFD的定義，t對無影響，所以仍是最小CFD。

（3）若r′＝｛t′｜t′∈r，t′［X］＝t［X］｝非空，且存在t′∈r′，使t′［X］＝t［X］?tp［X］，但t′［Y］≠t［Y］，則：

2.2 刪除元組與CFDs的增量計算

刪除元組可能使原有CFDs仍然有效或無效或新增CFDs。

2.2.1 原有CFDs失效及有效的情況

定理2關(guān)系模式為R的實例r中，刪除其中任一元組t，對CFD：（X→Y，tp［X］‖tp［Y］）而言，若刪除t后，tp［X∪A］的頻度仍滿足頻度k，則是有效的，否則是無效的。

證明假設(shè)刪除的是r中的元組t，則刪除后的關(guān)系為r′＝r＼｛t｝，r′′＝｛t′′｜t′′［X］?tp［X］，t′∈r′｝。在刪除t后，tp［X∪Y］仍滿足頻度k時，在r中成立，即?t1、t2∈r，t1≠t，t2≠t，只要t1［X］＝t2［X］?tp［X］，必有t1［Y］＝t2［Y］?tp［Y］。很顯然，r′′?r′?r，故在r中成立，當然在r的子集中r′也成立。即r′中的任意兩個元組只要符合t1［X］＝t2［X］?tp［X］必有t1［Y］＝t2［Y］?tp［Y］，故而仍成立。

若tp［X∪Y］的頻度在刪除元組后達不到k，則失效。

證畢

例如，對于表2中的OP2，（（Group，Major）→（Name），（－，－）‖（－））仍然是有效的（假設(shè)仍滿足k閾值），因為更新后的表r′中，除被刪除元組外，任意兩條元組都在更新前的表r中，它們也當然遵守在r中的規(guī)則。

2.2.2 新增CFDs的情況

在數(shù)據(jù)表r中刪除元組t可能使原來不屬于CFDs_old（r）中的某CFD：（X→Y，tp［X］‖tp［Y］）成立，因為在r中，若只有t違反了取值為tp［X］、Y取值為tp［Y］的約定，則刪除t后，?t1、t2?r′，只要t1［X］＝t2［X］?tp［X］，必有t1［Y］＝t2［Y］?tp［Y］。然而，由于CFDs_old（r）、CFDs_new（r）均要求是最小條件函數(shù)依賴集，所以情況有些復雜。

例如，在表2中的OP2操作前，表1中只有t1與t2的取值沖突使1：（（Gender，College）→（Group），（－，信息學院）‖（－））及2：（（Gender，College）→（Group），（Female，－）‖（－））不成立，刪去t1后應(yīng)該增加1及2，然而由于在操作前已存在以下CFDs：

2.2.3 最小CFDs集的更新

據(jù)上面討論的情況，設(shè)刪除的元組是t，刪除t后的關(guān)系為r，使用以下方法對最小CFDs集進行更新：

（1）檢測因刪去t而新生成的CFDs，并加入到CFDs_ new（r）中。新生成的CFDs可能是CFDs_old（r）中已有CFDs的更泛化版本（原CFDs雖仍成立，但已不是最小的），也可能是原CFDs_old（r）根本沒有涉及到的新CFDs。

這種情況需要采取啟發(fā)式的重新挖掘方法產(chǎn)生最小CFDs，在非增量的CTane算法中利用一些剪枝策略提高效率。

依據(jù)定理2，可以證明：若tp［X∪Y］的個數(shù)仍達到頻度k，還是最小CFD。

（3）在CFDs_new（r）中合并相應(yīng)可合并的CFDs，從而保證CFDs_new（r）中的CFD集是最小的，形成最終狀態(tài)的CFDs_new（r）。

依據(jù)第2.2.2節(jié)分析的新增CFD情況，經(jīng)過一系列模板合并成更泛化的模板可以產(chǎn)生最小CFD。

刪除更新的真正難點在于（1）的處理，這里采取啟發(fā)式的重新挖掘方法。首先修正劃分信息，再在重新挖掘時借助CFDs_old（r）中的CFDs作指導，盡早剪去無用的Lattice［15］分枝，從而有針對性地重新挖掘，加快挖掘效率。重新挖掘可利用的剪枝策略包括：

（1）對已判斷為主鍵或FD的屬性集／模板結(jié)點提前剪枝，甚至根本不生成這樣的結(jié)點。

（3）只檢測常量模板的Lattice結(jié)點。

例如，針對上一例子，在表2中的OP2操作后，直接生成1：（（Gender，College）→（Group），（－，信息學院）‖（－）），與1′：（（Gender，College）→（Group），（－，數(shù)學學院）‖（－））合并生成：（（Gender，College）→（Group），（－，－）‖（－）），然而，也可以只檢測加入常量的CFDs，θ1：（（Gender，College）→（Group），（Female，信息學院）‖（計算機））、θ2：（（Gender，College）→（Group），（Male，信息學院）‖（通信）），再由θ1與θ2合并成1，最后由1與已存在的1′合并成。

這種操作似乎由于增加合并操作而降低了效率，但在重新挖掘過程中，只生成判斷tp［X∪Y］全為常量的結(jié)點，不但減少了分枝的數(shù)目，而且使整體過程的復雜性有較大的降低。因為CTane算法操作的復雜性很大一部分是因為要處理變量模板，而相對來說，CFDs的合并操作盡管有一個循環(huán)反復的過程（如上述例子中，θ1與θ2合并成1，再由1與已存在的1′合并成），但時空復雜性并不會太高，故而總體效率不但沒有降低，反而有所提升。

在計算最小CFDs的過程中，還可以節(jié)省大量的計算，因為保留著劃分信息，從而可以避免重新掃描數(shù)據(jù)集帶來的巨大開銷，同時剪枝策略只處理常量模板，所以算法時間代價有較大程度的降低。

2.3 修改元組與條件函數(shù)依賴的增量計算

對數(shù)據(jù)表元組進行更新的操作實質(zhì)上都可以拆分成兩個操作的疊加：

刪除原元組：（a1，b1，c1，…，n1）；

插入新元組：（a2，b2，c2，…，n2）。

因而，更新一條元組引起對CFD集的修改，可采用上面所述的增加一條元組和刪除一條元組引起CFDs集修改的方法。

2.4 劃分的維護

無論因插入操作使tp［X∪Y］剛達頻度k還是因刪除操作使tp［X∪Y］剛好不足頻度k（本文統(tǒng)稱兩種頻度的變化為頻度臨界變化），都會涉及到的一個問題：對：（X→Y，tp［X］‖tp［Y］）而言，tp［X∪Y］的頻度需要維護，而這個問題歸根結(jié)底是CTane算法結(jié)束后對劃分的增量維護，實質(zhì)上，就是屬性集X上的等價類維護。在數(shù)據(jù)集變化的同時，標記發(fā)生頻度臨界變化的tp［X∪Y］，可以更有針對性地判斷新產(chǎn)生或刪去哪些CFDs。

當劃分信息更新完成后：

（1）針對刪除操作，對發(fā)生頻度臨界變化的tp［X∪Y］，從CFDs_new（r）中刪除：（X→Y，tp［X］‖tp［Y］）。

（2）針對插入操作，對發(fā)生頻度臨界變化的tp［X］，?A∈X，Y＝X＼｛A｝判斷（Y→A，tp［Y］‖tp［A］）是否成立，若成立則加到CFDs_new（r）中。

例如，取X＝（Group，Major），Y＝（Name），tp［X］＝（－，－），tp［Y］＝（－），在表2中的插入操作OP1前，關(guān)于X的劃分信息為π（X，tp［X］）＝｛｛t1｝、｛t2｝、｛t3｝、｛t4｝、｛t5｝、｛t6｝｝、π（X∪Y，tp［X∪Y］）＝｛｛t1｝、｛t2｝、｛t3｝、｛t4｝、｛t5｝、｛t6｝｝，由于π（X，tp［X］）與π（X∪Y，tp［X∪Y］）的劃分信息是一致的，所以：（X→Y，tp［X］‖tp［Y］）成立；在插入操作OP1后，π（X，tp［X］）＝｛｛t1，t7｝、｛t2｝、｛t3｝、｛t4｝、｛t5｝、｛t6｝｝、π（X∪Y，tp［X∪Y］）＝｛｛t1｝、｛t2｝、｛t3｝、｛t4｝、｛t5｝、｛t6｝、｛t7｝｝，則π（X，tp［X］）與π（X∪Y，tp［X∪Y］）有不一致的劃分，所以不再成立。

類似地，刪除時，就在各個相關(guān)的等價類中刪除元組信息即可。

2.5 CTane-IncProc算法

根據(jù)上述CFD增量計算的思路，基于CTane算法，本節(jié)提出了最小CFD的增量計算算法CTane-IncProc。

輸入R，r，Δr，Partitions，CFDs_old（r）

輸出CFDs_new（r）

2.6 算法復雜度

CTane-IncProc算法的時間復雜度可通過對如下兩個主要過程分析獲得［16］。令：｜r｜為數(shù)據(jù)集的元組數(shù)目，｜R｜為數(shù)據(jù)集包含的屬性數(shù)目，f為attr（R）中屬性的平均取值數(shù)目。

CTane-IncProc的空間復雜度為

雖然從理論上分析，CTane-IncProc算法在最壞情況下并沒有降低CTane算法的復雜度，但采用增量計算的CTane-IncProc算法，由于有CFDs_old（r）及增量操作的啟發(fā)，使得搜索空間要小于CTane算法需要的搜素空間，從而實際性能要優(yōu)于CTane算法，從第3節(jié)的實驗結(jié)果可以得到驗證。

3 實驗結(jié)果

3.1 實驗數(shù)據(jù)與環(huán)境

在實驗過程中，主要用到UCI（http：∥archive.ics.uci.edu／ml／datasets／）公開數(shù)據(jù)集，此外，也用到由開源數(shù)據(jù)生成器Spawner產(chǎn)生的數(shù)據(jù)集。實驗數(shù)據(jù)集如表3所示，其中，｜R｜表示數(shù)據(jù)集中的屬性數(shù)目，｜r｜表示數(shù)據(jù)集中的元組數(shù)目。

所有實驗在Red Hat Enterprise Linux 6.1（Kernel 2.6.32）、CPU Intel Pentium E2180 2.0GHz×2、內(nèi)存2.0GB的微機環(huán)境下，采用CodeBlocks 10.05開發(fā)工具及C＋＋編寫軟件完成。

表3 實驗數(shù)據(jù)集

3.2 實驗結(jié)果及分析

實驗中，主要參數(shù)為：｜r｜、｜R｜、｜CFDs_old（r）｜、頻繁度閾值k等。采用CTane與CTane-IncProc兩種算法分別針對表3中的數(shù)據(jù)集進行了實驗，產(chǎn)生的最小CFDs都是一致的，但兩種算法的時間性能不同，下面將進行比較分析。

3.2.1 數(shù)據(jù)集大小對CTane-IncProc性能的影響

這里使用Spawner工具生成的數(shù)據(jù)集，測試數(shù)據(jù)集的大小對CTane-IncProc性能影響。結(jié)果如圖1和圖2所示。從圖1所得結(jié)果來看，CTane與CTane-IncProc的性能基本都與｜R｜呈指數(shù)級增長，但顯然CTane-IncProc的增長率沒CTane快。另外，圖2顯示，CTane與CTane-IncProc都與｜r｜約呈線性增長關(guān)系。

由于插入更新與刪除更新都涉及CFDs_old（r）的遍歷，所以，在圖3中，還比較了｜CFDs_old（r）｜對3種操作（OP：INS表示插入，DEL表示刪除，UPD表示更新）的影響，用到的數(shù)據(jù)集是表3中的DB1與DB2，兩者在挖掘時所得的｜CFDs_old（r）｜分別為98 237、65 129。從該圖可以得出：｜CFDs_old（r）｜越大，增量更新CFDs所需的時間越多，且DEL操作引起的增量計算時間比INS操作引起的增量計算時間要多。

圖1 ｜R｜對性能的影響（｜r｜＝100 000，k＝10）

圖2 ｜r｜對性能的影響（｜R｜＝9，k＝10）

圖3 3種更新與｜CFDs_old（r）｜關(guān)系

3.2.2 CTane與CTane-IncProc的性能比較

表4列出的是CTane與CTane-IncProc作用于真實數(shù)據(jù)集中的性能對比，其中“耗時”指的是一個平均耗時，測量方法是隨機增加、刪除或從數(shù)據(jù)集中隨機選取一條元組進行修改以作為增量元組，再利用CTane或CTane-IncProc進行挖掘，各進行30次（每次采用不同的隨機元組）實驗，取平均值而得。

在各次測試中，使用k＝11。從表4的實驗結(jié)果可以得到如下結(jié)論：針對CTane-IncProc算法，總體上看，在3種情況下，增加元組后執(zhí)行增量計算的耗時最少，更新元組后執(zhí)行增量計算的耗時最多；針對非增量算法CTane，對每一數(shù)據(jù)集的挖掘時間都比更新算法的任一種情況消耗的時間多，尤其比增加元組情況下的增量挖掘時間多了近一倍。因此，實驗結(jié)果證明本文提出的增量計算算法比非增量計算算法的時間效率高。

表4 CTane與CTane-IncProc的平均性能

此外，CTane-IncProc與CTane算法產(chǎn)生的CFDs結(jié)果相同，且通過人工判斷均是正確的，表明了CTane-IncProc算法的正確性。

4 結(jié) 論

增量挖掘是分析處理海量動態(tài)數(shù)據(jù)的一項高效技術(shù)。本文首先介紹了條件函數(shù)依賴及相關(guān)概念；隨后在CTane算法的基礎(chǔ)上，分析了增、刪、改3種增量操作對最小CFDs集變化的影響，并提出增量維護最小FDs集的算法CTane-IncProc，且進行了正確性和復雜度說明；最后，通過實驗驗證了CTane-IncProc算法的有效性。與相關(guān)研究相比，提高了CFDs的計算效率，能夠為動態(tài)檢測數(shù)據(jù)質(zhì)量提供依據(jù)。

［1］Bohannon P，F(xiàn)an W F，Geerts F，et al.Conditional functional dependencies for data cleaning［C］∥Proc.of the IEEE 23rd International Conference on Data Enginering，2007：746- 755.

［2］Huhtala Y，Karkkainen J，Porkka P，et al.TANE：an efficient algorithm for discovering functional and approximate dependencies［J］.Computer Journal，1999，42（2）：100- 111.

［3］Wyss C M，Giannella C，Robertson E L.Fast FDs：a heuristicdriven，depth-first algorithm for mining functional dependencies from relation instances-extended for abstract［C］∥Proc.of the 3rd International Conference on Data Warehousing and Knowledge Discovery，2001：101- 110.

［4］Fan W F，Geerts F，Li J Z，et al.Discovering conditional functional dependencies［J］.IEEE Trans.on Knowledge and Data Engineering，2011，23（5）：683- 698.

［5］Diallo T，Novelli N，Petit J M.Discovering（frequent）constant conditional functional dependencies［J］.International Journal of Data Mining，Modelling and Management，2012，4（3）：205- 223.

［6］Nakayama H，Hoshino A，Ito C，et al.Formalization and discovery of approximate conditional functional dependencies［C］∥Proc.of the 24th International Conference on Database and Expert Systems Applications，2013：118- 128.

［7］Beskales G，Ilyas I F，Golab L，et al.Sampling from repairs of conditional functional dependency violations［J］.The International Journal on Very Large Data Bases Journal，2014，23（1）：103- 128.

［8］Fan W F，Li J Z，Tang N，et al.Incremental detection of inconsistencies in distributed data［C］∥Proc.of the IEEE 28th International Conference on Data Engineering，2012：318- 329.

［9］Cheng L Q.Conditional functional dependency and data quality control［J］.Information System Engineering，2009，11：106-108.（程錄慶.條件函數(shù)依賴與數(shù)據(jù)質(zhì)量控制［J］.信息系統(tǒng)工程，2009，11：106- 108.）

［10］Hu Y L，Zhang W M，Luo X H，et al.Dependencies theory and its application for repairing inconsistent data［J］.Computer Science，2009，36（10）：11- 15.（胡艷麗，張維明，羅旭輝，等.基于數(shù)據(jù)依賴的數(shù)據(jù)修復研究進展［J］.計算機科學，2009，36（10）：11- 15.）

［11］Geng Y R，Liu B.Conditional functional dependencies for detecting data inconsistencies［J］.Computer Engineering and Applications，2012，48（3）：122- 125.（耿寅融，劉波.基于條件函數(shù)依賴的數(shù)據(jù)庫一致性檢測研究［J］.計算機工程與應(yīng)用，2012，48（3）：122- 125.）

［12］Neehar C，Krishna T V S.Inconsistent relational data cleaning by detecting conditional functional dependencies［J］.International Journal of Computer Science and Information Technology&Security，2013，3（1）：120- 125.

［13］Ebaid A，Elmagarmid A，Ilyas I F，et al.NADEEF：a generalized data cleaning system［C］∥Proc.of the 39th International Conference on Very Large Data Bases，2013：1218- 1221.

［14］Bell S.Discovery and maintenance of functional dependencies by independencies［C］∥Proc.of the 1st International Conference on Knowledge Discovery and Data Mining，1995：27- 32.

［15］Han J W，Miceline K.Data mining concepts and techniques［M］.3rd ed.Fan M，Meng X F，trans.Beijing：China Machine Press，2012.（Han J W，Miceline K.數(shù)據(jù)挖掘概念與技術(shù)［M］.3版.范明，孟小峰，譯.北京：機械工業(yè)出版社，2012.）

［16］Zhou J C.Research on incremental mining algorithm of conditional functional dependencies［D］.Guangzhou：Jinan University，2013.（周健昌.條件函數(shù)依賴增量挖掘算法研究［D］.廣州：暨南大學，2013.）

周健昌（198-6- ），男，碩士研究生，主要研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘。

E-mail：jianchangzhou＠163.com

Incremental calculation of conditional functional dependencies

LIU Bo，ZHOU Jian-chang
（College of Information and Science Technology，Jinan University，Guangzhou 510632，China）

A conditional functional dependency（CFD）is an extension of the traditional functional dependency（FD）.By introducing the conditional pattern，the CFD is more accurate and more expressive than FDs in semantics.However，it is time-consuming for computing CFDs.In order to improve the efficiency of CFDs，the incremental maintenance method for CFDs is studied.The changing rules on the conditions of three different situations（i.e.，dataset insertion，deletion，update）are analyzed，and an incremental algorithm for calculating CFDs is proposed，so that we can efficiently and dynamically maintain CFDs while the database is changing.At the same time，the correctness of key steps of the algorithm is demonstrated，and the validness of the algorithm is verified through the experiments.

incremental calculation；conditional functional dependencies（CFDs）；data mining

TP 311.13

A

10.3969／j.issn.1001-506X.2015.11.33

劉 波（1965- ），女，教授，主要研究方向為數(shù)據(jù)庫、信息集成、數(shù)據(jù)挖掘。

E-mail：ddxllb＠163.com

1001-506X（2015）11-2640-08

2014- 06- 01；

2015- 03- 22；網(wǎng)絡(luò)優(yōu)先出版日期：2015- 07- 06。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150706.1705.014.html

國家自然科學基金（U1431227）；廣東省科技計劃項目（2013B010401017）；廣東省自然科學基金（S2012010008831）資助課題