黃 慧，李海林

1.三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210012

2.南京航空航天大學(xué) 電子與信息工程學(xué)院，南京 211100

隨著大數(shù)據(jù)時(shí)代的到來(lái)，劣質(zhì)數(shù)據(jù)也隨之增長(zhǎng)，給社會(huì)、企業(yè)帶來(lái)不可預(yù)知的經(jīng)濟(jì)損失[1]。據(jù)國(guó)外權(quán)威機(jī)構(gòu)的統(tǒng)計(jì)數(shù)據(jù)顯示，在對(duì)數(shù)據(jù)融合、加工、處理的過(guò)程中，企業(yè)有1%～30%的數(shù)據(jù)不可避免地存在各種不一致和錯(cuò)誤[2]；約13.6%～81.0%的重要醫(yī)療數(shù)據(jù)存在缺失或過(guò)時(shí)的現(xiàn)象[3]；全球財(cái)富1 000 強(qiáng)的企業(yè)中，超過(guò)25%的企業(yè)信息系統(tǒng)中存在錯(cuò)誤數(shù)據(jù)[4]。近年來(lái)，在軟件開(kāi)發(fā)過(guò)程中，數(shù)據(jù)修復(fù)工作占有越來(lái)越重要的地位[5]；學(xué)術(shù)界，數(shù)據(jù)質(zhì)量問(wèn)題也引起學(xué)者們的高度關(guān)注，其中，不一致性是數(shù)據(jù)質(zhì)量的關(guān)鍵問(wèn)題之一。

通常，不一致數(shù)據(jù)的檢測(cè)普遍基于函數(shù)依賴(lài)X→Y[6-7]。按照函數(shù)依賴(lài)規(guī)則，不難發(fā)現(xiàn)例1 中存在數(shù)據(jù)不一致問(wèn)題。

例1考慮關(guān)系模式Employee（ID,EmpID,Office_Tel,Office,Department）由五個(gè)屬性組成，分別表示為元組編號(hào)、員工編號(hào)、辦公室電話、辦公室、所在部門(mén)。其中，Employee：D0是由若干空值和正確數(shù)據(jù)組成的原始數(shù)據(jù)集。在員工信息管理的過(guò)程中，由于人員的調(diào)動(dòng)、辦公室的遷移等產(chǎn)生了信息的更新，這些更新處理存放在操作日志（operator log）中，D0在經(jīng)過(guò)了七步操作之后形成了Employee：D7，如圖1所示。

圖1 中的φ1為數(shù)據(jù)集D7上的函數(shù)依賴(lài)，表示辦公室電話唯一決定辦公室的值，用于檢測(cè)D7的一致性。D7中的元組t1～t4違反了該約束，同理，t5和t6兩條元組也違反了φ1。

Fig.1 Inconsistent data set Employee and operator log圖1 不一致數(shù)據(jù)集Employee和操作日志

通常，大多的數(shù)據(jù)不一致性錯(cuò)誤是數(shù)據(jù)在經(jīng)過(guò)加工、處理的過(guò)程中產(chǎn)生的。圖1 中，由于操作人員的不慎或?qū)?shù)據(jù)處理環(huán)節(jié)的不熟悉等原因，使得操作日志中存在著錯(cuò)誤的處理，最終形成了D7中的不一致數(shù)據(jù)。例如，圖1 中的OP1和OP2為誤操作，本應(yīng)將t2、t3元組的辦公室設(shè)置為“R101”，卻誤設(shè)置成了“R102”；更糟糕的是，OP3本是正確的操作，卻由于OP1和OP2，將錯(cuò)誤擴(kuò)散至t2和t3元組的Department屬性。同理，OP4和OP7也是誤操作，形成了D7中t4和t6元組中Offiec_Tel 屬性的錯(cuò)誤。其中，D7的灰色區(qū)域表示與實(shí)際情況相沖突的單元格，括號(hào)內(nèi)為對(duì)應(yīng)的真實(shí)值。

為了修復(fù)不一致數(shù)據(jù)，學(xué)者們根據(jù)不同的約束規(guī)則以及不同的應(yīng)用場(chǎng)景，提出了不同的修復(fù)方法。主要分為基于函數(shù)依賴(lài)的修復(fù)以及基于其他約束規(guī)則的修復(fù)。

（1）基于函數(shù)依賴(lài)的修復(fù)

學(xué)者們針對(duì)函數(shù)依賴(lài)約束規(guī)則提出了不同的修復(fù)方法，但這些方法均未考慮原始數(shù)據(jù)以及數(shù)據(jù)的處理過(guò)程，而是基于最終的數(shù)據(jù)集（如D7）直接進(jìn)行修復(fù)，主要分為三類(lèi)。

第一類(lèi)是基于最少刪除原則的不一致數(shù)據(jù)修復(fù)方法，最早由學(xué)者Chomicki 在文獻(xiàn)[8]提出。方法通過(guò)刪除最少元組使得剩余的數(shù)據(jù)集能夠符合函數(shù)依賴(lài)。按照最少刪除原則，D7中可以刪除t1和t4來(lái)消除t1～t4元組的不一致情形。但這種方法會(huì)造成信息的大量丟失，且可能會(huì)形成錯(cuò)誤的修復(fù)（如t1為正確的元組信息卻被刪除，而t2、t3為包含錯(cuò)誤信息的元組卻被保留）。

第二類(lèi)是由Fan 等提出的基于Master 數(shù)據(jù)和編輯規(guī)則的修復(fù)方法[9]。方法假定存在一個(gè)存放正確數(shù)據(jù)的Master 數(shù)據(jù)庫(kù)，當(dāng)檢測(cè)到不一致數(shù)據(jù)時(shí)，利用編輯規(guī)則建立Master 和不一致數(shù)據(jù)集的對(duì)應(yīng)關(guān)系，獲取Master 中的相應(yīng)數(shù)據(jù)進(jìn)行修復(fù)。能用該方法進(jìn)行修復(fù)的前提是必需存在Master 數(shù)據(jù)庫(kù)，然而，實(shí)際中大多數(shù)據(jù)集難以找到這樣的Master數(shù)據(jù)。

