張燕超

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

關(guān)鍵詞：時態(tài)數(shù)據(jù)模型；有效時間；時態(tài)數(shù)據(jù)的不一致性

中圖分類號：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）是由萬維網(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)域，而這些RDF數(shù)據(jù)常常帶有時間信息。時態(tài)信息在信息系統(tǒng)中扮演著日益重要的角色，因此，對于RDF數(shù)據(jù)進行時態(tài)數(shù)據(jù)建模具有重要意義，時態(tài)RDF數(shù)據(jù)的一致性檢測和恢復(fù)也有助于提高時態(tài)RDF數(shù)據(jù)庫系統(tǒng)的可靠性和高效性[3]，特別是對電子商務(wù)、數(shù)據(jù)挖掘、決策支持系統(tǒng)等信息系統(tǒng)有著越來越重要的意義和保障[4-6]。

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

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

2 時態(tài)RDF模型

國內(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ù)模型的建立，時間RDF三元組的基礎(chǔ)上添加時間標簽來實現(xiàn)數(shù)據(jù)的時態(tài)性，如（s，p，o）：[T]，其中T就是時態(tài)信息。后續(xù)的時態(tài)RDF模型的研究都是在此時態(tài)RDF數(shù)據(jù)模型的基礎(chǔ)上進行更多的語義和時間信息的表達上的擴展[13，14]，例如時態(tài)信息[T]更新為[n：T]，表示在T時間內(nèi)這個時態(tài)RDF三元組真存在n次，還有進行雙時態(tài)擴展，同時支持有效時間和事務(wù)時間。還有更多的時態(tài)和語義的邏輯分析與推理，基本都停留在理論上的分析。

2.1 有效時間標簽

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

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

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

綜上所述可以通過添加時間標簽來擴展時態(tài)信息，來建立時態(tài)RDF模型，用時間標簽來標記RDF數(shù)據(jù)三元組，且表示有效時間。以下就是時態(tài)RDF模型的基本定理：

定義1.一個時態(tài)RDF數(shù)據(jù)的組成分為兩部分，時間標簽和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是有效的。

添加有效時間區(qū)間的時間標簽來進行時間信息的擴充，模擬現(xiàn)實世界中RDF數(shù)據(jù)每個時間段的存在狀態(tài)，保留了數(shù)據(jù)的動態(tài)性，也簡化了時態(tài)RDF數(shù)據(jù)結(jié)構(gòu)。

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

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

3 時態(tài)RDF的不一致性

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

3.1 生命區(qū)間的定義

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

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

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

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

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

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

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

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

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

算法2 檢測時態(tài)RDF數(shù)據(jù)是否存在三元組重復(fù)的不一致性

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

3.3 生命區(qū)間的不一致性

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

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

檢測時態(tài)RDF數(shù)據(jù)是否存在生命區(qū)間的不一致性，要對每一個節(jié)點都要進行檢測，對比節(jié)點的所有邊的有效時間和節(jié)點的生命區(qū)間，有一個邊的有效時間超過了節(jié)點的生命區(qū)間，這個節(jié)點就存在生命區(qū)間的不一致性，時態(tài)RDF數(shù)據(jù)就存在生命區(qū)間的不一致性。只有所有節(jié)點都不存在不一致性，時態(tài)RDF數(shù)據(jù)才不存在生命區(qū)間的不一致性。

4 實驗結(jié)果

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

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

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

首先檢測500條時態(tài)RDF數(shù)據(jù)的不一致性，節(jié)點內(nèi)容包括節(jié)點的ID和節(jié)點的生命區(qū)間lf.start和lf.end。首次計算節(jié)點的生命區(qū)間，集合節(jié)點的所有入邊和出邊的有效時間。在500條記錄的基礎(chǔ)上添加新的紀錄就會產(chǎn)生不一致性。如圖1所示增加500條后出現(xiàn)的不一致性條數(shù)，修改后就不會存在不一致性的數(shù)據(jù)。

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

5 總 結(jié)

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

未來工作：1.時態(tài)RDF數(shù)據(jù)會時常更新，對于每次更新都要進行檢測和修復(fù)不一致性消耗太大，檢測和修復(fù)不一致性算法的效率還有待提高。2.對于支持有效時間的時態(tài)RDF數(shù)據(jù)之間的推理、蘊含等內(nèi)置函數(shù)和數(shù)據(jù)間關(guān)系和結(jié)構(gòu)都沒有討論和研究。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] 湯庸.時態(tài)數(shù)據(jù)庫導(dǎo)論[M].北京：北京大學(xué)出版社，2004

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

[6] 辜煒東，湯庸，王路幫，等.事務(wù)數(shù)據(jù)庫中的時態(tài)信息挖掘[J].計算機工程與應(yīng)用，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.