數(shù)據(jù)時效性的理論和算法研究.pdf

1、隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)的可用性受到廣泛的關(guān)注。真實世界會隨著時間的流逝迅速變化，進而導(dǎo)致數(shù)據(jù)庫中的數(shù)據(jù)過時失效。當前已有統(tǒng)計表明過時數(shù)據(jù)會對企業(yè)決策和國民生活造成眾多不良影響，且會引起其他維度的可用性下降，如引起數(shù)據(jù)不一致、不精確、不完整等，因此確保數(shù)據(jù)的時效性至關(guān)重要。當前數(shù)據(jù)可用性領(lǐng)域?qū)τ跁r效性的研究仍然不成體系，數(shù)據(jù)時效性研究面臨極大挑戰(zhàn)。首先，很多數(shù)據(jù)庫中都沒有精確可用的時間戳，這使得數(shù)據(jù)集合在給定時刻的時效性，即絕對時效性

2、，很難判定。其次，不同的查詢或應(yīng)用場景對時效性有不同的要求，在一些情境下絕對時效性可能無法判定，這使得數(shù)據(jù)相對于查詢或者用戶的時效性判定尤為重要。第三，在得到數(shù)據(jù)庫的時效性判定結(jié)果之后，必須進一步給出數(shù)據(jù)時效性的修復(fù)方法，當前數(shù)據(jù)可用性領(lǐng)域的研究并沒有給出可以直接用于修復(fù)時效性的數(shù)據(jù)修復(fù)方法。第四，在僅有一個數(shù)據(jù)源的情況下，完全地修復(fù)一個數(shù)據(jù)庫是非常困難，甚至不可行的。因為不同數(shù)據(jù)源包含的數(shù)據(jù)不同，所以往往要需要根據(jù)現(xiàn)有知識，將來自其他

3、數(shù)據(jù)源的數(shù)據(jù)和目標數(shù)據(jù)源的最新值整合起來才能得到完整的目標數(shù)據(jù)表最新值。為了有效地應(yīng)對上述挑戰(zhàn)，本文嘗試給出一系列理論和算法，解決了數(shù)據(jù)時效性的一些關(guān)鍵問題，主要研究內(nèi)容可以概括如下。
　　(1)本文研究了數(shù)據(jù)絕對時效性的表達原理及判定算法。為了克服當前基于時間戳和基于規(guī)則的兩類時效性判定方法的局限性，形式化地定義了不確定時效規(guī)則及相應(yīng)的數(shù)據(jù)時效性模型。該規(guī)則和模型可以表達不確定的領(lǐng)域知識，定量地判定數(shù)據(jù)時效性，且能夠判定數(shù)據(jù)在特

4、定時刻是否過時。在此基礎(chǔ)上，本文首先研究了不確定時效規(guī)則的基礎(chǔ)問題，如公理化、可滿足、蘊含等問題；然后給出了定量地判定數(shù)據(jù)時效性的模型，分別定義了數(shù)據(jù)項、元組、數(shù)據(jù)集合的時效性；接著，將數(shù)據(jù)項間的時序關(guān)系構(gòu)建成時序圖，并基于時序圖給出了多項式時間的時效性判定算法；最后在真實數(shù)據(jù)上的實驗驗證了算法的有效性。
　　(2)本文研究了數(shù)據(jù)相對時效性表達原理及判定算法。在數(shù)據(jù)的絕對時效性無法判定，或判定結(jié)果不能有效地表達用戶需求的情況下，可

5、以利用一些冗余記錄和時效約規(guī)則來實現(xiàn)數(shù)據(jù)相對時效性的判定。本文借助冗余記錄和時效規(guī)則研究數(shù)據(jù)相對時效性判定問題，建立了相對時效性的判定模型并提出了相關(guān)求解算法。本文首先定義了查詢相關(guān)時效性，將查詢歸結(jié)為最新值查詢和時效序列查詢兩類，對每類查詢，設(shè)計了查詢結(jié)果的時效性判定方法，并將每類查詢作為一個整體，給出了數(shù)據(jù)集合相對于一類查詢的平均時效性判定方法；然后，將用戶按查詢偏好分為3類，研究了用戶相關(guān)時效性；最后在真實數(shù)據(jù)和虛擬數(shù)據(jù)上分別進行

