黃 慧，李海林

1(三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210012)2(南京航空航天大學(xué) 電子與信息工程學(xué)院，南京 211100)

1 引 言

大數(shù)據(jù)時(shí)代，數(shù)據(jù)質(zhì)量直接關(guān)系數(shù)據(jù)深層使用價(jià)值的實(shí)現(xiàn)效果.高質(zhì)量數(shù)據(jù)不僅創(chuàng)造著巨額的社會(huì)財(cái)富，甚至已經(jīng)關(guān)乎國計(jì)民生.而劣質(zhì)的數(shù)據(jù)會(huì)導(dǎo)致決策偏差，社會(huì)財(cái)富損失，對(duì)社會(huì)安定和人身安全都形成巨大的威脅[1].近年來，學(xué)者們針對(duì)數(shù)據(jù)質(zhì)量問題展開了廣泛的研究，大多研究工作基于函數(shù)依賴規(guī)則[2-4]，進(jìn)行不一致數(shù)據(jù)的檢測(cè)與修復(fù).函數(shù)依賴(FDs)指的是，對(duì)于關(guān)系R中的屬性X和Y，X→Y是一個(gè)函數(shù)依賴，對(duì)于R中的任意兩條元組ti和tj，若ti[X]=tj[X]，則必有ti[Y]=tj[Y].依照該規(guī)則，不難發(fā)現(xiàn)表1中存在不一致數(shù)據(jù).

例1.表1中，關(guān)系模式Accident(ID，TeaID，TeaName，Level，Title，AccidentType，Salary，VT)由8個(gè)屬性組成，分別表示為元組編號(hào)、教師編號(hào)、教師名、等級(jí)、職稱、教學(xué)事故類型、工資和發(fā)生教學(xué)事故的有效時(shí)間.

表1 教學(xué)事故信息表(Accident)Table 1 Teaching accident information table(Accident)

為了擴(kuò)展約束語義，充分發(fā)現(xiàn)更多的不一致數(shù)據(jù)，F(xiàn)an W等人在函數(shù)依賴的基礎(chǔ)上進(jìn)一步擴(kuò)展，提出了條件函數(shù)依賴(CFDs)[5，6]，CFDs通過給定的條件可以發(fā)現(xiàn)更為復(fù)雜的不一致數(shù)據(jù).同時(shí)，在CFDs的基礎(chǔ)上，學(xué)者們又提出了一套推理規(guī)則以及公理系統(tǒng)[7-9]，擴(kuò)展了“并”和“與”語義[10]，用于檢測(cè)更多不一致數(shù)據(jù).文獻(xiàn)[11]定義了一種微函數(shù)依賴用于提取屬性的部分信息，利用提取函數(shù)的依賴關(guān)系，發(fā)現(xiàn)屬性中隱藏的錯(cuò)誤信息.文獻(xiàn)[12]通過定義硬約束、數(shù)量約束、等值約束和非等值約束以獲取更多的錯(cuò)誤數(shù)據(jù).文獻(xiàn)[13]利用屬性值的相似性擴(kuò)展了函數(shù)依賴，用來描述異構(gòu)數(shù)據(jù)的一致性問題.文獻(xiàn)[14]將CFDs與條件包含依賴結(jié)合，用于發(fā)現(xiàn)不一致數(shù)據(jù).文獻(xiàn)[15]基于分布式環(huán)境，結(jié)合最小通信原則，給出不一致數(shù)據(jù)的檢測(cè)方法.此外，其他研究工作提出的數(shù)據(jù)質(zhì)量規(guī)則還包括編輯規(guī)則[16]、修復(fù)規(guī)則[17]、差分約束[18]可比較約束[19]和否定約束[20]等，從不同角度描述數(shù)據(jù)不一致問題.

然而，已有的數(shù)據(jù)質(zhì)量規(guī)則僅適用于靜態(tài)數(shù)據(jù)集中不一致數(shù)據(jù)的發(fā)現(xiàn)，忽略了這樣一個(gè)事實(shí)：一些數(shù)據(jù)會(huì)隨時(shí)間動(dòng)態(tài)演化.如表1中的教師職稱、工資、教學(xué)事故、等級(jí)等信息并非一成不變，而是會(huì)隨VT值發(fā)生變化.但現(xiàn)有的規(guī)則難以適用于此類數(shù)據(jù)不一致性的檢測(cè).

例2.表1中存在如下約束語義：

L1：若發(fā)生教學(xué)事故，且事故類型為A，則2年內(nèi)，教師編號(hào)唯一決定教師工資(即2年內(nèi)不能加工資，2年后允許工資發(fā)生變動(dòng))；

L2：對(duì)于同一教師，工資隨VT值單調(diào)增長(即隨著時(shí)間推移，教師工資不會(huì)出現(xiàn)下降)；

L3：對(duì)于同一教師，在2012-2017年期間，等級(jí)的值隨VT值單調(diào)遞增(即教師等級(jí)在其他時(shí)間區(qū)間，允許等級(jí)的值不隨時(shí)間規(guī)律變化)；

L4：5年內(nèi)，若教師的教學(xué)事故累計(jì)3次，則Level的值小于等于2.

不難發(fā)現(xiàn)，例2中的約束語義有2個(gè)特點(diǎn)：①與時(shí)態(tài)相關(guān).②數(shù)據(jù)發(fā)生演化.而已有的數(shù)據(jù)質(zhì)量規(guī)則無法表達(dá)這樣的語義，因此難以發(fā)現(xiàn)表1中隱藏的不一致數(shù)據(jù).為了擴(kuò)展約束語義，本文提出了時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則，并在此基礎(chǔ)上進(jìn)行不一致數(shù)據(jù)的檢測(cè).

本文的主要工作如下：

1)提出時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則(Temporal Data Quality Rules，簡稱TDQRs)的形式化表達(dá)；

