基于Neo4j不確定性數(shù)據(jù)處理技術(shù)的研究

郭林斐，劉廣鐘

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引 言

隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)挖掘技術(shù)等的迅速發(fā)展，科學(xué)研究呈現(xiàn)出明顯的數(shù)據(jù)密集型特征。數(shù)字人文學(xué)[1](digital humanities)作為計(jì)算機(jī)與人文科學(xué)的跨學(xué)科領(lǐng)域，得到了前所未有的關(guān)注和研究。數(shù)字歷史(digital history)是數(shù)字人文學(xué)的一個(gè)重要分支，其使用計(jì)算機(jī)、因特網(wǎng)和軟件系統(tǒng)之類的通信技術(shù)進(jìn)行歷史分析、演示和研究。

由于歷史文獻(xiàn)久遠(yuǎn)、數(shù)據(jù)保存方式不當(dāng)和后人記載方式不同，導(dǎo)致歷史數(shù)據(jù)具有不確定性，即客觀世界的固有復(fù)雜性或數(shù)據(jù)采集、處理、分析和表述的過程中出現(xiàn)的誤差。歷史數(shù)據(jù)在其整個(gè)生命周期中會(huì)被不同的用戶使用，當(dāng)數(shù)據(jù)在不同的用戶之間傳遞時(shí)，不確定性導(dǎo)致其準(zhǔn)確度降低。為了保證歷史數(shù)據(jù)在生命周期各階段的準(zhǔn)確度和可用性，需要在用戶之間傳遞通用的數(shù)據(jù)模型和元數(shù)據(jù)(metadata)。歷史數(shù)據(jù)的不確定性研究正是解決這一問題，對(duì)于數(shù)據(jù)的使用與共享具有重要意義。傳統(tǒng)的關(guān)系模型(relational model)和概率模型(probabilistic model)并沒有使用一個(gè)通用的數(shù)據(jù)模型處理不確定性數(shù)據(jù)，缺乏信息交換和共同理解的介質(zhì)，效率較低。因此，文中以雙時(shí)態(tài)模型、關(guān)系模型、概率模型、可能世界模型等技術(shù)為依托，以屬性圖為基礎(chǔ)提出用于處理數(shù)據(jù)不確定性的通用模型。該模型整合了數(shù)據(jù)的時(shí)間、不確定性和世系三個(gè)方面，實(shí)現(xiàn)具有增刪改查(create，read，update，delete，CRUD)基本操作的存儲(chǔ)系統(tǒng)，用于存儲(chǔ)和檢索歷史數(shù)據(jù)庫(kù)中的數(shù)據(jù)。此系統(tǒng)可以動(dòng)態(tài)增加節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系，并實(shí)現(xiàn)了不確定性數(shù)據(jù)的篩選查詢和模糊查詢。最后通過模型的數(shù)據(jù)存儲(chǔ)方式和系統(tǒng)的查詢效率的對(duì)比實(shí)驗(yàn)，分析該模型和存儲(chǔ)系統(tǒng)在存儲(chǔ)和檢索不確定性歷史數(shù)據(jù)的優(yōu)劣特性。

1 歷史數(shù)據(jù)不確定性問題的研究現(xiàn)狀

從90年代到今天，有許多互聯(lián)網(wǎng)數(shù)字化歷史的研究項(xiàng)目被提出，一個(gè)標(biāo)志性的項(xiàng)目是影谷項(xiàng)目(valley of the shadow)[2]。該數(shù)字人文項(xiàng)目通過當(dāng)時(shí)遺留的紙質(zhì)資料重現(xiàn)了美國(guó)南北戰(zhàn)爭(zhēng)時(shí)期富蘭克林縣民眾的真實(shí)生活。國(guó)內(nèi)數(shù)字人文項(xiàng)目在文物保護(hù)和古籍修復(fù)方面最受關(guān)注?！皵?shù)字敦煌”項(xiàng)目以3D打印、測(cè)繪遙感等技術(shù)將莫高窟內(nèi)外形態(tài)和洞內(nèi)文物精確掃描、修復(fù)還原并以數(shù)字形式保存，以供石窟保護(hù)、敦煌學(xué)研究和文化旅游。歷史事件標(biāo)記和鏈接項(xiàng)目(HEML)[3]提出一個(gè)表示具有嵌套結(jié)構(gòu)和世系的歷史事件的模型，并通過資源描述框架(resource description framework，RDF)編碼將HEML連接到語(yǔ)義Web。基于歷史數(shù)據(jù)庫(kù)概念建模的SyMoGIH項(xiàng)目[4]，提供了可擴(kuò)展的本體來(lái)表示和檢索數(shù)據(jù)庫(kù)中的歷史事實(shí)，用于管理歷史事件的關(guān)系、來(lái)源、不確定性和世系。

