龐亞君

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

1 研究背景及現(xiàn)狀

隨著時態(tài)數(shù)據(jù)處理和語義網(wǎng)的發(fā)展，越來越多的時態(tài)RDF格式的數(shù)據(jù)涌入網(wǎng)絡(luò)。在對時態(tài)RDF的早期研究中，Gutierrez等提出了時態(tài)RDF的語法語義以及查詢語言[1-3]，Andrea等補充了非限定三元組的語法語義，并提出了tGRIN索引結(jié)構(gòu)將時態(tài)RDF存儲在關(guān)系型數(shù)據(jù)庫中[3-4]。Geetha等針對海量RDF存儲和語義網(wǎng)大量歷史數(shù)據(jù)存儲的問題，提出了一個基于語義的時態(tài)視圖機制，通過演示驗證了該機制可提高RDF三元組中的時變數(shù)據(jù)緩存到主存的效率[5-6]。時態(tài)RDF由于其獨特的語義支持和推理機制，通常應(yīng)用于人工智能領(lǐng)域中，如電力系統(tǒng)中[7]以及機器閱讀技術(shù)中等。

對數(shù)據(jù)的管理離不開數(shù)據(jù)庫的支持，而對于時態(tài)RDF數(shù)據(jù)的管理要建立在時態(tài)數(shù)據(jù)庫研究的基礎(chǔ)上。Tansel等在1993年對此前提出的時態(tài)數(shù)據(jù)庫技術(shù)的研究及時態(tài)數(shù)據(jù)模型做了全面的總結(jié)[8]。之后，時態(tài)數(shù)據(jù)庫研究重點由理論探討逐漸轉(zhuǎn)向模型的標(biāo)準(zhǔn)化和產(chǎn)品化。由于迄今為止時態(tài)模型尚不成熟未能完全統(tǒng)一等原因，各大數(shù)據(jù)庫廠商還沒有推出相關(guān)的時態(tài)數(shù)據(jù)庫產(chǎn)品，目前大多數(shù)應(yīng)用只是借助時態(tài)數(shù)據(jù)庫的概念與傳統(tǒng)的數(shù)據(jù)庫相結(jié)合來完成的。文獻[9-10]提出分層擴展RDBMS的思想，開發(fā)了TimeDB、TempDB等時態(tài)數(shù)據(jù)庫產(chǎn)品。

文中以時態(tài)數(shù)據(jù)庫管理系統(tǒng)TimeDB[11]為基礎(chǔ)，設(shè)計并實現(xiàn)了一個時態(tài)RDF數(shù)據(jù)存儲系統(tǒng)，切實解決當(dāng)前時態(tài)RDF存儲研究缺失的問題。

2 基礎(chǔ)知識

2.1 時態(tài)RDF

2.1.1 時態(tài)RDF模型概念

對傳統(tǒng)RDF時態(tài)擴展有兩種方式：時態(tài)標(biāo)簽法和版本更新法。時態(tài)標(biāo)簽法也就是給產(chǎn)生變化的三元組添加時間標(biāo)簽；版本更新法不關(guān)心過去狀態(tài)的時態(tài)RDF圖存在何處，只記錄更新后的時間快照。版本更新法可以更有效地獲取事務(wù)時間，而在獲取有效時間時通常使用時態(tài)標(biāo)簽法。雖然兩種方法是等價的，當(dāng)時態(tài)信息越多也就是RDF圖更新頻率越快，即產(chǎn)生的新版本也會越多，不斷記錄更新后的RDF圖無疑增加了查詢的復(fù)雜度，因此現(xiàn)有的時態(tài)RDF模型都是采用時態(tài)標(biāo)簽法進行時態(tài)擴展。

在時態(tài)RDF中，認為時間是離散的，線性有序的區(qū)域，使用時態(tài)標(biāo)簽法來對RDF進行時態(tài)擴展，也就是用時態(tài)元素t標(biāo)記三元組(s,p,o)。時態(tài)元素包含時間點和時間區(qū)間，不難想到一個在時間區(qū)間時，該區(qū)間就等同與一個時間點t1。