2)給出TDQRs相關(guān)性質(zhì)，通過性質(zhì)去除規(guī)則集中冗余的規(guī)則以提升檢測(cè)效率；

3)基于TDQRs，設(shè)計(jì)等價(jià)類劃分方法，形成基于時(shí)態(tài)的不一致數(shù)據(jù)檢測(cè)算法，并通過剪枝的策略優(yōu)化算法；

4)設(shè)計(jì)不一致數(shù)據(jù)查詢語言，通過查詢語言為用戶提供不一致檢測(cè)結(jié)果；

5)通過在擴(kuò)展的Accident數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文提出方法的有效性.

2 TDQRs的相關(guān)定義與性質(zhì)

2.1 TDQRs的相關(guān)定義

針對(duì)時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則，本文引入如下定義.

定義1.時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則TDQRs(Temporal Data Quality Rules).TDQRs是一組基于函數(shù)依賴進(jìn)行擴(kuò)展的不一致數(shù)據(jù)檢測(cè)規(guī)則.TDQRs不僅適用于隨時(shí)間動(dòng)態(tài)演化的數(shù)據(jù)集，也適用于傳統(tǒng)靜態(tài)數(shù)據(jù)集.關(guān)系模式R上的一條TDQRs規(guī)則表示為：

(VT|ω：X→Y，)

其中，1)VT表示有效時(shí)間；2)ω為時(shí)間算子，可以存儲(chǔ)時(shí)間值、時(shí)間區(qū)間或“forever”，用來刻畫時(shí)態(tài)語義；3)X→Y是類似于函數(shù)依賴的表達(dá)式，與函數(shù)依賴不同的是，X和Y的表示可分為3種形式：屬性、用戶定義函數(shù)和邏輯表達(dá)式；4)tp為一個(gè)條件模板，允許為空.

定義2.子規(guī)則.TDQRs中，X和Y可分為屬性、用戶定義函數(shù)和邏輯表達(dá)式3類，為區(qū)分不同，定義為3種子規(guī)則.

子規(guī)則1.X和Y均為屬性，標(biāo)記為Rules with Attributes，簡稱RwA規(guī)則.

若對(duì)應(yīng)的是RwA規(guī)則，當(dāng)ω的值為“forever”，且條件模板tp為空時(shí)，RwA規(guī)則可退化為傳統(tǒng)的函數(shù)依賴規(guī)則.

子規(guī)則2.X和Y均為邏輯表達(dá)式，標(biāo)記為Rules with Logic Expression，簡稱RwLE規(guī)則.

需要說明的是，RwLE規(guī)則的ω值可以為“forever”或時(shí)間區(qū)間[a，b]，當(dāng)為時(shí)間區(qū)間時(shí)，表示在時(shí)間起始點(diǎn)a和結(jié)束點(diǎn)b的時(shí)間范圍內(nèi)屬性的值符合偏序的特點(diǎn).

子規(guī)則3.X和Y包含用戶定義函數(shù)，標(biāo)記為Rules with Function，簡稱RwF規(guī)則.

若對(duì)應(yīng)的是RwF規(guī)則，X或Y可以是一個(gè)包含用戶定義函數(shù)的表達(dá)式，條件模板tp分為tpX和tpY，分別表示條件模板的前件和后件.

例3.根據(jù)定義2，例2中的L1-L4可由三種子規(guī)則表示為ψ1-ψ4，如下所示：

ψ1：(VT|2years：TeaID→Salary，)

ψ2：(VT|forever：ti?VTtj→ti[Salary]≤tj[Salary]，)

ψ3：(VT|[2012-2017]：ti?VTtj→ti≤Leveltj，)

ψ4：(VT|5 years：TeaID，COUNT(AccidentType)→Level，<(≥3，≤2)>)

其中，ψ1是RwA規(guī)則；ψ2和ψ3是RwLE規(guī)則；ψ4是RwF規(guī)則.

定義3.時(shí)間距離.I是R上的一個(gè)實(shí)例，對(duì)于I上任意兩條元組ti和tj在VT上的差值，稱為時(shí)間距離，記作DIFF(ti，tj).若DIFF(ti，tj)滿足ω，記為DIFF(ti，tj)～ω.

例如，表1中t1和t2元組的時(shí)間距離為762days，t2和t3元組的時(shí)間距離為550days，若ω為2 years，則DIFF(t1，t2)ω，DIFF(t2，t3)～ω.

定義4.一階等價(jià)類(First Equal Class，簡稱FEC).為了查找不一致數(shù)據(jù)，將數(shù)據(jù)集中的數(shù)據(jù)按照規(guī)則對(duì)元組進(jìn)行首次劃分歸類，得到的不同集合稱為一階等價(jià)類.

若ψ∈RwA，則按規(guī)則左部X劃分，如ψ1得到的一階等價(jià)類有兩個(gè)，分別表示為FEC1={ti|ti[TeaID]=′001′}={t1，t2，t3，t4}和FEC2={ti|ti[TeaID]=′002′}={t5，t6}；若ψ∈RwLE，則按條件模板tp中的屬性劃分一階等價(jià)類，如ψ2和ψ3得到的一階等價(jià)類也為FEC1和FEC2；若ψ∈RwF，則按規(guī)則左部X中的非聚合表達(dá)式劃分等價(jià)類，如ψ4同樣得到一階等價(jià)類為FEC1和FEC2.

定義5.二階等價(jià)類(Second Equal Class，簡稱SEC).在一階等價(jià)類的基礎(chǔ)上，對(duì)元組按照規(guī)則再次劃分歸類，得到的不同集合稱為二階等價(jià)類.

