張燕超

（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇南京210000）

資源描述框架 RDF（resource description framework）是由萬維網(wǎng)協(xié)會W3C提出的一個語義框架[1]，被廣泛應(yīng)用在描述語義網(wǎng)[2]中的各類海量數(shù)據(jù)，可以用三元組（主語、謂語、賓語）的形式來描述語義網(wǎng)上的任何數(shù)據(jù)。

隨著計算機技術(shù)和信息技術(shù)的深入發(fā)展，語義網(wǎng)中的時態(tài)RDF數(shù)據(jù)也在快速的累積中，RDF數(shù)據(jù)的涉及到各個領(lǐng)域。時態(tài)信息在信息系統(tǒng)中扮演著日益重要的角色，時態(tài)RDF數(shù)據(jù)的一致性檢測和恢復(fù)也有助于提高時態(tài)RDF數(shù)據(jù)庫系統(tǒng)的可靠性和高效性[3]，特別是對電子商務(wù)、數(shù)據(jù)挖掘、決策支持系統(tǒng)等信息系統(tǒng)有著越來越重要的意義和保障[4-6]。

國內(nèi)外學(xué)者提出了多種類型的時態(tài)數(shù)據(jù)庫模型，其中主要是基于關(guān)系模型的時態(tài)關(guān)系數(shù)據(jù)庫以及相應(yīng)的查詢語言[10]。除了關(guān)系模型，Chawathe首次提出了管理歷史的半結(jié)構(gòu)化數(shù)據(jù)[11]，他擴展了交換對象模型，使它可以表示更新，借助“增量（deltas）”來跟蹤它們。Claudio Gutierrez[12]首次提出了對于時態(tài)RDF數(shù)據(jù)模型的建立，添加時間標(biāo)簽來實現(xiàn)數(shù)據(jù)的時態(tài)性，如（s，p，o）：[T]，其中 T 就是時態(tài)信息。后續(xù)的時態(tài)RDF模型的研究都是在此時態(tài)RDF數(shù)據(jù)模型的基礎(chǔ)上進(jìn)行更多的語義和時間信息的表達(dá)上的擴展[13，14]，還有進(jìn)行雙時態(tài)擴展，同時支持有效時間和事務(wù)時間。還有更多的時態(tài)和語義的邏輯分析與推理，基本都停留在理論上的分析。

時態(tài)數(shù)據(jù)的一致性研究中文獻(xiàn)[7，8]是基于關(guān)系數(shù)據(jù)庫的多版本，文獻(xiàn)[7]需要追溯過去的版本中的所有的不一致性數(shù)據(jù)，操作復(fù)雜耗時。因為支持多時態(tài)多版本XML，恢復(fù)數(shù)據(jù)庫的一致性要通過糾正過去的所有錯誤和不一致性。文獻(xiàn)[8]對于時態(tài)RDF數(shù)據(jù)提出了新的框架，確定一個子類的一階一致性約束，利用調(diào)度理論有效的映射到約束圖來解決問題。這個方法優(yōu)于普通的近似啟發(fā)式算法，但是是對一個子類做出的約束，并不能更好的包含所有時態(tài)RDF圖，應(yīng)該一步推廣一致性約束。這篇文獻(xiàn)是針對于查詢中出現(xiàn)不確定性的結(jié)果進(jìn)一步做一致性檢測和恢復(fù)，存儲的數(shù)據(jù)還有不一致性和不正確性。文獻(xiàn)[9]提出了時態(tài)XML的一致性要求，并提出了環(huán)路檢測來檢測和修復(fù)不一致性，算法思路比較嚴(yán)謹(jǐn)。但是考慮數(shù)據(jù)不一致性不全面，分類太簡單，現(xiàn)實生活中的數(shù)據(jù)一定會更復(fù)雜。因為RDF的特殊性，并不適用于時態(tài)RDF數(shù)據(jù)的一致性分析。