2.1.2 時態(tài)RDF蘊含

一個RDF圖可以看作是一個由其他知識庫(也就是其他RDF圖)得到的知識庫。當(dāng)為RDF蘊含擴展時態(tài)屬性時，需要將時態(tài)數(shù)據(jù)庫定義為所有快照的集合。

時態(tài)蘊含的概念往往和時間區(qū)間的運算一起作用于時態(tài)推理機制中，例如若有(a,sc,b):[2,3]和(b,sc,c):[2](其中SC為rdf:SubclassOF屬性的縮寫形式)，那么可以推出(a,sc,c):[2]。

2.2 Jena工具

網(wǎng)頁上的RDF數(shù)據(jù)通常以文檔的形式存在，通用的RDF語法為Turtle(Terse RDF Triple Language)或者RDF/XML的格式。RDF數(shù)據(jù)以三元組“主語—謂語—賓語”的格式存儲在關(guān)系型數(shù)據(jù)庫中，因此在RDF數(shù)據(jù)存儲到數(shù)據(jù)庫之前，需要對RDF文檔進行解析。Jena是一個使用Java編寫的API(application programming interface，應(yīng)用程序編程接口)[12]，用于創(chuàng)建和操作RDF圖。Jena將以三元組為中心的解析方法與以資源及其屬性為中心的解析方法相結(jié)合，既可以對RDF三元組進行操作，也可以對單個的資源進行操作。

2.3 時態(tài)數(shù)據(jù)管理系統(tǒng)TimeDB

目前分層擴展非時態(tài)的數(shù)據(jù)庫管理系統(tǒng)建立時態(tài)中間件成為實現(xiàn)時態(tài)數(shù)據(jù)庫管理系統(tǒng)的最好方法。時態(tài)中間件不改變底層RDB的功能和結(jié)構(gòu)，而是作為上層構(gòu)件添加到應(yīng)用程序和關(guān)系數(shù)據(jù)庫之間，使得時態(tài)SQL語句能夠轉(zhuǎn)換成下層關(guān)系數(shù)據(jù)庫可以理解的標(biāo)準(zhǔn)SQL語句。在目前所有的時態(tài)數(shù)據(jù)庫應(yīng)用中，TimeDB不論是在數(shù)據(jù)管理還是用戶交互上都是目前最受歡迎、使用最為廣泛的時態(tài)數(shù)據(jù)庫產(chǎn)品化應(yīng)用。

TimeDB的時態(tài)查詢語言ATSQL2是在SQL標(biāo)準(zhǔn)查詢語言的基礎(chǔ)上加入了一些時態(tài)相關(guān)的關(guān)鍵字，TimeDB很容易將這些關(guān)鍵字識別出來并解釋其包含的時態(tài)語義，其次確定語句要進行查詢的具體類型，進行時態(tài)語言驗證后通過關(guān)系操作的算法來實現(xiàn)語句的轉(zhuǎn)換。

3 TRDF-STORAGE的設(shè)計實現(xiàn)

3.1 系統(tǒng)體系結(jié)構(gòu)

TRDF-Storage存儲時態(tài)RDF數(shù)據(jù)的具體流程如圖1所示。輸入數(shù)據(jù)為RDF/XML文檔，首先將其解析為時態(tài)RDF三元組。解析后的三元組要通過推理機制的處理，以保證時態(tài)RDF的數(shù)據(jù)庫的一致性，最后將處理后的不違背一致性的時態(tài)RDF三元組集合插入到時態(tài)數(shù)據(jù)庫中。

圖1 系統(tǒng)層次圖

3.2 時態(tài)RDF/XML文檔解析模塊

RDF標(biāo)準(zhǔn)規(guī)定在RDF中只存在三元組，如果直接為RDF三元組增加時間標(biāo)簽，那么三元組就變成了四元組。因此引入一個額外的對象即具體化(reification)，將時態(tài)屬性與原聲明中的主語、謂語和賓語通過屬性相關(guān)聯(lián)。如時態(tài)RDF三元組(Joe,isFollowing,Marry)：[2005-10-01,2017-06-27]被Jena工具解析后形式如圖2所示。

