基于Neo4j不確定性數據處理技術的研究

郭林斐，劉廣鐘

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

0 引 言

隨著計算機技術、網絡技術和數據挖掘技術等的迅速發展，科學研究呈現出明顯的數據密集型特征。數字人文學[1](digital humanities)作為計算機與人文科學的跨學科領域，得到了前所未有的關注和研究。數字歷史(digital history)是數字人文學的一個重要分支，其使用計算機、因特網和軟件系統之類的通信技術進行歷史分析、演示和研究。

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

1 歷史數據不確定性問題的研究現狀

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

從目前的研究現狀來看，歷史數據庫的研究雖然也實現了數據庫編碼和查詢功能，但是對于描述歷史數據庫中的不確定性數據的通用語義框架還未實現。文中整合時間模型的擴展、不確定性數據管理技術以及對于數據世系的處理方法這三個方面來提出不確定性歷史數據的數學模型。

1.1 不確定性歷史數據的時間

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

Koncilia提出了COMET[5]元模型的雙時態擴展，此擴展支持有效時間和事務時間，以表示有關在數據庫中存儲和更改了哪些數據。LIVE[6]是一個具有許多存儲派生關系的應用程序設計的完整數據庫管理系統，實現了修改基礎數據時需要簡單的版本控制功能。

1.2 不確定性歷史數據的不確定性

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

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

1.3 不確定性歷史數據的世系

數據產生并隨著事件推移而演化的整個過程被稱為數據的世系，包含了在各種異構數據源間的數據演化過程[12]。不確定性歷史數據的世系分析是基于數據產生和演變的過程來跟蹤數據不確定性的來源[13]。

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

2 基于圖數據庫的不確定性數據模型

在之前不確定性數據的研究中，一般用關系型數據庫來處理數據。關系型數據庫是使用關系模型來組織數據的數據庫，即在表中將信息與字段關聯起來從而存儲數據。關系型數據庫對于語義描述的準確性不佳、對于復雜模型建模困難、擴展性差且查詢效率低。文中使用Neo4j圖數據庫來處理數據的不確定性。基于屬性圖結構分別加入時間區間、概率值和世系信息等元素，整合出通用的不確定性歷史數據庫模型。

2.1 Neo4j圖數據庫

圖數據庫(graph database，GDB)是使用圖結構來表示和存儲具有語義查詢的節點、邊和屬性的數據的數據庫。Neo4j使用圖形來表示數據及其之間的關系，其基本單元是節點、關系和屬性。

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

總體來說，圖數據庫應用圖形理論來表達和存儲實體及實體之間的關系信息，與關系型數據庫相比，圖數據庫更直觀、更靈活、擴展性更強，查詢效率更高，且非常適合大數據的存儲和檢索。

2.2 標簽屬性圖

Neo4j是基于標簽屬性圖(labeled property graphs，LPG)的數據庫，LPG是一個有向圖，由節點(nodes)、關系(relationship)、屬性(properties)和標簽(labels)組成，提供了探索和圖形化描述連接數據的方法。節點和關系都包含屬性，屬性由key/value鍵值對表示。LPG是關于數據的存儲和查詢的有向圖，所以文中以此為基礎建立數學模型。

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

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

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

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 數據模型的建立

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

圖2 實現歷史數據模型的步驟

2.3.1 核心模型

基于屬性圖添加了實體U(entity)和從節點到實體的映射μ:V→U，得到擴展屬性圖。在圖數據庫模型中，節點常用來表示實體，但由于同一個實體可以存在于不同的時間段并具有不同的屬性，所以對應于不同的節點，即存在節點到實體的映射。

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

例2：基于定義3，用實際數據表示的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)={}

μ映射遵循從節點到實體的一對一的對應關系，是常規樹形圖中的雙射映射。同時用Ω=V∪E來表示圖中的結構元素集合，即節點和邊是EPG的知識片段(knowledge snippets，KS)。

2.3.2 針對時間的處理

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

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

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

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

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

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

