李丁月，劉建勛，翟海軍

（1.湘潭大學(xué)信息工程學(xué)院，湖南 湘潭411100；2.湖南科技大學(xué)知識處理與網(wǎng)絡(luò)化制造湖南省教育廳重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭411100）

1 引言

隨著信息技術(shù)的快速發(fā)展，人類社會(huì)累積的數(shù)據(jù)每年都在呈指數(shù)上漲，這些數(shù)據(jù)中存在大量錯(cuò)誤、不一致以及冗余的數(shù)據(jù)，即“臟數(shù)據(jù)”［1］?！芭K數(shù)據(jù)”從各個(gè)方面影響組織的運(yùn)作、收入和效率。據(jù)估計(jì)，美國政府每年在改善數(shù)據(jù)質(zhì)量方面的花費(fèi)達(dá)到了近600億美元［2］。數(shù)據(jù)清除的目的是解決“臟數(shù)據(jù)”問題，檢測和修改數(shù)據(jù)中的錯(cuò)誤、不一致和重復(fù)數(shù)據(jù)，從而提高數(shù)據(jù)質(zhì)量［3］。

數(shù)據(jù)質(zhì)量的主要評價(jià)指標(biāo)包括以下幾個(gè)方面：一致性（Consistency）、正確性（Correctness）、完整性（Completeness）和最小性（Minimality）［1］。其中，如何解決數(shù)據(jù)的不一致性問題是近年數(shù)據(jù)庫研究領(lǐng)域的一個(gè)熱門課題。早期，研究人員主要采用函數(shù)依賴FDs（Functional Dependencies）來檢測和修改不一致數(shù)據(jù)。其中，文獻(xiàn)［4～6］提出了一些自動(dòng)從關(guān)系數(shù)據(jù)庫中發(fā)現(xiàn)函數(shù)依賴的方法。函數(shù)依賴可以有效地進(jìn)行模式發(fā)現(xiàn)，然而，其在抓取數(shù)據(jù)中的語義方面往往無能為力。表1描述的記錄出自1994年美國Adult Census數(shù)據(jù)庫，其中包括work class（WC）、education（ED）、marital status（MS）、occupation（OCC）、relationship（REL）、sex（SEX）、native－country（NC）七個(gè)屬性。表1中存在一些不一致數(shù)據(jù)。例如，在Tuple為t5的記錄中，REL屬性的取值是 Wife，SEX屬性的取值是Male。很明顯，這條記錄中存在不一致數(shù)據(jù)，SEX屬性的正確取值應(yīng)是female。類似于表1中的這種數(shù)據(jù)不一致情形在現(xiàn)實(shí)數(shù)據(jù)中大量地存在，但是利用函數(shù)依賴無法有效檢測出這些不一致的數(shù)據(jù)。找到一種能夠自動(dòng)檢測和修改不一致數(shù)據(jù)的方法成為急需解決的問題。

文獻(xiàn)［7］在函數(shù)依賴的基礎(chǔ)上，提出了條件函數(shù)依賴 CFDs（Conditional Functional Dependencies）的概念，并將其應(yīng)用于檢測和修改不一致數(shù)據(jù)。條件函數(shù)依賴通過綁定關(guān)系中的屬性及其語義相關(guān)的數(shù)據(jù)，來定義滿足約束的數(shù)據(jù)應(yīng)用模式，從而檢測不符合依賴形式的數(shù)據(jù)。因此，條件函數(shù)依賴比函數(shù)依賴的數(shù)據(jù)約束能力更強(qiáng)，能更有效地修復(fù)不一致數(shù)據(jù)。

目前，國內(nèi)外學(xué)者對條件函數(shù)依賴開展了一系列的研究工作。其中，文獻(xiàn)［7～9］對條件函數(shù)依賴?yán)碚摷捌鋺?yīng)用做了相關(guān)介紹。文獻(xiàn)［10～13］提出了一些從數(shù)據(jù)集中發(fā)現(xiàn)條件函數(shù)依賴的方法。這些方法主要側(cè)重于提高條件函數(shù)依賴的精確度和減少執(zhí)行時(shí)間，其無法快速更新、維護(hù)和管理已挖掘出來的條件函數(shù)依賴。例如，當(dāng)數(shù)據(jù)集上增加一個(gè)新數(shù)據(jù)時(shí)，已有的方法必須將新增數(shù)據(jù)集與原始數(shù)據(jù)集進(jìn)行合并，再對合并后的整個(gè)數(shù)據(jù)集重新執(zhí)行發(fā)現(xiàn)過程，才能更新CFDs，但這將導(dǎo)致大部分時(shí)間都浪費(fèi)在對已處理數(shù)據(jù)集的重復(fù)計(jì)算上。