圖2 Jena解析結(jié)果

若在存儲過程中將這樣一個時態(tài)RDF圖存儲在數(shù)據(jù)庫中顯然是不現(xiàn)實的，因此需要將這個時態(tài)RDF圖解析成圖3所示的形式，然后以(S,P,O)：[T1，T2]的形式存儲在時態(tài)數(shù)據(jù)庫中。

圖3 標(biāo)準(zhǔn)時態(tài)RDF圖

前文已經(jīng)介紹了Jena API的解析過程，在此基礎(chǔ)上，需要將多余的三元組進行合并。合并算法的主要思想是，一旦檢測到節(jié)點類型中有temporl屬性不作輸出，而是直接獲取下一節(jié)點，然后將Initial的屬性值賦值給有效時間區(qū)間的起止時間點，F(xiàn)inal屬性值賦值給終止時間點，然后輸出有效時間標(biāo)簽。

3.3 推理引擎的原理與實現(xiàn)

由于時態(tài)RDF的語義特性，在存儲和刪除數(shù)據(jù)的過程中都要考慮數(shù)據(jù)的一致性。時態(tài)RDF中時間標(biāo)簽用時間點表示，屬于時態(tài)域，也就是一個正實數(shù)集合，與三元組集合屬于兩個互不相交的不同框架。因此時態(tài)RDF數(shù)據(jù)推理怡情可以分為對傳統(tǒng)RDF三元組的推理以及時態(tài)標(biāo)簽處理兩部分進行，文獻[13]也證明了這一點。

3.3.1 RDF三元組的處理

在存儲RDF三元組時，需要建立一個表格用于存儲三元組之間的推理關(guān)系—Rule_Table表格(InfID,Stmt1,Stmt2,Rule)。其中InfID表示根據(jù)規(guī)則推導(dǎo)出的三元組ID，Stmt1和Stmt2表示證明該三元組的ID，允許為空，且當(dāng)三元組是直接聲明而不是通過推理規(guī)則產(chǎn)生時，Stmt1與Stmt2都為Null，Rule則是來自W3C RDF文檔中的推理規(guī)則集。

另外，由于每一個三元組也是依賴自己作為推理條件的一個推理結(jié)果，所以規(guī)則之間會存在依賴循環(huán)問題，文獻[14]中提出了克服循環(huán)依賴問題的算法。

文中的推理引擎基于Jena推理機。Jena推理機是一種基于規(guī)則的推理引擎，使用前向、后向和混合執(zhí)行的推理模型[15-16]。表中的內(nèi)容已經(jīng)包含在Jena的推理規(guī)則中。此外，針對特定領(lǐng)域，Jena支持自定義規(guī)則，通過String rule_Name=“Rule1:(?xpredicate ?y),(?ypredicate? z)→(?xpredicate?z)”聲明，然后通過綁定實例文件與自定義推理機的方式進行實現(xiàn)。

3.3.2 時態(tài)標(biāo)簽的處理

時態(tài)RDF是根據(jù)Allen在1983年提出的一種基于時間段的時態(tài)邏輯方式進行表示的[17]。

1.插入操作。

對于插入操作來說，對時態(tài)標(biāo)簽的處理方式包括四種：直接插入情況、不執(zhí)行插入操作的情況、替換插入的情況以及合并插入的情況。下面分別就四種情況給出詳細的算法。為了方便描述，給出如下定義：

S：表示數(shù)據(jù)庫中已存的時態(tài)三元組集合。

A：表示待插入的三元組集合。這里的三元組集合都經(jīng)過了第一步處理。

T：時間點集合。

Tn：時間區(qū)間集合。

四種算法的輸入都是經(jīng)過第一步RDF三元組處理后的時態(tài)RDF三元組集合，輸出為經(jīng)過時態(tài)標(biāo)簽處理后可直接進行插入操作的時態(tài)RDF三元組集合。

