李默涵++李建中

摘要： 當前，隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)質(zhì)量問題受到越來越多的關注。數(shù)據(jù)質(zhì)量會隨著時間的流逝迅速下降，因此在數(shù)據(jù)質(zhì)量的各個維度中，數(shù)據(jù)時效性扮演的角色至關重要。判定一個給定的數(shù)據(jù)集合的時效性是確保數(shù)據(jù)時效性是第一步，但數(shù)據(jù)時效性的判定并非易事，其面臨極大挑戰(zhàn)。本文針對時效性判定問題面臨的各個挑戰(zhàn)，綜述了當前該領域針對絕對時效性判定和相對時效性判定的關鍵理論和技術，分析了現(xiàn)有的各方法的優(yōu)缺點，并對未來的研究方向給出了建議。

關鍵詞：數(shù)據(jù)質(zhì)量； 數(shù)據(jù)時效性； 時效性判定

中圖分類號： TP391.41

文獻標志碼：A

文章編號： 2095-2163（2016）06-0072-04

0引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)的“量”在飛速增長，但與此同時，數(shù)據(jù)的“質(zhì)”的下降也成為了不可忽視的問題。多家機構的統(tǒng)計數(shù)據(jù)表明，當前各行各業(yè)中信息的可用性（即數(shù)據(jù)質(zhì)量）問題亟待解決。在美國，企業(yè)中有1%～30%的數(shù)據(jù)存在各種質(zhì)量問題[1]，醫(yī)療中有13.6%～81%的組成是不完整、或過時數(shù)據(jù)[2]。同時，根據(jù)國際著名科技咨詢機構Gartner的調(diào)查結果，即使是在那些著名企業(yè)，如全球財富1 000強的企業(yè)中，也有超過25%的企業(yè)其信息系統(tǒng)中的關鍵信息不正確或不準確[3]。如果不能夠及時有效地針對這些數(shù)據(jù)質(zhì)量問題提供全面完整解決，就必將會對國民生活和企業(yè)決策形成不可預知的惡劣影響。事實上，已有多次調(diào)查結果陸續(xù)表明，如上的數(shù)據(jù)質(zhì)量問題每年都會在全球范圍內(nèi)造成重大不良效應后果：數(shù)據(jù)質(zhì)量問題在美國引發(fā)的醫(yī)療事故所導致的死亡人數(shù)高達98 000名，約等于總醫(yī)療事故致死人數(shù)的一半[4]；數(shù)據(jù)過時和錯誤將使得美國工業(yè)企業(yè)損失高達6 110億美元，這一數(shù)值幾乎可占美國GDP的6%[5]；標價錯誤還會導致美國零售業(yè)損失25億美元[6]；數(shù)據(jù)中的不一致錯誤則會導致信用卡欺詐問題的深度隱藏，這在2006年曾造成48億美元的財產(chǎn)損失[7]。由此，根據(jù)推算，劣質(zhì)數(shù)據(jù)的處理需要花費30%～80%的開發(fā)時間和預算[8]，進而數(shù)據(jù)質(zhì)量問題通常給企業(yè)增加獲得同等產(chǎn)值約10%～20%的成本[9]。這也隨即推動了數(shù)據(jù)質(zhì)量工具市場的飛速增長，甚至遠超IT行業(yè)的平均增長率[10]。劣質(zhì)數(shù)據(jù)無時無刻都將通過網(wǎng)絡在不同數(shù)據(jù)源之間傳播，因此對數(shù)據(jù)可用性的研究已經(jīng)成為數(shù)據(jù)管理領域中的首要問題內(nèi)容之一。近幾年來，數(shù)據(jù)庫領域的頂級國際會議及期刊每年都會達成和開展多項關系著數(shù)據(jù)質(zhì)量方面的相關議程和研究工作。

一般說來，要從下述5個維度來保證數(shù)據(jù)可用性[11]?，F(xiàn)作如下論述：

