基于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是良好的处理不确定性数据的工具。

虽然文中提出了一个处理世系的数据模型，但是在存储系统中没有实现对于世系的处理。在未来的研究中，要在存储系统中实现对世系的处理。此外要重点关注用于表示历史空间数据的模型，并结合时间数据和空间数据来研究历史数据的时空不确定性，这将为处理不确定性历史数据提供更完整的模型。