從目前的研究現(xiàn)狀來(lái)看，歷史數(shù)據(jù)庫(kù)的研究雖然也實(shí)現(xiàn)了數(shù)據(jù)庫(kù)編碼和查詢功能，但是對(duì)于描述歷史數(shù)據(jù)庫(kù)中的不確定性數(shù)據(jù)的通用語(yǔ)義框架還未實(shí)現(xiàn)。文中整合時(shí)間模型的擴(kuò)展、不確定性數(shù)據(jù)管理技術(shù)以及對(duì)于數(shù)據(jù)世系的處理方法這三個(gè)方面來(lái)提出不確定性歷史數(shù)據(jù)的數(shù)學(xué)模型。

1.1 不確定性歷史數(shù)據(jù)的時(shí)間

第一個(gè)需要解決的問題是歷史數(shù)據(jù)庫(kù)中的時(shí)間信息處理，時(shí)間信息可用于指示歷史事件何時(shí)發(fā)生及何時(shí)記錄。雙時(shí)態(tài)數(shù)據(jù)庫(kù)包含有效時(shí)間和事務(wù)時(shí)間(版本控制)，既能管理對(duì)象歷史，又能管理數(shù)據(jù)庫(kù)本身的歷史。對(duì)象歷史信息(例如：“1992年，約翰住在哪里？”)由有效時(shí)間提供，數(shù)據(jù)庫(kù)歷史信息(例如：“1992年，數(shù)據(jù)庫(kù)認(rèn)為John住在哪里？”)由事務(wù)時(shí)間提供。

Koncilia提出了COMET[5]元模型的雙時(shí)態(tài)擴(kuò)展，此擴(kuò)展支持有效時(shí)間和事務(wù)時(shí)間，以表示有關(guān)在數(shù)據(jù)庫(kù)中存儲(chǔ)和更改了哪些數(shù)據(jù)。LIVE[6]是一個(gè)具有許多存儲(chǔ)派生關(guān)系的應(yīng)用程序設(shè)計(jì)的完整數(shù)據(jù)庫(kù)管理系統(tǒng)，實(shí)現(xiàn)了修改基礎(chǔ)數(shù)據(jù)時(shí)需要簡(jiǎn)單的版本控制功能。

1.2 不確定性歷史數(shù)據(jù)的不確定性

第二個(gè)需要解決的問題是關(guān)于歷史數(shù)據(jù)的不確定性。許多不確定性理論用于處理不確定性的各個(gè)方面，例如信仰函數(shù)、概率區(qū)間、可能性理論和模糊集理論。最常用的模型是可能世界模型[7](possible worlds model)，該模型從一個(gè)不確定性數(shù)據(jù)庫(kù)演化出很多確定的可能世界實(shí)例，所有實(shí)例的概率之和為1。

Plewe等[8]提出了一個(gè)不確定的時(shí)間實(shí)體模型來(lái)描述不確定性的類型，并解釋各種不確定性的問題和原因。周傲英等[9]對(duì)已有的不確定性數(shù)據(jù)管理技術(shù)進(jìn)行了總結(jié)，列舉了多種針對(duì)不確定數(shù)據(jù)的數(shù)據(jù)模型。Aggarwal等[10]從算法與應(yīng)用角度綜述了不確定數(shù)據(jù)管理技術(shù)。HeisenData[11]項(xiàng)目將現(xiàn)有的確定性數(shù)據(jù)管理框架與不確定性查詢處理技術(shù)相結(jié)合，使得新增的功能模塊能夠嵌入到現(xiàn)有的框架中，增強(qiáng)其性能。

1.3 不確定性歷史數(shù)據(jù)的世系

數(shù)據(jù)產(chǎn)生并隨著事件推移而演化的整個(gè)過程被稱為數(shù)據(jù)的世系，包含了在各種異構(gòu)數(shù)據(jù)源間的數(shù)據(jù)演化過程[12]。不確定性歷史數(shù)據(jù)的世系分析是基于數(shù)據(jù)產(chǎn)生和演變的過程來(lái)跟蹤數(shù)據(jù)不確定性的來(lái)源[13]。

目前對(duì)于不確定性數(shù)據(jù)世系管理方法研究的有Trio系統(tǒng)[14]，該系統(tǒng)是斯坦福大學(xué)基于ULDB(uncertainty-lineage database)模型，主要研究不確定數(shù)據(jù)管理技術(shù)，針對(duì)不確定數(shù)據(jù)的世系分析技術(shù)提出了TriQL查詢語(yǔ)言。

2 基于圖數(shù)據(jù)庫(kù)的不確定性數(shù)據(jù)模型