第三類(lèi)是基于最小代價(jià)修復(fù)元組的方法。較為經(jīng)典的是由文獻(xiàn)[10]提出的將元組的可信度作為參數(shù)計(jì)算修復(fù)代價(jià)。通常，可信度越低，修復(fù)代價(jià)越小，表明該元組需要優(yōu)先修復(fù)，此時(shí)獲取修復(fù)代價(jià)最高的元組為目標(biāo)值進(jìn)行修復(fù)。然而，并非所有數(shù)據(jù)集都包含已知的元組可信度（如D7），當(dāng)可信度缺失時(shí)，方法難以適用；此外，當(dāng)檢測(cè)出元組違反函數(shù)依賴(lài)X→Y時(shí)，方法將X屬性集上取值相同的元組劃分為同一等價(jià)類(lèi)，僅支持修改Y屬性值，而實(shí)際中，造成沖突的原因既可能是Y屬性，也可能為X屬性，如t4和t6元組的Office_Tel屬性值。

（2）基于其他約束規(guī)則以及應(yīng)用場(chǎng)景的修復(fù)

文獻(xiàn)[11]基于條件函數(shù)依賴(lài)規(guī)則（CFD），利用已知的可信度和Master 數(shù)據(jù)庫(kù)，提出了數(shù)據(jù)一致性修復(fù)的方法。文獻(xiàn)[12]基于硬約束，提出了集合最小化以及基數(shù)最小化修復(fù)方法。文獻(xiàn)[13]將硬約束擴(kuò)展至數(shù)量約束和等值約束，結(jié)合集合最小化的方法進(jìn)行數(shù)據(jù)修復(fù)。文獻(xiàn)[14]提出了一種時(shí)效約束規(guī)則，并在圖模型的基礎(chǔ)上給出數(shù)據(jù)時(shí)序修復(fù)的算法。文獻(xiàn)[15]將時(shí)效約束和條件函數(shù)依賴(lài)相結(jié)合，使用規(guī)則序列圖的方式對(duì)相互依賴(lài)的規(guī)則排序，進(jìn)而完成修復(fù)操作。文獻(xiàn)[16]提出了序列依賴(lài)規(guī)則以解決有規(guī)律的數(shù)據(jù)不一致問(wèn)題。此外，學(xué)者們還針對(duì)不同的應(yīng)用場(chǎng)景提出了不同的數(shù)據(jù)修復(fù)方法。文獻(xiàn)[17]針對(duì)分布式數(shù)據(jù)庫(kù)，采用最小通信原則的方法，提出了不一致數(shù)據(jù)的檢測(cè)與修復(fù)問(wèn)題。文獻(xiàn)[18]基于XML 數(shù)據(jù)，利用文獻(xiàn)[10]提出的方法，對(duì)XML 數(shù)據(jù)的不一致性進(jìn)行修復(fù)。

例1 中D7的修復(fù)工作屬于基于函數(shù)依賴(lài)的修復(fù)，然而，由于不存在Master 數(shù)據(jù)庫(kù)以及每條元組的可信度值，在信息不丟失的情況下，三類(lèi)方法均難以適用。同時(shí)，其他的修復(fù)方法由于約束規(guī)則及應(yīng)用場(chǎng)景的不同，也不能適用本文。為了能完成修復(fù)，本文在沒(méi)有可信度值的情形下，提出了可信度值的自動(dòng)生成算法，并結(jié)合增量式數(shù)據(jù)修復(fù)方法對(duì)不一致數(shù)據(jù)進(jìn)行修復(fù)，主要貢獻(xiàn)如下：

首先，提出可信度標(biāo)記值自動(dòng)生成算法，算法基于操作日志以及知識(shí)庫(kù)中的知識(shí)規(guī)則進(jìn)行分析，自動(dòng)生成以單元格為粒度的可信度標(biāo)記值。

其次，針對(duì)傳統(tǒng)算法不能修改X屬性值的不足，提出新的數(shù)據(jù)修復(fù)算法，算法對(duì)于違反函數(shù)依賴(lài)X→Y的元組，依據(jù)可信度標(biāo)記值，判斷修復(fù)X屬性值還是Y屬性值，并結(jié)合條件概率和增量式修復(fù)方法對(duì)選定的屬性值進(jìn)行修復(fù)。

最后，在擴(kuò)展的Employee 數(shù)據(jù)集上進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，本文提出的修復(fù)方法具有較好的可行性以及較高的執(zhí)行效率。

1 模型與定義

1.1 相關(guān)定義

本文采用帶有可信度標(biāo)記的增量式數(shù)據(jù)修復(fù)方法進(jìn)行數(shù)據(jù)修復(fù)，引入如下定義。

定義1（操作日志（operator log））操作日志是定義在原始數(shù)據(jù)集（D0）上的一組由Insert、Update 和Delete 語(yǔ)句組成的有序操作的集合，記作Ω={OP1,OP2,…,OPn}。

如例1 中的Ω由7 個(gè)操作組成。

定義2（誤操作（error operator））當(dāng)執(zhí)行Update、Insert語(yǔ)句時(shí)，語(yǔ)句出現(xiàn)了錯(cuò)誤的賦值。

如例1 中的OP1，將Office 屬性錯(cuò)誤地賦值為“R102”，為一個(gè)誤操作。值得注意的是，OP3修改了t2的Department 屬性值，雖然該值有誤，但OP3不是誤操作，因?yàn)檫@一錯(cuò)誤是由OP1引起的。

執(zhí)行Delete 語(yǔ)句不會(huì)引入錯(cuò)誤數(shù)據(jù)，誤操作集合不包含Delete 語(yǔ)句。

定義3（數(shù)據(jù)集Dn）Dn是由原始數(shù)據(jù)集D0經(jīng)過(guò)操作日志Ω產(chǎn)生的新數(shù)據(jù)集，Dn=Ω(D0)=OPn(…(OP2(OP1(D0))))。對(duì)于?i，若0

