一個時態RDF存儲系統的設計與實現

龐亞君

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

1 研究背景及現狀

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

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

文中以時態數據庫管理系統TimeDB[11]為基礎，設計并實現了一個時態RDF數據存儲系統，切實解決當前時態RDF存儲研究缺失的問題。

2 基礎知識

2.1 時態RDF

2.1.1 時態RDF模型概念

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

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

2.1.2 時態RDF蘊含

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

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

2.2 Jena工具

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

2.3 時態數據管理系統TimeDB

目前分層擴展非時態的數據庫管理系統建立時態中間件成為實現時態數據庫管理系統的最好方法。時態中間件不改變底層RDB的功能和結構，而是作為上層構件添加到應用程序和關系數據庫之間，使得時態SQL語句能夠轉換成下層關系數據庫可以理解的標準SQL語句。在目前所有的時態數據庫應用中，TimeDB不論是在數據管理還是用戶交互上都是目前最受歡迎、使用最為廣泛的時態數據庫產品化應用。

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

3 TRDF-STORAGE的設計實現

3.1 系統體系結構

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

圖1 系統層次圖

3.2 時態RDF/XML文檔解析模塊

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

圖2 Jena解析結果

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

圖3 標準時態RDF圖

前文已經介紹了Jena API的解析過程，在此基礎上，需要將多余的三元組進行合并。合并算法的主要思想是，一旦檢測到節點類型中有temporl屬性不作輸出，而是直接獲取下一節點，然后將Initial的屬性值賦值給有效時間區間的起止時間點，Final屬性值賦值給終止時間點，然后輸出有效時間標簽。

3.3 推理引擎的原理與實現

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

3.3.1 RDF三元組的處理

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

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

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

3.3.2 時態標簽的處理

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

1.插入操作。

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

S：表示數據庫中已存的時態三元組集合。

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

T：時間點集合。

Tn：時間區間集合。

四種算法的輸入都是經過第一步RDF三元組處理后的時態RDF三元組集合，輸出為經過時態標簽處理后可直接進行插入操作的時態RDF三元組集合。

●直接插入情況：針對待插入數據與數據庫中已存數據三元組以及時態標簽都不重復的時態RDF三元組，具體算法思想如下：

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

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

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

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

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

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

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

2.刪除操作。

在對時態RDF三元組進行插入操作時,需要考慮時間區間的合并以防出現數據冗余，而對三元組進行刪除操作時，則需要考慮時間區間的分裂以維持時態數據表格式的統一。例如對于待刪除的三元組(a,b,c):[3,5]，若在原有數據庫中已經存在時態RDF三元組(a,b,c):[2,6]，那么該刪除操作不僅不會使原時態RDF數據庫中的數據減少，反正會轉變為插入兩個三元組(a,b,c):[2,3]和(a,b,c):[5,6]的插入操作。

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

S：表示數據庫中已存的時態三元組集合。

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

T：時間點集合。

Tn：時間區間集合。

●直接刪除情況：針對待刪除數據與已存數據的對應時間標簽完全匹配的時態RDF三元組數據，主要思想如下：

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

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

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

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

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

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

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

3.4 時態RDF數據存儲到TimeDB

按照前文提出的關系表結構，將處理后的時態RDF三元組數據存儲在TimeDB中。

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

部分實現代碼如下：

/*設置數據庫的鏈接參數*/

TDBCI t=new TDBCI();

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

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

……

/*對于每個時態RDF三元組，分別將解析出的主語、謂語、賓語以及有效時間區間對應插入TimeDB，以時態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());//將時態RDF三元組的主語、謂語、賓語以及有效時間分別插入。

}

……

4 系統演示

1.插入操作。

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

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

TimeDB通過執行下列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’);

通過查看時態本體信息表得到結果如圖4所示。

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

2.刪除操作。

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

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

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

由于T002三元組在規則中依賴于刪除的時態RDF三元組T001，因此在刪除T001時，推理算法會將T002也刪除，并將它們在規則信息表中的數據一并刪除。

5 結束語

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