支持有效時間的時態RDF數據的不一致性分析

張燕超

摘 要：資源描述框架（RDF）是一個元數據模型，是由W3C建立的基礎設施，使得Web上的數據機器可讀。近年來，語義網的快速發展和RDF的普遍應用，產生了大量的含有時態信息的RDF數據，并涉及到各個方面領域的關鍵數據。時態RDF數據的一致性能提高時態RDF數據的準確性，時態數據的一致性檢測和恢復也有助于提高數據庫系統的可靠性和高效性，對于時態信息處理也能提供可靠的保證，也能提高時態信息處理的效率。研究了對傳統RDF引入時間信息的建模方式，通過添加有效時間的時間標簽的方式構建了支持有效時間的時態RDF模型，在此基礎上對時態RDF數據存在的不一致性情況進行了分析和研究，并提出了相關的檢測和修復的算法。

關鍵詞：時態數據模型；有效時間；時態數據的不一致性

中圖分類號：TP311 文獻標識碼：A

Abstract： The resource description framework （RDF） is a metadata model，the infrastructure established by the W3C，which makes the data machines on Web readable.In recent years，the rapid development of semantic web and the widespread application of RDF have produced a lot of RDF data containing temporal information and related key data in various fields.Consistent performance of temporal RDF data to improve the accuracy of temporal RDF data，temporal data consistency detection and recovery also helps to improve the reliability and efficiency of the database system，the temporal information processing can also provide a reliable guarantee，also can improve the efficiency of temporal information processing.This paper presents a modeling way of introducing the time information of traditional RDF，temporal RDF models support valid time through constructing the time tag time effective way，inconsistency on the basis of temporal RDF data are analyzed and studied，and put forward the related detection and repair algorithm.

Key words：temporal data model；effective time；inconsistency of temporal data

1 引 言

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

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

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

對傳統的RDF三元組進行了時態擴充，通過增加有效時間的時間標簽來進行建模，針對有效時間的現實意義提出了時態RDF數據存在的不一致性，并對每一類的不一致性提出了檢測和修復的方法，并通過實驗驗證了算法的實施性。

2 時態RDF模型

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

2.1 有效時間標簽

對RDF數據引入時間信息，要對RDF模型進行時態信息的擴展，就要考慮一下幾個方面的問題，再選擇其中比較合適和符合實際應用條件的模式。

1.版本化和時間標簽化：版本化就是當RDF數據有更改時，通過快照的方式保存更改前后的RDF數據庫狀態。加入時間的方法很簡便，但是會造成數據冗余，產生大量的重復的RDF數據信息，存儲空間的開銷也會增大，對于跨版本的查詢操作復雜需要查詢多個RDF數據表中的數據消耗時間。時間標簽化就是直接對RDF三元組添加時間戳，對于每一個改變的三元組加上時間標簽，保留了RDF中分布式和可擴展性的特點，添加了時間信息，只是數據的結構比版本化的復雜。帶時間標簽的RDF數據模型只要增加和修改更改的數據，增長方式會遠小于版本化的時態RDF模型，可以消除大部分的時態RDF數據冗余。

2.事務時間和有效時間：事務時間是捕捉并保存每次操作前后的RDF數據的變化，對于在過去時間段存儲的RDF數據只能方便查詢。有效時間是用來模擬現實世界中RDF數據存在的狀態，對于RDF數據的每個時間階段的狀態可以保存也可以進行任意的修改，發現過去一段時間的RDF數據有錯誤可以直接更改數據的有效時間。兩者以不同的方式來展現RDF數據的動態性，保存的都是有更新的數據，數據冗余度會大大降低，存儲需要的空間也會緩慢增長。

綜上所述可以通過添加時間標簽來擴展時態信息，來建立時態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是有效的。

添加有效時間區間的時間標簽來進行時間信息的擴充，模擬現實世界中RDF數據每個時間段的存在狀態，保留了數據的動態性，也簡化了時態RDF數據結構。

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

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

3 時態RDF的不一致性

盡管現在從語義網上提取信息的技術有了很大的進步，例如DBpedia、Freebase、YAGO等都是采用自動化提取技術，但是產生的RDF知識庫仍然面臨著存在大量的噪音和與事實不一致的問題，這些不一致性的數據一般用不確定的數據來概括，需要添加一些額外的一致性約束。本節就是針對添加了有效時間標簽的RDF數據模型，根據有效時間的現實意義，分析時態RDF數據存在的不一致性，并對存在的所有類型的不一致性進行檢測與修復。

3.1 生命區間的定義

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

s節點的p屬性值為O在[start，end]時間都有效，證明s節點和o節點是存在的，因此，計算節點的生命區間要包含節點的所有出邊和所有入邊的有效時間。

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

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

計算生命區間時輸入節點node，通過遍歷這個節點的所有的出邊入邊，計算所有邊的有效時間的并集的最大集合，也就是找到最早的開始點和最晚的結束點。算法的復雜度是O（n），n是存儲的時態RDF數據記錄的條數，要計算時態RDF數據中所有節點的生命區間，則是節點數*n。

3.2 三元組重復的不一致性

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

有效時間區間是唯一確定的，如果有重疊其中一個有效時間區間一定是與事實不符存在不一致性的。對于T1和T2的關系是間斷的，可以解釋為在T1和T2這兩個時間段內s的p屬性值為o，但是在T1和T2間隔的時間內這個信息失效了，所以不存在不一致性。