定義4（不一致數(shù)據(jù)集）對(duì)于數(shù)據(jù)集Dn上定義的一組函數(shù)依賴(lài)集Σ={φ1,φ2,…,φn}，?φi∈Σ，使得Dn不滿(mǎn)足函數(shù)依賴(lài)規(guī)則φi，稱(chēng)Dn是不一致數(shù)據(jù)集，記作Dn?Σ。否則，稱(chēng)Dn是干凈數(shù)據(jù)集，記作Dn?Σ。

如例1 中Employee：D7違反了函數(shù)依賴(lài)φ1，為一個(gè)不一致數(shù)據(jù)集。

定義5（可信度標(biāo)記（confidence value token，CVT））對(duì)于數(shù)據(jù)集Dn上的屬性X以及元組ti，CVT(ti[X])為獲取ti[X]取值的可信度標(biāo)記，記作α，且α∈{0,1,…,∞}。

定義6（可信度（confidence level，CL））可信度值與可信度標(biāo)記成反比例關(guān)系，當(dāng)α=0，可信度最高，表示ti[X]的取值正確；當(dāng)α=∞，可信度最低，表示ti[X]的取值錯(cuò)誤；除此之外，ti[X]的取值可能正確，也可能錯(cuò)誤，正確的可能性取決于α的標(biāo)記，標(biāo)記值越小，可信度越高，正確的可能性也越大。

定義7（操作的度（degree））對(duì)于數(shù)據(jù)集Dn上的屬性X以及元組ti，單元格ti[X]經(jīng)歷的操作鏈長(zhǎng)度稱(chēng)為操作的度。

如例1 中的t6[Office_Tel]，先基于OP6插入“S4”值，再基于t6[Department]的插入值修改t6[Office_Tel]）。因此，t6[Office_Tel]的度為2，同理，t6[Office]的度為1，經(jīng)歷的操作鏈如圖2 所示。

Fig.2 Degree of t6[Office_Tel]and t6[Office]圖2 t6[Office_Tel]和t6[Office]操作的度

當(dāng)α值不為0 和∞時(shí)，操作的度等價(jià)于α。出現(xiàn)不一致數(shù)據(jù)時(shí)，一般情況下，度越大（即α值越大），表示單元格經(jīng)歷的操作鏈越長(zhǎng)，也越易出錯(cuò)，可信度也越低。因此，例1中的t5和t6違反了φ1，t6[Office_Tel]的α值為2，其他屬性的α值均為1，算法選擇修復(fù)t6[Office_Tel]的值。

定義8（知識(shí)庫(kù)（knowledge base））知識(shí)庫(kù)中的知識(shí)由專(zhuān)家領(lǐng)域給出，是一組知識(shí)規(guī)則集合，記作Γ={R1,R2,…,Rn}。每條規(guī)則Ri包含該規(guī)則所聯(lián)系的事實(shí)及數(shù)據(jù)。對(duì)于?Ri∈Γ，Ri可表示為：

(A:v1)=>(B:v2)其中，A為數(shù)據(jù)集Dn上的屬性集合，v1為A屬性上的常量取值；B為數(shù)據(jù)集Dn上的單個(gè)屬性，且B∈attr(R)A（B為R上除去A的其他某個(gè)屬性），v2為B屬性上的常量取值。

例如，下文的R1、R2為兩條知識(shí)庫(kù)規(guī)則，R1的含義是當(dāng)Office 的值為“R103”時(shí)，Office_Tel 的值必定為“83428533”；R2的含義是當(dāng)Office_Tel 的值為“83428535”時(shí)，Office的值必定為“R105”。

R1:(Office:'R103')=>(Office_Tel:'83428533')

R2:(Office_Tel:'83428535')=>(Office:'R105')

定義9（沖突操作（conflict operator））對(duì)于?OPi∈Ω，?Rj∈Γ，使得函數(shù)isConflict(OPi,Rj)返回True，則稱(chēng)OPi是一個(gè)沖突操作。

如例1 中的OP4為一個(gè)沖突操作，因?yàn)镺P4描述的是當(dāng)Office 值為“R103”，則將Office_Tel 設(shè)置為“83428531”，而定義7 中出現(xiàn)的知識(shí)規(guī)則R1要求在Office值同為“R103”時(shí)，Office_Tel值應(yīng)為“83428533”。通常認(rèn)為知識(shí)庫(kù)中的知識(shí)規(guī)則是正確的，因此沖突操作也是誤操作，若將所有的沖突操作放入集合Υ，則Υ是誤操作的一個(gè)子集。本文中的沖突操作可以通過(guò)isConflict 函數(shù)判斷（isConflict 函數(shù)的實(shí)現(xiàn)詳見(jiàn)2.1 節(jié)），但誤操作無(wú)法通過(guò)算法判斷，具體原因參見(jiàn)1.2 節(jié)。

1.2 修復(fù)模型

修復(fù)模型由兩部分組成：設(shè)置可信度標(biāo)記和增量式數(shù)據(jù)修復(fù)。

第一部分：若檢測(cè)出元組ti、tj違反函數(shù)依賴(lài)X→Y，更合理的方式是分析ti[X]、ti[Y]、tj[X]和tj[Y]的可信度，選擇可信度值低的單元格進(jìn)行修復(fù)。本文使用α作為單元格可信度標(biāo)記，獲取算法可參見(jiàn)2.1 節(jié)。

第二部分：當(dāng)數(shù)據(jù)集Dn的單元格獲取α值后，可以依據(jù)知識(shí)規(guī)則和α=0 的標(biāo)記，優(yōu)先修復(fù)部分單元格，這部分單元格的修復(fù)值是正確的、可靠的。剩余不一致的單元格，則依據(jù)α標(biāo)記，采用條件概率和增量式方法進(jìn)行修復(fù)，直到所有的不一致數(shù)據(jù)消除，完成修復(fù)過(guò)程，相關(guān)算法可參見(jiàn)2.2 節(jié)。

