胡章兵，左良利

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

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和普及，各個領(lǐng)域的數(shù)據(jù)都呈現(xiàn)指數(shù)級的增長。中國云計算大會網(wǎng)站2018年發(fā)布的數(shù)據(jù)量增長報告顯示，2020年的互聯(lián)網(wǎng)數(shù)據(jù)量將是目前的44倍。正是由于各個領(lǐng)域的數(shù)據(jù)量不斷增長和軟硬件計算能力的提升，云計算、大數(shù)據(jù)、機器學(xué)習(xí)等智能技術(shù)得以迅猛發(fā)展和應(yīng)用。由此，利用這些智能技術(shù)來挖掘出在大量數(shù)據(jù)的背后所隱含的發(fā)展趨勢和規(guī)律就顯得極具有價值和必要[1]。

時間屬性作為自然界數(shù)據(jù)表達的一種重要衡量維度，挖掘出在大量數(shù)據(jù)發(fā)展過程中的時態(tài)規(guī)律，逐漸得到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注和研究。時態(tài)數(shù)據(jù)挖掘算法(temporal data mining)就是在這一背景下逐漸被研究和應(yīng)用的成果[2]。時態(tài)數(shù)據(jù)挖掘算法是對觀測到的時間屬性數(shù)據(jù)進行分析，然后發(fā)現(xiàn)未知的知識和以時間數(shù)據(jù)擁有者可以理解且對其有價值的方式來總結(jié)時間知識。由于現(xiàn)實世界總是按照時間不斷發(fā)展變化的，大多數(shù)信息都包含有時間屬性，例如股票的波動，超市的交易，天氣的變化，文檔的編輯，含時間的實驗數(shù)據(jù)等。因此，在數(shù)據(jù)知識領(lǐng)域，如何對現(xiàn)有的隨時間變化的數(shù)據(jù)進行時態(tài)建模，一直是學(xué)者們的熱點研究方向。

1 相關(guān)工作

文中的主要工作與時態(tài)數(shù)據(jù)庫和時態(tài)XML非常相似。接下來分別從這兩個領(lǐng)域介紹其相關(guān)工作。

1.1 時態(tài)數(shù)據(jù)庫

首先，在時態(tài)數(shù)據(jù)庫發(fā)展過程中，如何在傳統(tǒng)的數(shù)據(jù)庫模式中引入時態(tài)信息得到了眾多學(xué)者的廣泛研究。自20世紀80年代，E.F.Codd提出的關(guān)系數(shù)據(jù)庫模型得到廣泛應(yīng)用之后，Jensen等就隨即提出了基于關(guān)系表模式的時態(tài)關(guān)系數(shù)據(jù)庫[3]，并給出了時態(tài)數(shù)據(jù)庫的概念定義和詞匯表。James Clifford通過將時間屬性添加到關(guān)系表模型，提出了歷史關(guān)系數(shù)據(jù)庫模型[4]，當需要跟蹤來自數(shù)據(jù)的所有更改并具有建?，F(xiàn)實的完整歷史時，其時間標記數(shù)據(jù)值可以體現(xiàn)數(shù)據(jù)在時間維度上的歷史變化過程。在文獻[5]中，將時間關(guān)系模型主要分為兩類：非分組記錄(ungrouped)和分組記錄(grouped)。非分組記錄模型在記錄后面添加表示該記錄的有效時間屬性(有效開始時間vstart和有效結(jié)束時間vend)。而分組記錄是根據(jù)記錄在時間上的發(fā)展變化過程對記錄中的每個屬性進行時間分組標記。表現(xiàn)形式的區(qū)別用一張員工表展示，如圖1所示。

namesalarytitledeptvstartvendtom50 000engineerd1v1e1tom60 000engineerd1v2e2tom60 000Sr engineerd2v3e3tom60 000leaderd2v4e4

(a)ungrouped record

(b)grouped record

圖1 非分組記錄和分組記錄