在之前不確定性數(shù)據(jù)的研究中，一般用關(guān)系型數(shù)據(jù)庫(kù)來(lái)處理數(shù)據(jù)。關(guān)系型數(shù)據(jù)庫(kù)是使用關(guān)系模型來(lái)組織數(shù)據(jù)的數(shù)據(jù)庫(kù)，即在表中將信息與字段關(guān)聯(lián)起來(lái)從而存儲(chǔ)數(shù)據(jù)。關(guān)系型數(shù)據(jù)庫(kù)對(duì)于語(yǔ)義描述的準(zhǔn)確性不佳、對(duì)于復(fù)雜模型建模困難、擴(kuò)展性差且查詢效率低。文中使用Neo4j圖數(shù)據(jù)庫(kù)來(lái)處理數(shù)據(jù)的不確定性?；趯傩詧D結(jié)構(gòu)分別加入時(shí)間區(qū)間、概率值和世系信息等元素，整合出通用的不確定性歷史數(shù)據(jù)庫(kù)模型。

2.1 Neo4j圖數(shù)據(jù)庫(kù)

圖數(shù)據(jù)庫(kù)(graph database，GDB)是使用圖結(jié)構(gòu)來(lái)表示和存儲(chǔ)具有語(yǔ)義查詢的節(jié)點(diǎn)、邊和屬性的數(shù)據(jù)的數(shù)據(jù)庫(kù)。Neo4j使用圖形來(lái)表示數(shù)據(jù)及其之間的關(guān)系，其基本單元是節(jié)點(diǎn)、關(guān)系和屬性。

在可擴(kuò)展方面，關(guān)系型數(shù)據(jù)庫(kù)嚴(yán)格的模式約束使得已經(jīng)存在的數(shù)據(jù)庫(kù)擴(kuò)展變得非常困難，而Neo4j具有良好的可擴(kuò)展性，可以動(dòng)態(tài)增加節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系，并且能輕易擴(kuò)展到上億級(jí)別節(jié)點(diǎn)和關(guān)系，且不需要重構(gòu)數(shù)據(jù)庫(kù)。在查詢數(shù)據(jù)方面，關(guān)系型數(shù)據(jù)庫(kù)則需要大量的連接操作(join operations)，不僅復(fù)雜且費(fèi)時(shí)，而Neo4j是圍繞圖形進(jìn)行數(shù)據(jù)建模，其查詢效率只與它附近的節(jié)點(diǎn)的數(shù)量成正比而和圖的整體規(guī)模無(wú)關(guān)，并利用其免索引鄰接(index-free adjacency)特性實(shí)現(xiàn)快速、高效的圖遍歷能力，從而提高了查詢速度。

總體來(lái)說(shuō)，圖數(shù)據(jù)庫(kù)應(yīng)用圖形理論來(lái)表達(dá)和存儲(chǔ)實(shí)體及實(shí)體之間的關(guān)系信息，與關(guān)系型數(shù)據(jù)庫(kù)相比，圖數(shù)據(jù)庫(kù)更直觀、更靈活、擴(kuò)展性更強(qiáng)，查詢效率更高，且非常適合大數(shù)據(jù)的存儲(chǔ)和檢索。

2.2 標(biāo)簽屬性圖

Neo4j是基于標(biāo)簽屬性圖(labeled property graphs，LPG)的數(shù)據(jù)庫(kù)，LPG是一個(gè)有向圖，由節(jié)點(diǎn)(nodes)、關(guān)系(relationship)、屬性(properties)和標(biāo)簽(labels)組成，提供了探索和圖形化描述連接數(shù)據(jù)的方法。節(jié)點(diǎn)和關(guān)系都包含屬性，屬性由key/value鍵值對(duì)表示。LPG是關(guān)于數(shù)據(jù)的存儲(chǔ)和查詢的有向圖，所以文中以此為基礎(chǔ)建立數(shù)學(xué)模型。

定義1 屬性[15](property)：屬性p=(k,v)是一個(gè)鍵值對(duì)，其中k∈Σ是有限集合，v∈D是一個(gè)線性的可數(shù)的無(wú)限域。其中包含所有屬性的無(wú)限集P表示如下：P=Σ×D。

定義2 屬性圖[15](property graph)：屬性圖是指用有向圖的方式建模并在圖中存儲(chǔ)數(shù)據(jù)的通用數(shù)據(jù)結(jié)構(gòu)。屬性圖可以用元組G=(V,E,?,?,λ,π)描述。(V,E,?,?,λ)是一個(gè)邊標(biāo)記的有向圖，其中V是頂點(diǎn)集，E是邊集；?是從E到V的映射，將每條邊與其源節(jié)點(diǎn)(source node)相關(guān)聯(lián)；?為從E到V的映射，將每條邊與其目標(biāo)節(jié)點(diǎn)(target node)相關(guān)聯(lián)；λ是從E到Σ的映射，將每條邊與其標(biāo)簽(label)相關(guān)聯(lián)；π是指從(V∪E)到2P的映射。