值得注意的是，修復(fù)操作日志并非本文的工作，本文將在不改變操作日志的基礎(chǔ)上，基于對(duì)操作日志的分析，最終形成不一致數(shù)據(jù)的修復(fù)方案。本文之所以不選擇先修復(fù)操作日志，進(jìn)而根據(jù)正確的操作日志修復(fù)數(shù)據(jù)的原因是：一個(gè)錯(cuò)誤的數(shù)據(jù)可能由多條操作共同形成，很難通過(guò)算法有效判斷具體是哪一條操作導(dǎo)致了最終錯(cuò)誤數(shù)據(jù)的形成。如例1 中t2元組的Department 屬性，究竟是OP1還是OP3，或是兩條操作共同形成的錯(cuò)誤？再有，即使能夠確定某條操作是錯(cuò)誤的，也很難找到Set 語(yǔ)句后正確的更新值，若選擇了錯(cuò)誤的值進(jìn)行更新，不僅不能修復(fù)數(shù)據(jù)，還會(huì)將這個(gè)錯(cuò)誤進(jìn)一步擴(kuò)散至其他的屬性。

2 解決方案

2.1 設(shè)置可信度標(biāo)記

數(shù)據(jù)集Dn中的可信度標(biāo)記值分為三類(lèi)：0、∞、正整數(shù)。如式（1）所示：

式（1）分為三種情形：

情形1通常，D0是允許包含空值但不存在不一致數(shù)據(jù)的集合，但隨著時(shí)間的推移，受外部環(huán)境的影響，部分?jǐn)?shù)據(jù)會(huì)發(fā)生一些合理的變化（如例1 中電話的變更、部門(mén)的調(diào)整、員工的增加等），由于操作日志Ω中存在誤操作，使得這些數(shù)據(jù)出現(xiàn)了不一致情形。而對(duì)于另一部分未受操作日志影響，即操作的度為0 的單元格，表示該值不需要發(fā)生更新，且ti[X]的α值為0，是正確的值。

如例1 中的元組t1，操作的度為0，表示“E001”員工的信息未發(fā)生過(guò)變動(dòng)，因此對(duì)于t1上的任意屬性X，都有t1[X]的α值為0。

情形2若作用于ti[X]上的操作OPj為沖突操作，則ti[X]的α值為∞，表示為錯(cuò)誤的值。

如例1 中的OP4是一個(gè)沖突操作，t4[Office_Tel]的值被OP4更改，因此t4[Office_Tel]的α值為∞。

情形3若作用于ti[X]上的操作OPj不為沖突操作，則先獲取ti元組在OPj前置條件（Where 子句）中對(duì)應(yīng)屬性的α值，再將α值加1。

如例1中t2[EmpID]操作的度為0（α=0），t2[Office]上對(duì)應(yīng)操作OP1，因 此t2[Office]的α值為1；t2[Department]對(duì)應(yīng)操作OP4，其前置條件是t2[Office]，因此t2[Department]的α值為2。當(dāng)插入新元組時(shí)，該元組的所有屬性操作的度為1（α=1）。若ti[X]的α值為∞，則α+1 的值仍然為∞，即ti[X]若是一個(gè)錯(cuò)誤的值，無(wú)論OPj正確與否，OPj（ti[X]）都是一個(gè)錯(cuò)誤的值。

按照式（1），算法實(shí)現(xiàn)分為三個(gè)步驟。

步驟1獲取沖突操作集Υ。

判斷OPi是否為沖突操作時(shí)，可將OPi操作的Where 子句的內(nèi)容作為前置條件，Set 子句的內(nèi)容作為后置結(jié)果；將知識(shí)規(guī)則中符號(hào)“=>”的左部作為前置條件，右部作為后置結(jié)果，通過(guò)調(diào)用函數(shù)getConflict獲取沖突操作集Υ。isConflict 函數(shù)用于判斷OPi是否為沖突操作，若OPi∈Υ，則返回True，表示OPi是沖突操作。getConflict函數(shù)的算法代碼如下。

算法1getConflict

輸入：操作日志Ω，知識(shí)庫(kù)Γ。

輸出：沖突操作集Υ。

代碼第4 行表示OPi和Rj的前置條件匹配，但后置條件不匹配，即滿(mǎn)足沖突條件；第5 行將沖突的OPi放入集合Υ。

步驟2生成可信度標(biāo)記追蹤表（confidence value token tracing，CVTT 表）。

生成CVTT 表算法稱(chēng)為getCVTT，該表由5 個(gè)字段組成：元組編號(hào)（ID）、后置屬性名（RA）、后置屬性值（RV）、前置條件（C）和α（可信度標(biāo)記值）。算法代碼如下。

算法2getCVTT

輸入：原始數(shù)據(jù)集D0，操作日志Ω，沖突操作集Υ。

輸出：CVTT。

算法第2～14 行表示當(dāng)操作為“Update”時(shí)，按照式（1）設(shè)置可信度標(biāo)記的過(guò)程。其中，第4 行表示D0中的元組與操作OPi匹配，分為兩種情況：若元組對(duì)應(yīng)的字段值已被更新過(guò)，則通過(guò)代碼第6 行計(jì)算α值；若元組對(duì)應(yīng)的字段值未被更新過(guò)，則α初始值設(shè)為0。第5 行判斷操作OPi是否為沖突操作，根據(jù)返回的BOOL 值，第6 行遍歷當(dāng)前CVTT 表，若有和OPi前置條件匹配的RA 和RV 值，則取出α，第7～9 行根據(jù)式（1）中的情形2、情形3進(jìn)行賦值。第15～16行表示當(dāng)操作為“Insert”時(shí)，tJ元組所有屬性的α值均為1。

例1 執(zhí)行算法2，得到CVTT，如表1 所示。

Table 1 CVTT表1 CVTT

步驟3設(shè)置可信度標(biāo)記。

依次讀取CVTT 表的α值，將α設(shè)置到Dn數(shù)據(jù)集對(duì)應(yīng)的單元格中，對(duì)于CVTT 中未出現(xiàn)的單元格，表示操作的度為0，按照式（1），α=0。

例1 中D7，按照步驟3，獲得帶有可信度標(biāo)記的Employee表，如表2 所示。

Table 2 Employee with confidence value token表2 帶有可信度標(biāo)記的Employee表

2.2 增量式數(shù)據(jù)修復(fù)