隨著單時態(tài)數(shù)據(jù)庫的不斷深入研究，其在時態(tài)表達方面的缺點就逐漸顯現(xiàn)出來。不論是單時態(tài)有效時間數(shù)據(jù)庫還是單時態(tài)事務(wù)時間數(shù)據(jù)庫，都僅能夠表達數(shù)據(jù)在某一個時間維度的信息。由此，雙時態(tài)數(shù)據(jù)庫逐漸成為學(xué)者們研究的熱點方向。Knolmayer等給出了雙時態(tài)關(guān)系數(shù)據(jù)庫的模型定義和具體實現(xiàn)[6],其在關(guān)系數(shù)據(jù)庫模型中同時加入有效時間(數(shù)據(jù)在現(xiàn)實世界中真實有效的時間區(qū)間)和事務(wù)時間(數(shù)據(jù)在存儲介質(zhì)世界的有效時間區(qū)間)，得到了能夠在現(xiàn)實世界維度和物理介質(zhì)維度都能體現(xiàn)數(shù)據(jù)在時間線索上的發(fā)展變化歷史模型。此外，Dayal等實現(xiàn)了一個基于面向?qū)ο蟮臅r態(tài)數(shù)據(jù)庫系統(tǒng)[7]，在面向?qū)ο竽Ｐ椭屑尤胗行r間維度，擴展了面向?qū)ο髷?shù)據(jù)庫數(shù)據(jù)對象在時態(tài)語義表達的功能。Zheng等提出了一個基于圖數(shù)據(jù)庫的時態(tài)圖模型[8]。

1.2 時態(tài)XML

關(guān)系型數(shù)據(jù)庫模型和查詢語言SQL(structure query language)雖然能夠很好地表達和處理結(jié)構(gòu)化數(shù)據(jù)，但是現(xiàn)有的很多應(yīng)用領(lǐng)域需要處理半結(jié)構(gòu)化的數(shù)據(jù)，但關(guān)系數(shù)據(jù)模型和SQL對半結(jié)構(gòu)化數(shù)據(jù)模型表達的靈活性差，因此半結(jié)構(gòu)化模型和查詢語言處理逐漸成為數(shù)據(jù)庫，網(wǎng)絡(luò)數(shù)據(jù)傳輸，元數(shù)據(jù)等領(lǐng)域的研究熱點。特別的，隨著現(xiàn)代計算機應(yīng)用(例如社交網(wǎng)絡(luò)，協(xié)作web信息系統(tǒng)等)的迅速發(fā)展，要求網(wǎng)絡(luò)上的數(shù)據(jù)交換具有較高的傳輸效率。XML(extensible markup language)自20世紀80年代被萬維網(wǎng)聯(lián)盟(W3C)擬定，因其自描述、易理解等優(yōu)點已經(jīng)成為了W3C的推薦標準。但是由于非時態(tài)XML模型既不能支持時態(tài)語義表達功能，也不能體現(xiàn)XML文檔在隨時間更迭過程中的數(shù)據(jù)變化過程等缺點，時態(tài)XML逐漸吸引了眾多學(xué)者的研究。Amagasa等針對非時態(tài)XML的XPath模型，通過在每條邊上添加有效時間戳，以表示子節(jié)點是否有效存在[9]。另外，Wang等在其管理系統(tǒng)中，為了支持多個客戶端編輯XML文檔進行協(xié)同工作，利用時態(tài)XML模型來管理文檔在協(xié)同編輯過程中的版本變化[10]。同時，Grandi為了高效地管理XML格式的法律文獻，實現(xiàn)了一個時態(tài)XML模型，通過時態(tài)模型中的發(fā)表時間，有效時間，效力時間，事務(wù)時間四個時間維度表示法律文獻的演變歷史[11]。同樣，為了更好地突出模型在時態(tài)表達和模型一致性等方面的特性，雙時態(tài)XML在許多應(yīng)用領(lǐng)域也日益成為研究對象。Wang等提出了在雙時態(tài)XML領(lǐng)域中較為普遍的實現(xiàn)方案，通過在標簽屬性中加入有效時間區(qū)間和事務(wù)時間區(qū)間來表達數(shù)據(jù)在雙時態(tài)維度的體現(xiàn)[12]。另外，湯娜等討論了在雙時態(tài)XML查詢中now語義失真的研究和擴展[13]。一般的，在由時態(tài)XML模型到時態(tài)XML文檔的轉(zhuǎn)化中，時態(tài)文檔通過時態(tài)屬性或時態(tài)標簽來表示數(shù)據(jù)的時間信息。屬性的時間過程同樣用屬性元素來表示。

2 非時態(tài)JSON數(shù)據(jù)模型