例1：圖1是基于定義2用實(shí)際數(shù)據(jù)表示的屬性圖。由元組Ge=(Ve,Ee,?e,?e,λe,πe)描述。圓圈表示節(jié)點(diǎn)，圓圈間的連線表示邊，邊上的文字表示其關(guān)系的標(biāo)簽，長(zhǎng)方形里是節(jié)點(diǎn)和邊的屬性，其中屬性的鍵為屬性的標(biāo)簽。包括以下元素：

Ve={Alice,Bob}

Ee={e1,e2}

?e(e1)=Alice，?e(e1)=Bob，λe(e1)='known'

?e(e2)=Bob，?e(e2)=Alice，λe(e2)='hasfriend'

πe(Alice)={〈'birthyear','1995'〉，〈'job','teacher'〉}

πe(Bob)={〈'gender','male'〉}

πe(e1)=?

πe(e2)={〈'happenedin','Nantes'〉}

圖1 屬性圖

2.3 數(shù)據(jù)模型的建立

歷史數(shù)據(jù)模型以定義2的屬性圖和知識(shí)圖(knowledge graphs)為基礎(chǔ)，在此基礎(chǔ)上處理歷史數(shù)據(jù)的時(shí)間、不確定性和世系三個(gè)方面。歷史數(shù)據(jù)模型的實(shí)現(xiàn)步驟如圖2所示。

圖2 實(shí)現(xiàn)歷史數(shù)據(jù)模型的步驟

2.3.1 核心模型

基于屬性圖添加了實(shí)體U(entity)和從節(jié)點(diǎn)到實(shí)體的映射μ:V→U，得到擴(kuò)展屬性圖。在圖數(shù)據(jù)庫(kù)模型中，節(jié)點(diǎn)常用來(lái)表示實(shí)體，但由于同一個(gè)實(shí)體可以存在于不同的時(shí)間段并具有不同的屬性，所以對(duì)應(yīng)于不同的節(jié)點(diǎn)，即存在節(jié)點(diǎn)到實(shí)體的映射。

定義3 擴(kuò)展屬性圖(extended property graph，EPG)：擴(kuò)展屬性圖用元組(Σ,U,V,E,ρ,μ,π)描述。(Σ,V,E,ρ)是一個(gè)邊標(biāo)記的有向圖，其中Σ是有限集合，即一組標(biāo)簽集；V是一組節(jié)點(diǎn)集，E是一組邊集；ρ:E→V×Σ×V將邊映射到所謂的關(guān)系(relationship)，即連接兩個(gè)節(jié)點(diǎn)的邊有一個(gè)標(biāo)簽；U是一組實(shí)體集；μ:V→U是從節(jié)點(diǎn)到實(shí)體的映射；π:V∪E→2P是從EPG的節(jié)點(diǎn)和邊到一組鍵值對(duì)屬性的映射

例2：基于定義3，用實(shí)際數(shù)據(jù)表示的EPG如下：

Σ={birthyear,job,gender,knows,hasfriend,ha-ppenedin}

V={Alice,Bob}

E={knows,hasfriend}

ρ:{Alice×knows×Bob},{Bob×hasfriend×Alice}

U={Alice,Bob}

μ(Alice)=Alice,μ(Bob)=Bob

π(Alice)={birthyear:1995,job:teacher}

π(Bob)={gender:male}

π(hasfriend)={happenedin:Nantes}

π(knows)={}

μ映射遵循從節(jié)點(diǎn)到實(shí)體的一對(duì)一的對(duì)應(yīng)關(guān)系，是常規(guī)樹形圖中的雙射映射。同時(shí)用Ω=V∪E來(lái)表示圖中的結(jié)構(gòu)元素集合，即節(jié)點(diǎn)和邊是EPG的知識(shí)片段(knowledge snippets，KS)。

2.3.2 針對(duì)時(shí)間的處理

許多歷史事件無(wú)法指定精確的日期，所以用模糊日期而不是具體的時(shí)間點(diǎn)，同時(shí)需要在模糊日期間隔兩端的范圍加上最小和最大持續(xù)時(shí)間的范圍。對(duì)于歷史事實(shí)中的時(shí)間信息，最好使用一段時(shí)間間隔來(lái)表示時(shí)間的開始和結(jié)束。有效時(shí)間數(shù)據(jù)庫(kù)用于記錄現(xiàn)實(shí)世界中的信息，并可以修改時(shí)態(tài)數(shù)據(jù)。但是在修改之后將不保留先前的值，即數(shù)據(jù)庫(kù)無(wú)法返回到更改之前的狀態(tài)，因此要用事務(wù)時(shí)間來(lái)指示歷史記錄何時(shí)發(fā)現(xiàn)歷史事件并將其記錄在歷史數(shù)據(jù)庫(kù)中。