本節(jié)基于可信度標(biāo)記值，結(jié)合條件概率，采用增量式的修復(fù)方法進(jìn)行不一致數(shù)據(jù)的修復(fù)。增量式修復(fù)的原則為：對(duì)于每一個(gè)函數(shù)依賴(lài)，先按照文獻(xiàn)[6]的方法劃分等價(jià)類(lèi)，檢測(cè)數(shù)據(jù)的一致性，若檢測(cè)到不一致數(shù)據(jù)，則進(jìn)行修復(fù)。修復(fù)時(shí)，根據(jù)α值依次將單元格增量式插入臨時(shí)表，先插入α值較小的單元格（可信度較高），盡量修復(fù)α值較大的單元格，已插入的單元格的值不可修改。若插入的單元格沖突，則通過(guò)條件概率公式獲取目標(biāo)修復(fù)值進(jìn)行修復(fù)。

修復(fù)算法分為三個(gè)步驟：

步驟1讀取知識(shí)庫(kù)中的每一條知識(shí)規(guī)則修復(fù)單元格。

若利用一條知識(shí)規(guī)則Rj修復(fù)單元格，需同時(shí)滿(mǎn)足以下兩個(gè)條件：

（1）?ti[X]，使得ti[X]=condition(Rj)；

（2）ti[X]的α為0。

例如，可以使用定義8 中的知識(shí)規(guī)則R1，將t4[Office_Tel]的值修復(fù)為“83428533”，同時(shí)修改t4[Office_Tel]的α值為0；此外，表2不能使用規(guī)則R2將t6[Office]的屬性值修復(fù)為“R105”，因?yàn)閠6[Office_Tel]的α值不為0。

步驟2修復(fù)“缺角”單元格。

對(duì)于數(shù)據(jù)集Dn上的屬性A和B，有函數(shù)依賴(lài)關(guān)系A(chǔ)→B。若?ti,tj∈Dn，使得ti[A]=tj[A]，ti[B]≠tj[B]，CVT(ti[A])=CVT(ti[B])=CVT(tj[A])=0，CVT(tj[B])≠0，則tj[B]為“缺角”單元格，可選擇ti[B]為目標(biāo)值修復(fù)tj[B]。

如表2 中，要滿(mǎn)足函數(shù)依賴(lài)φ1，t2[Office]是“缺角”單元格，可選擇t1[Office]作為目標(biāo)修復(fù)值，同時(shí)，t2[Office]的α值變?yōu)?；同理，t3[Office]也為“缺角”單元格。修復(fù)后，要滿(mǎn)足圖1中的φ2：Office →Department，t2[Department]和t3[Department]也為“缺角”單元格，可修復(fù)t2[Department]=t3[Department]='S1'。

步驟3非0 的α值，依次向臨時(shí)表從低至高增量式插入單元格的值。為滿(mǎn)足函數(shù)依賴(lài)A→B，插入時(shí)，對(duì)于α值相同的單元格，先選擇A屬性的值插入，再插入B屬性的值，處理的過(guò)程有三種情形。

情形1A屬性值已插入，即將插入的B屬性值與已有的B屬性值沖突，則修改B屬性的值為已有的值。

情形2B屬性值已插入，即將插入的A屬性值與已有的元組沖突，則根據(jù)條件概率式（2）獲取A屬性的修復(fù)目標(biāo)值，進(jìn)行修復(fù)。

情形3同一條元組的A、B屬性的α值均為∞，則統(tǒng)計(jì)數(shù)據(jù)集Dn中所有已確定的元組在屬性A、B上的取值情況，選取概率值最大的進(jìn)行修復(fù)。

算法3 描述了增量式數(shù)據(jù)修復(fù)的整個(gè)過(guò)程。

算法3increasedRepair

第1～7 行對(duì)應(yīng)步驟1，讀取知識(shí)庫(kù)修復(fù)單元格；第8～15 行對(duì)應(yīng)步驟2，修復(fù)“缺角”單元格；第16～25 行對(duì)應(yīng)步驟3，根據(jù)不同的情形修復(fù)單元格。

例2圖3 完整地展示了算法3 的執(zhí)行過(guò)程。圖中的數(shù)據(jù)需遵守函數(shù)依賴(lài)規(guī)則A→B，知識(shí)庫(kù)有一條知識(shí)規(guī)則為R:(B:'b3')=>(A:'a3')，每個(gè)單元格的可信度標(biāo)記α已根據(jù)算法2 生成。

Fig.3 Process of increased data repair圖3 增量式數(shù)據(jù)修復(fù)過(guò)程