當(dāng)ψ∈RwA時(shí)，才存在二階等價(jià)類.獲取二階等價(jià)類的方法分為5步：1)對(duì)給定的一階等價(jià)類，按照VT值對(duì)元組進(jìn)行先后排序；2)查找與條件模板tp匹配的首條元組ti；3)獲取集合Ω，Ω={tj|DIFF(ti，tj)～ω}；4)獲取Ω中與條件模板匹配的最后一條元組，若有，將該元組設(shè)置為ti，重復(fù)第3)- 4)步，直到Ω中沒有與條件模板匹配的元組為止；5)將第2)- 4)步得到的元組放入一個(gè)二階等價(jià)類，并將剩余的元組按照第2)- 4)形成新的等價(jià)類，直到所有元組處理完畢為止.

例4.按照ψ1，對(duì)一階等價(jià)類集合{t1，t2，t3，t4}再次劃分二階等價(jià)類歸類，執(zhí)行順序?yàn)椋?a)按照VT排序，集合仍然為{t1，t2，t3，t4}；(b)查找與tp匹配的首條元組為t1；(c)獲取Ω1，此時(shí)Ω1=φ，將t1放入SEC1；(d)剩余的元組{t2，t3，t4}按照步驟2)繼續(xù)處理，首條元組為t2；(e)獲取Ω2，此時(shí)Ω2={t3}；(f)重復(fù)第3)- 4)步，得到Ω3={t4}；(g)重復(fù)第3)- 4)步，得到Ω4=φ，獲得SEC2={t2，t3，t4}.最終{t1，t2，t3，t4}得到的二階等價(jià)類有兩個(gè)：{t1}和{t2，t3，t4}.

按照規(guī)則ψ1，要求t2和t3在Salary屬性上的值相同；同樣，t3和t4在Salary屬性上的值也需相同.因此，雖然DIFF(t2，t4)ω，但也應(yīng)放在同一個(gè)類別中進(jìn)行比較.

定義6.RwA規(guī)則一致性.I是R上的一個(gè)實(shí)例，A、B是R上的屬性，規(guī)則ψ∈RwA，ψ關(guān)于I是一致的，當(dāng)且僅當(dāng)，對(duì)于任意元組ti和tj，在ti和tj屬于同一個(gè)二階等價(jià)類的條件下，若ti[A]=tj[A]，則ti[B]=tj[B]，記作I|=ψ.否則，I關(guān)于ψ是不一致的，記作I|≠ψ.

根據(jù)定義6，對(duì)于例4中的二階等價(jià)類{t2，t3，t4}，當(dāng)t2[TeaID]=t3[TeaID]，卻有t2[Salary] ≠t3[Salary]，元組t2和t3相互沖突，記作：t2?t3.同理，t3?t4.因此，Accident|≠ψ1.

定義7.RwLE規(guī)則一致性.I是R上的一個(gè)實(shí)例，A、B是R上的屬性，規(guī)則ψ∈RwLE，ψ關(guān)于I是一致的，當(dāng)且僅當(dāng)，對(duì)于任意元組ti和tj，在ti和tj屬于同一個(gè)一階等價(jià)類的條件下，有集合Ω={tj|DIFF(ti，tj)～ω}(ti，tj在同一時(shí)間區(qū)間內(nèi))，tj∈Ω，若ti?Atj，則tiOPBtj，記作I|=ψ.否則，I關(guān)于ψ是不一致的，記作I|≠ψ.

根據(jù)定義7，表1中t1?VTt2，但t1[Salary]≥t2[Salary]，違反了ψ2，因此Accident|≠ψ2；同理，t3?VTt4，但t3[level]≥t4[level]，因此Teacher|≠ψ3.

定義8.RwF規(guī)則一致性.I是R上的一個(gè)實(shí)例，A、B是R上的屬性，對(duì)于I上任意一條元組ti，規(guī)則ψ∈RwF，ψ關(guān)于I是一致的，當(dāng)且僅當(dāng)，在ti和tj屬于同一個(gè)一階等價(jià)類的條件下，對(duì)于集合Ω={tj|DIFF(ti，tj)～ω}∪ti，若f(Ω(A))≈tpA，則ti[B]≈tpB，記作I|=ψ.否則，I關(guān)于ψ是不一致的，記作I|≠ψ.

其中，“≈”表示與條件模板匹配.根據(jù)定義8，表1中元組t3，對(duì)于規(guī)則ψ4，獲得集合Ω={t1，t2，t3}，f(Ω(AccidentType))=COUNT(Ω(AccidentType))=3，COUNT(Ω(AccidentType))≈≥3，而t3[Level]≤2，因此，元組t3違反了ψ4，Accident|≠ψ4.

定義9.干凈數(shù)據(jù).給定關(guān)系模式R上的數(shù)據(jù)實(shí)例I以及TDQRs規(guī)則集合Σ，對(duì)于?ψi∈Σ，都有I|=ψi，則稱I為干凈數(shù)據(jù).

定義10.ω1?ω2.“?”為時(shí)間關(guān)系運(yùn)算符，表示ω1和ω2時(shí)間上的關(guān)系.

假設(shè)有ω1表示2 years，ω2表示1 year，易見，若ψ在ω1上成立，則必在ω2上也成立(證明參見2.2小節(jié)).如例2中在L1成立的條件下，此時(shí)將ω1改為ω2，有L1*：若發(fā)生教學(xué)事故，且事故類型為A，則1年內(nèi)，教師編號(hào)唯一決定教師工資.易見，L1*也成立.本文將ω1和ω2的這種關(guān)系表示為ω1?ω2.

2.2 TDQRs的性質(zhì)

關(guān)系模式R上所有屬性集合為U，Σ是U上一組時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則，于是有關(guān)系模式R，本小節(jié)針對(duì)R，給出其上滿足的一些性質(zhì)及證明.

1)若ψi∈RwA(i=1，2，3…n)，則滿足如下3條性質(zhì).

性質(zhì)1.若(VT|ω1：X→Y，)，且ω1?ω2，則(VT|ω2：X→Y，).

