帶有可信度標(biāo)記的增量式數(shù)據(jù)修復(fù)方法研究

黃 慧，李海林

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后，在擴(kuò)展的Employee 數(shù)據(jù)集上進(jìn)行驗證，實(shí)驗結(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 語句組成的有序操作的集合，記作Ω={OP1,OP2,…,OPn}。

如例1 中的Ω由7 個操作組成。

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

如例1 中的OP1，將Office 屬性錯誤地賦值為“R102”，為一個誤操作。值得注意的是，OP3修改了t2的Department 屬性值，雖然該值有誤，但OP3不是誤操作，因為這一錯誤是由OP1引起的。

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

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

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

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

定義5（可信度標(biāo)記（confidence value token，CVT））對于數(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]的取值錯誤；除此之外，ti[X]的取值可能正確，也可能錯誤，正確的可能性取決于α的標(biāo)記，標(biāo)記值越小，可信度越高，正確的可能性也越大。

定義7（操作的度（degree））對于數(shù)據(jù)集Dn上的屬性X以及元組ti，單元格ti[X]經(jī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 和∞時，操作的度等價于α。出現(xiàn)不一致數(shù)據(jù)時，一般情況下，度越大（即α值越大），表示單元格經(jīng)歷的操作鏈越長，也越易出錯，可信度也越低。因此，例1中的t5和t6違反了φ1，t6[Office_Tel]的α值為2，其他屬性的α值均為1，算法選擇修復(fù)t6[Office_Tel]的值。

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

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

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

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

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

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

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

1.2 修復(fù)模型

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

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

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

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

2 解決方案

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

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

式（1）分為三種情形：

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

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

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

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

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

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

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

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

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

算法1getConflict

輸入：操作日志Ω，知識庫Γ。

輸出：沖突操作集Υ。

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

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

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

算法2getCVTT

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

輸出：CVTT。

算法第2～14 行表示當(dāng)操作為“Update”時，按照式（1）設(shè)置可信度標(biāo)記的過程。其中，第4 行表示D0中的元組與操作OPi匹配，分為兩種情況：若元組對應(yīng)的字段值已被更新過，則通過代碼第6 行計算α值；若元組對應(yīng)的字段值未被更新過，則α初始值設(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”時，tJ元組所有屬性的α值均為1。

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

Table 1 CVTT表1 CVTT

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

依次讀取CVTT 表的α值，將α設(shè)置到Dn數(shù)據(jù)集對應(yīng)的單元格中，對于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ù)的原則為：對于每一個函數(shù)依賴，先按照文獻(xiàn)[6]的方法劃分等價類，檢測數(shù)據(jù)的一致性，若檢測到不一致數(shù)據(jù)，則進(jìn)行修復(fù)。修復(fù)時，根據(jù)α值依次將單元格增量式插入臨時表，先插入α值較小的單元格（可信度較高），盡量修復(fù)α值較大的單元格，已插入的單元格的值不可修改。若插入的單元格沖突，則通過條件概率公式獲取目標(biāo)修復(fù)值進(jìn)行修復(fù)。

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

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

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

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

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

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

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

對于數(shù)據(jù)集Dn上的屬性A和B，有函數(shù)依賴關(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 中，要滿足函數(shù)依賴φ1，t2[Office]是“缺角”單元格，可選擇t1[Office]作為目標(biāo)修復(fù)值，同時，t2[Office]的α值變?yōu)?；同理，t3[Office]也為“缺角”單元格。修復(fù)后，要滿足圖1中的φ2：Office →Department，t2[Department]和t3[Department]也為“缺角”單元格，可修復(fù)t2[Department]=t3[Department]='S1'。

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

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

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

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

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

算法3increasedRepair

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

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

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

圖3 中，首先按照知識規(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ù)依賴規(guī)則，此時，算法基于t4[B]=b4，使用式（2）計算條件概率，假設(shè)經(jīng)過計算，t4[A]=a4的概率最大，則t4[A]的修復(fù)值為a4；繼續(xù)設(shè)置B屬性α=1 的單元格（剩余單元格中無符合要求的屬性值，跳過）。同理，A屬性α=2 時也無滿足的單元格，設(shè)置B屬性α=2 的單元格，如圖3（f）所示，由于放置t3[B]=b2造成沖突，修復(fù)t3[B]的值為b1。圖3（g）修復(fù)t6元組，由于AB屬性的α值為∞，修復(fù)時，刪除原表中A屬性值為a1或B屬性值為b2的元組，對剩下的已確定元組在(A,B）上的取值進(jìn)行統(tǒng)計，假設(shè)(a4,b4)的概率最高，則選擇(a4,b4)修復(fù)t6。

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

3 實(shí)驗

3.1 實(shí)驗設(shè)置

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

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

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

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

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

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

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

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

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

（1）E值固定

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

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

（2）R值固定

通過固定R值為0.1，在不同的E值情況下，圖5展示了準(zhǔn)確率、召回率與元組規(guī)模之間的關(guān)系。當(dāng)E值相同時，準(zhǔn)確率和召回率均不受元組規(guī)模的影響。雖然隨著元組規(guī)模的增大，錯誤數(shù)據(jù)也會增多，但由于注入的錯誤率是相同的，在數(shù)據(jù)集的各屬性上的數(shù)據(jù)值都均勻分布的情況下，通過本文修復(fù)方法獲得修復(fù)的單元格比例也相當(dāng)，因此準(zhǔn)確率和召回率的曲線波動幅度都較小，且呈現(xiàn)穩(wěn)定趨勢。當(dāng)E取值不同時，準(zhǔn)確率和召回率會隨著E值的增加而下降，這是由于同規(guī)模的數(shù)據(jù)集中，注入的錯誤越多，修復(fù)時干擾的數(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í)際錯誤數(shù)，根據(jù)式（3）和式（4），召回率總會略低于準(zhǔn)確率。

3.2.2 運(yùn)行時間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

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