一種增量發(fā)現(xiàn)條件函數(shù)依賴的算法＊

李丁月，劉建勛，翟海軍

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

1 引言

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

數(shù)據(jù)質(zhì)量的主要評價指標包括以下幾個方面：一致性（Consistency）、正確性（Correctness）、完整性（Completeness）和最小性（Minimality）［1］。其中，如何解決數(shù)據(jù)的不一致性問題是近年數(shù)據(jù)庫研究領(lǐng)域的一個熱門課題。早期，研究人員主要采用函數(shù)依賴FDs（Functional Dependencies）來檢測和修改不一致數(shù)據(jù)。其中，文獻［4～6］提出了一些自動從關(guān)系數(shù)據(jù)庫中發(fā)現(xiàn)函數(shù)依賴的方法。函數(shù)依賴可以有效地進行模式發(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）七個屬性。表1中存在一些不一致數(shù)據(jù)。例如，在Tuple為t5的記錄中，REL屬性的取值是 Wife，SEX屬性的取值是Male。很明顯，這條記錄中存在不一致數(shù)據(jù)，SEX屬性的正確取值應(yīng)是female。類似于表1中的這種數(shù)據(jù)不一致情形在現(xiàn)實數(shù)據(jù)中大量地存在，但是利用函數(shù)依賴無法有效檢測出這些不一致的數(shù)據(jù)。找到一種能夠自動檢測和修改不一致數(shù)據(jù)的方法成為急需解決的問題。

文獻［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ù)約束能力更強，能更有效地修復(fù)不一致數(shù)據(jù)。

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

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

2 基本概念

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

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

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

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

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

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

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

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

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

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

定義4（條件函數(shù)依賴語義）［14］對于定義在R上的條件函數(shù)依賴φ＝（R：X→Y，Tp），如果R上的實例I中的任意兩個元組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è)計與分析

3.1 CFINDER算法介紹

CFINDER算法的核心思想是找到屬性集X、Y中滿足如下關(guān)系的屬性值x和y：在關(guān)系R的任意元組中，只要屬性X取值為x，則屬性Y的取值一定為y。CFINDER算法發(fā)現(xiàn)的條件函數(shù)依賴具有以下三個特點：（1）所發(fā)現(xiàn)的條件函數(shù)依賴的Y屬性是由一個單一屬性A構(gòu)成的，其模式組Tp是由單一的模式元組tp組成；（2）關(guān)系R上的實例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)點在于其有效地發(fā)現(xiàn)了條件函數(shù)依賴，同時結(jié)構(gòu)簡單，易于理解，沒有過多的復(fù)雜推導(dǎo)。但是，CFINDER算法無法對已挖掘出來的條件函數(shù)依賴進行快速的更新、維護和管理。數(shù)據(jù)集的更新可能導(dǎo)致原始數(shù)據(jù)集上的CFDs失效，或新的CFDs的產(chǎn)生。為獲得更新后的整個數(shù)據(jù)集中的條件函數(shù)依賴，最簡單的方法就是在更新后的數(shù)據(jù)集上重新執(zhí)行挖掘過程，但這樣將導(dǎo)致大量時間浪費在對已處理過的原始數(shù)據(jù)集的重復(fù)計算上。為更好地解決由數(shù)據(jù)集更新所引起的條件函數(shù)依賴改變的問題，本文應(yīng)用遞進處理思想，在CFINDER算法的基礎(chǔ)上提出并實現(xiàn)了一種增量式更新算法（簡稱CFUP）。

3.2 CFUP算法設(shè)計

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

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

CFUP算法的具體步驟如下：

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

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

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

其中，CFD判定步驟為：

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

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

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

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

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

（8）若相對數(shù)據(jù)集D′上的實例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ì)量比較大的球體異常值比較大，同時異常分布明顯。因此，對于中心埋深相同的情況下，質(zhì)量大的球體異常表現(xiàn)更加明顯，該成像方法適用淺層地質(zhì)體模型的大質(zhì)量異常礦體勘探。

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

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

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

（5）若φ為第二類條件函數(shù)依賴，則根據(jù)變量屬性的可取域，將φ轉(zhuǎn)換成多個第一類條件函數(shù)依賴α。計算一個α在相對數(shù)據(jù)集D′上的滿足情況。若相對數(shù)據(jù)集D′上所有實例I都滿足α，則計算α在整個數(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ù)依賴變更這個問題，一種簡單的方法是在當數(shù)據(jù)庫更新時，重新運行CFINDER算法?，F(xiàn)在我們將增量式更新算法CFUP與重新運行CFINDER算法進行性能比較。

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

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

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

4 實驗及其分析

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

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

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

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

為驗證當原始數(shù)據(jù)集的大小固定時，新增數(shù)據(jù)集的大小對CFUP算法和CFINDER算法的運行時間和準確率的影響，本文選取了Adult和Mushroom兩個較小的數(shù)據(jù)集進行實驗。其中，選取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時的運行時間和準確率。圖3和圖4分別展示了CFUP算法和CFINDER算法在Mushroom數(shù)據(jù)集上增量式地發(fā)現(xiàn)CFDs時的運行時間和準確率。

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

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

為驗證CFUP算法和CFINDER算法的存儲空間變化，本文選取了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時的存儲空間的變化。從圖7可以看出，CFUP算法和CFINDER算法的存儲空間都隨著數(shù)據(jù)集的增大而增大。這是因為數(shù)據(jù)集的增大會導(dǎo)致CFDs的可取域變大，而CFDs的可取域是影響CFUP算法和CFINDER算法的存儲空間的重要因素。同時，CFUP算法的存儲空間的開銷比CFINDER算法微大，這是因為CFUP算法在實現(xiàn)的過程中保留了每個有效CFD的匹配元組數(shù)目。

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

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

5 結(jié)束語

目前，國內(nèi)外研究人員正在對條件函數(shù)依賴理論及其應(yīng)用展開深入研究。條件函數(shù)依賴將在檢測和修改數(shù)據(jù)庫的不一致性方面起到重要作用。本文在CFINDER算法的基礎(chǔ)上，提出了條件函數(shù)依賴增量式更新算法CFUP，其充分利用了之前得到的挖掘結(jié)果來對條件函數(shù)依賴進行增量式更新。該算法是針對當數(shù)據(jù)庫增加一批新數(shù)據(jù)時，對條件函數(shù)依賴進行快速、有效的更新。因此，下一步工作將針對數(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.

附中文參考文獻：

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

［9］ 胡艷麗，張維明.條件依賴理論及其應(yīng)用展望 ［J］.計算機科學，2009，36（12）：115－118.