證明：反正法.假設(shè)(VT|ω2：X→Y，)不成立，由定義6可知，有二階等價(jià)類SECk，存在ti和tj∈SECk，若ti[X]=tj[X]，則ti[Y]≠tj[Y]；又已知ω1?ω2，DIFF(ti，tj)～ω2，由定義3和定義10易得，DIFF(ti，tj)～ω1，因此在相同的條件模板下，有ω1生成的二階等價(jià)類SECM，使得SECk?SECM，且ti和tj∈SECM；又因?yàn)閠i[X]=tj[X]，有ti[Y]≠tj[Y]，使得(VT|ω1：X→Y，)不成立，與已知條件矛盾.得證.

性質(zhì)2.若(VT|ω1：X→Y，)，(VT|ω2：Y→Z，)，且ω1?ω2，則(VT|ω2：X→Z，).

證明：已知(VT|ω1：X→Y，)成立，且ω1?ω2，由性質(zhì)1可得，(VT|ω2：X→Y，)成立；由定義6可知，存在一個(gè)二階等價(jià)類SECk，對(duì)于任意的ti和tj∈SECk，若ti[X]=tj[X]，有ti[Y]=tj[Y]；又因?yàn)?VT|ω2：Y→Z，)成立，存在相同的二階等價(jià)類SECk，有ti[Y]=tj[Y]，則ti[Z]=tj[Z]；因此，有相同的二階等價(jià)類SECk，ti和tj∈SECk，若ti[X]=tj[X]，則ti[Z]=tj[Z]，(VT|ω2：X→Z，)成立.得證.

性質(zhì)3.若(VT|ω1：X→Y，)，且Z?U，則(VT|ω1：XZ→YZ，).

證明：已知(VT|ω1：X→Y，)成立，由定義6可知，存在一個(gè)二階等價(jià)類SECk，對(duì)于任意的ti和tj∈SECk，若ti[X]=tj[X]，有ti[Y]=tj[Y]；又因?yàn)樵谙嗤亩A等價(jià)類中，已知ti[XZ]=tj[XZ]，易得，ti[X]=tj[X]和ti[Z]=tj[Z]，于是有ti[YZ]=tj[YZ]；因此，(VT|ω1：XZ→YZ，)成立.得證.

2)若ψi∈RwLE(i=1，2，3…n)，則滿足如下3條性質(zhì).

性質(zhì)4.若(VT|ω：q1→κ，)，且(VT|ω：q2→κ，)，則(VT|ω：q1∧q2→κ，).

證明：因?yàn)?VT|ω：q1→κ，)成立，由定義7可知，存在一個(gè)一階等價(jià)類FECk，對(duì)于任意的ti和tj∈FECk，若DIFF(ti，tj)～ω，使得q1為TRUE，則有κ；又因?yàn)?VT|ω：q2→κ，)成立，使得ti和tj在相同的前提條件下，若q2為TRUE，則有κ，因此易得，q1∧q2也為TRUE時(shí)，有κ，因此(VT|ω：q1∧q2→κ，)成立.得證.

性質(zhì)5.若(VT|ω：ti?Xtj→ti?Ytj，)，且(VT|ω：ti?Ytj→tiOPZtj，)，則(VT|ω：ti?Xtj→tiOPZtj，).

證明：因?yàn)?VT|ω：ti?Xtj→ti?Ytj，)成立，由定義7可知，存在一個(gè)一階等價(jià)類FECk，對(duì)于任意的ti和tj∈FECk，且DIFF(ti，tj)～ω，使得若ti?Xtj，有ti?Ytj；同理，因?yàn)?VT|ω：ti?Ytj→tiOPZtj，)成立，在相同的前提條件下，已知ti?Ytj，則tiOPZtj成立.因此有，對(duì)于任意的ti和tj∈FECk，且DIFF(ti，tj)～ω，若ti?Xtj，則必有tiOPZtj.可得(VT|ω：ti?Xtj→tiOPZtj，，成立.得證.

性質(zhì)6.若(VT|ω1：ti?Xtj→tiOPYtj，)，且ω1?ω2，則(VT|ω2：ti?Xtj→tiOPYtj，).

證明：反正法.假設(shè)(VT|ω2：ti?Xtj→tiOPYtj，)不成立，由定義7可知，有一階等價(jià)類FECk，存在ti和tj∈FECk，對(duì)于ti，有集合Ω2={tj|DIFF(ti，tj)～ω2}，tj∈Ω2，使得若ti?xtj，有ti!OPYtj；又已知ω1?ω2，因?yàn)镈IFF(ti，tj)～ω2，必有DIFF(ti，tj)～ω1，所以存在集合Ω1={tj|DIFF(ti，tj)～ω1}，且Ω2?Ω1，易得ti，tj∈Ω1；又ti?xtj，則ti!OPYtj，因此，(VT|ω1：ti?Xtj→tiOPYtj，)不成立，與已知矛盾.得證.

進(jìn)行不一致數(shù)據(jù)檢測(cè)時(shí)，TQDRs規(guī)則越多，時(shí)間開銷越大.因此，可以利用以上性質(zhì)，去除冗余的規(guī)則，提升查詢效率.例如，假設(shè)規(guī)則集中包含如下3條規(guī)則：

ψ1*：(VT|forever：ti?VTtj→ti?Titletj，)

ψ2*：(VT|forever：ti?Titletj→ti[Salary]≤tj[Salary]，)

ψ3*：(VT|forever：ti?VTtj→ti[Salary]≤tj[Salary]，)

3 基于TDQRs不一致數(shù)據(jù)的檢測(cè)

對(duì)于給定的關(guān)系模式R上的一個(gè)實(shí)例I和用于檢測(cè)不一致數(shù)據(jù)的TDQRs約束規(guī)則集Σ，本節(jié)針對(duì)RwA、RwLE和RwF這3種子規(guī)則分別給出不一致數(shù)據(jù)的檢測(cè)算法.

3.1 RwA規(guī)則的檢測(cè)算法