圖3 中，首先按照知識(shí)規(guī)則R修復(fù)t5[A]=a3，如圖3（b）所示。圖3（c）將所有α=0 的屬性值插入單元格。圖3（d）修復(fù)“缺角”單元格，修復(fù)t2[B]=b1。圖3（e）設(shè)置A屬性α=1 的單元格，設(shè)置t3[A]=a1，當(dāng)設(shè)置t4[A]為a1時(shí)，違反了函數(shù)依賴(lài)規(guī)則，此時(shí)，算法基于t4[B]=b4，使用式（2）計(jì)算條件概率，假設(shè)經(jīng)過(guò)計(jì)算，t4[A]=a4的概率最大，則t4[A]的修復(fù)值為a4；繼續(xù)設(shè)置B屬性α=1 的單元格（剩余單元格中無(wú)符合要求的屬性值，跳過(guò)）。同理，A屬性α=2 時(shí)也無(wú)滿(mǎn)足的單元格，設(shè)置B屬性α=2 的單元格，如圖3（f）所示，由于放置t3[B]=b2造成沖突，修復(fù)t3[B]的值為b1。圖3（g）修復(fù)t6元組，由于AB屬性的α值為∞，修復(fù)時(shí)，刪除原表中A屬性值為a1或B屬性值為b2的元組，對(duì)剩下的已確定元組在(A,B）上的取值進(jìn)行統(tǒng)計(jì)，假設(shè)(a4,b4)的概率最高，則選擇(a4,b4)修復(fù)t6。

同理，為了滿(mǎn)足函數(shù)依賴(lài)φ1和φ2，按照算法3 對(duì)表2 進(jìn)行修復(fù)，修復(fù)結(jié)果如圖1 括號(hào)中數(shù)據(jù)所示。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境基于Microsoft Windows 10 操作系統(tǒng)，機(jī)器配置為Intel i7-8700 3.2 GHz CPU，16 GB 內(nèi)存。編程開(kāi)發(fā)環(huán)境為Microsoft Visual Studio 2013，數(shù)據(jù)庫(kù)采用SQL SERVER 2012。

實(shí)驗(yàn)過(guò)程中，測(cè)試數(shù)據(jù)集采用一個(gè)基于圖1 擴(kuò)展的Employee表，數(shù)據(jù)結(jié)構(gòu)如表3 所示。

測(cè)試數(shù)據(jù)集分為模擬的數(shù)據(jù)集Employee*和真實(shí)的數(shù)據(jù)集Employee。其中，仿照真實(shí)數(shù)據(jù)集，首先在模擬數(shù)據(jù)集上定義了6 條反映真實(shí)約束關(guān)系的函數(shù)依賴(lài)以及100 條知識(shí)規(guī)則，再通過(guò)算法隨機(jī)生成包含4 萬(wàn)條員工的初始數(shù)據(jù)D0，D0中的所有數(shù)據(jù)均遵守函數(shù)依賴(lài)規(guī)則以及知識(shí)規(guī)則。在此基礎(chǔ)上，依據(jù)操作的度越高越易出錯(cuò)的規(guī)律和原則，隨機(jī)生成了包含若干誤操作的操作日志（誤操作可為Employee*注入一定比例的噪聲），共計(jì)50 條，最終將D0按照操作日志逐條執(zhí)行形成Dn，Dn是違反了函數(shù)依賴(lài)和知識(shí)規(guī)則的數(shù)據(jù)集。本文分別在模擬的和真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，來(lái)驗(yàn)證本文提出的數(shù)據(jù)修復(fù)方法的性能。

Table 3 Table structure of experimental data set表3 實(shí)驗(yàn)數(shù)據(jù)集表結(jié)構(gòu)

實(shí)驗(yàn)分為三部分：首先利用本文方法在Employee*上驗(yàn)證準(zhǔn)確率以及召回率；在獲取可靠的修復(fù)結(jié)果后，再用本文方法在真實(shí)的Employee 上進(jìn)行數(shù)據(jù)修復(fù)，同時(shí)在Employee 數(shù)據(jù)集上，給出本文方法測(cè)試的運(yùn)行時(shí)間，以驗(yàn)證方法的高效性；最后將文本方法與相關(guān)方法進(jìn)行了對(duì)比。

3.2 實(shí)驗(yàn)結(jié)果與分析

本節(jié)分別以修復(fù)準(zhǔn)確率（Accuracy）、修復(fù)召回率（Recall）和程序運(yùn)行時(shí)間三方面來(lái)考察所提出算法的性能（本節(jié)中簡(jiǎn)稱(chēng)為準(zhǔn)確率和召回率）。這里引入?yún)?shù)R表示依賴(lài)知識(shí)規(guī)則修復(fù)的單元格數(shù)與實(shí)際錯(cuò)誤的單元格數(shù)的比值，參數(shù)E表示操作日志中錯(cuò)誤的操作影響的單元格數(shù)與總單元格數(shù)的比值。如定義了2 條知識(shí)規(guī)則，10 條操作，數(shù)據(jù)集可依據(jù)2 條規(guī)則修復(fù)10 個(gè)單元格，依據(jù)10 條操作形成了20 個(gè)錯(cuò)誤的單元格，數(shù)據(jù)集中共100 個(gè)單元格，則R的值為0.5，E的值為0.2。同時(shí)，使用準(zhǔn)確率與召回率來(lái)評(píng)價(jià)修復(fù)的效果，分別如式（3）、式（4）所示。

3.2.1 準(zhǔn)確率與召回率

本小節(jié)在模擬的數(shù)據(jù)集上分別從E值固定和R值固定兩方面來(lái)驗(yàn)證提出方法的準(zhǔn)確率和召回率。

（1）E值固定

圖4（a）展示了本文算法的準(zhǔn)確率，圖4（b）展示了召回率。其中，通過(guò)固定E值為0.1，在不同的R值情況下，顯示準(zhǔn)確率、召回率與元組規(guī)模之間的關(guān)系?？梢钥闯?，當(dāng)R取值相同時(shí)，準(zhǔn)確率和召回率均不受元組規(guī)模的影響。這是由于，當(dāng)向不同規(guī)模的數(shù)據(jù)集注入同比例的知識(shí)規(guī)則時(shí)，利用知識(shí)規(guī)則修復(fù)的錯(cuò)誤比例也相當(dāng)。同時(shí)，有別于傳統(tǒng)方法，本文修復(fù)時(shí)，依據(jù)單元格可信度標(biāo)記，先客觀地選擇需要修復(fù)的屬性值，再依據(jù)數(shù)據(jù)的內(nèi)在規(guī)律，選取可能性最大的目標(biāo)值進(jìn)行修復(fù)，因此修復(fù)方案更為可靠、穩(wěn)定，獲得了較高的修復(fù)率。當(dāng)R取值不同時(shí)，可以發(fā)現(xiàn)，R值越大，準(zhǔn)確率和召回率值也越高，這是因?yàn)镽值越大，知識(shí)庫(kù)的規(guī)則就越多，修復(fù)時(shí)，可以利用知識(shí)規(guī)則直接獲取正確的修復(fù)值的機(jī)會(huì)也隨之增大。

Fig.4 Comparison of accuracy and recall with different tuples(E value is fixed)圖4 不同元組規(guī)模的準(zhǔn)確率和召回率比較（E 值固定）

（2）R值固定