●直接插入情況：針對待插入數(shù)據(jù)與數(shù)據(jù)庫中已存數(shù)據(jù)三元組以及時態(tài)標(biāo)簽都不重復(fù)的時態(tài)RDF三元組，具體算法思想如下：

(1)判斷A是否為空，若為空終止算法，若A不為空，取ai∈A，i++，進入步驟2。

(2)對時間標(biāo)簽的有效性進行檢查，若t1>t2，返回錯誤提示并進入步驟1，否則進入第2步。

(3)遍歷已存RDF三元組數(shù)據(jù)的三元組集合S，檢查a是否在S中，若不在則可以直接返回原時間標(biāo)簽，返回步驟1。若在，取相同三元組Sj對應(yīng)的時間標(biāo)簽T2(t3,t4)，進入步驟4。

(4)若t2t4且|t2-t3|與|t1-t4|均不等于一個時間粒度(即為Before與After關(guān)系)，說明待插入三元組與數(shù)據(jù)庫中的三元組不相同，返回T1并進入第一步。

●不執(zhí)行插入操作的情況：針對待插入數(shù)據(jù)被已存數(shù)據(jù)語義包含的時態(tài)RDF三元組，這種情況下，應(yīng)直接在待存集合中刪除對應(yīng)時態(tài)RDF數(shù)據(jù)。若t3≤t1≤t2≤t4，即待插入三元組的有效時間T1區(qū)間被包含在數(shù)據(jù)庫中已存的相同三元組的有效時間區(qū)間T2，即During(T1,T2)、Starts(T1,T2)以及Finishes(T1,T2)。對于這幾種情況，直接返回步驟1而不執(zhí)行插入操作，否則會產(chǎn)生重復(fù)性問題，造成存儲空間浪費。

●替換插入的情況：該情況與第一種情況恰好相反，針對待插入數(shù)據(jù)語義包含已存數(shù)據(jù)的時態(tài)RDF三元組，也就是待插入數(shù)據(jù)的有效時間范圍包含對應(yīng)已存數(shù)據(jù)的有效時間。即如果兩個時間區(qū)間中的四個時間點存在關(guān)系t1≤t3≤t4≤t2，即待插入三元組的有效區(qū)間T1包含了數(shù)據(jù)庫中已存的相同三元組的有效時間區(qū)間T2，即During(T2,T1)、Starts(T2,T1)以及Finishes(T2,T1)，在這幾種情況下，要將原有數(shù)據(jù)庫中的對應(yīng)的三元組刪除，插入有效區(qū)間更大的三元組。

●合并插入的情況：若插入數(shù)據(jù)的有效時間區(qū)間與已存數(shù)據(jù)庫中對應(yīng)有效時間區(qū)間部分重疊，出現(xiàn)t1≤t3≤t2≤t4的情況，即Overlaps(T1,T2)或Meets(T1,T2)(反之亦然)，這時則需要將兩個RDF三元組(即待插入三元組和對應(yīng)的已存三元組)的有效時間區(qū)間進行合并操作，返回步驟1。

2.刪除操作。

在對時態(tài)RDF三元組進行插入操作時,需要考慮時間區(qū)間的合并以防出現(xiàn)數(shù)據(jù)冗余，而對三元組進行刪除操作時，則需要考慮時間區(qū)間的分裂以維持時態(tài)數(shù)據(jù)表格式的統(tǒng)一。例如對于待刪除的三元組(a,b,c):[3,5]，若在原有數(shù)據(jù)庫中已經(jīng)存在時態(tài)RDF三元組(a,b,c):[2,6]，那么該刪除操作不僅不會使原時態(tài)RDF數(shù)據(jù)庫中的數(shù)據(jù)減少，反正會轉(zhuǎn)變?yōu)椴迦雰蓚€三元組(a,b,c):[2,3]和(a,b,c):[5,6]的插入操作。

對于刪除算法也需要根據(jù)有效區(qū)間進行分類探討，分為三種情況：直接刪除情況、區(qū)間一次分裂刪除以及區(qū)間兩次分裂刪除。

S：表示數(shù)據(jù)庫中已存的時態(tài)三元組集合。

