胡章兵，左良利

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

namesalarytitledeptvstartvendtom50 000engineerd1v1e1tom60 000engineerd1v2e2tom60 000Sr engineerd2v3e3tom60 000leaderd2v4e4

(a)ungrouped record

(b)grouped record

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

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

1.2 時(shí)態(tài)XML

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

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

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

2.1 JSON語(yǔ)法及文檔示例

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

{

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

"age":18，

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

}

2.2 JSON文檔樹(shù)

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

圖2 JSON樹(shù)

2.3 JSON樹(shù)模型

定義1(節(jié)點(diǎn))：假設(shè)J是一個(gè)JSON文檔，其中V(J)是文檔J的節(jié)點(diǎn)集，則V(J)有六種節(jié)點(diǎn)：根節(jié)點(diǎn)、字符串節(jié)點(diǎn)、數(shù)字節(jié)點(diǎn)、布爾類型節(jié)點(diǎn)、數(shù)組節(jié)點(diǎn)和對(duì)象節(jié)點(diǎn)，分別標(biāo)記為r，vs(J)，vn(J)，vb(J)，va(J),vo(J)。為了簡(jiǎn)化討論，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 時(shí)態(tài)JSON數(shù)據(jù)模型

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

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

3.1 時(shí)態(tài)JSON模型

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

[2017-12-01,2018-01-15]。2017年12月1號(hào)到2018年1月15號(hào)是該邊尾部對(duì)應(yīng)節(jié)點(diǎn)的有效時(shí)間范圍。

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

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

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

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

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

3.2 JSON Schema

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

圖4 JSON Schema

但是，隨著JSON文檔的變化，JSON文檔的Schema 也同樣會(huì)發(fā)生變化。例如，文檔加入了屬性“vip”之后，原本的Schema不能夠表達(dá)JSON文檔的結(jié)構(gòu)了。但是由于Schema也是JSON文檔，因此采用同樣的方法，可以用類似圖3所示的時(shí)態(tài)JSON模型來(lái)表征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ù)上述提出的時(shí)態(tài)模型到時(shí)態(tài)文檔的映射算法，可以得到如圖5所示的時(shí)態(tài)JSON文檔。

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

3.4 時(shí)態(tài)文檔查詢語(yǔ)言

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

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

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

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

return{

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

}

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

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

return time($vip)

4 結(jié)束語(yǔ)

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