本文是針對添加有效時間標(biāo)簽來擴展的時態(tài)RDF數(shù)據(jù)模型，根據(jù)有效時間的現(xiàn)實意義分析時態(tài)RDF數(shù)據(jù)存在的不一致性，并對每一類的不一致性提出了修復(fù)的方法，針對執(zhí)行變化操作時產(chǎn)生的不一致性，進(jìn)行了預(yù)處理的研究，以保護時態(tài)RDF數(shù)據(jù)的一致性，并通過實驗驗證了可行性。

1 時態(tài)RDF數(shù)據(jù)的不一致性修復(fù)

盡管現(xiàn)在從語義網(wǎng)上提取信息的技術(shù)有了很大的進(jìn)步，但是產(chǎn)生的RDF知識庫仍然存在大量的噪音和與事實不一致的問題，需要添加一些額外的一致性約束。本節(jié)就是根據(jù)擴展的有效時間的現(xiàn)實意義，分析時態(tài)RDF數(shù)據(jù)存在的不一致性，根據(jù)不同情況進(jìn)行了分類，并對存在的所有類型的不一致性提出修復(fù)算法。

1.1 有效時間的設(shè)定

本文研究的時態(tài)RDF模型是用時間標(biāo)簽來標(biāo)記RDF數(shù)據(jù)三元組，且表示有效時間。以下就是時態(tài)RDF模型的基本定理。

定義1一個時態(tài)RDF數(shù)據(jù)的組成分為兩部分，時間標(biāo)簽和 RDF 三元組，用符號表示（s，p，o）:[t].（s，p，o）：[t1，t2]表示{（s，p，o）：[t]|t1≤t≤t2}。

其中SPO代表RDF三元組中的主體、謂詞和客體。t是一個自然數(shù)，用來代表時間，表示在t時刻s的p屬性值為o是有效的。

定義 2 時間區(qū)間[start，end]中，start+1≤end，單位時間設(shè)為1；

為了表示時間上的連續(xù)，即使使用秒數(shù)作為單位時間在現(xiàn)實中時間也是不連續(xù)的，為了下文的使用方便和自然，將單位時間設(shè)為1，t和t+1兩個時刻就表示是時間上的連續(xù)。

1.2 三元組重復(fù)的不一致性修復(fù)

主體、屬性、客體都是相同的，即RDF三元組是一樣的，表示為（s，p，o）[T1]和（s，p，o）[T2]，其中T1和T2只要有重合的部分就是存在三元組重復(fù)不一致性。

對于T1和T2間斷，可以解釋為在T1和T2時間段內(nèi)s的p屬性值為o，但是在T1和T2間隔的時間內(nèi)這個信息失效了，所以不存在不一致性。

修復(fù)重復(fù)三元組不一致性，用R代表（s，p，o）[start，end]）是一條時態(tài)RDF數(shù)據(jù)記錄，Ri表示第i條記錄，Ri+1就是下一條記錄。首先在時態(tài)RDF數(shù)據(jù)庫中的記錄中匹配（s，p，o）三元組，找到三元組完全一樣的時態(tài)RDF數(shù)據(jù)記錄，通過比較兩個時間區(qū)間的起始時間點和結(jié)束時間點，計算出修改時間區(qū)間，對一條記錄的兩個時間點進(jìn)行修改，再刪除另外一條記錄。

算法1 修復(fù)三元組重復(fù)的不一致性

FixSameRDF（）{

（1）Group by SPO；

（2）Foreach R have same SPO

（3）gathe of T[start，end]

（4）If T have superposition；

（5）//時間完全重合，就刪除記錄

（6）Then{

（7）if R1.T incloded R2.T delete R2

（8）else{//修改時間點，使時間連續(xù)

（9）R.end=start+1；

（10）or R.start=end-1；}}}//T變連續(xù)

1.3 生命區(qū)間的不一致性修復(fù)