對(duì)于RwA規(guī)則，本文通過創(chuàng)建一棵沖突檢測(cè)樹的方法獲取數(shù)據(jù)集中不一致數(shù)據(jù).沖突檢測(cè)樹深度為4，第0層為根結(jié)點(diǎn)，保存要檢測(cè)的數(shù)據(jù)集地址；第1層獲取一階等價(jià)類的元素作為根結(jié)點(diǎn)的一級(jí)子結(jié)點(diǎn)；第2層獲取二階等價(jià)類的元素作為根結(jié)點(diǎn)的二級(jí)子結(jié)點(diǎn)；以第2層結(jié)點(diǎn)為父結(jié)點(diǎn)，依次遍歷，獲取每個(gè)結(jié)點(diǎn)在Y屬性上的不同取值，作為第3層結(jié)點(diǎn).檢測(cè)算法DetectWithRwA如算法1所示.

算法1.DetectWithRwA(I，ψ)

輸入：數(shù)據(jù)實(shí)例I，RwA規(guī)則ψ

輸出：沖突檢測(cè)樹Tree

1. M=?；

2. CreateTree()；

3. arrayFirst=GetFirtstEquClass(ψ)；

4. FOREACH e1in arrayFirst DO

5. AddFirstNode()；

6. arraySecond=GetSecondEquClass(e1，ψ)；

7. FOREACH e2in arraySecond DO

8. AddSecondNode()；

9. arrayThird=GetConflictValue(e2)；

10. AddEachNodeInArrayThird()；

11. IF e2.Child.Count>1 THEN

12. M=M∪child；

13. END IF

14. END FOR

15. END FOR

16. RETURN Tree；

算法1中，第3行獲取一階等價(jià)類，第6行獲取二階等價(jià)類，第7-13行用于判斷第2層結(jié)點(diǎn)的孩子結(jié)點(diǎn)數(shù)，若超過1，則沖突，并將孩子結(jié)點(diǎn)加入集合M.

算法復(fù)雜度，一階等價(jià)類的創(chuàng)建可在O(n)完成、二階等價(jià)類創(chuàng)建可在O(n2)完成，查找沖突元組可在O(n)完成.那么，算法1的時(shí)間復(fù)雜度為O(n2).

例5.根據(jù)算法1，用本文的ψ1規(guī)則檢測(cè)表1，可創(chuàng)建一棵沖突檢測(cè)樹，如圖1所示.

圖1 沖突檢測(cè)樹Fig.1 Conflicts detect tree

樹中的每個(gè)結(jié)點(diǎn)有3個(gè)域，分別用于存儲(chǔ)數(shù)據(jù)、首個(gè)孩子結(jié)點(diǎn)地址和下一個(gè)兄弟結(jié)點(diǎn)的地址.一棵沖突檢測(cè)樹有如下結(jié)論.

結(jié)論1.沖突檢測(cè)樹的深度為4，葉子結(jié)點(diǎn)中所包含的元組數(shù)為關(guān)系R中所有元組的子集.

結(jié)論2.葉子結(jié)點(diǎn)中，對(duì)于數(shù)據(jù)域的任意兩個(gè)元組ti和tj，若ti和tj的父結(jié)點(diǎn)不同，則必有DIFF(ti，tj)ω.

結(jié)論3.葉子結(jié)點(diǎn)中，若某個(gè)結(jié)點(diǎn)存在兄弟結(jié)點(diǎn)，則該結(jié)點(diǎn)與其兄弟結(jié)點(diǎn)包含的元組互為沖突對(duì)；若某個(gè)結(jié)點(diǎn)不存在兄弟結(jié)點(diǎn)，則該結(jié)點(diǎn)包含的元組不存在沖突.

值得注意的是，可以通過遍歷圖1中的沖突檢測(cè)樹進(jìn)行不一致數(shù)據(jù)的檢測(cè).本文采用鏈表的方式進(jìn)行不一致數(shù)據(jù)的存儲(chǔ)是因?yàn)榭紤]到數(shù)據(jù)集中的元組時(shí)刻發(fā)生變化，而鏈表存儲(chǔ)的方式可以保證在原沖突檢測(cè)樹不變的情況下，方便的添加以及刪除結(jié)點(diǎn).為了提升不一致數(shù)據(jù)的查詢效率，在執(zhí)行檢測(cè)任務(wù)前，可先對(duì)沖突檢測(cè)樹剪枝，進(jìn)行三次優(yōu)化操作.

首次優(yōu)化：對(duì)葉子結(jié)點(diǎn)進(jìn)行優(yōu)化操作，由結(jié)論3可知，無兄弟結(jié)點(diǎn)的葉子結(jié)點(diǎn)包含的元組不存在沖突，因此圖1中可將包含t1的葉子結(jié)點(diǎn)刪除；

二次優(yōu)化：對(duì)第2層結(jié)點(diǎn)進(jìn)行優(yōu)化操作，若第2層的結(jié)點(diǎn)無子結(jié)點(diǎn)，則該結(jié)點(diǎn)包含的元組不會(huì)產(chǎn)生沖突，可刪除該結(jié)點(diǎn)，因此圖1中可將包含t1的第2層結(jié)點(diǎn)刪除；

三次優(yōu)化：對(duì)第1層結(jié)點(diǎn)進(jìn)行優(yōu)化操作，若第1層的結(jié)點(diǎn)無子結(jié)點(diǎn)，則該結(jié)點(diǎn)包含的元組不會(huì)產(chǎn)生沖突，可刪除該結(jié)點(diǎn)，因此圖1中可將包含t5和t6對(duì)應(yīng)的結(jié)點(diǎn)刪除.

圖1的優(yōu)化過程如圖2所示.

圖2 沖突檢測(cè)樹優(yōu)化過程Fig.2 Optimization process of conflicts detect tree

3.2 RwLE規(guī)則的檢測(cè)算法