6、了實驗，驗證了算法的有效性，分析了各參數(shù)對算法的影響。
　　(3)本文研究了基于規(guī)則的數(shù)據(jù)時效性錯誤修復(fù)模型及修復(fù)算法。將數(shù)據(jù)庫中的過時數(shù)據(jù)修復(fù)為最新值是提高數(shù)據(jù)質(zhì)量的關(guān)鍵步驟。當前主要有基于規(guī)則和基于統(tǒng)計兩類數(shù)據(jù)修復(fù)方法：基于規(guī)則的修復(fù)方法難以表達數(shù)據(jù)中某些復(fù)雜的關(guān)聯(lián)關(guān)系，而基于統(tǒng)計的方法需要學習較復(fù)雜的條件概率分布，且難以直接應(yīng)用數(shù)據(jù)語義相關(guān)的領(lǐng)域知識。為了克服上述兩類方法的缺點，本文提出一類新的修復(fù)規(guī)則，將規(guī)則和統(tǒng)計的方法結(jié)

7、合起來修復(fù)過時數(shù)據(jù)，該規(guī)則一方面能夠通過規(guī)則模式表達領(lǐng)域知識，另一方面還能夠使用其特有的分布表來描述數(shù)據(jù)隨時間變化的統(tǒng)計信息。首先，本文研究了靜態(tài)數(shù)據(jù)上的最小規(guī)則模式生成問題，證明了靜態(tài)數(shù)據(jù)上的規(guī)則模式生成問題是NP-難的，并給出了兩個解決該問題的多項式時間近似算法。接著，本文研究了動態(tài)數(shù)據(jù)上的最小規(guī)則模式生成問題，給出算法可在數(shù)據(jù)動態(tài)變化的情況下迅速更新現(xiàn)有的規(guī)則模式集合，最好情況下，只需O(1)時間即可完成更新。同時，本文還給出了靜

8、態(tài)數(shù)據(jù)上的分布表學習算法和數(shù)據(jù)動態(tài)變化情況下的分布表更新算法。然后，本文研究了不同修復(fù)代價約束條件下的最優(yōu)修復(fù)計劃產(chǎn)生問題，證明了在修復(fù)預(yù)算為正無窮時，該問題在多項式時間內(nèi)可解，否則該問題是NP-難的，并給出了上述兩種情況下該問題的解決方法。最后本文通過真實和虛擬數(shù)據(jù)集合上的實驗證明了上述方法的有效性。
　　(4)本文研究了基于查詢的數(shù)據(jù)時效性錯誤修復(fù)問題。在數(shù)據(jù)集成或Web環(huán)境下，許多數(shù)據(jù)表被分散地存儲在不同地方，這些數(shù)據(jù)表之間

9、往往存在著部分數(shù)據(jù)重疊的情況，但不同數(shù)據(jù)源的更新頻率不盡相同。如果我們向某數(shù)據(jù)源請求一個數(shù)據(jù)表或發(fā)出一個查詢，往往會因為數(shù)據(jù)源更新不及時而無法得到目標數(shù)據(jù)表的最新數(shù)據(jù)。為了將目標數(shù)據(jù)表修復(fù)為最新值，需根據(jù)數(shù)據(jù)庫中的時序約束和參照完整性約束構(gòu)造一個合取查詢，使得該查詢的結(jié)果恰由目標數(shù)據(jù)表對應(yīng)的最新值構(gòu)成，稱為時效保持查詢。本文研究在給定數(shù)據(jù)庫時序關(guān)系和參照完整性約束的情況下時效保持查詢構(gòu)造問題。首先，本文給出了時效保持查詢的形式化定義，使