為了繼續(xù)建立歷史數(shù)據(jù)模型，基于定義3，用標(biāo)準(zhǔn)雙時(shí)態(tài)(bi-temporal)來(lái)處理數(shù)據(jù)的時(shí)間。事務(wù)時(shí)間(transaction time)表示管理KS的版本信息，有效時(shí)間(valid time)表示數(shù)據(jù)實(shí)際存在的時(shí)間信息。將離散時(shí)域T視為線性排序的時(shí)間點(diǎn)序列。用區(qū)間代數(shù)[16]來(lái)管理由端點(diǎn)a和端點(diǎn)b組成的在T上的時(shí)間段(a,b)，其中a≤Tb，用I(T)表示T上的一組區(qū)間。在EPG的基礎(chǔ)上添加了事務(wù)時(shí)間τt和有效時(shí)間I(T)，得到了雙時(shí)態(tài)擴(kuò)展屬性圖。

定義4 雙時(shí)態(tài)擴(kuò)展屬性圖(bi-temporal extended property graph，BT-EPG))：BT-EPG用元組G=(Σ,U,V,E,ρ,μ,π,τt)描述。

·基于定義3，在每個(gè)KS上添加事務(wù)時(shí)間τt和有效時(shí)間I(T)：實(shí)體映射：μ:V→U×I(T)表示從節(jié)點(diǎn)映射到實(shí)體和實(shí)體的有效時(shí)間；關(guān)系映射：ρ:E→V×Σ×V×I(T)表示從邊映射到關(guān)系和關(guān)系的有效時(shí)間。

·τt:Ω→I(T)將每個(gè)知識(shí)片段映射到事務(wù)時(shí)間段，即該數(shù)據(jù)實(shí)際存在于數(shù)據(jù)庫(kù)的時(shí)間。

例3：圖3是BT-EPG的示例，與EPG相比增加了知識(shí)片段的有效時(shí)間和事務(wù)時(shí)間，沒有有效時(shí)間的KS和事務(wù)時(shí)間從0開始都意味著時(shí)間是無(wú)限的，即從負(fù)無(wú)窮大到正無(wú)窮大，表示可以處于任何時(shí)間。

Σ={birthyear,job,gender,knows,hasfriend,ha-ppenedin}

V={Alice,Bob}

E={knows,hasfriend}

ρ:{Alice×knows×Bob×[2001,2003),Alice×knows×Bob×[2003,2007),

Bob×hasfriend×Alice×[2003,2005)}

U={Alice,Bob}

μ(Alice)=Alice×[2001,2003),

μ(Alice)=Alice×[2003,2007),μ(Bob)=Bob

π(Alice)={birthyear:1995,job:author}，

π(Alice)={birthyear:1995,job:teacher}

π(Bob)={gender:male}

π(hasfriend)={happenedin:Nantes}

π(knows)={}

τt={Alice×2009,Alice×0,Bob×0,knows×0,hasfriend×2003}

圖3 BT-EPG實(shí)例

2.3.3 針對(duì)不確定性的處理

歷史數(shù)據(jù)庫(kù)中的一個(gè)關(guān)鍵問題是對(duì)數(shù)據(jù)不確定性的處理。文中提出遵循概率塊獨(dú)立不相交模型來(lái)表示歷史數(shù)據(jù)庫(kù)中的不確定性。在BT-EPG的基礎(chǔ)上添加了知識(shí)片段的互斥關(guān)系⊕和概率值w，并將事務(wù)時(shí)間和有效時(shí)間由時(shí)間段擴(kuò)展為開始時(shí)間和結(jié)束時(shí)間的時(shí)間區(qū)間來(lái)表明其時(shí)間的不確定性，得到了概率塊獨(dú)立不相交雙時(shí)態(tài)擴(kuò)展屬性圖。

定義5 概率塊獨(dú)立不相交雙時(shí)態(tài)擴(kuò)展屬性圖(probabilistic block-independent-disjoint bi-temporal extended property graph，PBID-BT-EPG)：PBID-BT-EPG用元組ξ=(Σ,U,V,E,ρ,μ,π,τt,⊕,w)描述，其中(Σ,U,V,E,ρ,μ,π,τt)是一個(gè)雙時(shí)態(tài)擴(kuò)展屬性圖，Ω=V∪E遵循概率塊獨(dú)立不相交模型。

·在知識(shí)片段Ω中存在實(shí)體之間互為互斥關(guān)系⊕：x⊕y(?y∈[x]⊕)，指x和y不能出現(xiàn)在同一個(gè)可能的雙時(shí)態(tài)擴(kuò)展屬性圖中；

·映射w:Ω→[0,1]將概率值w(x)與每個(gè)實(shí)體或關(guān)系x∈Ω相關(guān)聯(lián)。

