數據時效性判定：關鍵理論和技術

李默涵++李建中

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

關鍵詞：數據質量； 數據時效性； 時效性判定

中圖分類號： TP391.41

文獻標志碼：A

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

0引言

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

一般說來，要從下述5個維度來保證數據可用性[11]。現作如下論述：

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

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

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

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

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

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

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

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

[BT4]1絕對時效性判定

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[BT5]1.3小結

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

[BT4]2相對時效性判定

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

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

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

[BT5]2.2小結

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

[BT4〗3結束語

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

[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]李建中， 劉顯敏. 大數據的一個重要方面： 數據可用性[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.