1）時效性。保證數(shù)據(jù)與時俱進，不陳舊過時。例如，某數(shù)據(jù)庫中的用戶地址在2010年是正確的，但在2011年未必正確，即存在過時數(shù)據(jù)。

2） 一致性。保證數(shù)據(jù)不違背某些特定約束。例如，記錄（郵編=“150000”，城市=“上海”）就違背了郵編和城市的對應關系，因為150000是哈爾濱的郵編、而非上海郵編。

3） 完整性。保證數(shù)據(jù)不存在缺失。例如，醫(yī)療數(shù)據(jù)庫遺失某患者病史就會導致數(shù)據(jù)不完整，進而可能妨礙醫(yī)生正確診斷病情。

4） 精確性。保證數(shù)據(jù)能夠準確地描述對應實體。例如，哈爾濱全市總面積約為5.384萬平方公里，但數(shù)據(jù)庫中記錄卻為5萬平方公里，這雖在宏觀來看是合理的，但不精確。精確性和一致性并不相同，一致的信息也可能含有誤差，即未必精確。

5） 實體同一性。保證描述同一實體的數(shù)據(jù)在不同數(shù)據(jù)源上是統(tǒng)一的。例如，可以通過對比個人信息來判斷信用卡的使用者和持有者是否為同一人，從而防止欺詐。

在數(shù)據(jù)可用性的5個維度中，數(shù)據(jù)時效性的作用地位至關重要。據(jù)統(tǒng)計，在商業(yè)和醫(yī)療信息數(shù)據(jù)庫中，約有2%的客戶信息會在一個月內(nèi)變得陳舊失效[5]，如果這些數(shù)據(jù)未獲修復，那么在2年內(nèi)，就將有近50%的記錄會因為過時而使其可用性受到影響，而過時數(shù)據(jù)將會導致嚴重后果。在企業(yè)決策時，企業(yè)往往會因為使用了陳舊的數(shù)據(jù)而做出錯誤的決策，而在日常生活中，銀行可能會將信用卡賬單寄送到持有人搬家前的舊地址。同時，有相當一部分數(shù)據(jù)的不一致、不精確、不完整等都是由數(shù)據(jù)過時失效引起的。例如，銀行未能及時更新客戶的地址信息將會導致同一客戶的住址和郵編難以匹配；隨著人口的增長和流動，數(shù)據(jù)庫中各城市的人口數(shù)會因為過時變得不再精確；新入學的學生的學籍信息未及時錄入會導致記錄學生信息的數(shù)據(jù)庫無法趨于完整。因此，確保數(shù)據(jù)的時效性已成為熱點與焦點。

判定一個給定的數(shù)據(jù)集合的時效性是確保數(shù)據(jù)時效性的第一步。只是數(shù)據(jù)時效性的判定卻并非易事。同一記錄的不同屬性隨時間變化的頻率不同，使得同一記錄的不同屬性的新舊程度也會不同，這即使得數(shù)據(jù)時效性判定問題的研究面臨嚴峻挑戰(zhàn)。首先，數(shù)據(jù)庫中通常沒有完整、可用、精確的時間戳[12]，此時就需要建立一個不依賴于時間戳的數(shù)據(jù)時效性度量模型。使用該模型，可以對一個給定數(shù)據(jù)庫，形式化地表示單個數(shù)據(jù)項、元組以及數(shù)據(jù)庫整體的時效性（稱為絕對時效性），并定量地判定其時效性。其次，數(shù)據(jù)庫的絕對時效性可能無法直接判定，又或者判定結果不能有效地表達用戶需求。為此，則需要針對該數(shù)據(jù)庫上的常用查詢或用戶的特定需求，設計數(shù)據(jù)庫的相對時效性度量模型。該模型能夠度量數(shù)據(jù)庫中較重要部分的時效性，如某些重要查詢的提供結果的時效性，或者用戶最常使用的數(shù)據(jù)集合的時效性。