對(duì)于RwLE規(guī)則，首先根據(jù)條件模板遍歷數(shù)據(jù)集獲得一階等價(jià)類，再根據(jù)時(shí)序關(guān)系判斷對(duì)應(yīng)的屬性值是否滿足偏序條件，若不滿足，則將一階等價(jià)類的值放入集合M中.檢測(cè)算法DetectWithRwLE如算法2所示.

算法2.DetectWithRwLE(I，ψ)

輸入：數(shù)據(jù)實(shí)例I，RwLE規(guī)則ψ

輸出：沖突集合M

1. M=?；

2. equClass=GetFirstEquClass(ψ)；

3. FOREACH e in equClass DO

4. Order e by VT ASC

5. FOREACHtiin e

6. FOREACHtjin e

7. IF DIFF(ti,tj)～ωand (ti,tj) violatesψ

8. M.Add(e)；

9. END FOR

10. END FOR

11. END FOR

12. RETURN M；

算法第2行用于獲取等價(jià)類，第3-7行比較每個(gè)等價(jià)類中的元組是否按時(shí)間滿足相應(yīng)要求，第8行將不滿足要求的等價(jià)類放入M中.

算法復(fù)雜度，一階等價(jià)類的創(chuàng)建可在O(n)完成、查找沖突元組可在O(n2)完成.那么，算法2的時(shí)間復(fù)雜度為O(n2).

3.3 RwF規(guī)則的檢測(cè)算法

對(duì)于RwF規(guī)則，首先遍歷數(shù)據(jù)集的每條元組，再根據(jù)規(guī)則中的X劃分一階等價(jià)類，利用一階等價(jià)類和ω獲取定義8中的集合Ω，對(duì)集合按照用戶定義的函數(shù)求值，若與模板不匹配，則將相應(yīng)元組放入集合M中.檢測(cè)算法DetectWithRwF如算法3所示.

算法3.DetectWithRwF(I，ψ)

輸入：數(shù)據(jù)實(shí)例I，RwLE規(guī)則ψ

輸出：沖突集合M

1. M=?；

2. FOREACHtiin I DO

3. equClass=GetFirstEquClass(ψ)；

4. FOREACHtjin equClas DO

5. value=F(tj)；

6. IF(ti，value)violatesψ(tp)

7. M.Add(ti)；

8. END FOR

9. RETURN M；

算法第3行用于獲取一階等價(jià)類，第5行對(duì)集合Ω按照用戶定義函數(shù)求值，第6行判斷元組ti是否與模板tp匹配，第7行將不匹配的元組加入M.

算法復(fù)雜度，一階等價(jià)類的創(chuàng)建可在O(n)完成、查找沖突元組可在O(n2)完成.那么，算法3的時(shí)間復(fù)雜度為O(n2).

4 查詢語言

為查找數(shù)據(jù)庫中存在的不一致數(shù)據(jù)，本文設(shè)計(jì)了一種不一致數(shù)據(jù)查詢語言(Inconsistent Data Query Language，簡稱IDQL語言)，包含CREATE和SELECT兩種語句.

1)CREATE語句用于創(chuàng)建沖突檢測(cè)樹，語法如下：

CREATE TREE

FROM

WITH RULE

其中，為沖突檢測(cè)樹名稱；為要檢測(cè)的數(shù)據(jù)集名稱；為RwA的一條規(guī)則.

2)SELECT語句用于查詢沖突元組，語法如下：

SELECT

FROM

WHERE

[RULE TYPE ]

[WITH RULES ]

[WITH OPTIMIZATION]

其中，為根據(jù)數(shù)據(jù)質(zhì)量規(guī)則或沖突檢測(cè)樹投影出數(shù)據(jù)集中沖突元組對(duì)；為表名或沖突檢測(cè)樹名；為查詢條件；為規(guī)則類型；[WITH RULES ]為可選項(xiàng)；為RwLE或RwF規(guī)則；[WITH OPTIMIZATION]為可選項(xiàng)，表示是否優(yōu)化查詢.

例6.可以使用IDQL語言執(zhí)行以下語句.

Q1：根據(jù)ψ1規(guī)則，為Accident表創(chuàng)建沖突檢測(cè)樹，樹名為DetectTree.

CREATE TREE DetectTree

FROM Accident

WITH RULE (VT|2years：TeaID→Salary，)

通過Q1執(zhí)行算法1創(chuàng)建沖突樹.

Q2：若發(fā)生教學(xué)事故，查找TeaID為1-2000的教師在2年內(nèi)的工資是否一致，若沖突，將沖突元組顯示出來.

SELECT M.tuple

FROM DetectTree

WHERE TeaID BETWEEN 1 AND 2000

通過算法1生成的沖突樹，查找沖突集合M中滿足條件的沖突元組.

Q3：對(duì)Q2優(yōu)化查詢(此時(shí)先對(duì)DetectTree進(jìn)行剪枝操作，再查詢).

SELECT M.tuple

FROM DetectTree

WHERE TeaIDBETWEEN 1AND 2000

WITH OPTIMIZATION

對(duì)算法1生成的沖突樹進(jìn)行剪枝操作，再查詢.

Q4：找出工資未隨VT時(shí)間單調(diào)增長的教師編號(hào).

SELECT M.tuple

FROM Accident

RULE TYPE RwLE

WITH RULES (VT|forever：ti?VTtj→ti[Salary]≤tj[Salary]，)

通過Q3執(zhí)行算法2.

Q5：5年內(nèi)，若教師的教學(xué)事故累計(jì)3次，則Level的值小于等于2.

SELECT M.tuple

FROM Accident

RULE TYPE RwF

WITH RULES

(VT|5years：TeaID，COUNT(AccidentType)→Level，<(≥3，≤2)>)

通過Q5執(zhí)行算法3.

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