針對條件函數(shù)依賴的更新問題，本文借鑒增量更新思想提出一種增量更新條件函數(shù)依賴的方法，并在條件函數(shù)依賴的發(fā)現(xiàn)方法［11］（簡稱CFINDER算法）的基礎(chǔ)上實(shí)現(xiàn)了條件函數(shù)依賴增量更新算法CFUP。當(dāng)數(shù)據(jù)集上增加一批新的數(shù)據(jù)時(shí)，CFUP算法通過掃描新增數(shù)據(jù)集，來判定原數(shù)據(jù)集上的CFDs在更新后的數(shù)據(jù)集上是否有效，是否產(chǎn)生了新的CFDs，從而達(dá)到更新CFDs的目的。最后，通過實(shí)驗(yàn)對CFUP算法和重新運(yùn)行的CFINDER算法進(jìn)行性能比較，實(shí)驗(yàn)表明CFUP算法比重新運(yùn)行CFINDER算法在時(shí)間上更有效。

2 基本概念

定義1 （條件函數(shù)依賴）［14］在關(guān)系模式R上成立的條件函數(shù)依賴φ表示為（R：X→Y，Tp），其中：

（1）X、Y表示關(guān)系R上的屬性集合。

（2）X→Y表示一個(gè)嵌入φ的函數(shù)依賴。

（3）Tp是X∪Y 屬性集上的模式組（Pattern Tableau），由若干模式元組tp組成。tp定義了相關(guān)屬性在取值上的約束條件，可以是對應(yīng)屬性可取域中的某個(gè)常量，也可以是對應(yīng)屬性可取域中的任意值，用“＿”表示任意值 。

從以上定義可以看出，Tp通過綁定屬性及其取值，來指定嵌入式函數(shù)依賴成立的條件。表1中的條件函數(shù)依賴φ如下所示：

Table 1 Records in the USA Adult database in 1994表1 1994年美國Adult數(shù)據(jù)庫的記錄

其中，φ指一個(gè)人若是已婚的男性，則其家庭成分為丈夫。

定義2（匹配）［14］對于屬性A的取值a和b，若：（1）a和b都是常量，且a＝b；（2）a或b為“＿”，則a匹配b，記作ab。

匹配是對函數(shù)依賴中屬性取值相等的擴(kuò)展，主要用于判斷實(shí)例與模式元組或者模式元組之間相同的屬性取值是否存在對應(yīng)關(guān)系。

定義3（元組匹配）［14］對于一個(gè)元組t和模式組Tp中的一個(gè)模式元組tp，如果tp中的每一個(gè)屬性A，都有tp［A］＝t［A］，或者tp［A］＝“＿”，那么稱t匹配tp，記作ttp。

定義4（條件函數(shù)依賴語義）［14］對于定義在R上的條件函數(shù)依賴φ＝（R：X→Y，Tp），如果R上的實(shí)例I中的任意兩個(gè)元組t1、t2滿足如下關(guān)系：若t1［X］＝t2［X］tp［X］，則t1［Y］＝t2［Y］tp［Y］，那么稱I滿足φ，記作I╞φ。

定義5（支持度）條件函數(shù)依賴φ＝（R：X→Y，Tp）在R上的支持度定義為與φ相匹配的元組數(shù)目在R上所占的比例，其公式如下：

其中，φ·count表示關(guān)系R中與φ相匹配的元組數(shù)目，｜R｜表示關(guān)系R上所包含的元組數(shù)。若元組t匹配φ中的模式組Tp中的任意模式元組tp，則稱元組t匹配φ。

3 算法設(shè)計(jì)與分析

3.1 CFINDER算法介紹