檢測存在數據庫中的時態RDF數據是否存在上述的不一致性，每一條時態RDF記錄進行逐一匹配，發現有相同的時態RDF三元組且時間上并不是有間隔的就說明存在不一致性。用R代表（s，p，o）[start，end]）是一條時態RDF數據記錄，Ri表示第i條記錄，Ri+1就是下一條記錄。

算法2 檢測時態RDF數據是否存在三元組重復的不一致性

修復重復三元組不一致性，首先在時態RDF數據庫中的記錄中匹配（s，p，o）三元組，找到三元組完全一樣的時態RDF數據記錄，再通過比較兩個時間區間的起始時間點R1.start、R2.start和結束時間點R1.end、R2.end，計算出要修改的時間區間，對一條記錄的兩個時間點進行修改，再刪除另外一條記錄。

3.3 生命區間的不一致性

父節點s和子節點o連接的邊e，但是這條邊是有效時間Te超過了父節點的生命區間lf（s）就是存在不一致性。

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

檢測時態RDF數據是否存在生命區間的不一致性，要對每一個節點都要進行檢測，對比節點的所有邊的有效時間和節點的生命區間，有一個邊的有效時間超過了節點的生命區間，這個節點就存在生命區間的不一致性，時態RDF數據就存在生命區間的不一致性。只有所有節點都不存在不一致性，時態RDF數據才不存在生命區間的不一致性。

4 實驗結果

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

LUBM是關于1000所高校的RDF數據，為了得到時態RDF數據，為每個RDF三元組隨機生成整數來表示有效時間標簽，分別對不同數量的數據進行不一致性檢測和修復。

時態RDF數據存儲在phpmysql的test數據庫中，以共建立了三張表，其中URI表將所有的RDF三元中的s、p、o的URI用節點名ID表示。TRDF表中osp表示的是RDF三元組的主體、屬性和客體。Start和end是有效時間的兩個時間端點，隨機生成時，要求end>start即可。Attribute and lifespan表中ID就是代表RDF三元組中的spo的URI對應的節點ID。生命區間是要計算的，初始化都為0。

首先檢測500條時態RDF數據的不一致性，節點內容包括節點的ID和節點的生命區間lf.start和lf.end。首次計算節點的生命區間，集合節點的所有入邊和出邊的有效時間。在500條記錄的基礎上添加新的紀錄就會產生不一致性。如圖1所示增加500條后出現的不一致性條數，修改后就不會存在不一致性的數據。

每增加1 000條時態RDF數據，產生的每一種不一致性是在逐漸增加的，因此數據量很大時，對于存在的不一致性數據需要進行修復。生命區間的不一致性產生的數量最多也是因為一開始計算節點的生命區間只有500條時態數據，對于后續添加的有效時間又是隨機產生，超過節點的生命區間的可能性也就很高了。

5 總 結

針對RDF三元組添加有效時間的時間標簽來表示的時態RDF數據，并進行了在有效時間上的不一致性研究和分析，提出了兩種類型的不一致性，分別是三元組重復的不一致性和生命區間的不一致性，對于兩種類型的不一致性分別進行檢測和修復。

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

參考文獻

[1] SWICK R R.Resource description framework（RDF）model and syntax specification W3C recommendation[M].[S1]：W3C Recommendation World Wide Web Consortium，2009.

[2] BERNERS-LEE T，HENDLER J，LASSILA O.The semantic Web.Scientific American，2001，284（5）：34—43

[3] HURTADO C，VAISMAN A.Reasoning with Temporal Constraints in RDF.In PPSWR Workshop，164—178，2006，4187：164-178.

[4] 湯庸.時態數據庫導論[M].北京：北京大學出版社，2004

[5] 陳秀萬，吳歡，李小娟，等.基于事件的土地利用時空數據模型研究[J].中國圖象圖形學報，2003：8（8）：957—963

[6] 辜煒東，湯庸，王路幫，等.事務數據庫中的時態信息挖掘[J].計算機工程與應用，2004：40（18）：174—177

[7] BOHLEN M H，JENSEN C S，SNODGRASS R T.Evaluating and Enhancing the Completeness of TSQL2[R].TR 95-5.Computer Science Department，University of Arizona.

[8] DYLLA M，SOZIO M，THEOBALD M：Resolving Temporal Conflicts in Inconsistent RDF Knowledge Bases，2011.

[9] RIZZOLO F，VAISMAN A A.Temporal XML：modeling，indexing，and query processing [J].VLDB Journal，2008，17（5）：1179—1212.

[10] TANSEL A，CLIFFORD J，GADIA EDS S.Temporal Databases：Theory，Design and Implementation，Benjamin/Cummings，1993.

[11] CHAWATHE S，ABITEBOUL S，WIDOM J. Managing historical semistructured data[J]. Theory and Practice of Object Systems，1999，5（3）：143—162.

[12] Hurtado L C，Gutiérrez C，Vaisman A.Temporal RDF [J].2014.

[13] PUGLIESE A，UDREA O，SUBRAHMANIAN V S.Scaling RDF with time [C]// Proc of the 17th international conference on World Wide Web.2008：605—614.

[14] UDREA O，RECUPERO D R，SUBRAHMANIAN V S.Annotated RDF [J].ACM Trans on Computational Logic，2010，11（2）：10.