例4：圖4是PBID-BT-EPG的示例，與BT-EPG相比增加了互斥關(guān)系⊕和每個(gè)知識(shí)片段Ω的概率值w，還有對(duì)時(shí)間信息的擴(kuò)展。

圖4 PBID-BT-EPG實(shí)例

Σ={birthyear,job,gender,knows,hasfriend,happ-enedin}

V={Alice,Bob}

E={knows,hasfriend}

ρ:{Alice×knows×Bob×[2000,2004)[2003,2005)，

Alice×knows×Bob×[2002,2005)[2004,2008)，

Bob×hasfriend×Alice×[2001,2004)[2003,2006)}

μ(Alice)=Alice×[2000,2001)[2002,2005),

μ(Alice)=Alice×[2000,2005)[2004,2008),

μ(Bob)=Bob

π(Alice)={birthyear:1995,job:author},

π(Alice)={birthyear:1995,job:teacher}

π(Alice)={birthyear:1996,job:teacher}

π(Bob)={gender:male}

π(hasfriend)={happenedin:Nantes}

π(knows)={}

τt={Alice×2009,Alice×0,Alice×2008,Bob×0,knows×0,hasfriend×2003}

{Alice×0}⊕{Alice×2008}

w={Alice×0.4,Alice×0.5,Alice×0.5,Bob×0.3,knows×0.6,konws×0.9,hasfriend×0.8}

其概率值計(jì)算如下：

2.3.4 針對(duì)世系的處理

歷史數(shù)據(jù)庫(kù)應(yīng)使用來(lái)源信息支持?jǐn)?shù)據(jù)的可追溯性或譜系(lineage)，可以用來(lái)區(qū)分歷史數(shù)據(jù)的來(lái)源屬于主要來(lái)源(primary source)還是次要來(lái)源(secondary source)。

定義6 世系圖(provenance graph，ProvG)：ProvG用元組P=(Σ,S,Ω,L)描述，(Σ,S∪Ω,L)是一個(gè)帶有邊緣標(biāo)記的有向圖，其中X=S∪Ω是節(jié)點(diǎn)的集合，L?X×Σ×X是邊的集合。

在世系圖中，每一個(gè)KS都可以看作是世系圖的節(jié)點(diǎn)，邊上的標(biāo)簽是指從主要和次要來(lái)源的分析方式。例如：自然語(yǔ)言處理、圖像處理、光學(xué)字符識(shí)別等。圖5中的Source 1即為初級(jí)來(lái)源，Source 2即為次級(jí)來(lái)源。

圖5 世系圖

2.3.5 全功能歷史數(shù)據(jù)庫(kù)

定義7 歷史數(shù)據(jù)庫(kù)(historical database，HDB)：歷史數(shù)據(jù)庫(kù)由元組Κ=(ξ,P)描述，其中ξ是概率塊獨(dú)立不相交雙時(shí)態(tài)擴(kuò)展屬性圖，P是世系圖。

將用于處理歷史數(shù)據(jù)時(shí)間和不確定性的PBID-BT-EPG和用于處理世系的ProvG結(jié)合起來(lái)，即得到全功能的歷史數(shù)據(jù)庫(kù)(HDB)。

3 基于Neo4j和SQLite存儲(chǔ)系統(tǒng)的實(shí)現(xiàn)

為了存儲(chǔ)和檢索歷史數(shù)據(jù)庫(kù)中的不確定性歷史數(shù)據(jù)，文中實(shí)現(xiàn)了一個(gè)由Neo4j圖形數(shù)據(jù)庫(kù)和SQLite關(guān)系數(shù)據(jù)庫(kù)組成的存儲(chǔ)系統(tǒng)(Neo4j and SQLite storage systems，NSSS)。該系統(tǒng)使用Python語(yǔ)言，用來(lái)創(chuàng)建、插入、更新、刪除歷史數(shù)據(jù)庫(kù)中的歷史數(shù)據(jù)信息并實(shí)現(xiàn)了高效率的查詢功能。Neo4j使用Cypher對(duì)圖數(shù)據(jù)庫(kù)進(jìn)行CRUD操作，在該系統(tǒng)中，Neo4j用于存儲(chǔ)KS及其屬性、標(biāo)簽等數(shù)據(jù)。SQLite用于存儲(chǔ)時(shí)間信息、實(shí)體、概率及互斥關(guān)系等數(shù)據(jù)。