CFINDER算法的核心思想是找到屬性集X、Y中滿足如下關(guān)系的屬性值x和y：在關(guān)系R的任意元組中，只要屬性X取值為x，則屬性Y的取值一定為y。CFINDER算法發(fā)現(xiàn)的條件函數(shù)依賴具有以下三個(gè)特點(diǎn)：（1）所發(fā)現(xiàn)的條件函數(shù)依賴的Y屬性是由一個(gè)單一屬性A構(gòu)成的，其模式組Tp是由單一的模式元組tp組成；（2）關(guān)系R上的實(shí)例I必定滿足所發(fā)現(xiàn)的條件函數(shù)依賴；（3）所發(fā)現(xiàn)的條件函數(shù)依賴是令人感興趣的，滿足最小評估閾值。根據(jù)條件函數(shù)依賴模式元組tp上的屬性取值的不同，可將條件函數(shù)依賴分為如下三類：

（1）第一類條件函數(shù)依賴（CFD＿1）：模式元組tp上的所有屬性的取值都是常數(shù)的條件函數(shù)依賴。

（2）第二類條件函數(shù)依賴（CFD＿2）：模式元組tp上的屬性的取值既存在常數(shù)又存在變量的條件函數(shù)依賴。

（3）第三類條件函數(shù)依賴（CFD＿3）：模式元組tp上的所有屬性的取值都是變量的條件函數(shù)依賴，即傳統(tǒng)的函數(shù)依賴。

CFINDER算法的優(yōu)點(diǎn)在于其有效地發(fā)現(xiàn)了條件函數(shù)依賴，同時(shí)結(jié)構(gòu)簡單，易于理解，沒有過多的復(fù)雜推導(dǎo)。但是，CFINDER算法無法對已挖掘出來的條件函數(shù)依賴進(jìn)行快速的更新、維護(hù)和管理。數(shù)據(jù)集的更新可能導(dǎo)致原始數(shù)據(jù)集上的CFDs失效，或新的CFDs的產(chǎn)生。為獲得更新后的整個(gè)數(shù)據(jù)集中的條件函數(shù)依賴，最簡單的方法就是在更新后的數(shù)據(jù)集上重新執(zhí)行挖掘過程，但這樣將導(dǎo)致大量時(shí)間浪費(fèi)在對已處理過的原始數(shù)據(jù)集的重復(fù)計(jì)算上。為更好地解決由數(shù)據(jù)集更新所引起的條件函數(shù)依賴改變的問題，本文應(yīng)用遞進(jìn)處理思想，在CFINDER算法的基礎(chǔ)上提出并實(shí)現(xiàn)了一種增量式更新算法（簡稱CFUP）。

3.2 CFUP算法設(shè)計(jì)

CFUP算法是一個(gè)基于CFINDER算法的條件函數(shù)依賴增量式更新算法。增量式的發(fā)現(xiàn)條件函數(shù)依賴的主要思想是掃描新增數(shù)據(jù)集，充分利用前期挖掘過程中獲得的CFDs及其部分中間結(jié)果，去掉那些不滿足條件的舊的CFDs，發(fā)現(xiàn)滿足條件的新的CFDs，其目的是減少對原始數(shù)據(jù)集的掃描和處理，快速發(fā)現(xiàn)更新后整個(gè)數(shù)據(jù)集上的CFDs。

為了找到那些令人感興趣的條件函數(shù)依賴，CFINDER算法采用了支持度、置信度等多種興趣測量方法來對條件函數(shù)依賴進(jìn)行評估。CFUP算法選擇采用支持度來發(fā)現(xiàn)那些令人感興趣的條件函數(shù)依賴。

CFUP算法的具體步驟如下：

首先，掃描新增數(shù)據(jù)集，利用CFINDER算法發(fā)現(xiàn)其上的CFDs。

其次，將新增數(shù)據(jù)集ΔD上的CFDs和原數(shù)據(jù)集D上的CFDs進(jìn)行比較，選出ΔD上不重復(fù)的CFDs。

最后，對新增數(shù)據(jù)集ΔD上的不重復(fù)的CFDs和原數(shù)據(jù)集D上的CFDs進(jìn)行判定，看其在整個(gè)數(shù)據(jù)集上是否仍然是有效CFDs或是否產(chǎn)生了新的CFDs。

其中，CFD判定步驟為：

（1）對每一個(gè)CFDφ，計(jì)算其相對數(shù)據(jù)集中的實(shí)例I對φ的滿足情況。其中，原數(shù)據(jù)集上的CFDs的相對數(shù)據(jù)集D′是新增數(shù)據(jù)集ΔD，新增數(shù)據(jù)集上的CFDs的相對數(shù)據(jù)集D′是原數(shù)據(jù)集D。

