時態(tài)數(shù)據(jù)質(zhì)量規(guī)則的研究及檢測

黃 慧，李海林

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

1 引 言

大數(shù)據(jù)時代，數(shù)據(jù)質(zhì)量直接關(guān)系數(shù)據(jù)深層使用價值的實現(xiàn)效果.高質(zhì)量數(shù)據(jù)不僅創(chuàng)造著巨額的社會財富，甚至已經(jīng)關(guān)乎國計民生.而劣質(zhì)的數(shù)據(jù)會導致決策偏差，社會財富損失，對社會安定和人身安全都形成巨大的威脅[1].近年來，學者們針對數(shù)據(jù)質(zhì)量問題展開了廣泛的研究，大多研究工作基于函數(shù)依賴規(guī)則[2-4]，進行不一致數(shù)據(jù)的檢測與修復.函數(shù)依賴(FDs)指的是，對于關(guān)系R中的屬性X和Y，X→Y是一個函數(shù)依賴，對于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個屬性組成，分別表示為元組編號、教師編號、教師名、等級、職稱、教學事故類型、工資和發(fā)生教學事故的有效時間.

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

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

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

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

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

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

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

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

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

本文的主要工作如下：

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

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

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

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

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

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

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

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

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

(VT|ω：X→Y，)

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

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

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

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

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

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

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

若對應的是RwF規(guī)則，X或Y可以是一個包含用戶定義函數(shù)的表達式，條件模板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.時間距離.I是R上的一個實例，對于I上任意兩條元組ti和tj在VT上的差值，稱為時間距離，記作DIFF(ti，tj).若DIFF(ti，tj)滿足ω，記為DIFF(ti，tj)～ω.

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

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

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

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

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

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

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

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

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

定義7.RwLE規(guī)則一致性.I是R上的一個實例，A、B是R上的屬性，規(guī)則ψ∈RwLE，ψ關(guān)于I是一致的，當且僅當，對于任意元組ti和tj，在ti和tj屬于同一個一階等價類的條件下，有集合Ω={tj|DIFF(ti，tj)～ω}(ti，tj在同一時間區(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上的一個實例，A、B是R上的屬性，對于I上任意一條元組ti，規(guī)則ψ∈RwF，ψ關(guān)于I是一致的，當且僅當，在ti和tj屬于同一個一階等價類的條件下，對于集合Ω={tj|DIFF(ti，tj)～ω}∪ti，若f(Ω(A))≈tpA，則ti[B]≈tpB，記作I|=ψ.否則，I關(guān)于ψ是不一致的，記作I|≠ψ.

其中，“≈”表示與條件模板匹配.根據(jù)定義8，表1中元組t3，對于規(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ù)實例I以及TDQRs規(guī)則集合Σ，對于?ψi∈Σ，都有I|=ψi，則稱I為干凈數(shù)據(jù).

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

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

2.2 TDQRs的性質(zhì)

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

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

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

證明：反正法.假設(VT|ω2：X→Y，)不成立，由定義6可知，有二階等價類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生成的二階等價類SECM，使得SECk?SECM，且ti和tj∈SECM；又因為ti[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可知，存在一個二階等價類SECk，對于任意的ti和tj∈SECk，若ti[X]=tj[X]，有ti[Y]=tj[Y]；又因為(VT|ω2：Y→Z，)成立，存在相同的二階等價類SECk，有ti[Y]=tj[Y]，則ti[Z]=tj[Z]；因此，有相同的二階等價類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可知，存在一個二階等價類SECk，對于任意的ti和tj∈SECk，若ti[X]=tj[X]，有ti[Y]=tj[Y]；又因為在相同的二階等價類中，已知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→κ，).

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

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

證明：因為(VT|ω：ti?Xtj→ti?Ytj，)成立，由定義7可知，存在一個一階等價類FECk，對于任意的ti和tj∈FECk，且DIFF(ti，tj)～ω，使得若ti?Xtj，有ti?Ytj；同理，因為(VT|ω：ti?Ytj→tiOPZtj，)成立，在相同的前提條件下，已知ti?Ytj，則tiOPZtj成立.因此有，對于任意的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，).

證明：反正法.假設(VT|ω2：ti?Xtj→tiOPYtj，)不成立，由定義7可知，有一階等價類FECk，存在ti和tj∈FECk，對于ti，有集合Ω2={tj|DIFF(ti，tj)～ω2}，tj∈Ω2，使得若ti?xtj，有ti!OPYtj；又已知ω1?ω2，因為DIFF(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，)不成立，與已知矛盾.得證.

進行不一致數(shù)據(jù)檢測時，TQDRs規(guī)則越多，時間開銷越大.因此，可以利用以上性質(zhì)，去除冗余的規(guī)則，提升查詢效率.例如，假設規(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ù)的檢測

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

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

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

算法1.DetectWithRwA(I，ψ)

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

輸出：沖突檢測樹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行獲取一階等價類，第6行獲取二階等價類，第7-13行用于判斷第2層結(jié)點的孩子結(jié)點數(shù)，若超過1，則沖突，并將孩子結(jié)點加入集合M.

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

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

圖1 沖突檢測樹Fig.1 Conflicts detect tree

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

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

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

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

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

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

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

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

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

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

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

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

算法2.DetectWithRwLE(I，ψ)

輸入：數(shù)據(jù)實例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行用于獲取等價類，第3-7行比較每個等價類中的元組是否按時間滿足相應要求，第8行將不滿足要求的等價類放入M中.

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

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

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

算法3.DetectWithRwF(I，ψ)

輸入：數(shù)據(jù)實例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行用于獲取一階等價類，第5行對集合Ω按照用戶定義函數(shù)求值，第6行判斷元組ti是否與模板tp匹配，第7行將不匹配的元組加入M.

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

4 查詢語言

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

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

CREATE TREE

FROM

WITH RULE

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

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

SELECT

FROM

WHERE

[RULE TYPE ]

[WITH RULES ]

[WITH OPTIMIZATION]

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

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

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

CREATE TREE DetectTree

FROM Accident

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

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

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

SELECT M.tuple

FROM DetectTree

WHERE TeaID BETWEEN 1 AND 2000

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

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

SELECT M.tuple

FROM DetectTree

WHERE TeaIDBETWEEN 1AND 2000

WITH OPTIMIZATION

對算法1生成的沖突樹進行剪枝操作，再查詢.

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

5.1 實驗設置

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

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

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

5.2 覆蓋率

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

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

(1)

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

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

(2)

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

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

圖3 覆蓋率Fig.3 Coverage

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

5.3 實驗性能

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

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

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

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

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

圖5 TDQRs的總運行時間以及檢測一個沖突對的平均時間Fig.5 Total running time of TDQRs and average running time of a conflict

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

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

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

6 總 結(jié)

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