XML雖然得到了廣泛的應(yīng)用和研究，但是隨著需求的不斷增加和復(fù)雜，XML的缺點也逐漸顯露出來，如冗余度高，數(shù)據(jù)插入修改困難，處理大量數(shù)據(jù)時效率低下，客戶端瀏覽器解析困難等。2006年，Douglas Crockford把JSON(JavaScript Object Notation)提交給Internet Engineering Task Force (IETF)，JSON因相比XML易讀寫，同時也易于機器解析生成等特點得到了廣泛應(yīng)用。自JSON數(shù)據(jù)格式提出以來，針對JSON和XML在實用性、傳輸效率、安全性等方面進行了深入的討論研究和實驗[14-16]，都一致認為JSON在傳輸效率和瀏覽器解析等方面都比XML更加的實用和高效。因此，數(shù)據(jù)交換格式在WEB領(lǐng)域中逐漸從XML轉(zhuǎn)為JSON。2009年，權(quán)重民等利用JSON實現(xiàn)了一種高效、安全訪問遠程數(shù)據(jù)庫的方式[14]。2018年，王東興等提出基于JSON的GeoJSON在異構(gòu)地理信息數(shù)據(jù)集成中的應(yīng)用[16]。但是在非時態(tài)JSON得到廣泛應(yīng)用時，針對JSON的理論研究和模型定義卻鮮有成果。

2.1 JSON語法及文檔示例

JSON語法定義，JSON文檔是由鍵值對組成的字典，其中的值又可以是一個JSON文檔，從而JSON模型允許任意級別的嵌套。完整的JSON規(guī)范定義了七種類型的值：分別是字符串，數(shù)字，對象，數(shù)組，true，false和null。文中給出了一個來自某論壇網(wǎng)站用戶信息的簡單JSON文檔示例，如下：

{

"name":{"firstname":"Tom","lastname":"Doe"}，

"age":18，

"hobbies" ["fish","tennis"]

}

2.2 JSON文檔樹

根據(jù)JSON文檔的語法定義，可以用樹型結(jié)構(gòu)來描述JSON文檔的信息，如圖2所示。

圖2 JSON樹

2.3 JSON樹模型

定義1(節(jié)點)：假設(shè)J是一個JSON文檔，其中V(J)是文檔J的節(jié)點集，則V(J)有六種節(jié)點：根節(jié)點、字符串節(jié)點、數(shù)字節(jié)點、布爾類型節(jié)點、數(shù)組節(jié)點和對象節(jié)點，分別標記為r，vs(J)，vn(J)，vb(J)，va(J),vo(J)。為了簡化討論，null暫不做考慮。滿足：

V(J)=r∪vs(J)∪vn(J)∪vb(J)∪va(J)∪vo(J)

定義2(邊)：E(J)是文檔J的所有邊的集合，其中每條邊可以表示為(p,c),其中p=r,c∈ve(J)或p∈ve(J),c∈ve(J)或p∈ve(J),c∈vt(J)或p∈ve(J),c∈va(J)或p∈va(J),c∈vt(J)。

定義3(文檔)：JSON文檔J=(V(J),E(J),r)。

3 時態(tài)JSON數(shù)據(jù)模型

隨著時間的更迭，用戶的數(shù)據(jù)不斷發(fā)生變化。該用戶在2017年12月1號創(chuàng)建，基本信息如圖2所示。此后，在2017年12月15號其“firstname”變更為“Alen”，在2018年1月1號加入“vip”屬性，并且成為該論壇的VIP用戶，在2018年1月1號新添了愛好“yoga”，在2018年1月5號刪除愛好“tennis”，在2018年1月23號，其年齡由18增長為19。

由于非時態(tài)JSON模型不能很好地表達數(shù)據(jù)對象在時間上的變化過程，通過對非時態(tài)JSON模型進行時態(tài)擴展得到了時態(tài)JSON模型。

3.1 時態(tài)JSON模型

定義4(邊)：將有效時間屬性加入到邊的定義中，以此反映這條邊尾部節(jié)點的有效時間區(qū)間，得到TE=((p,c),t)。其中(p,c)與非時態(tài)模型的定義一致，而t表征該邊的時態(tài)信息，t是一個時間區(qū)間，由有效開始時間和有效結(jié)束時間構(gòu)成-[vstart,vend]，如:

[2017-12-01,2018-01-15]。2017年12月1號到2018年1月15號是該邊尾部對應(yīng)節(jié)點的有效時間范圍。

定義5(文檔一致性)：若一個節(jié)點有很多孩子節(jié)點，其有效時間為t，連接雙親節(jié)點和孩子節(jié)點的邊分別為:

((p,c),t1),((p,c),t2),…,((p,c),tn),則：

(2)t1∩t2∩…∩tn=?(數(shù)組除外)。

根據(jù)用戶信息的變化過程，可以用圖3所示的時態(tài)模型表示文檔的演變進程。

圖3 時態(tài)JSON模型

3.2 JSON Schema

JSON Schema是用來規(guī)范JSON文檔的屬性結(jié)構(gòu)的，JSON Schema本身也是一個JSON文檔。JSON文檔的schema如圖4所示。

圖4 JSON Schema

但是，隨著JSON文檔的變化，JSON文檔的Schema 也同樣會發(fā)生變化。例如，文檔加入了屬性“vip”之后，原本的Schema不能夠表達JSON文檔的結(jié)構(gòu)了。但是由于Schema也是JSON文檔，因此采用同樣的方法，可以用類似圖3所示的時態(tài)JSON模型來表征JSON Schema的變化。

3.3 模型到文檔的映射算法

Algorithm：Temporal Model Translation

Input temporal model root nodeR

Output temporal document

1.DgetDocument(R)

2.getDocumetn (N) {

3.if(Nis object) :

4.getDocument(N)

5.else :

6.If(Nis array) :

7.for each edge:

8.p1createKVpair(N.attribute,N.text)

9.p2createKVpair(“validtime”,time)

10.else :

11.for each edge:

12.p1createKVpair(N.attribute,N.text)

13.p2createKVpair(“validtime”,time)

14.}

15.createKVpair(key,value) {

16.kv.set(key)

17.kv.set(value)

18.retrun kv

19.}

根據(jù)上述提出的時態(tài)模型到時態(tài)文檔的映射算法，可以得到如圖5所示的時態(tài)JSON文檔。

圖5 時態(tài)JSON文檔

3.4 時態(tài)文檔查詢語言

非時態(tài)JSON查詢語言目前還沒有標準規(guī)范，但是對于非時態(tài)JSON文檔，已經(jīng)有JSONPath，JSONip，N1QL等處理方法。文中時態(tài)文檔的查詢語言綜合上述幾種方式的特點進行時態(tài)擴展。首先，在JSONPath表達式中添加時態(tài)屬性擴展支持，可以滿足大部分檢索需求，例如普通的JSONPath從2.1節(jié)文檔示例中查詢用戶的名字，可以用如下JSONPath表達式：

$.name.firstname或$[“name”][“firstname”]

但是要檢索出在圖3時態(tài)文檔中的名字，需要對其進行時態(tài)擴展，結(jié)合JSONPath和JSONip，提出了時態(tài)查詢語言。例如要檢索出在2017年12月5號該用戶的名字，可以用如下表達式：

let $name=collection.find("name")

return{

"firstname"=$name("firstname")[@from eq 2017-12-05 and @end eq 2017-12-05]

}

其中，“@from”屬性表示開始時間，“@end”表示結(jié)束時間，“eq”表示相等,用“=”表示作用一樣。另外，如果要檢索該用戶注冊為VIP的有效時間，可以用自定義time()函數(shù)獲取，表達式如下：

let $vip=collection.find("vip")[@value=true]

return time($vip)

4 結(jié)束語

目前，針對JSON時態(tài)信息建模和時態(tài)查詢語言處理的理論研究非常少，文中提出了時態(tài)JSON數(shù)據(jù)模型。根據(jù)時態(tài)JSON模型，對傳統(tǒng)的查詢語言做了簡單的時態(tài)擴展，但目前僅能支持一些相對簡單的查詢，后續(xù)會進一步提出類似TempSQL能完成連接、分組、排序等更高級的時態(tài)查詢處理。另外，還提出了一個由時態(tài)模型到時態(tài)文檔的映射算法，解決了從模型到文檔的映射方法，后續(xù)會根據(jù)提出的時態(tài)模型和針對映射后的文檔解決其在存儲方面的問題,因為存儲的性能好壞直接影響查詢性能。