（2）如果相對數(shù)據(jù)集上的所有實(shí)例I都滿足φ，則計(jì)算φ在相對數(shù)據(jù)集D′上的支持度：

如果Support（φ）≥minsupport，則α是整個(gè)數(shù)據(jù)集上滿足條件的CFD。

（6）若φ為第三類條件函數(shù)依賴，則根據(jù)變量屬性的可取域，將φ轉(zhuǎn)換成多個(gè)第二類條件函數(shù)依賴α。計(jì)算α相對數(shù)據(jù)集上的滿足情況。

（7）若相對數(shù)據(jù)集D′上的所有實(shí)例I都滿足α，則利用（5）中的支持度公式計(jì)算α在整個(gè)數(shù)據(jù)集上的支持度。如果Support（φ）≥minsupport，則α是整個(gè)數(shù)據(jù)集上滿足條件的CFD。

（8）若相對數(shù)據(jù)集D′上的實(shí)例I不全滿足α，則重復(fù)步驟（5）。

CFUP算法偽代碼如下：

INPUT：Dis the original dataset；ΔDis the additional dataset；CLDis the set of CFDs in the original dataset；

1：scanΔDand use CFINDER algorithm get CFDs in CL△D

2：CLD∪△D＝?

3：for every CFDαin CLD

4： Judge－CFD（ΔD，D∪△D，α，CLD∪△D）

5：end for

6：for every CFDαin CL△D－CLD

7： Judge－CFD（D，D∪△D，CLD∪△D）

8：end for

OUTPUT：CLD∪△D

圖7a分析結(jié)果顯示，異常地質(zhì)體中心埋深比較清楚，異常值中心埋深都在z0=20m，左側(cè)質(zhì)量小的球體異常值比較小，右側(cè)質(zhì)量比較大的球體異常值比較大，同時(shí)異常分布明顯。因此，對于中心埋深相同的情況下，質(zhì)量大的球體異常表現(xiàn)更加明顯，該成像方法適用淺層地質(zhì)體模型的大質(zhì)量異常礦體勘探。

如果Support（φ）≥minsupport，則φ是整個(gè)數(shù)據(jù)集上滿足條件的CFD。

（3）如果相對數(shù)據(jù)集上存在不滿足φ的實(shí)例，則根據(jù)CFD的所屬類別對CFD進(jìn)行操作。

（4）若φ為第一類條件函數(shù)依賴，則φ是整個(gè)數(shù)據(jù)集上滿足條件的CFD。

（5）若φ為第二類條件函數(shù)依賴，則根據(jù)變量屬性的可取域，將φ轉(zhuǎn)換成多個(gè)第一類條件函數(shù)依賴α。計(jì)算一個(gè)α在相對數(shù)據(jù)集D′上的滿足情況。若相對數(shù)據(jù)集D′上所有實(shí)例I都滿足α，則計(jì)算α在整個(gè)數(shù)據(jù)集上的支持度：

DEFINE Judge－CFD（D，D∪△D，α，CLD∪△D）

1：scan Dand comput the satisfaction ofαon the in－stance I

2：if（I╞α）then compute Support（α）in D

3： if（Support（α）≥minsupport）then

5： else CLD＝CLD－α

6： end if

7：else

8： if（α∈CFD＿1）then CLD＝CLD－α；

9： else

10： if（α∈CFD＿2）then

11： convertαtoφof CFD＿1and Judge－CFD（D ∪ △D，D ∪ △D，φ，CLD∪△D）

12： else

13： if（α∈CFD＿3）then

14： convertαtoφof CFD＿2and Judge－CFD（D ∪ △D，D ∪△D，φ，CLD∪△D）

15： end if

16： end if

17： end if

18：end if

19：return（CLD∪△D）

3.3 CFUP算法性能分析

對于由數(shù)據(jù)庫更新而引起的條件函數(shù)依賴變更這個(gè)問題，一種簡單的方法是在當(dāng)數(shù)據(jù)庫更新時(shí)，重新運(yùn)行CFINDER算法?，F(xiàn)在我們將增量式更新算法CFUP與重新運(yùn)行CFINDER算法進(jìn)行性能比較。

