時態RDF數據的不一致性修復和預處理

張燕超

（南京航空航天大學計算機科學與技術學院，江蘇南京210000）

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

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

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

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

本文是針對添加有效時間標簽來擴展的時態RDF數據模型，根據有效時間的現實意義分析時態RDF數據存在的不一致性，并對每一類的不一致性提出了修復的方法，針對執行變化操作時產生的不一致性，進行了預處理的研究，以保護時態RDF數據的一致性，并通過實驗驗證了可行性。

1 時態RDF數據的不一致性修復

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

1.1 有效時間的設定

本文研究的時態RDF模型是用時間標簽來標記RDF數據三元組，且表示有效時間。以下就是時態RDF模型的基本定理。

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

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

定義 2 時間區間[start，end]中，start+1≤end，單位時間設為1；

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

1.2 三元組重復的不一致性修復

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

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

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

算法1 修復三元組重復的不一致性

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{//修改時間點，使時間連續

（9）R.end=start+1；

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

1.3 生命區間的不一致性修復

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

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

算法2 計算節點的生命區間

輸入：節點的URI（唯一性）

輸出：節點的生命區間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的生命區間就是存在生命區間的不一致性。

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

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

算法3 修復生命區間的的不一致性

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）//縮小記錄的時間區間，包含于節點的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 發散性屬性的不一致性修復

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

發散性屬性的不一致性修復，需要對具有發散性p屬性的記錄進行分類，按照s分為不同的記錄子集，重復的有效時間就縮小有效時間區間。需要修復所有節點的p屬性不一致性出邊。

算法4 修復發散性屬性的不一致性

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）//縮小時間區間，使得有效時間連續

（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 收斂性屬性的不一致性修復

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

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

算法5 修復收斂性屬性的不一致性

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）//縮小時間區間，使得有效時間連續

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

（14）if（T1 included T2）

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

（16）then deled R2；}

2 變化操作的不一致性預處理

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

2.1 插入操作

插入一條新的時態 RDF 數據 （s，p，o）[start，end]，考慮存在的不一致性類型，對不存在的s、p、o，在操作執行后還要建立新的URI，節點o和節點p的生命區間也要計算添加。

第一步：當s和o同時已經在時態數據庫中存在，需要對兩個節點的生命區間的交集作為生命區間lf進行生命區間的不一致性檢測和修復；只有一個節點存在，對這個節點的生命區間進行生命區間的不一致性檢測，執行操作，設置另一節點的生命區間為最終的有效時間；兩個節點都不存在，執行操作，創建兩個節點的URI，并設置兩個節點的生命區間為[start，end]。

圖1 生命區間和插入數據的有效時間關系

如圖1所示，實現表示生命區間，虛線是插入數據的有效時間[start，end]。情況 1：在[start，lf.start-1]和[lf，end+1，end]的兩段時間，節點不存在，存在生命區間的不一致性，修改插入數據的有效時間為[lf.start，lf.end]；2：[start，end]與 lf有間隔或連續，不一致性的時間為[start，end]，不執行插入操作；3：生命區間一致性；4：[lf.end+1，end]時間內，存在不一致性，修改插入數據的有效時間為相交的時間[start，lf.end]。

第二步，當p和s存在且p是發散性屬性，需要檢測修復s的p發散性屬性不一致性，如果插入操作執行，但是o不存在，o的生命區間為修改后的數據的有效時間。

圖2 發散性屬性出邊的有效時間關系

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

第三步，當p和o存在且p是發散性屬性，需要對o進行p屬性的收斂性屬性不一致性檢測和修復，如果插入操作執行，s不存在，s的生命區間為修改后數據的有效時間。

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

第四步，當spo都存在時，進行三元組重復的不一致性檢測與修復。

圖3 （s，p，o）所有的有效時間關系

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

分情況按照上述的步驟進行所有類型的不一致性檢測和修復，如果執行插入操作，就將spo中不存在的創建URI，并對節點添加生命區間。

2.2 刪除操作

刪除一條時態 RDF 數據（s，p，o）[start，end]，當spo中的一個或多個不存在時，就不執行刪除操作。

圖4 相同三元組的有效時間的關系

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

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

2.3 更新操作

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

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

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

3 實驗結果

本節是對上文中提出的時態RDF數據的不一致修復和變化操作的不一致性預處理進行了實驗驗證。在LUBM（Lehigh University Benchmark）標準數據集的基礎上隨機生成有效時間添加時間標簽，在對不同數量的數據集上分別進行了實驗，并進行對比和說明，實驗環境如表1所示。

表1 實驗環境

首先檢測500條時態RDF數據的不一致性，首次計算節點的生命區間。左邊就是存在不一致性數據，右邊是修改后的一致性數據。

圖5 時態RDF數據存在的不一致性

下圖是逐漸增加數據且修改后產生的不一致性的折線圖：

圖6 不同數量時態RDF數據存在的不一致

每增加1000條時態RDF數據，產生的每一種不一致性是在逐漸增加的。生命區間的不一致性產生的數量最多是因為節點的生命區間是由500條時態數據產生，后續的有效時間隨機產生，超過生命區間可能性很高。

對于變化操作的預處理實驗采用5000條一致性的時態RDF數據的數據集。

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

圖7 插入500條數據存在的不一致性

圖8是刪除300條數據造成不一致性的修復情況，有213條數據不能直接刪除，有176條數據不一致性修復后刪除，有37條數據找不到對應的記錄，不執行刪除操作。

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

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

4 結束語

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

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