時態數據質量規則的研究及檢測

黃 慧，李海林

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

本文的主要工作如下：

1)提出時態數據質量規則(Temporal Data Quality Rules，簡稱TDQRs)的形式化表達；

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

3)基于TDQRs，設計等價類劃分方法，形成基于時態的不一致數據檢測算法，并通過剪枝的策略優化算法；

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

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

2 TDQRs的相關定義與性質

2.1 TDQRs的相關定義

針對時態數據質量規則，本文引入如下定義.

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

(VT|ω：X→Y，)

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

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

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

若對應的是RwA規則，當ω的值為“forever”，且條件模板tp為空時，RwA規則可退化為傳統的函數依賴規則.

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

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

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

若對應的是RwF規則，X或Y可以是一個包含用戶定義函數的表達式，條件模板tp分為tpX和tpY，分別表示條件模板的前件和后件.

例3.根據定義2，例2中的L1-L4可由三種子規則表示為ψ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規則；ψ2和ψ3是RwLE規則；ψ4是RwF規則.

定義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).為了查找不一致數據，將數據集中的數據按照規則對元組進行首次劃分歸類，得到的不同集合稱為一階等價類.

若ψ∈RwA，則按規則左部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，則按規則左部X中的非聚合表達式劃分等價類，如ψ4同樣得到一階等價類為FEC1和FEC2.

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

當ψ∈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}再次劃分二階等價類歸類，執行順序為：(a)按照VT排序，集合仍然為{t1，t2，t3，t4}；(b)查找與tp匹配的首條元組為t1；(c)獲取Ω1，此時Ω1=φ，將t1放入SEC1；(d)剩余的元組{t2，t3，t4}按照步驟2)繼續處理，首條元組為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}.

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

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

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

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

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

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

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

定義9.干凈數據.給定關系模式R上的數據實例I以及TDQRs規則集合Σ，對于?ψi∈Σ，都有I|=ψi，則稱I為干凈數據.

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

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

2.2 TDQRs的性質

關系模式R上所有屬性集合為U，Σ是U上一組時態數據質量規則，于是有關系模式R，本小節針對R，給出其上滿足的一些性質及證明.

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

性質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，)不成立，與已知條件矛盾.得證.

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

證明：已知(VT|ω1：X→Y，)成立，且ω1?ω2，由性質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，)成立.得證.

性質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條性質.

性質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→κ，)成立.得證.

性質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，，成立.得證.

性質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，)不成立，與已知矛盾.得證.

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

ψ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不一致數據的檢測

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

3.1 RwA規則的檢測算法

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

算法1.DetectWithRwA(I，ψ)

輸入：數據實例I，RwA規則ψ

輸出：沖突檢測樹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層結點的孩子結點數，若超過1，則沖突，并將孩子結點加入集合M.

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

例5.根據算法1，用本文的ψ1規則檢測表1，可創建一棵沖突檢測樹，如圖1所示.

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

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

結論1.沖突檢測樹的深度為4，葉子結點中所包含的元組數為關系R中所有元組的子集.

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

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

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

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

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

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

圖1的優化過程如圖2所示.

圖2 沖突檢測樹優化過程Fig.2 Optimization process of conflicts detect tree

3.2 RwLE規則的檢測算法

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

算法2.DetectWithRwLE(I，ψ)

輸入：數據實例I，RwLE規則ψ

輸出：沖突集合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中.

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

3.3 RwF規則的檢測算法

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

算法3.DetectWithRwF(I，ψ)

輸入：數據實例I，RwLE規則ψ

輸出：沖突集合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行對集合Ω按照用戶定義函數求值，第6行判斷元組ti是否與模板tp匹配，第7行將不匹配的元組加入M.

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

4 查詢語言

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

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

CREATE TREE

FROM

WITH RULE

其中，為沖突檢測樹名稱；為要檢測的數據集名稱；為RwA的一條規則.

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

SELECT

FROM

WHERE

[RULE TYPE ]

[WITH RULES ]

[WITH OPTIMIZATION]

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

例6.可以使用IDQL語言執行以下語句.

Q1：根據ψ1規則，為Accident表創建沖突檢測樹，樹名為DetectTree.

CREATE TREE DetectTree

FROM Accident

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

通過Q1執行算法1創建沖突樹.

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

SELECT M.tuple

FROM DetectTree

WHERE TeaID BETWEEN 1 AND 2000

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

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

SELECT M.tuple

FROM DetectTree

WHERE TeaIDBETWEEN 1AND 2000

WITH OPTIMIZATION

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

Q4：找出工資未隨VT時間單調增長的教師編號.

SELECT M.tuple

FROM Accident

RULE TYPE RwLE

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

通過Q3執行算法2.

Q5：5年內，若教師的教學事故累計3次，則Level的值小于等于2.

SELECT M.tuple

FROM Accident

RULE TYPE RwF

WITH RULES

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

通過Q5執行算法3.

5 實 驗

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

5.1 實驗設置

實驗環境：實驗基于Microsoft Windows 10操作系統，開發環境為Microsoft Visual Studio 2013，數據庫采用SQL SERVER 2012.為了進行錯誤檢測，向Teacher表注入2.5%-20%的噪聲數據.

在Teacher上，有15條TDQRs規則，依據2.2小節的性質，去掉冗余的規則，本文使用剩余8條TDQRs規則檢測Teacher上不一致數據.8條TDQRs規則如表2所示.

表2 關系Teacher上的數據質量規則Table 2 TDQRs on Teacher

5.2 覆蓋率

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

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

(1)

類似地，對一個時態數據質量規則集Σ，覆蓋率如公式(2)所示.

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

(2)

經過8次獨立的運行，得到時態數據質量規則(TDQRs)的覆蓋率，如圖3所示.

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

圖3 覆蓋率Fig.3 Coverage

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

5.3 實驗性能

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

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

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

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

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

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

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

圖6 優化技術對運行時間的影響Fig.6 Effect of running time with optimization technology

從上述實驗結果可以看出，本文提出的時態數據質量規則檢測方法可以有效地檢測出時態條件下的不一致數據.且本文在算法1的基礎上提出的3次優化操作進行不一致數據查詢時，查詢效率得到了明顯的提高.

6 總 結

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