通過(guò)固定R值為0.1，在不同的E值情況下，圖5展示了準(zhǔn)確率、召回率與元組規(guī)模之間的關(guān)系。當(dāng)E值相同時(shí)，準(zhǔn)確率和召回率均不受元組規(guī)模的影響。雖然隨著元組規(guī)模的增大，錯(cuò)誤數(shù)據(jù)也會(huì)增多，但由于注入的錯(cuò)誤率是相同的，在數(shù)據(jù)集的各屬性上的數(shù)據(jù)值都均勻分布的情況下，通過(guò)本文修復(fù)方法獲得修復(fù)的單元格比例也相當(dāng)，因此準(zhǔn)確率和召回率的曲線波動(dòng)幅度都較小，且呈現(xiàn)穩(wěn)定趨勢(shì)。當(dāng)E取值不同時(shí)，準(zhǔn)確率和召回率會(huì)隨著E值的增加而下降，這是由于同規(guī)模的數(shù)據(jù)集中，注入的錯(cuò)誤越多，修復(fù)時(shí)干擾的數(shù)據(jù)就越多，獲取正確的目標(biāo)修復(fù)值的可能性降低。但即使E達(dá)到0.2，召回率也在60%以上。

Fig.5 Comparison of accuracy and recall with different tuples(R value is fixed)圖5 不同元組規(guī)模的準(zhǔn)確率和召回率比較（R 值固定）

圖4、圖5 中的召回率均略低于準(zhǔn)確率，這是由于總修復(fù)數(shù)通常小于實(shí)際錯(cuò)誤數(shù)，根據(jù)式（3）和式（4），召回率總會(huì)略低于準(zhǔn)確率。

3.2.2 運(yùn)行時(shí)間

模擬的數(shù)據(jù)集展示了本文的修復(fù)方法具有較高的準(zhǔn)確率和召回率，將該方法用于真實(shí)數(shù)據(jù)集Employee 修復(fù)數(shù)據(jù)的同時(shí)，本小節(jié)還從元組規(guī)模角度展示算法2 和算法3 的運(yùn)行時(shí)間，分析如下。

圖6 展示了算法2 的運(yùn)行時(shí)間。當(dāng)Ω中的操作數(shù)（OP）不變時(shí)，隨著元組規(guī)模的增加，算法的運(yùn)行時(shí)間也遞增，這是因?yàn)樗惴ㄐ枰獙?duì)每條元組的每個(gè)單元格進(jìn)行可信度值分析，元組數(shù)越多，耗費(fèi)的代價(jià)越大。對(duì)于同等規(guī)模的數(shù)據(jù)集，運(yùn)行時(shí)間隨著OP 值的增長(zhǎng)，也呈增長(zhǎng)趨勢(shì)，這是因?yàn)閷?duì)于每一個(gè)操作日志，算法都需遍歷一次完整的數(shù)據(jù)集，操作日志越多，運(yùn)行時(shí)間越長(zhǎng)。算法2 的時(shí)間復(fù)雜度為|m|×|n|×|OP|，其中|m|為CVTT 表中的行數(shù)，|n|為D0中的元組數(shù)，|OP|為操作數(shù)，即使在極端情況下，每條元組都做了更新，|m|的值趨于|n|，總的時(shí)間復(fù)雜度也在O(n2)內(nèi)。

Fig.6 Running time of getCVTT圖6 getCVTT 算法的運(yùn)行時(shí)間

圖7 展示了算法3 的運(yùn)行時(shí)間。算法分為兩部分，第1～8 行使用知識(shí)規(guī)則（KR）修復(fù)單元格，運(yùn)行時(shí)間如圖7（a）所示，剩余部分為增量式修復(fù)，運(yùn)行時(shí)間如圖7（b）所示。KR 值相同時(shí)，運(yùn)行時(shí)間會(huì)隨著數(shù)據(jù)規(guī)模的增大而增加；KR 值不同時(shí)，值越大，耗費(fèi)的代價(jià)越大。但是，即使規(guī)則再多，執(zhí)行時(shí)間也不超過(guò)1 s，說(shuō)明規(guī)則數(shù)的增多，對(duì)修復(fù)的總體運(yùn)行時(shí)間影響不大，這是由于算法只利用規(guī)則修改單元格值，不做其他任何操作，故而時(shí)間開(kāi)銷(xiāo)不大。增量式修復(fù)時(shí)，運(yùn)行時(shí)間受元組規(guī)模的影響，規(guī)模越大，時(shí)間開(kāi)銷(xiāo)越多，算法3 的時(shí)間復(fù)雜度為O(n2)。

Fig.7 Running time of algorithm 3圖7 算法3 運(yùn)行時(shí)間

綜上所述，本文方法由算法1、算法2 和算法3 組成，算法1 的時(shí)間復(fù)雜度為|OP|×|KR|，因此，本文方法總的時(shí)間復(fù)雜度為O(n2)。

3.3 相關(guān)方法比較與分析

本節(jié)將引言中基于函數(shù)依賴(lài)的三類(lèi)修復(fù)方法與本文方法（increased data repair，IDR）進(jìn)行比較分析。其中，采用實(shí)驗(yàn)的方式與最小刪除原則方法進(jìn)行對(duì)比；另兩類(lèi)方法需要給定的Master 數(shù)據(jù)庫(kù)或可信度值，因此難以進(jìn)行實(shí)驗(yàn)對(duì)比，這里采用文字分析的方式進(jìn)行比較。

（1）與基于最小刪除原則（minimal deletion principle，MDP）方法的比較分析

基于最小刪除原則指的是：給定一個(gè)關(guān)系實(shí)例Dn和約束規(guī)則集Σ，若Dn?Σ，則通過(guò)刪除若干元組的方式獲得修復(fù)集合r*，使得r*?Σ，且不存在另一個(gè)修復(fù)集合r**，使得r**?Σ且|Δ(r*,Dn)|<|Δ(r**,Dn)|，則r*是滿(mǎn)足Σ的一個(gè)修復(fù)。其中，|Δ(r*,Dn)|為r*與Dn交集的元組數(shù)。