插入操作可用于插入節(jié)點(diǎn)，關(guān)系以及節(jié)點(diǎn)和關(guān)系的屬性等。插入節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)、關(guān)系和它們的屬性和ID將添加到Neo4j圖數(shù)據(jù)庫(kù)中，實(shí)體、有效時(shí)間和事務(wù)時(shí)間、概率和ID等信息將插入到SQLite關(guān)系中數(shù)據(jù)庫(kù)。對(duì)于同一個(gè)實(shí)體，可能存在有不同時(shí)間信息的不同節(jié)點(diǎn)。插入關(guān)系有兩種方法。一種是直接插入新的節(jié)點(diǎn)及其關(guān)系，另一個(gè)是將關(guān)系插入在已經(jīng)存在于數(shù)據(jù)庫(kù)中的節(jié)點(diǎn)上。在節(jié)點(diǎn)和關(guān)系插入之前，有必要檢查它們的時(shí)間限制(比如開始時(shí)間點(diǎn)不能晚于結(jié)束時(shí)間點(diǎn))。在插入屬性的時(shí)候，需要先查找到某個(gè)節(jié)點(diǎn)或者某個(gè)關(guān)系，再加入其對(duì)應(yīng)的屬性。

在刪除節(jié)點(diǎn)時(shí)，刪除的是某一個(gè)節(jié)點(diǎn)而不是某一個(gè)實(shí)體，所以要用實(shí)體和事務(wù)時(shí)間來(lái)查找節(jié)點(diǎn)后再刪除。刪除后此節(jié)點(diǎn)和與此節(jié)點(diǎn)關(guān)聯(lián)的關(guān)系和屬性都將在Neo4j和SQLite中刪除；當(dāng)刪除關(guān)系時(shí)，與此關(guān)系關(guān)聯(lián)的節(jié)點(diǎn)也將被刪除，所以要使用關(guān)系上的標(biāo)簽來(lái)找到此關(guān)系后刪除。但該節(jié)點(diǎn)只會(huì)在Neo4j中被刪除，并不在SQLite中刪除。因?yàn)榕c該節(jié)點(diǎn)相關(guān)聯(lián)的關(guān)系不存在了，但是此節(jié)點(diǎn)應(yīng)該仍然存在于數(shù)據(jù)庫(kù)中。

更新節(jié)點(diǎn)意味著更新事務(wù)時(shí)間的版本化(versioning)。例如存在一個(gè)實(shí)體U1，其事務(wù)時(shí)間為0。如果需要更新實(shí)體的版本信息且仍要保存之前的實(shí)體，就添加具有新的事務(wù)時(shí)間的實(shí)體U2，此時(shí)U1的版本信息就是[0,5]。如果用戶想要在某時(shí)間更新該實(shí)體U2，應(yīng)該插入一個(gè)屬性為Null和交易時(shí)間是7的實(shí)體U3。此時(shí)U2的版本信息是[5,7]。

對(duì)不確定圖數(shù)據(jù)庫(kù)進(jìn)行查詢處理具有十分重要的實(shí)際意義。該系統(tǒng)的讀取查詢實(shí)現(xiàn)了對(duì)于每一個(gè)節(jié)點(diǎn)、關(guān)系以及屬性即存在于歷史數(shù)據(jù)庫(kù)中每一項(xiàng)的查詢。此外還有對(duì)于不確定性數(shù)據(jù)的查詢，例如用其關(guān)鍵詞對(duì)于數(shù)據(jù)的篩選，用時(shí)間區(qū)間對(duì)數(shù)據(jù)的模糊查詢。

4 實(shí)驗(yàn)結(jié)果及分析

通過對(duì)比實(shí)驗(yàn)來(lái)分析HDB模型和NSSS系統(tǒng)的優(yōu)劣特性，一是通過HDB模型的數(shù)據(jù)存儲(chǔ)方式同關(guān)系型數(shù)據(jù)庫(kù)的對(duì)比，二是通過NSSS的查詢效率同SQL的對(duì)比。實(shí)驗(yàn)環(huán)境為Windows10操作系統(tǒng)，Intel core i7處理器和8 G內(nèi)存，開發(fā)工具為Spyder，代碼使用Python語(yǔ)言實(shí)現(xiàn)。

4.1 HDB模型的優(yōu)劣分析

為了分析HDB模型在處理不確定性歷史數(shù)據(jù)上的優(yōu)劣性，以圖4的實(shí)際數(shù)據(jù)為例，研究了在關(guān)系型數(shù)據(jù)庫(kù)和HDB模型中數(shù)據(jù)的存儲(chǔ)方式。在關(guān)系型數(shù)據(jù)庫(kù)中，這些數(shù)據(jù)的存儲(chǔ)方式如圖6所示。

圖6 關(guān)系型數(shù)據(jù)庫(kù)的存儲(chǔ)方式

而在HDB模型中，這些數(shù)據(jù)可以組織成圖7的形式。不確定性歷史數(shù)據(jù)的節(jié)點(diǎn)和關(guān)系以及其屬性都存儲(chǔ)在Neo4j中，時(shí)間信息、實(shí)體、互斥關(guān)系和概率值都存儲(chǔ)在SQLite中。