實(shí)驗(yàn)數(shù)據(jù)集為某高校教職員工2010年-2019年共計(jì)10年的信息數(shù)據(jù)，采集信息平臺(tái)中獲獎(jiǎng)、教學(xué)事故以及教職員工基本信息3方面的數(shù)據(jù)，實(shí)驗(yàn)中，為了方便的在同一數(shù)據(jù)集上執(zhí)行不同種類的子規(guī)則，故將以上信息融合至一張表，稱為Teaher.關(guān)系模式Teacher(ID、TeaID、TeaName、TeaAge、TeaSex、Prize、Bonus、Level、Title、AccidentType、Salary、VT、VTType)由13個(gè)屬性組成，分別表示為元組編號(hào)、教師編號(hào)、姓名、年齡、性別、獲獎(jiǎng)名稱(允許為空)、獎(jiǎng)金、級(jí)別、事故類型(允許為空)、工資、事故(獲獎(jiǎng))發(fā)生時(shí)間，事故(獲獎(jiǎng))發(fā)生時(shí)間類型(1為教學(xué)事故時(shí)間，2為獲獎(jiǎng)發(fā)生時(shí)間).數(shù)據(jù)集中記錄了2239位教職員工共計(jì)41876條記錄.在此數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，來驗(yàn)證基于時(shí)態(tài)的數(shù)據(jù)質(zhì)量規(guī)則的檢測(cè)方法的性能.

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

實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)基于Microsoft Windows 10操作系統(tǒng)，開發(fā)環(huán)境為Microsoft Visual Studio 2013，數(shù)據(jù)庫采用SQL SERVER 2012.為了進(jìn)行錯(cuò)誤檢測(cè)，向Teacher表注入2.5%-20%的噪聲數(shù)據(jù).

在Teacher上，有15條TDQRs規(guī)則，依據(jù)2.2小節(jié)的性質(zhì)，去掉冗余的規(guī)則，本文使用剩余8條TDQRs規(guī)則檢測(cè)Teacher上不一致數(shù)據(jù).8條TDQRs規(guī)則如表2所示.

表2 關(guān)系Teacher上的數(shù)據(jù)質(zhì)量規(guī)則Table 2 TDQRs on Teacher

5.2 覆蓋率

對(duì)于給定的ψ，將實(shí)際違反ψ的單元格集合記為RealErrorψ，|RealErrorψ|為實(shí)際違反ψ的單元格數(shù).若幾個(gè)單元格作為一個(gè)沖突對(duì)共同違反了ψ，稱這幾個(gè)單元格被規(guī)則ψ檢測(cè)出來，由文本算法依據(jù)規(guī)則ψ測(cè)出的所有單元格集合記為DetectErrorψ，|DetectErrorψ|為算法測(cè)得違反ψ的單元格數(shù).如例5中，DetectErrorψ1={{{t2，t4}，t3}}，|DetectErrorψ|=3.這里引入覆蓋率的概念以檢測(cè)本文方法的有效性，如公式(1)所示.

ψ的覆蓋率=|DetectErrorψ∩RealErrorψ|/|RealErrorψ|

(1)

類似地，對(duì)一個(gè)時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則集Σ，覆蓋率如公式(2)所示.

Σ的覆蓋率=|∪ψ∈ΣDetectErrorψ∩RealErrorΣ|/|RealErrorΣ|

(2)

經(jīng)過8次獨(dú)立的運(yùn)行，得到時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則(TDQRs)的覆蓋率，如圖3所示.

圖3(a)中，當(dāng)注入10%的噪聲數(shù)據(jù)時(shí)，圖形顯示了表2中ψ1-ψ8規(guī)則對(duì)于不同的元組規(guī)模與覆蓋率之間的關(guān)系.易見，利用TDQRs規(guī)則檢測(cè)，不同的元組規(guī)模得到的覆蓋率均波動(dòng)不大，體現(xiàn)了算法的穩(wěn)定性.同時(shí)，圖形顯示通過算法獲得的覆蓋率值較高，均介于0.9-1之間，說明本文提出的算法在基于時(shí)態(tài)的數(shù)據(jù)集中檢測(cè)沖突元組方面具有較好的性能.

圖3 覆蓋率Fig.3 Coverage

圖3(b)在元組數(shù)為2×104時(shí)，顯示了不同的錯(cuò)誤率與覆蓋率之間的關(guān)系.其中，隨著錯(cuò)誤率的增高，覆蓋率略有下降，這是由于數(shù)據(jù)集中錯(cuò)誤數(shù)據(jù)增加后，更多的錯(cuò)誤數(shù)據(jù)被分散到不同的實(shí)體中，當(dāng)同一實(shí)體只有一條元組或多條元組同為錯(cuò)誤時(shí)，算法無法檢測(cè)導(dǎo)致.

5.3 實(shí)驗(yàn)性能

圖4分別從元組數(shù)和錯(cuò)誤率兩個(gè)方面檢測(cè)TDQRs的3種規(guī)則對(duì)應(yīng)算法的性能.向數(shù)據(jù)集注入10%的噪聲，選擇ψ6、ψ2和ψ8對(duì)應(yīng)TDQRs的3種規(guī)則執(zhí)行算法1、算法2和算法3,3種規(guī)則的時(shí)間復(fù)雜度均為O(n2)，因此，圖4(a)中隨著元組數(shù)增加，3種規(guī)則的運(yùn)行時(shí)間接近，其中RwA的時(shí)間開銷稍高，是因?yàn)樗惴ㄐ枰獎(jiǎng)?chuàng)建二階等價(jià)類耗費(fèi)了一些代價(jià).圖4(b)展示了對(duì)于2×104元組的數(shù)據(jù)集，隨著錯(cuò)誤率增高，算法的運(yùn)行時(shí)間.圖中顯示，運(yùn)行時(shí)間并不會(huì)隨之增長，這是因?yàn)樗惴ǖ臅r(shí)間開銷只與元組數(shù)相關(guān)，不受錯(cuò)誤數(shù)的影響.

圖4 TDQRs運(yùn)行時(shí)間隨元組數(shù)、錯(cuò)誤率的變化Fig.4 Running time of TDQRs with different number of tuples and different error ratio