D：表示待刪除的三元組集合。這里的三元組集合同樣也經(jīng)過了第一步處理。

T：時間點集合。

Tn：時間區(qū)間集合。

●直接刪除情況：針對待刪除數(shù)據(jù)與已存數(shù)據(jù)的對應(yīng)時間標(biāo)簽完全匹配的時態(tài)RDF三元組數(shù)據(jù)，主要思想如下：

(1)判斷待刪除三元組集合D是否為空，若為空則終止運算，否則i++，進入下一步。

(2)對刪除三元組語句的合法性進行分析，對于每一個待刪除三元組di∈D,若其時間標(biāo)簽[t1,t2]中t1>t2，返回錯誤提示并返回第一步，否則就進入第三步。

(3)進一步對語句有效性進行判斷，遍歷已存三元組集合S，若對于每一個s∈S，都不能與待刪除di匹配，說明刪除語句無效，返回步驟1，否則就進入下一步。

(4)取與待刪除三元組di匹配的已存三元組s的有效區(qū)間T2=[t3,t4]，若待刪除三元組的有效區(qū)間與s的有效區(qū)間存在關(guān)系t2t4，說明此時兩個三元組的時間區(qū)間無交集，即為Before與After關(guān)系，說明此時并未在已存三元組中找到待刪除的三元組，以及當(dāng)t1≤t3≤t4≤t2時，即待刪除的三元組di的有效區(qū)間T1包含了對應(yīng)的已存三元組s的有有效區(qū)間T2，都要提示錯誤并返回步驟1，否則進入下一步。

(5)若T1嚴(yán)格等于T2，即t1=t3且t2=t4，也就是說兩個時間區(qū)間存在關(guān)系Equals(T1,T2)，此時將已存三元組集合中的s直接刪除，同時清除刪除列表中的di，返回第一步。

●區(qū)間一次分裂刪除：針對待刪除數(shù)據(jù)有效時間區(qū)間包含在對應(yīng)已存數(shù)據(jù)的有效時間區(qū)間內(nèi)的時態(tài)RDF數(shù)據(jù)。首先對刪除語句的有效性進行判斷(以下所有情況都與第一種情況的前四步相同，都予以省略)，然后通過兩個有效區(qū)間的大小關(guān)系將待刪除數(shù)據(jù)的有效區(qū)間在對應(yīng)已存數(shù)據(jù)中的有效區(qū)間中刪除，即將刪除操作轉(zhuǎn)化為插入操作，并將對應(yīng)數(shù)據(jù)庫中的數(shù)據(jù)刪除。

●區(qū)間兩次分裂刪除：針對待刪除數(shù)據(jù)的有效區(qū)間將對應(yīng)已存數(shù)據(jù)有效區(qū)間分成三段的時態(tài)RDF數(shù)據(jù)。將原有數(shù)據(jù)庫中的三元組時間標(biāo)簽分成兩個不相連的部分存儲，當(dāng)四個時間點之間存在關(guān)系t3≤t1≤t2≤t4時，即存在關(guān)系During(T1,T2)，那么此時在刪除s的同時，還要執(zhí)行對以下兩個三元組的插入操作，即時態(tài)三元組(di,T3)和時態(tài)RDF三元組(di,T4)，其中T3=(t3,t1)，T4=(t2,t4)。

3.4 時態(tài)RDF數(shù)據(jù)存儲到TimeDB

按照前文提出的關(guān)系表結(jié)構(gòu)，將處理后的時態(tài)RDF三元組數(shù)據(jù)存儲在TimeDB中。

TimeDB在Java中提供了三類調(diào)用接口：TimeDB的調(diào)用接口(TDBCI)、結(jié)果集(ResultSet)類接口和結(jié)果行(ResultRow接口)。

部分實現(xiàn)代碼如下：

/*設(shè)置數(shù)據(jù)庫的鏈接參數(shù)*/

TDBCI t=new TDBCI();

t.setPrefs(“C:TimeDB2.2”,1,“Oracle.jdbc.driver.OracleDriver”,

“jdbc:oracle:thin:1512:ORCL”);