圖7 在Neo4j和SQLite中存儲(chǔ)數(shù)據(jù)

圖8 在Neo4j和SQLite中增加數(shù)據(jù)

當(dāng)增加信息時(shí)，如加入一個(gè)新的節(jié)點(diǎn)并和已經(jīng)存在的節(jié)點(diǎn)存在關(guān)系，對(duì)于關(guān)系型數(shù)據(jù)庫(kù)來(lái)說(shuō)，為了能存儲(chǔ)增加的信息必須重構(gòu)圖7的數(shù)據(jù)表。然而在HDB模型中，則不需要重構(gòu)整個(gè)數(shù)據(jù)庫(kù)，僅僅需要?jiǎng)討B(tài)增加該節(jié)點(diǎn)和表示節(jié)點(diǎn)間的關(guān)系的邊即可，如圖8所示。可以得出基于Neo4j圖數(shù)據(jù)庫(kù)的HDB模型更加靈活、擴(kuò)展性更強(qiáng)。雖然從理論與技術(shù)的成熟度來(lái)說(shuō)，關(guān)系型數(shù)據(jù)庫(kù)相比于圖數(shù)據(jù)庫(kù)理論體系更加堅(jiān)實(shí)且有相當(dāng)成熟的實(shí)現(xiàn)，例如Oracle與SQL Server等。但Neo4j在處理數(shù)據(jù)不確定性方面優(yōu)勢(shì)更加明顯，其成熟度也在不斷發(fā)展和完善。

4.2 NSSS查詢效率分析

為了分析NSSS的查詢效率，使用了César劇院數(shù)據(jù)庫(kù)的歷史數(shù)據(jù)來(lái)測(cè)量查詢效率。分別在數(shù)據(jù)量為50、100、2 500、10 000和100 000的數(shù)據(jù)庫(kù)中查詢同一條數(shù)據(jù)所需要的時(shí)間，如表1所示。

表1 查詢效率對(duì)比 ms

由表1可知，文中的NSSS查詢效率比SQL要高，而且在處理大規(guī)模數(shù)據(jù)時(shí)更有優(yōu)勢(shì)。NSSS所用的Cypher語(yǔ)句不僅完全實(shí)現(xiàn)SQL語(yǔ)句的功能，而且能實(shí)現(xiàn)SQL不能實(shí)現(xiàn)的遍歷搜索功能。最重要的是，NSSS在大規(guī)模數(shù)據(jù)的查詢效率更有優(yōu)勢(shì)。

通過以上分析可以得出，當(dāng)數(shù)據(jù)量較小且數(shù)據(jù)對(duì)象間的關(guān)聯(lián)關(guān)系固定時(shí)，關(guān)系數(shù)據(jù)庫(kù)可以很好地工作。然而當(dāng)數(shù)據(jù)規(guī)模龐大、數(shù)據(jù)對(duì)象間的關(guān)系復(fù)雜且動(dòng)態(tài)變化時(shí)，文中提出的HDB模型和NSSS更有優(yōu)勢(shì)。

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

不確定性是數(shù)據(jù)的本質(zhì)特征。文中總結(jié)了當(dāng)前處理不確定性數(shù)據(jù)的方法，基于Neo4j圖數(shù)據(jù)庫(kù)研究了不確定性歷史數(shù)據(jù)。第一個(gè)主要工作是以屬性圖為基礎(chǔ)，提出用于處理數(shù)據(jù)不確定性的通用模型，該模型處理不確定性歷史數(shù)據(jù)的時(shí)間、不確定性和世系的問題。第二個(gè)主要工作實(shí)現(xiàn)了具有CRUD基本操作的存儲(chǔ)系統(tǒng)作為概念驗(yàn)證性實(shí)驗(yàn)，該系統(tǒng)用于存儲(chǔ)和檢索歷史數(shù)據(jù)庫(kù)中的數(shù)據(jù)。最后通過對(duì)比實(shí)驗(yàn)證明該HDB模型和NSSS是良好的處理不確定性數(shù)據(jù)的工具。

雖然文中提出了一個(gè)處理世系的數(shù)據(jù)模型，但是在存儲(chǔ)系統(tǒng)中沒有實(shí)現(xiàn)對(duì)于世系的處理。在未來(lái)的研究中，要在存儲(chǔ)系統(tǒng)中實(shí)現(xiàn)對(duì)世系的處理。此外要重點(diǎn)關(guān)注用于表示歷史空間數(shù)據(jù)的模型，并結(jié)合時(shí)間數(shù)據(jù)和空間數(shù)據(jù)來(lái)研究歷史數(shù)據(jù)的時(shí)空不確定性，這將為處理不確定性歷史數(shù)據(jù)提供更完整的模型。