基于如上的論證分析，本文將綜述當前數(shù)據(jù)時效性判定的關鍵理論和技術，包括數(shù)據(jù)的絕對時效性和相對時效性判定模型，數(shù)據(jù)時效性修復算法及查詢相關的數(shù)據(jù)時效性研究等。

[BT4]1絕對時效性判定

當前的時效性判定工作大致可以分為2類：基于時間戳的時效性判定和基于規(guī)則的時效性判定。其中，基于時間戳的時效性判定要求數(shù)據(jù)庫中對每個待判定的值都存有完整、清潔、可用的時間戳，通常是事務時間，根據(jù)事務時間和數(shù)值有效性的衰減來判定當前值是否過時失效，即推斷有效時間。該方法的優(yōu)點是能夠?qū)τ诮o定的時間點，判定數(shù)據(jù)在該時刻過時失效，但缺點卻在于其需要大量的輔助信息，如每個值的事務時間和每個值的有效性衰減規(guī)律。由于各種屬性的不同特性，這些輔助信息在真實應用中很難獲得精煉提取，因此基于時間戳的時效性判定方法的適用范圍隨之受到一定限制。為了克服基于時間戳的方法的缺點與不足，基于規(guī)則的方法相應地據(jù)此而獲提出。這類方法只需要根據(jù)少量的由領域知識得到的時效規(guī)則，就可以判斷描述同一實體的不同屬性值的時序關系，從而判定哪些值是過時失效的。這類方法所需的輔助信息大大減少，但其缺點卻表現(xiàn)在當前的基于規(guī)則的方法仍不能判定某個值在給定的時間點是否過時失效。下面，即對這2類判定方法展開分析與討論。

[BT5]1.1基于時間戳的絕對時效性判定

文獻[13–18] 定義數(shù)據(jù)從上一次更新到本次使用的時間間隔為數(shù)據(jù)年齡（age（）），從不同角度定義了數(shù)據(jù)的時效性。文獻[13]和文獻[16]均假設數(shù)據(jù)有一個確定的保質(zhì)期（ShelfLife（）），當數(shù)據(jù)的年齡大于保質(zhì)期時認為數(shù)據(jù)過時失效。給定值A，文獻[13]將其時效性定義為過期概率（ShelfLife（A）-age（A）>0），而文獻[16]則直接使用age（A）作為數(shù)據(jù)的時效性，同時要求數(shù)據(jù)滿足ShelfLife（A）-age（A）>0的約束。文獻[14， 15]假設對于設定值A，A的時效性隨時間流逝的減弱程度可以用時效性衰減函數(shù)decline（A）刻畫，并進一步地定義A的時效性為exp（-decline（A）×age（A））。文獻[17]與文獻[16]類似，簡單地使用數(shù)據(jù)年齡作為數(shù)據(jù)的時效性。并且，文獻[18]又提出了一種基于模糊邏輯來推斷時效性衰減函數(shù)的時效性判定方法，與前述工作相同，該方法也假定數(shù)據(jù)庫有完整可用的時間戳來表示數(shù)據(jù)的存儲時間。

文獻[13–18] 提出的數(shù)據(jù)絕對時效性判定模型在數(shù)據(jù)庫中有完整、清潔、可用的時間戳，且用戶對數(shù)據(jù)的語義了解較為充分時可以有效地判定數(shù)據(jù)的時效性，但這些模型存在一定不足。具體闡析描述如下：

1）在實際應用中，數(shù)據(jù)庫中不一定存在有效的時間戳，這就使得計算數(shù)據(jù)的年齡在多數(shù)情況下趨于困難。

2）上述工作均認為最近更新的數(shù)據(jù)就一定是最新的，這在實際應用中也不會一定成立，數(shù)據(jù)庫管理人員可能只是用一個舊值替代了另一個舊值。

3）文獻[13]和[16]均假設數(shù)據(jù)的保質(zhì)期總是能被用戶預先知曉，這在實際應用中也并不合理，而且文獻[13]也沒有確切給出該文獻定義的數(shù)據(jù)時效性的計算方法。