最小刪除原則方法以刪除操作替代了尋找目標(biāo)值修復(fù)數(shù)據(jù)的過(guò)程，故難以計(jì)算3.2.1 小節(jié)提到的修復(fù)準(zhǔn)確率和召回率。但即便是刪除，該方法也需先檢測(cè)出錯(cuò)誤的元組（一般認(rèn)為，需要?jiǎng)h除的元組即被認(rèn)定為錯(cuò)誤的元組），而錯(cuò)誤元組的檢測(cè)是否準(zhǔn)確是修復(fù)過(guò)程中最為重要的環(huán)節(jié)，直接關(guān)系到最終的修復(fù)結(jié)果。這里引入檢測(cè)召回率來(lái)評(píng)價(jià)兩種方法對(duì)于錯(cuò)誤元組的檢測(cè)效果，如式（5）所示。其中，本文方法中將需修復(fù)的單元格對(duì)應(yīng)的元組標(biāo)記為錯(cuò)誤元組，|算法檢測(cè)出錯(cuò)誤元組集合∩實(shí)際錯(cuò)誤元組集合|表示算法準(zhǔn)確檢測(cè)到錯(cuò)誤元組的計(jì)數(shù)。

圖8 展示了錯(cuò)誤率為5%，R=0.1，不同元組規(guī)模與檢測(cè)召回率之間的關(guān)系。

Fig.8 Comparison between IDR and MDP in detection recall圖8 IDR 與MDP 檢測(cè)召回率的比較

由圖8 可見(jiàn)，MDP 檢測(cè)召回率對(duì)應(yīng)的值較低且波動(dòng)較大，這是由于誤操作通常為批處理語(yǔ)句，當(dāng)對(duì)同一等價(jià)類(lèi)中的數(shù)據(jù)注入相同錯(cuò)誤，且相同錯(cuò)誤的值對(duì)應(yīng)的元組數(shù)達(dá)到一定數(shù)值時(shí)，采用最少刪除原則會(huì)造成錯(cuò)誤的檢測(cè)，如例1 中的t1～t4會(huì)錯(cuò)誤地將t2和t3保留而刪除正確的元組t1；同時(shí)，當(dāng)修復(fù)集合r*有多個(gè)時(shí)，算法會(huì)隨機(jī)選擇其中一種進(jìn)行修復(fù)，從而可能導(dǎo)致錯(cuò)誤的刪除，如例1 中刪除t5或t6都可以解決值為“83428535”帶來(lái)的不一致問(wèn)題，算法會(huì)隨機(jī)刪除先出現(xiàn)的元組t5。IDR 方法不存在隨機(jī)選擇和簡(jiǎn)單判定錯(cuò)誤元組的情況，而是通過(guò)分析操作日志獲得數(shù)據(jù)演化規(guī)律，再依據(jù)生成的單元格可信度以及知識(shí)庫(kù)進(jìn)行錯(cuò)誤判定，因此獲得了較高的檢測(cè)率，且結(jié)果更為穩(wěn)定。

另一方面，更為重要的是，MDP 方法會(huì)造成企業(yè)的重要信息丟失，而本文方法可以在不丟失任何數(shù)據(jù)的情形下，穩(wěn)定、可靠地完成修復(fù)工作。

（2）與基于Master 數(shù)據(jù)庫(kù)和編輯規(guī)則的修復(fù)方法（master and rule edit，MRE）比較分析

MRE 方法強(qiáng)依賴(lài)于Master 數(shù)據(jù)庫(kù)，當(dāng)企業(yè)無(wú)法提供時(shí)，修復(fù)工作難以完成，而IDR 方法不受此限制；此外，Master 數(shù)據(jù)庫(kù)存放的是經(jīng)企業(yè)確定的正確數(shù)據(jù)，這部分?jǐn)?shù)據(jù)占整體數(shù)據(jù)的比重較小，當(dāng)大多錯(cuò)誤元組無(wú)法在Master 數(shù)據(jù)庫(kù)中找到參照值時(shí)，會(huì)導(dǎo)致較低的修復(fù)召回率。雖然本文也提出了知識(shí)規(guī)則修復(fù)的概念，但即使不存在知識(shí)規(guī)則或知識(shí)規(guī)則僅幫助修復(fù)5%的錯(cuò)誤元組，圖4 也顯示了較高的修復(fù)召回率。

（3）與基于最小代價(jià)修復(fù)元組方法（minimal costbased repair，MCR）的比較分析

MCR 方法強(qiáng)依賴(lài)于用戶(hù)給定的元組可信度值，由于該值具有一定的主觀性，較難獲得客觀的修復(fù)結(jié)果，而IDR 方法通過(guò)算法分析數(shù)據(jù)自動(dòng)產(chǎn)生可信度值，獲得的修復(fù)結(jié)果更為客觀、可靠；同時(shí)，對(duì)于函數(shù)依賴(lài)X→Y，MCR 方法修復(fù)時(shí)，僅僅允許修復(fù)Y值，而IDR 方法突破了此限制，不僅可以修復(fù)Y值，也允許修復(fù)X值，進(jìn)一步提高了修復(fù)效果。

綜上所述，與其他三類(lèi)修復(fù)方法相比，本文的修復(fù)方法不受外界因素的限制，且更為可靠、穩(wěn)定，能獲得較為滿(mǎn)意的修復(fù)效果。

4 小結(jié)

本文研究了在數(shù)據(jù)不丟失的情形下，企業(yè)無(wú)法提供Master 數(shù)據(jù)庫(kù)或給定可信度時(shí)，基于函數(shù)依賴(lài)修復(fù)不一致數(shù)據(jù)的問(wèn)題。首先基于操作日志和知識(shí)規(guī)則，提出了可信度標(biāo)記的生成方法；再根據(jù)可信度標(biāo)記，采用條件概率和增量式數(shù)據(jù)修復(fù)相結(jié)合的方式，對(duì)不一致數(shù)據(jù)進(jìn)行修復(fù)；最后通過(guò)實(shí)驗(yàn)驗(yàn)證以及對(duì)比分析，本文方法可靠穩(wěn)定，且具有較好的修復(fù)效果。由于目前已有的修復(fù)策略大多基于可信度的概念展開(kāi)，本文的工作可擴(kuò)展至基于可信度的其他約束規(guī)則和場(chǎng)景的修復(fù)模型中，具備一定的通用性。