在增量發(fā)現(xiàn)CFDs的過程中，CFINDER算法需要存儲(chǔ)CFDs的可取域，而CFUP算法需要存儲(chǔ)CFDs的可取域和其對應(yīng)的匹配元組數(shù)。假設(shè)整個(gè)數(shù)據(jù)集上發(fā)現(xiàn)了N個(gè)CFDs，且每個(gè)CFDs的可取域的大小為ki，則CFINDER算法的空間復(fù)雜度CFUP 算 法 的 空 間 復(fù) 雜 度 為。相對于 CFINDER算法而言，CFUP算法增加了O（N）的存儲(chǔ)開銷。

數(shù)據(jù)一致性維護(hù)是NP完全問題，CFINDER和CFUP算法都采用窮舉法來解決NP完全問題，所以其時(shí)間復(fù)雜度都較高。CFINDER算法在更新CFDs的過程中需要掃描整個(gè)數(shù)據(jù)集多次，掃描的次數(shù)由數(shù)據(jù)集中屬性的個(gè)數(shù)決定。而CFUP算法利用已有的挖掘結(jié)果以減少原數(shù)據(jù)集掃描的次數(shù)，對原始數(shù)據(jù)集的掃描次數(shù)取決于新增數(shù)據(jù)集上與原有CFDs不同的CFDs個(gè)數(shù)L。假設(shè)數(shù)據(jù)集的屬性個(gè)數(shù)為M，原數(shù)據(jù)集記錄總數(shù)為N，新增數(shù)據(jù)記錄總數(shù)為ΔN，則在最壞的情況下，CFINDER算法需要掃描數(shù)據(jù)集2M次，其時(shí)間復(fù)雜度為O（（N＋ΔN）＊2M）。CFUP算法需要掃描新增數(shù)據(jù)集2M次，原數(shù)據(jù)集L次。CFUP算法時(shí)間復(fù)雜度為O（N＊L＋ΔN ＊2M），其中，0≤L≤2M－L1，L1為原數(shù)據(jù)集中CFDs的個(gè)數(shù)。CFUP算法比CFINDER算法減少了O（N＊（2M－L））的時(shí)間開銷。在N／ΔN較大、L和M 較小的情況下，不管新增數(shù)據(jù)如何變化，CFUP算法都在時(shí)間上明顯優(yōu)于CFINDER算法。CFUP算法的時(shí)間復(fù)雜度主要受屬性的個(gè)數(shù)和新增數(shù)據(jù)記錄數(shù)的影響，數(shù)據(jù)變化的快慢程度對其影響不大。所以，當(dāng)數(shù)據(jù)變化十分迅速但每次增量微小時(shí)，CFUP算法仍然能夠有效地進(jìn)行增量更新。

總的來說，CFUP算法保存挖掘過程中的一些中間結(jié)果，用于后續(xù)的增量式發(fā)現(xiàn)，從而造成了系統(tǒng)所需存儲(chǔ)空間的增大，但是其絕對增加量并不大。在不討論新增數(shù)據(jù)內(nèi)容變化迅速的情況下，只要新增數(shù)據(jù)集相對原數(shù)據(jù)集較小、數(shù)據(jù)集屬性個(gè)數(shù)較小，CFUP算法都能在時(shí)間上明顯優(yōu)于CFINDER算法。

4 實(shí)驗(yàn)及其分析

為驗(yàn)證CFUP算法的可行性和有效性，本文采用了三個(gè)真實(shí)數(shù)據(jù)集，并在運(yùn)行Windows操作系統(tǒng)（處理器：Intel（R）Core（TM）i3CPU 3.20 GHz，內(nèi)存：2.00GB）的PC上進(jìn)行了實(shí)驗(yàn)。

4.1 數(shù)據(jù)集

本文選取了UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的三個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別是 Adult、Mushroom、Census－income（KDD）數(shù)據(jù)集。其中，Adult數(shù)據(jù)集是一個(gè)描述美國公民基本特性的數(shù)據(jù)集，其中包含32 561條記錄和14個(gè)屬性。Mushroom數(shù)據(jù)集是一個(gè)描述蘑菇基本特性的數(shù)據(jù)集，其中包含8 124條記錄和23個(gè)屬性。Census－income數(shù)據(jù)集是一個(gè)與A－dult數(shù)據(jù)集相似的大型數(shù)據(jù)集，其中包含299 285條記錄和40個(gè)屬性。