4）文獻[14， 15]要求數(shù)據(jù)的時效性減弱程度可以用decline（）刻畫，卻沒有提出decline（）的獲得方法，同時文獻中也沒有完整的理論分析來證實其時效性定義的合理性。文獻[18]給出了decline（）的推斷方法，卻又需要額外的數(shù)據(jù)存儲時間來輔助支持推斷。

5）文獻[16， 17]中僅用數(shù)據(jù)的年齡作為數(shù)據(jù)的時效性是遠遠不夠的，不同數(shù)據(jù)表示的具體含義也各有不同，年齡長的數(shù)據(jù)其時效性也未必就會較差。

[BT5]1.2基于規(guī)則的絕對時效性判定

文獻[19， 20]首次研究了在數(shù)據(jù)庫中不存在時間戳時，如何使用規(guī)則來幫助判定數(shù)據(jù)的時效性。這些工作首次給出了不依賴于時間戳的數(shù)據(jù)時效性度量模型。該文獻分3部分對數(shù)據(jù)的時效性來實現(xiàn)建模：時序關系（Currency Order）、時效約束（Currency Constraint）、不同數(shù)據(jù)源間的拷貝函數(shù)（Copy Function）。具體地，時序關系tiAtj表示元組ti在屬性A上比元組tj舊。時效約束定義為一階邏輯語句t1，…，tj： R（∧j∈[1，k]t1[EID]=tj[EID]∧φ→tuAtv），能夠描述數(shù)據(jù)的語義信息。該約束表示如果一組元組t1，…，tj描述的實體相同（即EID相同），且滿足特定條件φ，那么就有結論tuAtv。當數(shù)據(jù)來自于多個數(shù)據(jù)源時，拷貝函數(shù)R1[A→]←R2[B→]可以描述不同數(shù)據(jù)源間的依賴關系，如數(shù)據(jù)源R1的A→向量表示的屬性可能就是拷貝自數(shù)據(jù)源R2的B→。

上述研究實現(xiàn)首次提出了時間戳不可用情況下的數(shù)據(jù)絕對時效性模型，其中雖然給出了較完整的數(shù)據(jù)時效性定義，但仍有許多問題沒有解決：

1）沒有給出定量地確定數(shù)據(jù)時效性的方法，僅能對給定的實體推測其屬性值是否為最新。

2）沒有給出任何能夠判定數(shù)據(jù)庫時效性的算法，而且上述工作定義的判定問題多為NP-完全或更難，這將給該模型進入實際工作帶來相關困難，因此需要尋找快速的數(shù)據(jù)時效性判定算法。

3）提出的模型準確性依賴于時效約束，但是在實際應用中，用戶很難給出完整正確的時效約束，該工作也沒有討論時效約束的獲得方法。

4）提出的模型依賴于數(shù)據(jù)庫中的冗余元組，當冗余元組不存在時，該模型就無法就直接使用。

5）文中提出的模型只能夠針對不同屬性值間的序關系進行建模，但是在實際應用中，數(shù)據(jù)時效性往往和具體的時間點有關，因此需要借助與時間點有關的數(shù)據(jù)語義來判定數(shù)據(jù)是否過時。

[BT5]1.3小結

綜上可知，在數(shù)據(jù)絕對時效性的研究中，仍有如下關鍵問題亟待解決。首先應建立不依賴于時間戳和冗余元組的，能夠定量度量數(shù)據(jù)絕對時效性的模型，該模型不僅要能夠推斷數(shù)據(jù)之間的時序關系，還要能夠推斷數(shù)據(jù)在給定時刻是否失效。而在此模型構建的基礎上，還應給出多項式時間的數(shù)據(jù)時效性判定算法。

[BT4]2相對時效性判定

[BT5]2.1相對時效性判定方法研究