……

/*對于每個時態(tài)RDF三元組，分別將解析出的主語、謂語、賓語以及有效時間區(qū)間對應(yīng)插入TimeDB，以時態(tài)RDF實例信息為例*/

String atsql=“VALIDTIME PERIOD[+“Begintime+”-“+Endtime+”]”+“INSERT INTO TStatement_Table values(?,?,?,?,?)”

PreparedStatement prest=conn.prepareStatement(sql,ResultSet.TYPE_SCROLL_SENSITIVE,

ResultSet.CONCUR_READ_ONLY);

For(int i=0;x

{

prest.setString(1,rdfnode.getSubject());

prest.setString(2,rdfnode.getPredicate());

prest.setString(3,rdfnode.getObject());

prest.setString(4,rdfnode.Begintime());

prest.setString(4,rdfnodeEndtime());//將時態(tài)RDF三元組的主語、謂語、賓語以及有效時間分別插入。

}

……

4 系統(tǒng)演示

1.插入操作。

系統(tǒng)將會通過TimeDB的調(diào)用接口(TDBCI)，將三元組中的三個字符串分別插入到數(shù)據(jù)表中的主語、謂語和賓語對應(yīng)列，然后將有效時間區(qū)間插入到起始時間列和終止時間列。

將時態(tài)RDF三元組(Manager,rdfs:SubclassOf,Employee):[0,Now]實例信息和(Ailsa,rdf:type,Manager):[2017,NOW]本體信息分別存入時態(tài)三元組表和時態(tài)本體信息表，

TimeDB通過執(zhí)行下列ATSQL2語句：

VALIDTIME PRIOD [0-Now] INSERT INTO TOntolygy_Table VALUES(OT002,‘Manager’,‘rdfs:SubclassOf’,‘Emolyee’);

VALIDTIME PRIOD [2017-Now] INSERT INTO TStatement_Table VALUES(T001,‘Ailsa’,‘rdf:type’,‘Manager’);

通過查看時態(tài)本體信息表得到結(jié)果如圖4所示。

圖4 F-Storage系統(tǒng)示意圖(1)

2.刪除操作。

下面刪除時態(tài)RDF三元組(Ailsa,rdf:type,Manager):[2017,NOW]，執(zhí)行操作后，查看時態(tài)RDF表和規(guī)則信息表，結(jié)果如圖5和圖6所示。

圖5 F-Storage系統(tǒng)示意圖(2)

圖6 F-Storage系統(tǒng)示意圖(3)

由于T002三元組在規(guī)則中依賴于刪除的時態(tài)RDF三元組T001，因此在刪除T001時，推理算法會將T002也刪除，并將它們在規(guī)則信息表中的數(shù)據(jù)一并刪除。

5 結(jié)束語

針對時態(tài)RDF數(shù)據(jù)存儲研究相對缺失的現(xiàn)狀，提出了一種時態(tài)RDF數(shù)據(jù)存儲系統(tǒng)的設(shè)計方案。針對TRDF-Storage存儲系統(tǒng)中最重要的推理引擎進行了詳細闡述，針對不同的時間區(qū)間關(guān)系，將插入操作和刪除操作分類討論，就每種區(qū)間關(guān)系的操作實現(xiàn)提供了算法。最后通過一個公司的模擬時態(tài)RDF數(shù)據(jù)，對存儲系統(tǒng)的使用進行驗證。實驗結(jié)果表明，系統(tǒng)可以完成時態(tài)RDF本體信息和實例信息的分別存儲，且推理機制可以得到正確的推理結(jié)果并對事態(tài)RDF數(shù)據(jù)進行存儲或刪除，維護了時態(tài)RDF數(shù)據(jù)庫的一致性。但該研究內(nèi)容也有一些不足之處，例如存儲所涉及的時態(tài)RDF模型沒有針對匿名時間點的處理以及對于海量時態(tài)RDF數(shù)據(jù)的處理還未能進行有效驗證，這些都有待進一步的研究與改進。