4.2 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證當(dāng)原始數(shù)據(jù)集的大小固定時(shí)，新增數(shù)據(jù)集的大小對CFUP算法和CFINDER算法的運(yùn)行時(shí)間和準(zhǔn)確率的影響，本文選取了Adult和Mushroom兩個(gè)較小的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，選取A－dult數(shù)據(jù)集中的15 000條數(shù)據(jù)作為原始數(shù)據(jù)集，新增數(shù)據(jù)的記錄總數(shù)從2 000到18 000條，其屬性數(shù)目n＝10，最小支持度閾值s＝0.6。Mushroom數(shù)據(jù)集中的4 000條記錄作為原始數(shù)據(jù)集，新增數(shù)據(jù)集中的記錄總數(shù)從500到4 000條，其中屬性數(shù)目n＝15，最小支持度閾值s＝0.6。

圖1和圖2分別展示了CFUP算法和CFINDER算法在Adult數(shù)據(jù)集上增量式地發(fā)現(xiàn)CFDs時(shí)的運(yùn)行時(shí)間和準(zhǔn)確率。圖3和圖4分別展示了CFUP算法和CFINDER算法在Mushroom數(shù)據(jù)集上增量式地發(fā)現(xiàn)CFDs時(shí)的運(yùn)行時(shí)間和準(zhǔn)確率。

從圖1～圖4可以看出，對于不同大小的新增數(shù)據(jù)集，CFUP算法和CFINDER算法的準(zhǔn)確率沒有顯著差異。但是，CFUP算法耗費(fèi)的時(shí)間明顯少于CFINDER算法，且CFUP算法和CFINDER算法消耗的時(shí)間差隨著新增數(shù)據(jù)集的增大而逐漸減少。這是由于CFUP算法主要是通過減少對原始數(shù)據(jù)集的掃描次數(shù)來達(dá)到減少運(yùn)行時(shí)間的目的。新增數(shù)據(jù)集增大了，原始數(shù)據(jù)集的大小對算法運(yùn)行時(shí)間的影響就越小。所以，在原始數(shù)據(jù)集大小固定的情況下，新增數(shù)據(jù)集越小，CFUP算法比CFINDER算法的時(shí)間優(yōu)勢就體現(xiàn)得越明顯。

為進(jìn)一步驗(yàn)證當(dāng)新增數(shù)據(jù)集的大小固定時(shí)，原始數(shù)據(jù)集的大小對CFINDER算法和CFUP算法的運(yùn)行時(shí)間和準(zhǔn)確率的影響，本文采用Census income數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，其中選取的新增數(shù)據(jù)集的大小為1k，原始數(shù)據(jù)集從20k到100k，屬性個(gè)數(shù)n＝10，最小支持度閾值s＝0.6。圖5和圖6分別顯示了CFUP算法和CFINDER算法在Census－income數(shù)據(jù)集上增量式地發(fā)現(xiàn)條件函數(shù)依賴的運(yùn)行時(shí)間和準(zhǔn)確率。從圖5可以看出，在新增數(shù)據(jù)集的大小固定的條件下，原數(shù)據(jù)集越大，CFUP算法運(yùn)行時(shí)間與CFINDER算法的運(yùn)行時(shí)間差越大，CFUP算法在時(shí)間上的優(yōu)勢越大。從圖6可以看出，Census－income數(shù)據(jù)集上CFUP算法和CFINDER算法的準(zhǔn)確率沒有顯著差異。

為驗(yàn)證CFUP算法和CFINDER算法的存儲(chǔ)空間變化，本文選取了Mushroom數(shù)據(jù)集中的4 000條記錄作為原始數(shù)據(jù)集，新增數(shù)據(jù)集中的記錄總數(shù)從500到4 000條，其中屬性數(shù)目n＝15，最小支持度閾值s＝0.6。

圖7展示了CFUP算法和CFINDER算法在Mushroom數(shù)據(jù)集上增量式地發(fā)現(xiàn)CFDs時(shí)的存儲(chǔ)空間的變化。從圖7可以看出，CFUP算法和CFINDER算法的存儲(chǔ)空間都隨著數(shù)據(jù)集的增大而增大。這是因?yàn)閿?shù)據(jù)集的增大會(huì)導(dǎo)致CFDs的可取域變大，而CFDs的可取域是影響CFUP算法和CFINDER算法的存儲(chǔ)空間的重要因素。同時(shí)，CFUP算法的存儲(chǔ)空間的開銷比CFINDER算法微大，這是因?yàn)镃FUP算法在實(shí)現(xiàn)的過程中保留了每個(gè)有效CFD的匹配元組數(shù)目。