目前，相對時效性的研究工作非常有限，僅在分布式數(shù)據(jù)庫環(huán)境下有類似的研究，即文獻[21]。該工作研究數(shù)據(jù)分布式存儲的環(huán)境下，查詢結果的時效性度量，具體是將數(shù)據(jù)的更新建模為泊松過程，并計算當前查詢能夠用最新數(shù)據(jù)回答的概率，并以之作為數(shù)據(jù)的時效性。查詢能夠用最新數(shù)據(jù)回答的概率等于查詢在數(shù)據(jù)過期之前發(fā)出的概率。文獻[21]能夠一定程度上解決相對時效性判定問題，但其不足卻在于，只是考慮了數(shù)據(jù)分布式存儲的情況，且假設2次更新的時間間隔長度的概率分布已知，而若數(shù)據(jù)的更新規(guī)律未知時則不可能知道更新時間間隔長度的概率分布，因此算法的使用也還未形成廣泛拓展的新格局。

盡管相對時效性的研究工作迄今仍然限量可數(shù)，但是在數(shù)據(jù)可用性管理的其他領域，卻也存在一些針對相對數(shù)據(jù)可用性的特征研究，這些進展成果對于相對時效性研究頗具啟發(fā)意義。文獻[22]是較早期的度量結果可信度的研究工作，通過將數(shù)據(jù)庫構建為一個圖，結點代表數(shù)據(jù)庫中的元組，邊表示元組間關系，邊權值表示2個元組存在關系的概率。給定數(shù)據(jù)庫以及特定關系R，查詢要求返回那些有可能滿足R的元組集合，而查詢的結果可信度則定義為該結果滿足R的概率。分析這一設計實現(xiàn)的不足可知，該文獻本質(zhì)上只是研究一個不確定數(shù)據(jù)庫上的查詢回答問題，并沒有給出邊權值的定義方法及來源，因此也未從本質(zhì)上解決相對數(shù)據(jù)質(zhì)量的判定問題。文獻[23–25]研究不確定數(shù)據(jù)上查詢結果的質(zhì)量判定問題。文獻[23， 24]均從結果二義性的角度出發(fā)，以信息熵的相反數(shù)為查詢結果的質(zhì)量度量指標，該指標取值范圍為（-∞，0]，結果質(zhì)量越接近于0，則其二義性越弱，質(zhì)量越好。其中，文獻[23]研究了不確定數(shù)據(jù)上的范圍查詢（Range Query）和最大值查詢（MAX Query）的結果質(zhì)量度量方法，文獻[24]研究了不確定數(shù)據(jù)上的Top-k查詢的結果質(zhì)量度量方法。并且，文獻[25]則重點結合了skyline和Top-k查詢來對復雜情況下不確定數(shù)據(jù)的查詢給出一個可信結果?，F(xiàn)結合這部分工作可提出2點存在問題：首先，文中提出的度量在施于數(shù)據(jù)二義性時，本質(zhì)上是考察查詢的可能結果的數(shù)目，結果數(shù)越多，則二義性越大，但事實上，某些查詢雖然會得到較多可能的查詢結果，但各個查詢結果之間呈現(xiàn)了顯著可觀的相似度，此時，將無法簡單地斷定該查詢結果具有較高的二義性；其次，因為完全沒有考慮查詢在時間維度的特點，即使得文中提出的二義性的定義也無法直接用來解析數(shù)據(jù)的相對時效性。此外，文獻[26–28]又深入研究了數(shù)據(jù)的相對完整性問題。文獻[26， 27]研究了給定主數(shù)據(jù)（Master Data）Dm、約束集合V、查詢Q以及數(shù)據(jù)庫實例T時，T在Dm和V的約束下的相對完整性判定問題。文獻[28]則代表性地給出了完整度度量模型，一方面可以表示數(shù)據(jù)集合中特定部分的完整性，稱為表完整性（Table Completeness），另一方面也可以表示查詢結果的完整性，稱為查詢完整性（Query Completeness）。這部分技術進展均能從不同角度判定數(shù)據(jù)相對完整性，但由于數(shù)據(jù)時效性與時序密切相關，則決定了這些工作仍然未能真正解決相對時效性判定問題。