Σ={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實例

2.3.3 針對不確定性的處理

歷史數據庫中的一個關鍵問題是對數據不確定性的處理。文中提出遵循概率塊獨立不相交模型來表示歷史數據庫中的不確定性。在BT-EPG的基礎上添加了知識片段的互斥關系⊕和概率值w，并將事務時間和有效時間由時間段擴展為開始時間和結束時間的時間區間來表明其時間的不確定性，得到了概率塊獨立不相交雙時態擴展屬性圖。

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

·在知識片段Ω中存在實體之間互為互斥關系⊕：x⊕y(?y∈[x]⊕)，指x和y不能出現在同一個可能的雙時態擴展屬性圖中；

·映射w:Ω→[0,1]將概率值w(x)與每個實體或關系x∈Ω相關聯。

例4：圖4是PBID-BT-EPG的示例，與BT-EPG相比增加了互斥關系⊕和每個知識片段Ω的概率值w，還有對時間信息的擴展。

圖4 PBID-BT-EPG實例

Σ={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}

其概率值計算如下：

2.3.4 針對世系的處理

歷史數據庫應使用來源信息支持數據的可追溯性或譜系(lineage)，可以用來區分歷史數據的來源屬于主要來源(primary source)還是次要來源(secondary source)。

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

在世系圖中，每一個KS都可以看作是世系圖的節點，邊上的標簽是指從主要和次要來源的分析方式。例如：自然語言處理、圖像處理、光學字符識別等。圖5中的Source 1即為初級來源，Source 2即為次級來源。

圖5 世系圖

2.3.5 全功能歷史數據庫

定義7 歷史數據庫(historical database，HDB)：歷史數據庫由元組Κ=(ξ,P)描述，其中ξ是概率塊獨立不相交雙時態擴展屬性圖，P是世系圖。

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

3 基于Neo4j和SQLite存儲系統的實現

為了存儲和檢索歷史數據庫中的不確定性歷史數據，文中實現了一個由Neo4j圖形數據庫和SQLite關系數據庫組成的存儲系統(Neo4j and SQLite storage systems，NSSS)。該系統使用Python語言，用來創建、插入、更新、刪除歷史數據庫中的歷史數據信息并實現了高效率的查詢功能。Neo4j使用Cypher對圖數據庫進行CRUD操作，在該系統中，Neo4j用于存儲KS及其屬性、標簽等數據。SQLite用于存儲時間信息、實體、概率及互斥關系等數據。

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

在刪除節點時，刪除的是某一個節點而不是某一個實體，所以要用實體和事務時間來查找節點后再刪除。刪除后此節點和與此節點關聯的關系和屬性都將在Neo4j和SQLite中刪除；當刪除關系時，與此關系關聯的節點也將被刪除，所以要使用關系上的標簽來找到此關系后刪除。但該節點只會在Neo4j中被刪除，并不在SQLite中刪除。因為與該節點相關聯的關系不存在了，但是此節點應該仍然存在于數據庫中。

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

對不確定圖數據庫進行查詢處理具有十分重要的實際意義。該系統的讀取查詢實現了對于每一個節點、關系以及屬性即存在于歷史數據庫中每一項的查詢。此外還有對于不確定性數據的查詢，例如用其關鍵詞對于數據的篩選，用時間區間對數據的模糊查詢。

4 實驗結果及分析

通過對比實驗來分析HDB模型和NSSS系統的優劣特性，一是通過HDB模型的數據存儲方式同關系型數據庫的對比，二是通過NSSS的查詢效率同SQL的對比。實驗環境為Windows10操作系統，Intel core i7處理器和8 G內存，開發工具為Spyder，代碼使用Python語言實現。

4.1 HDB模型的優劣分析

為了分析HDB模型在處理不確定性歷史數據上的優劣性，以圖4的實際數據為例，研究了在關系型數據庫和HDB模型中數據的存儲方式。在關系型數據庫中，這些數據的存儲方式如圖6所示。

圖6 關系型數據庫的存儲方式

而在HDB模型中，這些數據可以組織成圖7的形式。不確定性歷史數據的節點和關系以及其屬性都存儲在Neo4j中，時間信息、實體、互斥關系和概率值都存儲在SQLite中。

圖7 在Neo4j和SQLite中存儲數據

圖8 在Neo4j和SQLite中增加數據

當增加信息時，如加入一個新的節點并和已經存在的節點存在關系，對于關系型數據庫來說，為了能存儲增加的信息必須重構圖7的數據表。然而在HDB模型中，則不需要重構整個數據庫，僅僅需要動態增加該節點和表示節點間的關系的邊即可，如圖8所示。可以得出基于Neo4j圖數據庫的HDB模型更加靈活、擴展性更強。雖然從理論與技術的成熟度來說，關系型數據庫相比于圖數據庫理論體系更加堅實且有相當成熟的實現，例如Oracle與SQL Server等。但Neo4j在處理數據不確定性方面優勢更加明顯，其成熟度也在不斷發展和完善。

4.2 NSSS查詢效率分析

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

表1 查詢效率對比 ms

由表1可知，文中的NSSS查詢效率比SQL要高，而且在處理大規模數據時更有優勢。NSSS所用的Cypher語句不僅完全實現SQL語句的功能，而且能實現SQL不能實現的遍歷搜索功能。最重要的是，NSSS在大規模數據的查詢效率更有優勢。

通過以上分析可以得出，當數據量較小且數據對象間的關聯關系固定時，關系數據庫可以很好地工作。然而當數據規模龐大、數據對象間的關系復雜且動態變化時，文中提出的HDB模型和NSSS更有優勢。

5 結束語

不確定性是數據的本質特征。文中總結了當前處理不確定性數據的方法，基于Neo4j圖數據庫研究了不確定性歷史數據。第一個主要工作是以屬性圖為基礎，提出用于處理數據不確定性的通用模型，該模型處理不確定性歷史數據的時間、不確定性和世系的問題。第二個主要工作實現了具有CRUD基本操作的存儲系統作為概念驗證性實驗，該系統用于存儲和檢索歷史數據庫中的數據。最后通過對比實驗證明該HDB模型和NSSS是良好的處理不確定性數據的工具。

雖然文中提出了一個處理世系的數據模型，但是在存儲系統中沒有實現對于世系的處理。在未來的研究中，要在存儲系統中實現對世系的處理。此外要重點關注用于表示歷史空間數據的模型，并結合時間數據和空間數據來研究歷史數據的時空不確定性，這將為處理不確定性歷史數據提供更完整的模型。