Figure 7 Space cost on the Mushroom dataset圖7 Mushroom數(shù)據(jù)集上存儲(chǔ)空間開銷

總的來說，當(dāng)新增數(shù)據(jù)集相對于原數(shù)據(jù)集較小的情況下，CFUP算法雖然比CFINDER算法增加了一點(diǎn)存儲(chǔ)開銷，但在時(shí)間上明顯優(yōu)于CFINDER算法。

5 結(jié)束語

目前，國內(nèi)外研究人員正在對條件函數(shù)依賴?yán)碚摷捌鋺?yīng)用展開深入研究。條件函數(shù)依賴將在檢測和修改數(shù)據(jù)庫的不一致性方面起到重要作用。本文在CFINDER算法的基礎(chǔ)上，提出了條件函數(shù)依賴增量式更新算法CFUP，其充分利用了之前得到的挖掘結(jié)果來對條件函數(shù)依賴進(jìn)行增量式更新。該算法是針對當(dāng)數(shù)據(jù)庫增加一批新數(shù)據(jù)時(shí)，對條件函數(shù)依賴進(jìn)行快速、有效的更新。因此，下一步工作將針對數(shù)據(jù)庫數(shù)據(jù)內(nèi)容改變這種情況研究條件函數(shù)依賴的發(fā)現(xiàn)策略。

［1］ Aebi D，Perrochon L.Towards improving data quality［C］∥Proc of the International Conference on Information Systems and Management of Data，1993：273－281.

［2］ Eckerson W.Data auality and the bottom line［R］.Technical Report，TDWI Report Series，2002.

［3］ Rahm E，Do H H.Data cleaning：Problems and current approaches［J］.IEEE Data Engineering Bulletin，2000，23（4）：3－13.

［4］ Huhtala Y，Kinen J，Porkka P，et al.Efficient discovery of functional and approximate dependencies using partitions［C］∥Proc of the 14th International Conference on Data Engineering，1998：392－401.

［5］ Lopes S，Petit J－M，Lakhal L.Efficient discovery of functional dependencies and armstrong relations［C］∥Proc of the 7th International Conference on Extending Database Technology：Advances in Database Technology，2000：350－364.

［6］ Wyss C，Giannella C，Robertson E L.FastFDs：A heuristicdriven，depth－first algorithm for mining functional dependencies from relations instances［C］∥Proc of the 3rd International Conference on Data Warehousing and Knowledge Discovery，2001：101－110.

［7］ Bohannon P，F(xiàn)an W，Geerts F，et al.Conditional functional dependencies for data cleaning［C］∥Proc of the 23rd International Conference on Database Engineering，2007：764－755.

［8］ Hu Y，Zhang W，Luo X，et al.Dependencies theory and its application for repairing inconsistent data［J］.Computer Science，2009，36（10）：11－15.（in Chinese）

［9］ Hu Y，Zhang W.Theory of conditional functional dependencies and its application for improving data quality［J］.Computer Science，2009，36（12）：115－118.（in Chinese）

［10］ Golab L，Korn F，Srivastava D，et al.On generating nearoptimal tableaux for conditional functional dependencies［C］∥Proc of the 34th International Conference on Very Large Data Bases，2008：376－390.

［11］ Chiang F，Miller R.Discovering data quality rules［C］∥Proc of the 34th International Conference on Very Large Data Bases，2008：1166－1177.

［12］ Yeh Z P.Discovering conditional functional dependencies to detect data inconsistencies［C］∥Proc of the 36th International Conference on Very Large Data Bases，2010：256－270.

［13］ Fan W，Geerts F，Lakshmanan L V S，et al.Discovering conditional functional dependencies ［C］∥ Proc of 2009 IEEE International Conference on Data Engineering，2009：1231－1234.

［14］ Fan W，Jia X，Kementsietsidis A.Conditional functional dependencies for capturing data inconsistencies［J］.ACM Transactions on Database Systems，2008，33（2）：1－48.

附中文參考文獻(xiàn)：

［8］ 胡艷麗，張維明，羅旭輝，等.基于數(shù)據(jù)依賴的數(shù)據(jù)修復(fù)研究進(jìn)展 ［J］.計(jì)算機(jī)科學(xué)，2009，36（10）：11－15.

［9］ 胡艷麗，張維明.條件依賴?yán)碚摷捌鋺?yīng)用展望 ［J］.計(jì)算機(jī)科學(xué)，2009，36（12）：115－118.