定義3（節(jié)點的生命區(qū)間lifespan）節(jié)點的生命區(qū)間是這個節(jié)點的所有入邊和出邊的有效時間的并集的最大集合。在只有（s，p，o）[start，end]一條數(shù)據(jù)的情況下，lf[start，end]就是節(jié)點s和節(jié)點o的生命區(qū)間。

計算節(jié)點的生命區(qū)間要包含節(jié)點的所有出邊和入邊的有效時間。通過遍歷并計算所有邊的有效時間的并集的最大集合，也就是找到最早的開始點和最晚的結(jié)束點。

算法2 計算節(jié)點的生命區(qū)間

輸入：節(jié)點的URI（唯一性）

輸出：節(jié)點的生命區(qū)間lf[start，end]

Lifespan（URI）{

（1）Initialize lf[start，end]lf.atart=null，lf.end=null；

（2）for each（s，p，o）[start，end]{

（3）if（URI==s||URI==o）{

（4）if（lf.start==null）lf[start，end]；

（5）//lf取范圍大的時間點

（6）Else{lf.start=MIN（lf.start，start）；

（7）lf.end=MAX（lf.end，end）；}}

（8）Return lf；}

記錄的有效時間T超過S和O的生命區(qū)間就是存在生命區(qū)間的不一致性。

只有s和o有效存在，s的p屬性值為o的信息才會有意義，否則就是與事實不一致。

對于生命區(qū)間的不一致性修復(fù)，需要修復(fù)所有不一致性出入邊的有效時間，首先在記錄中匹配s，找到節(jié)點所有相關(guān)記錄，再通過比較兩個時間區(qū)間的起始時間點和結(jié)束時間點，計算出保持一致性的有效時間區(qū)間，對邊的記錄的兩個時間點進(jìn)行修改，或直接刪除這條出邊信息的記錄。

算法3 修復(fù)生命區(qū)間的的不一致性

FixLifespan（）{

（1）For each node（URI）n do

（2）lf=lifespan（URI）；

（3）group by R.O gathe of T[start，end]

（4）foreach T

（5）if（lf and T have superposition）

（6）//縮小記錄的時間區(qū)間，包含于節(jié)點的lf

（7）then{R.start=lf，start||R.end=lf.end}

（8）if（lf and T have no superposition）

（9）//沒有重合就刪除記錄

（10）then deled R；}

1.4 發(fā)散性屬性的不一致性修復(fù)

主體和屬性相同，不同或相同的客體，表示為（s，p，o1）[T1]和（s，p，o2）[T2]，其中 T1 和 T2 有效時間有重疊就存在發(fā)散性屬性不一致。例如一個人的體重屬性在同一時刻的體重值就是唯一的。

發(fā)散性屬性的不一致性修復(fù)，需要對具有發(fā)散性p屬性的記錄進(jìn)行分類，按照s分為不同的記錄子集，重復(fù)的有效時間就縮小有效時間區(qū)間。需要修復(fù)所有節(jié)點的p屬性不一致性出邊。

算法4 修復(fù)發(fā)散性屬性的不一致性

CheckDivergent（p）{

（1）collection of R.p=p，{R.s}is grouped by different R.s

（2）foreach{R.s}gathe of T[start，end]

（3）if（T1 and T2 have superposition）

（4）//縮小時間區(qū)間，使得有效時間連續(xù)

（5）then {R2.start =R2.end -1 or R1.end=R2.start-1}

（6）if（T1 included T2）

（7）//完全重合就刪除記錄

（8）then deled R2；}

1.5 收斂性屬性的不一致性修復(fù)

主體不同或相同，但是屬性和客體相同，表示為（s1，p，o）[T1]和（s2，p，o）[T2]，其中 T1 和 T2 有效時間有重疊就是存在收斂性屬性不一致。例如手術(shù)室O1在同一時刻只能有一個病人在做手術(shù)。

收斂性屬性的不一致性修復(fù)，將包含p屬性的記錄按照O分為不同的記錄子集，重復(fù)的有效時間就縮小有效時間區(qū)間。

算法5 修復(fù)收斂性屬性的不一致性

CheckDivergent（p）{

（9）collection of R.p=p，{R.o}is grouped by different R.o

（10）foreach{R.o}gathe of T[start，end]

（11）if（T1 and T2 have superposition）

（12）//縮小時間區(qū)間，使得有效時間連續(xù)

（13）then{R2.start=R2.end-1 or R1.end=R2.start-1}

（14）if（T1 included T2）

（15）//完全重合就刪除記錄

（16）then deled R2；}

2 變化操作的不一致性預(yù)處理

對于時態(tài)RDF數(shù)據(jù)的添加、修改和刪除都可能會造成上文中提出的不一致性問題，因此需要對插入操作、刪除操作和更新操作的時態(tài)RDF數(shù)據(jù)首先進(jìn)行檢測與分析，是否會造成4種類型的不一致性，如果存在不一致性問題就要通過修改新的時態(tài)RDF數(shù)據(jù)來進(jìn)行修復(fù)，使得操作后的數(shù)據(jù)庫中的時態(tài)RDF始終保持一致性。

2.1 插入操作

插入一條新的時態(tài) RDF 數(shù)據(jù) （s，p，o）[start，end]，考慮存在的不一致性類型，對不存在的s、p、o，在操作執(zhí)行后還要建立新的URI，節(jié)點o和節(jié)點p的生命區(qū)間也要計算添加。

第一步：當(dāng)s和o同時已經(jīng)在時態(tài)數(shù)據(jù)庫中存在，需要對兩個節(jié)點的生命區(qū)間的交集作為生命區(qū)間lf進(jìn)行生命區(qū)間的不一致性檢測和修復(fù)；只有一個節(jié)點存在，對這個節(jié)點的生命區(qū)間進(jìn)行生命區(qū)間的不一致性檢測，執(zhí)行操作，設(shè)置另一節(jié)點的生命區(qū)間為最終的有效時間；兩個節(jié)點都不存在，執(zhí)行操作，創(chuàng)建兩個節(jié)點的URI，并設(shè)置兩個節(jié)點的生命區(qū)間為[start，end]。

圖1 生命區(qū)間和插入數(shù)據(jù)的有效時間關(guān)系

如圖1所示，實現(xiàn)表示生命區(qū)間，虛線是插入數(shù)據(jù)的有效時間[start，end]。情況 1：在[start，lf.start-1]和[lf，end+1，end]的兩段時間，節(jié)點不存在，存在生命區(qū)間的不一致性，修改插入數(shù)據(jù)的有效時間為[lf.start，lf.end]；2：[start，end]與 lf有間隔或連續(xù)，不一致性的時間為[start，end]，不執(zhí)行插入操作；3：生命區(qū)間一致性；4：[lf.end+1，end]時間內(nèi)，存在不一致性，修改插入數(shù)據(jù)的有效時間為相交的時間[start，lf.end]。

第二步，當(dāng)p和s存在且p是發(fā)散性屬性，需要檢測修復(fù)s的p發(fā)散性屬性不一致性，如果插入操作執(zhí)行，但是o不存在，o的生命區(qū)間為修改后的數(shù)據(jù)的有效時間。

圖2 發(fā)散性屬性出邊的有效時間關(guān)系

如圖2實線為s的p屬性的有效時間，虛線是要插入數(shù)據(jù)的有效時間。情況1：在[start，t2]和[t3，end]有兩個p屬性值，存在發(fā)散性屬性的不一致性，但[t2+1，t3+1]有間隔，將插入的數(shù)據(jù)的有效時間修改為[t2+1，t3+1]；2：p 屬性一致性；3：在[start，end]內(nèi)s有兩個p屬性值，存在不一致性，不執(zhí)行插入操作。

第三步，當(dāng)p和o存在且p是發(fā)散性屬性，需要對o進(jìn)行p屬性的收斂性屬性不一致性檢測和修復(fù)，如果插入操作執(zhí)行，s不存在，s的生命區(qū)間為修改后數(shù)據(jù)的有效時間。

找到p屬性值是o的所有記錄的有效時間，與圖2的情況相同，情況1：存在收斂性屬性不一致性，將插入的數(shù)據(jù)的有效時間修改為[t2+1，t3+1]；2：p 屬性一致性；3：[start，end]內(nèi)都存在 p 屬性的不一致性，不執(zhí)行插入操作。

第四步，當(dāng)spo都存在時，進(jìn)行三元組重復(fù)的不一致性檢測與修復(fù)。

圖3 （s，p，o）所有的有效時間關(guān)系

如圖3 所示，實線是（s，p，o）的所有有效時間，虛線是插入的有效時間。情況1：時間的重疊存在三元組重復(fù)的不一致性，修改插入數(shù)據(jù)有效時間為[t1，t4]，并刪除記錄（s，p，o）[t1，t2]和（s，p，o）[t3，t4]；2：不存在三元組重復(fù)的不一致性；3：不一致性時間區(qū)間為[start，end]，不執(zhí)行插入操作；4：[start，end]包含[t7，t8]，只需刪除記錄（s，p，o）[t7，t8]。

分情況按照上述的步驟進(jìn)行所有類型的不一致性檢測和修復(fù)，如果執(zhí)行插入操作，就將spo中不存在的創(chuàng)建URI，并對節(jié)點添加生命區(qū)間。

2.2 刪除操作

刪除一條時態(tài) RDF 數(shù)據(jù)（s，p，o）[start，end]，當(dāng)spo中的一個或多個不存在時，就不執(zhí)行刪除操作。

圖4 相同三元組的有效時間的關(guān)系

如圖4 所示，實線是（s，p，o）的所有有效時間，虛線是要刪除數(shù)據(jù)的有效時間。情況1：[start，end]包含[t1，t2]，或者相等，直接刪除（s，p，o）[t1，t2]記錄；2：（s，p，o）在[t1，start-1]的時間內(nèi)有效，修改記錄（s，p，o）有效時間為[t1，start-1]；3：（s，p，o）在[start，end]的時間內(nèi)無效，刪除操作不用執(zhí)行；4：（s，p，o）在[t3，start-1]和[end+1，t4]時間內(nèi)是有效的，修改記錄（s，p，o）有效時間為[t3，start-1]，再插入一條記錄（s，p，o）[end+1，t4]。

（s，p，o）的有效時間的縮小并不會造成任何的不一致性，要對相應(yīng)的記錄做修改，而不是直接匹配一模一樣的數(shù)據(jù)記錄進(jìn)行刪除。

2.3 更新操作

更新操作可以分為兩部分，首先是刪除原有的數(shù)據(jù)，再插入新的數(shù)據(jù)。

更 新（s，p，o）[start，end]為（s’，p’，o’）[start’，end’]。首先找到（s，p，o）[start，end]所對應(yīng)的記錄。情況與圖4 一樣，情況 1：[start，end]包含[t1，t2]，或者相等，最后要刪除的記錄就是（s，p，o）[t1，t2]；2：修改記錄（s，p，o）[t1，t2]為[t1，start-1]；3：不執(zhí)行更新操作；4：修改記錄（s，p，o）[t3，t4]為[t3，start-1]，再插入一條記錄（s，p，o）[end+1，t4]。

找到相應(yīng)的記錄后，插入（s’，p’，o’）[start’，end’]，對這條新時態(tài)RDF數(shù)據(jù)也要進(jìn)行4種類型的不一致性的分析，如果不執(zhí)行插入操作，說明存在不一致性，不執(zhí)行更新操作，在之前找到相應(yīng)記錄的分析作廢，也就不用修改記錄了。

3 實驗結(jié)果

本節(jié)是對上文中提出的時態(tài)RDF數(shù)據(jù)的不一致修復(fù)和變化操作的不一致性預(yù)處理進(jìn)行了實驗驗證。在LUBM（Lehigh University Benchmark）標(biāo)準(zhǔn)數(shù)據(jù)集的基礎(chǔ)上隨機生成有效時間添加時間標(biāo)簽，在對不同數(shù)量的數(shù)據(jù)集上分別進(jìn)行了實驗，并進(jìn)行對比和說明，實驗環(huán)境如表1所示。

表1 實驗環(huán)境

首先檢測500條時態(tài)RDF數(shù)據(jù)的不一致性，首次計算節(jié)點的生命區(qū)間。左邊就是存在不一致性數(shù)據(jù)，右邊是修改后的一致性數(shù)據(jù)。

圖5 時態(tài)RDF數(shù)據(jù)存在的不一致性

下圖是逐漸增加數(shù)據(jù)且修改后產(chǎn)生的不一致性的折線圖：

圖6 不同數(shù)量時態(tài)RDF數(shù)據(jù)存在的不一致

每增加1000條時態(tài)RDF數(shù)據(jù)，產(chǎn)生的每一種不一致性是在逐漸增加的。生命區(qū)間的不一致性產(chǎn)生的數(shù)量最多是因為節(jié)點的生命區(qū)間是由500條時態(tài)數(shù)據(jù)產(chǎn)生，后續(xù)的有效時間隨機產(chǎn)生，超過生命區(qū)間可能性很高。

對于變化操作的預(yù)處理實驗采用5000條一致性的時態(tài)RDF數(shù)據(jù)的數(shù)據(jù)集。

圖7是插入的500條數(shù)據(jù)中存在的不一致性分布情況，白色的柱狀圖表示可以修復(fù)的不一致性，插入修改后數(shù)據(jù)；黑色的柱狀圖是無法修復(fù)的不一致性，只能放棄執(zhí)行插入。

圖7 插入500條數(shù)據(jù)存在的不一致性

圖8是刪除300條數(shù)據(jù)造成不一致性的修復(fù)情況，有213條數(shù)據(jù)不能直接刪除，有176條數(shù)據(jù)不一致性修復(fù)后刪除，有37條數(shù)據(jù)找不到對應(yīng)的記錄，不執(zhí)行刪除操作。

圖9是更新150條數(shù)據(jù)存在不一致性的情況，沒有對應(yīng)刪除的數(shù)據(jù)有26條，不更新，有125條更新后的數(shù)據(jù)存在不一致性，白色的柱狀圖表示有90條數(shù)據(jù)修復(fù)后更新，35條數(shù)據(jù)不執(zhí)行插入操作。

圖9 更新操作的不一致性情況

4 結(jié)束語

針對支持有效時間的時態(tài)RDF數(shù)據(jù)進(jìn)行了在有效時間上的不一致性研究和分析，分別是三元組重復(fù)的不一致性、生命區(qū)間的不一致性、發(fā)散性和收斂性屬性的不一致性，并對4種類型的不一致進(jìn)行了修復(fù)，對于更新的時態(tài)RDF數(shù)據(jù)，針對每種變化操作，即插入、刪除和更新，分析了每種操作的不一致性預(yù)處理方法。

未來工作：1.時態(tài)RDF數(shù)據(jù)會時常更新，修復(fù)不一致性消耗太大，修性算法的效率還有待提高。2.對于支持有效時間的時態(tài)RDF數(shù)據(jù)之間的推理、蘊含等內(nèi)置函數(shù)和數(shù)據(jù)間關(guān)系和結(jié)構(gòu)都沒有討論和研究。3.對有效時間的確定與驗證沒有進(jìn)行討論，對于不確定時間的處理也需要另行研究。