設(shè)置錯(cuò)誤率為10%，選擇ψ6、ψ2和ψ8這3條規(guī)則分別執(zhí)行算法1、算法2和算法3，將總的耗費(fèi)代價(jià)作為TDQRs的總運(yùn)行時(shí)間，元組規(guī)模與總運(yùn)行時(shí)間的關(guān)系如圖5(a)所示.圖5(a)中，每種規(guī)則耗費(fèi)的時(shí)間復(fù)雜度均為O(n2)，TDQRs的總時(shí)間復(fù)雜度仍然為O(n2)，因此圖形呈現(xiàn)出二次曲線的形狀.隨著元組規(guī)模的增大，TDQRs運(yùn)行時(shí)間也隨著增長，但無論元組規(guī)模多大，總運(yùn)行時(shí)間均能在多項(xiàng)式時(shí)間內(nèi)完成檢測(cè)工作.

圖5(b)展示了在10%的錯(cuò)誤率下，每檢測(cè)到一個(gè)沖突對(duì)，花費(fèi)的平均時(shí)間.由圖可知，隨著元組規(guī)模增大，均攤到檢測(cè)每一個(gè)沖突對(duì)的時(shí)間開銷也隨之增加，且呈線性增長.這是由于TDQRs總運(yùn)行時(shí)間的復(fù)雜度為O(n2)，錯(cuò)誤率固定時(shí)，算法檢測(cè)到的沖突對(duì)個(gè)數(shù)與n值基本呈線性關(guān)系，且n值越大，檢測(cè)到的沖突對(duì)個(gè)數(shù)也越多，將總運(yùn)行時(shí)間與沖突對(duì)個(gè)數(shù)相除，獲得的單個(gè)沖突對(duì)的檢測(cè)時(shí)間也符合一次線性函數(shù)，且隨著n值的增長而遞增.

圖5(c)展示了當(dāng)元組數(shù)為2×104時(shí)，隨著錯(cuò)誤率的增加，檢測(cè)單個(gè)沖突對(duì)花費(fèi)的平均時(shí)間逐漸減少.這是由于規(guī)則的總運(yùn)行時(shí)間并不隨錯(cuò)誤率的增加而發(fā)生變動(dòng)，雖然錯(cuò)誤率的增加會(huì)使得少部分沖突對(duì)難以檢測(cè)出來，但這部分沖突對(duì)的影響甚微，不會(huì)改變被檢測(cè)出的沖突對(duì)總個(gè)數(shù)隨錯(cuò)誤比率呈線性增長的趨勢(shì)，兩者相除，獲得的單個(gè)沖突對(duì)的檢測(cè)時(shí)間接近于反比例函數(shù)關(guān)系.故而導(dǎo)致圖形隨錯(cuò)誤率的增加，均攤在檢測(cè)每個(gè)沖突對(duì)耗費(fèi)的代價(jià)呈下降趨勢(shì).

圖5 TDQRs的總運(yùn)行時(shí)間以及檢測(cè)一個(gè)沖突對(duì)的平均時(shí)間Fig.5 Total running time of TDQRs and average running time of a conflict

RwA規(guī)則在創(chuàng)建沖突檢測(cè)樹時(shí)可以通過剪枝的方法進(jìn)行優(yōu)化查詢，圖6(a)展示了錯(cuò)誤率為10%時(shí)RwA規(guī)則在優(yōu)化前和優(yōu)化后在查詢時(shí)間上的對(duì)比.由圖6(a)可知，在執(zhí)行例6中的Q3查詢時(shí)，優(yōu)化后的查詢時(shí)間明顯低于優(yōu)化前，這是因?yàn)閮?yōu)化方法中的3次剪枝操作使得沖突樹只保留了不一致的數(shù)據(jù)，而這部分?jǐn)?shù)據(jù)只占數(shù)據(jù)集的很小比例，遍歷時(shí)，算法在很短時(shí)間內(nèi)能查詢到對(duì)應(yīng)的不一致數(shù)據(jù).圖6(b)中，數(shù)據(jù)規(guī)模為2×104條元組，時(shí)間開銷隨著錯(cuò)誤率的增加緩慢增長，這是由于錯(cuò)誤越多，優(yōu)化后沖突樹中保留的結(jié)點(diǎn)就越多，遍歷時(shí)耗費(fèi)的時(shí)間代價(jià)就越大.

圖6 優(yōu)化技術(shù)對(duì)運(yùn)行時(shí)間的影響Fig.6 Effect of running time with optimization technology

從上述實(shí)驗(yàn)結(jié)果可以看出，本文提出的時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則檢測(cè)方法可以有效地檢測(cè)出時(shí)態(tài)條件下的不一致數(shù)據(jù).且本文在算法1的基礎(chǔ)上提出的3次優(yōu)化操作進(jìn)行不一致數(shù)據(jù)查詢時(shí)，查詢效率得到了明顯的提高.

6 總 結(jié)

本文對(duì)已有的函數(shù)依賴進(jìn)行擴(kuò)展，加入時(shí)態(tài)語義，提出了時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則，并給出了規(guī)則相關(guān)的性質(zhì)及對(duì)應(yīng)的檢測(cè)算法.此外，本文還提出了IDQL語言用于查詢不一致數(shù)據(jù).最后，通過實(shí)驗(yàn)驗(yàn)證了時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則能夠檢測(cè)出更多的不一致數(shù)據(jù)，且算法可在多項(xiàng)式時(shí)間內(nèi)完成.然而，檢測(cè)出不一致數(shù)據(jù)后，還需對(duì)不一致數(shù)據(jù)加以分析，獲得可靠的修復(fù)方案，本文的下一步工作將基于時(shí)態(tài)數(shù)據(jù)質(zhì)量規(guī)則，研究不一致數(shù)據(jù)的修復(fù)方法.