[BT5]2.2小結

綜上所述，目前相對數(shù)據(jù)質(zhì)量判定方面的研究仍處在萌芽階段，現(xiàn)有工作大多關注模型定義和問題復雜度，關鍵算法的研究相對匱乏。在數(shù)據(jù)相對時效性的研究中，必須考慮到查詢與時序密切相關這一特點，根據(jù)查詢在時間維度的特性，一方面給出合理的相對時效性的定量度量，另一方面也需給出判定相對時效性的迅捷有效的關鍵算法。

[BT4〗3結束語

本文討論了當前數(shù)據(jù)時效性判定的關鍵理論和技術，分析了當前理論和技術的優(yōu)點及不足。通過分析可知，當前數(shù)據(jù)質(zhì)量領域?qū)τ跁r效性的研究已經(jīng)有一些不同角度的較為成型的理論和方法，但綜合看來此領域的研究仍然不成體系，解決時效性維度的質(zhì)量問題需依次解決以下幾個問題：絕對時效性判定模型、多項式時間的絕對時效性判定算法、相對時效性的形式化定義以及相應的相對時效性判定算法。在必要時，還需給出時效性修復策略以及判定和修復結果的整合策略。因此，數(shù)據(jù)時效性的研究任重而道遠，仍需不斷推進探索。

[HS1*2][HT5H]參考文獻：[HT]

[WTBZ][ST6BZ][HT6SS][1] [ZK（#〗

[HJ*2]

REDMAN T C. The impact of poor data quality on the typical enterprise[J]. Commun. ACM， 1998， 41（2）：79-82.

[2] MILLER Jr D W， YEAST J D， EVANS R L. Missing prenatal records at a birth center： A communication problem quantified[C]//AMIA Annual Symposium Proceedings. Bethesda， MD， USA： American Medical Informatics Association， 2005：535.

[3] SWARTZ N. Gartner warns firms of ”dirty data”[J]. Information Management Journal， 2007， 41（3）：6-7.

[4] KOHN L T， CORRIGAN J M， DONALDSON M S， et al. To err is human： Building a Safer Health System[M]. Washington， D.C.： National Academies Press， 2000.

[5] Eckerson W. Data Warehousing Special Report： Data quality and the bottom line[R]. Washington： The Data Warehouse Institute， 2002.

[6] ENGLISH L P. Information quality management： The next frontier[C]//ASQ World Conference on Quality and Improvement Proceedings. Milwaukee， Wisconsin： American Society for Quality， 2001：529.

[7] Ben W， Schulz S. Credit card statistics， industry facts， debt statistics[EB/OL]. [2010-06-04]. http：//www.creditcards.com.

[8] Christopher S， Julie T. Enterprise information portals[R]. New York， NY， USA： Merrill Lynch， 1998.

[9] RAHM E， DO H H. Data cleaning： Problems and current approaches[J]. IEEE Data Eng. Bull.， 2000， 23（4）：3-13.

[10]FLESCA S， FURFARO F， GRECO S， et al. Querying and repairing inconsistent XML data[C]//Proceedings of Web Information Systems Engineering （WISE）. Berlin， Heidelberg，Germany： Springer， 2005：175-188.

[11]李建中， 劉顯敏. 大數(shù)據(jù)的一個重要方面： 數(shù)據(jù)可用性[J]. 計算機研究與發(fā)展， 2015， 50（6）：1147-1162.

[12]ZHANG H， DIAO Y， IMMERMAN N. Recognizing patterns in streams with imprecise timestamps[J]. Information Systems， 2013， 38（8）：1187-1211.

[13]GRZ Q. An economicsdriven decision model for data quality improvement： A contribution to data currency[C]//AMCIS. Atlanta， Georgia， USA： AIS， 2011：1-8.

[14]HEINRICH B， KLIER M. Assessing data currency： A probabilistic approach[J]. Journal of Information Science， 2011， 37（1）：86-100.