常识图谱行为标记主义发展的最新收场, 是东说念主工智能的进击基石.跟着常识图谱领域的日益扩大, 其数据不竭问题更加进击.一方面, 以文献体式保存常识图谱无法满足用户的查询、检索、推理、分析及各式应用需求; 另一方面, 传统数据库的关系模子与常识图谱的图模子之间存在显贵互异, 关所有这个词据库无法有用不竭大领域常识图谱数据.为了更好地不竭常识图谱melody marks 肛交, 语义Web领域发展出特地存储RDF数据的三元组库; 数据库领域发展出用于不竭属性图的图数据库.然而面前还莫得一种数据库系统被公以为是具有主导地位的常识图谱数据库.

面前, 领域为百万顶点(106)和上亿条边(108)的常识图谱数据集已不时见.通顺洞开数据2018年8月发布的LOD云图中许多常识图谱数据集领域跨越10亿条三元组.举例, 维基百科常识图谱DBpedia(> 30亿条)、地舆信息常识图谱LinkedGeoData(> 30亿条)和卵白质常识图谱UniProt(> 130亿条)等.各领域大领域常识图谱的构建和发布对常识图谱数据不竭建议了新的挑战.本文将投诚数据不竭领域的雅致传统, 以数据模子的结构和操作两大约素为干线, 对面前的常识图谱数据不竭表面、设施、技艺与系统等方面的磋议与实践进行综述.

数据模子是任何数据不竭领域的基础与中枢.各人皆知, 数据模子包括数据的结构、操作和拘谨.由于常识图谱数据不竭尚处于起步阶段, 常识图谱数据模子的结构和操作方面还未发展完善, 拘谨方面仅有尚在制定中的RDF Shapes拘谨言语[1]等少许磋议职责, 故而本文仅综述常识图谱数据模子中的结构和操作要素.本文起先先容面前常识图谱的两种主流数据模子:RDF图模子和属性图模子; 之后, 行为常识图谱数据模子的操作, 先容5种常识图谱查询言语, 包括SPARQL、Cypher、Gremlin、PGQL和G-CORE; 接着, 先容怎样使用各式存储不竭决议兑现常识图谱逻辑模子的物理存储, 包括基于关系的常识图谱存储不竭和原生常识图谱存储不竭; 然后, 探讨常识图谱上3种主要的查询操作类型, 即图模式匹配、导航式和分析型查询; 临了, 先容兑现了常识图谱数据模子的主流数据库不竭系统, 包括RDF三元组库和原生图数据库, 同期描写面前边向常识图谱的各式分散式系统与框架, 并简要先容常识图谱评测基准.本文临了对常识图谱数据不竭的当年磋议标的进行瞻望.行为阅读率领, 图 1给出了本综述各部天职容之间的总体阶梯图.

Fig. 1 A roadmap of the contents of this survey 图 1 本文各部天职容的总体阶梯图

接洽职责.面前, 尚未发现与本文相易使用数据模子要素行为干线对常识图谱数据不竭进行综述的文献.文献[2]对2002年之前的早期图数据模子进行了综述, 但这些图数据模子由于结构复杂均未成为自后常识图谱的默示基础.文献[3]对2006年之前的图模式匹配查询算法进行了综述, 图模式匹配查询是面前常识图谱的查询操作类型之一.文献[4]对RDF图模式进行了体式化界说, 对其上的基本图模式查询给出了若干表面收场.文献[5-7]是对于RDF图数据不竭的综述, 包括单机和分散式系统.文献[8]是对于图数据不竭的较新综述, 但其内容与本综述别离较大, 且莫得按照数据模子结构与操作要素伸开先容.文献[9]把稳在图数据查询处理方面进行综述, 包括RDF图和属性图上的图模式匹配和导航式查询, 但内容上侧重表面收场, 本文不仅涵盖了这些内容, 而且还包括了常识图谱数据不竭兑现技艺与系统, 同期本文比文献[9]多先容了PGQL和G-CORE两种查询言语.文献[10]综述了以顶点为中心的分散式图算计框架.文献[11]综述了分散式环境中的RDF存储和查询处理.文献[12]使用真确与合成数据集对主要的分散式SPARQL引擎进行了实验评估.文献[13]和文献[14]从分类体系和高层编程详尽角度综述了分散式图处理框架.文献[15]亦然大领域图数据的分散式处理平台综述, 但侧重于分析型处理任务.在汉文文献中, 文献[16]按照基于云算计平台、基于数据诀别和联邦式系统的分类综述了RDF图分散式存储和查询设施, 但莫得波及属性图数据不竭.文献[17]从图存储、图索引、图分割、图算计模子、音信通讯机制、图查询处理等方面综述了大领域图数据的分散式处理技艺, 但那时还未形成常识图谱数据模子.文献[18]仅就单机版块的图模式匹配查询进行了综述.最新的接洽综述包括:文献[19]主要先容了基于Pregel的分散式图处理框架的磋议推崇, 而本文第5.3节会在更广的范围内先容面向常识图谱数据不竭的分散式系统与框架; 文献[20]聚拢于谈论常识图谱上的推理设施与技艺, 而本文主题是常识图谱的数据不竭, 并在第6节中将常识图谱数据不竭对于实质和常识推理的支抓行为当年磋议标的之一.由于篇幅所限, 本文不波及常识图谱在时刻维度上的变化, 对于动态图的图模式匹配查询磋议综述可参见文献[21].

1 常识图谱数据模子

数据模子界说了数据的逻辑组织结构(structure)、其上的操作(operation)和拘谨(constraint), 决定了数据不竭所遴选的有用设施与战术, 对于存储不竭、查询处理、查询言语遐想均至关进击.关所有这个词据库长盛不衰的一个进击原因是关所有这个词据模子(relational data model)中精真金不怕火而通用的关捆绑构, 以及用具有严格数学界说的关系代数抒发关系上的操作和拘谨[22].使用图结构形容数据最早要追猜测档次数据模子(hierarchical data model)和网状数据模子(network data model):档次数据模子使用树结构默示数据, 树是一种特殊的图; 网状数据模子诚然支抓图结构, 但与自后的图数据模子有较大互异, 也持久未能成为主流数据模子.早期的若干图数据模子基本上是以图论中的图结构(G=(V, E), 其中, V是顶点集, E是边集)或其扩张行为数据结构[2]; 不错以为, 常识图谱数据模子是图数据模子的继承和发展.常识图谱数据模子基于图结构, 用顶点默示实体, 用边默示实体间的接洽, 这种一般和通用的数据默示正好好像天然地形容现实宇宙中事物的粗拙接洽.面前, 主流的常识图谱数据模子有两种: RDF图模子和属性图模子.底下分别进行先容.

1.1 RDF图模子

RDF全称为资源描写框架(resource description framework), 是万维网定约(World Wide Web consortium, 简称W3C)制定的在语义Web(semantic Web)上默示和交换机器可相识(machine-understandable)信息的模范数据模子[23].在RDF图中, 每个资源具有一个HTTP URI行为其唯一id; RDF图界说为三元组(s, p, o)的有限集合; 每个三元组默示是一个事实敷陈句, 其中, s是主语, p是谓语, o是宾语; (s, p, o)默示s与o之间具有接洽p, 或默示s具有属性p且其取值为o.底下给出RDF图的严格界说.

界说1(RDF图).设U、B和L为互不相交的无限集合, 分别代表URI、空顶点(blank node)和字面量(literal).一个三元组(s, p, o)$\in $(U$\cup $B)×U×(U$\cup $B$\cup $L)称为RDF三元组, 其中, s为主语, p为谓语, o为宾语.RDF图G是RDF三元组的有限集合.

图 2所示的RDF图示例描写了一个电影常识图谱, 其中包括电影(movie)Titanic、导演(director)James_ Cameron、演员(actor)Leonardo_DiCaprio和Kate_Winslet等资源以及这些资源上的若干属性及资源之间的执导(direct)和出演(acts_in)接洽.在RDF图示例中, 用椭圆默示资源, 用矩形默示字面量; 一条有向边偏执贯串的两个顶点对应于一条三元组, 尾顶点是主语, 边标签是谓语, 头顶点是宾语.资源所属的类型由RDF内置谓语rdf:type指定, 如三元组(James_Cameron, rdf:type, Director)默示James_Cameron是导演.为方便起见, 本文RDF图中资源和谓语URI称呼不祥了定名空间前缀(RDF内置称呼不不祥, 如rdf:type).对于本例中字面量的类型, 字符串放在双引号中, 整数195是电影分钟数, 定点数1.79E9和2.0E8分别是导演净财富和电影预算金额, 日历1954-08-16、1974-11-11和1975-10-05分别是导演和两位演员的出身日历.由于空顶点的引入不会对RDF数据不竭设施产生本质改变, 本文将RDF图中的空顶点等同为URI.

Fig. 2 An RDF graph example: Movie knowledge graph 图 2 RDF图示例:电影常识图谱

例1:图 2所示的RDF图的三元组集合体式为

G={(James_Cameron, rdf:type, Director), (James_Cameron, name, "James Cameron"),

(James_Cameron, birthDate, 1954-08-16), (James_Cameron, networth, 1.79E9),

(James_Cameron, directs, Titanic), (James_Cameron, acts_in, Titanic),

(Titanic, rdf:type, Movie), (Titanic, label, "Titanic(1997 film)"),

(Titanic, budget, 2.0E8), (Titanic, length, 195),

(Leonardo_DiCaprio, rdf:type, Actor), (Leonardo_DiCaprio, name, "Leonardo DiCaprio"),

(Leonardo_DiCaprio, birthDate, 1974-11-11), (Leonardo_DiCaprio, acts_in, Titanic),

(Kate_Winslet, rdf:type, Actor), (Kate_Winslet, name, "Kate Winslet"),

(Kate_Winslet, birthDate, 1975-10-05), (Kate_Winslet, acts_in, Titanic)}.

导演在此片中也出演了扮装, 但图 2并莫得包含出演(acts_in)的扮装信息.现实上, RDF图模子莫得对于顶点和边上属性的内置支抓.顶点上的属性可默示为宾语是字面量的三元组; 边上属性的默示需要使用额外的机制, 最常见的是哄骗“具体化(reification)”设施[24], 引入额外的顶点默示统统这个词三元组, 将边属性默示为以该顶点为主语的三元组.图 3给出了怎样使用“具体化”为acts_in边添加扮装(role)属性; 通过引入资源acts_in_1来默示三元组(James_Cameron, acts_in, Titanic), 并使用RDF内置谓语rdf:subject、rdf:predicate和rdf:object分别指明该条三元组的主语、谓语和宾语; 三元组(acts_in_1, role, "Steerage Dancer")为acts_in边添加了role属性, 即导演James_Cameron在影片Titanic中上演了“Steerage Dancer”这一扮装.为了精真金不怕火起见, 图 3中不祥了三元组(acts_in_1, rdf:type, rdf:Statement), 即指明新引入的资源acts_in_1的类型是三元组(RDF内置类型rdf:Statement默示一条三元组).

Fig. 3 Representation of edge attributes in RDF graphs using reification 图 3 RDF图中通过“具体化”设施默示边上的属性

从数据模子角度看, RDF图是一种特殊的有向标签图(directed labeled graphs).与平方有向标签图比较, RDF图的特殊性在于, 其三元组集合的本质使得一个三元组中的谓语也可行为另一个三元组的主语或宾语.反应在有向标签图中, 即边亦可行为顶点(如图 3中的边acts_in), 顶点与边杂乱非空.在数学上, 将这种图称为3-均匀超图(3-uniform hypergraph)[25].文献[4]给出了对于RDF图更加丰富的体式化界说, 包括RDF模式(RDF schema)[26]、基于模子论的语义和基本推理系统.需要指出的是, W3C为RDF图界说了基于描写逻辑(一阶谓词逻辑的可判定子集)的实质言语OWL[27], 可描写倡导之间更为复杂的逻辑关系, 并给出了相应的逻辑推理法则.RDF图上的实质推理超出了本文的范围, 感兴味的读者可参见文献[28].

1.2 属性图模子

属性图是另一种不竭常识图谱数据常用的数据模子.与RDF图模子比较, 属性图模子对于顶点属性和边属性具备内置的支抓.面前, 属性图模子被图数据库业界粗拙聘任, 包括着名的图数据库Neo4j[29].最近, 由图数据不竭领域学术界和工业界成员共同组成的关联数据基准委员会(Linked Data Benchmark Council, 简称LDBC)也正在以属性图为基础对图数据模子和图查询言语进行模范化[30].底下给出属性图的体式化界说.

界说2(属性图).属性图G是5元组(V, E, ρ, λ, σ), 其中, (1) V是顶点的有限集合; (2) E是边的有限集合且V$ \cap $E=$\emptyset $; (3)函数ρ:E→(V×V)将边域联到顶点对, 如ρ(e)=(v1, v2)默示e是从顶点v1到顶点v2的有向边; (4)设Lab是标签集合, 函数λ:(V$\cup $E)→Lab为顶点或边赋予标签, 如v$\in $V(或e$\in $E)且λ(v)=l(或λ(e)=l), 则l为顶点v(或边e)的标签; (5)设Prop是属性集合, Val是值集合, 函数σ:(V$\cup $E)×Prop→Val为顶点或边域联属性, 如v$\in $V(或e$\in $E)、p$\in $Prop且σ(v, p)=val(或σ(e, p)=val), 则顶点v(或边e)上属性p的值为val.

图 4给出了图 2中电影常识图谱的属性图示例.在属性图中, 每个顶点和边都具有唯一id(如顶点v1、边e2); 顶点和边均可具有标签(如顶点v1上的标签Director、边e2上的标签acts_in), 其作用基本相称于RDF图中的资源类型; 顶点和边上均可具有一组属性, 每个属性由属性名和属性值组成(如顶点v1上的属性name="James Cameron"、边e2上的属性role="Steerage Dancer").不错看出, 哄骗边属性的界说, 图 4比图 2加多了出演的扮装信息, 同期又莫得改变属性图的合座结构(RDF图的“具体化”设施加多了顶点和边, 改变了图结构).

Fig. 4 A property graph example: Movie knowledge graph 图 4 属性图示例:电影常识图谱

例2:图 4所示的属性图G=(V, E, ρ, λ, σ), 其中,

V={v1, v2, v3, v4}, E={e1, e2, e3, e4},

ρ(e1)=(v1, v2), ρ(e2)=(v1, v2), ρ(e3)=(v3, v2), ρ(e4)=(v4, v2),

λ(v1)=Director, λ(v2)=Movie, λ(v3)=Actor, λ(v4)=Actor,

λ(e1)=directs, λ(e2)=acts_in, λ(e3)=acts_in, λ(e4)=acts_in,

σ(v1, name)="James Cameron", σ(v1, birthDate)=1954-08-16, σ(v1, networth)=1.79E9,

σ(v2, label)="Titanic(1997 film)", σ(v2, length)=195, σ(v2, budget)=2.0E8,

σ(v3, name)="Leonardo DiCaprio", σ(v3, birthDate)=1974-11-11, σ(v4, name)="Kate Winslet",

σ(v4, birthDate)=1975-10-05, σ(e2, role)="Steerage Dancer", σ(e3, role)="Jack Dawson",

σ(e4, role)="Rose DeWitt".

在界说2中, 每个顶点或边上只可有一个标签, 每个属性也只可具有一个值; 如果允许顶点或边上具有多个标签, 可将界说中的函数l改为λ:(V$\cup $E)→$\mathbb{P}$(Lab), 如果允许属性对应多个值, 可将函数σ改为σ:(V$\cup $E)×Prop→$\mathbb{P}$(Val), 其中, $\mathbb{P}$(X)默示集合X的幂集.在现实中, 不同图数据库不竭系统可能有不同规定, 举例, 在Neo4j兑现的属性图模子中, 顶点上不错有多个标签, 边上只可有一个标签, 每个属性唯唯独个值.

例3:图 5给出了一个关系更为复杂的酬酢蚁集常识图谱的属性图模子, 其中, 顶点标签有3种:Person、Post和Tag; 边标签有5种:knows、likes、dislikes、hasTag和follower.Person顶点上可有属性firstName、lastName、gender和country; Post顶点上可有属性text和lang; Tag顶点上可有属性label; likes和dislikes边上可有属性date.细心到图中存在回路(cycle), 如v4e1v1e5v5e8和v2e3v3e4.

Fig. 5 A property graph example: Social network knowledge graph 图 5 属性图示例:酬酢蚁集常识图谱 1.3 两种数据模子比较

表 1给出了RDF图模子和属性图模子这两种主流常识图谱数据模子的比较, 包括数据模子的结构、操作和拘谨3个方面.RDF图模子的抒发力强于属性图模子, 是因为RDF的超图本质, 一条三元组的谓语可在另一条三元组中作东语或宾语, 而属性图中顶点和边属性上却不可再界说属性[31].总体说来, 由于RDF图具有加强的逻辑表面配景, 加之语义Web多年的模范化职责, 其数据模子性情相对完善, 但也恰是因为表面性过强而影响了其在工业界的扩充; 属性图诚然在表面基础方面还不够完善, 然而跟着Neo4j等图数据库的应用, 其赢得了较强的用户招供度.

Table 1 The comparison of the RDF graph model and the property graph model 表 1 RDF图模子和属性图模子的比较 2 常识图谱查询言语

常识图谱查询言语主要兑现了常识图谱数据模子的操作部分.面前, RDF图的模范查询言语是SPARQL; 属性图查询言语主要有Cypher、Gremlin、PGQL和G-CORE.从查询言语的类型看, 除了Gremlin属于进程式(procedural)言语外, SPARQL、Cypher、PGQL和G-CORE均属于声明式(declarative)言语.底下分别加以先容.对于各式常识图谱查询言语的比较请参见后文的表 5.

Table 5 The comparison of knowledge graph query languages 表 5 常识图谱查询言语比较 2.1 SPARQL

SPARQL是W3C制定的RDF常识图谱模范查询言语[36].SPARQL从语法上模仿了SQL.SPARQL查询的基本单位是三元组模式(triple pattern), 多个三元组模式可组成基本图模式(basic graph pattern).SPARQL支抓多种运算符, 将基本图模式扩张为复杂图模式(complex graph pattern).SPARQL 1.1版块引入了属性旅途(property path)机制[40]以支抓RDF图上的导航式查询.底下使用图 2所示的电影常识图谱RDF图, 通过示例先容SPARQL言语的基本功能.

例4:查询1950年之后出身的财富大于1.0E9的导演执导的电影的出演演员.

SELECT?x4?x5

WHERE {?x1 rdf:type Director.?x1 birthDate?x2.FILTER (?x2 > =1950-01-01).

?x1 networth?x3.FILTER(?x3 > 1.0E9).?x1 directs?x4.?x5 acts_in?x4.}

查询收场:

SELECT子句指明要复返的收场变量; WHERE子句指明查询条目; “?x1 rdf:type Director.”是三元组模式, 其中, rdf:type和Director是常量, ?x1是变量(SPARQL中的变量以?起首), 句点默示一条三元组模式的收场.图 6给出了例4对应的查询图, 不错看出, 每个三元组模式对应一条边, 由5个三元组模式组成了基本图模式; 要津字FILTER用于指明过滤条目, 对变量匹配收场按条目进行筛选; 加上了FILTER过滤后基本图模式, 临了组成复杂图模式查询.

Fig. 6 A complex graph pattern query: A SPARQL example 图 6 复杂图模式查询:SPARQL示例

例5:查询具有有限多步“互助距离(collaborative distance)”的两名演员.

SELECT?x1?x2

WHERE{?x1 (acts_in/^acts_in)*?x2.FILTER (?x1!=?x2).?x1 rdf:type Actor.?x2 rdf:type Actor.}

查询收场:

该查询用到了SPARQL 1.1中的属性旅途功能兑现导航式查询, 现实上, (acts_in/^acts_in)*是正则抒发式, 匹配0步到多步“互助距离”, 其中, 运算符/默示旅途贯串(path concatenation), 运算符^默示反向旅途(inverse path), 运算符*默示克林闭包(Kleene closure).使用FILTER将?x1和?x2匹配到并吞演员的情况过滤掉.

SPARQL经过W3C的模范化进程, 具有精准界说的语法和语义.齐备的SPARQL 1.1语法与语义请参见文献[36](W3C推选模范).文献[41]最早给出了SPARQL语义、复杂度和抒发力接洽的表面收场.W3C推选模范中图模式是包语义(bag semantics), 属性旅途中的闭包算子(即*和+)是集合语义(set semantics).文献[42, 43]的磋议职责平直影响了SPARQL 1.1属性旅途语义的详情, 即用“存在式(existential)”的集合语义取代了之前草案中“数旅途式(counting paths)”的包语义, 从而裁减了SPARQL属性旅途的算计复杂度.同期, SPARQL 1.1中还包括特地用于RDF图数据更新和不竭的子言语SPARQL 1.1 Update[44].

2.2 Cypher

Cypher起先是图数据库Neo4j中兑现的属性图数据查询言语.2015年, Neo4j公司发起开源表情open Cypher(https://www.opencypher.org), 旨在对Cypher进行模范化职责, 为其他兑现者提供语法和语义的参考模范.诚然Cypher的发展面前仍由Neo4j主导, 但包括SAP HANA Graph[45]、Redis Graph[46]、AgensGraph[47]和Memgraph[48]等在内的图数据库产物照旧兑现了Cypher.Cypher的一个主要特色是使用“ASCII艺术(ASCII art)”语法抒发图模式匹配.底下通过例子先容Cypher言语的基本功能.使用的图数据是图 4所示的电影常识图谱和图 5所示的酬酢蚁集常识图谱.

例6:查询1950年之后出身的财富大于1.0E9的导演执导的电影的出演演员.

MATCH (x1:Director)-[:directs]- > (:Movie) < -[:acts_in]-(x2:Actor)

WHERE x1.networth > 1.0E9 AND x1.birthDate > =date("1950-01-01")

RETURN x2

查询收场:

本例与例4的SPARQL查策画题相易.MATCH子句用于指明要匹配的图模式, 顶点信息写在圆括号“()”中, 边信息写在方括号“[]”中, 属性信息写在花括号“{ }”中, 用“:”分开顶点(或边)变量和标签.在本例中, “(x1: Director)”默示该图模式顶点要匹配的数据图顶点标签为Director, 且变量x1会绑定到匹配收场顶点; “-[:directs]- > ”默示要匹配标签为directs的有向边; MATCH子句教导的图模式是一个以“(:Movie)”为中心、由两条边组成的星形图模式.这些语法阐发了Cypher怎样使用ASCII艺术体式抒发图查询.WHERE要津字与MATCH子句配合使用, 用于指定图模式匹配的拘谨条目.内置函数date用于将字符串转换为日历类型. RETURN子句用于复返收场变量.本例等价于SPARQL基本图模式查询.

例7:查询San Zhang平直和障碍坚忍的东说念主.

MATCH (x1:Person)-[:knows*]- > (x2:Person)

WHERE x1.firstName="San" AND x1.lastName="Zhang"

RETURN x1, x2

查询收场:

本例使用图 5行为常识图谱, 展示了Cypher的导航式查询功能.Cypher通过变长模式(variable-length pattern)匹配对导航式查询提供有限支抓.不同于SPARQL属性旅途, Cypher变长模式仅兑现了正则旅途查询(regular path query)的一个子集, 即传递闭包算子*只可作用在单唯独个边标签上, 如:knows*; 对比例5中SPARQL属性旅途对正则抒发式的齐备支抓.

同期, Cypher还提供了相应的语句进行属性图的数据更新操作, 包括图结构更新和属性更新.Cypher言语的官方文档请参见文献[29].最新的文献[37]给出了Cypher现时版块中枢查询功能的体式语法和语义界说, 并谈论了Cypher不才一版块将引入的新性情.

2.3 Gremlin

Gremlin是Apache TinkerPop图算计框架[38]提供的属性图查询言语.Gremlin是图遍历言语, 其履行机制是在图中沿着有向边进行导航式的游走.这种履行形貌决定了用户使用Gremlin需要指明具体的导航要领, 是以Gremlin是进程式言语.与受到SQL影响的声明式言语SPARQL和Cypher不同, Gremlin更像一种函数式的编程言语接口.底下通过例子来先容Gremlin言语的基本功能.使用的属性图是图 4所示的电影常识图谱.

例8:查询1950年之后出身的财富大于1.0E9的导演执导的电影的出演演员名字.

g.V().hasLabel('Director').has('birthDate', gte('1950-01-01'))

.has('networth', gt(1.0E9)).out('directs').in('acts_in').hasLabel('Actor').values('name')

查询收场:

Leonardo DiCaprio

Kate Winslet

本例使用Gremlin抒发基本图模式查询.g是图遍历对象, 即属性图.函数调用g.V()复返图中统统顶点集; 接着施加3个过滤条目, 函数hasLabel('Director')限定顶点标签为Director, 函数has('birthDate', gte('1950-01-01'))限定顶点上属性birthDate值大于等于'1950-01-01', 函数has('networth', gt(1.0E9))限定顶点上属性networth值大于1.0E9, 其中, 谓词gte和gt分别默示比较运算符≥和 > ;函数out('directs')复返由满足上述条目的顶点集启航, 沿有向边directs好像到达的顶点集, 即1950年之后出身的财富大于1.0E9的导演执导的电影顶点; 函数in('acts_in')复返从这些电影顶点启航, 沿着有向边acts_in的反标的好像到达的顶点集; 函数hasLabel('Actor')将不是Actor标签的顶点过滤掉, 因此收场中不包括James Cameron(诚然v1到v2也有acts_in边e2); 临了, 函数values('name')复返这些顶点的name属性值.由本例不错看出Gremlin的图遍历、进程式和函数式格调.底下, 咱们来对比该查询的SPARQL(例4)和Cypher(例6)版块.

例9:列出演员“Leonardo DiCaprio”与距其有限多步“互助距离”演员之间的全部旅途.

g.V().hasLabel('Actor').has('name', 'Leonardo DiCaprio').repeat(

out('acts_in').hasLabel('Movie').in('acts_in').hasLabel('Actor')

).emit().path()

查询收场:

[v[3], v[2], v[3]]

[v[3], v[2], v[4]]

[v[3], v[2], v[3], v[2], v[3]]

[v[3], v[2], v[3], v[2], v[4]]

…

本例展示了Gremlin的导航式查询.使用函数repeat相通履行指定的导航操作; 一步“互助距离”导航操作被履行了自便屡次; 使用emit()输出每次相通履行的求值收场; 使用path()输出整条导航线径.不错看出操作后得到了无尽多个匹配旅途, 原因是Gremlin默许语义是“自便旅途”语义, 对于旅途中顶点和边的相通出现莫得限制.旅途查询的不同语义将在第4节中给出谈论.

要了解Gremlin的全面语法功能, 请参见文献[38].面前, 还未见对于Gremlin体式语义方面的磋议职责.

2.4 PGQL

PGQL是Oracle在2016年建议的属性图查询言语[39], 支抓图模式匹配查询和导航式查询.PGQL在语法结构上参照SQL遐想, 同期查询复返与SQL相易的收场集, 可将其行为子查询镶嵌到SQL查询中.PGQL从Cypher模仿了ASCII艺术语法默示图模式; 与Cypher比较, PGQL齐备地支抓正则旅途查询语义; 与SPARQL属性旅途仅支抓边标签组成的正则旅途不同, PGQL通过旅途模式(path pattern)抒发式界说, 还支抓正则旅途中含有顶点标签条目以及顶点(或边)属性值比较, 在提高了属性图上正则旅途查询抒发力(expressiveness)的同期保抓求值复杂度(complexity)不变.底下给出一个PGQL查询示例, 请对比例5和例9.

例10:列出与演员“Leonardo DiCaprio”距离有限多步“互助距离”的演员姓名和诞辰.

PATH collaborate AS ()-[:acts_in]- > (:Movie) < -[:acts_in]-()

SELECT x2.name, x2.birthDate

FROM movie_graph

MATCH (x1:Actor)-/:collaborate*/- > (x2:Actor)

WHERE x1.name='Leonardo DiCaprio' AND id(x1) < > id(x2)

查询收场:

查询起首使用PATH要津字指定名为“collaborate”旅途模式“()-[:acts_in]- > (:Movie) < -[:acts_in]-()”; 与SQL一致, SELECT子句用于复返查询收场变量, FROM子句指明图数据, WHERE子句给出过滤条目, 其中, PGQL内置函数id(x)复返顶点或边x的标记id; 在MATCH子句中, “-/:collaborate*/- > ”默示匹配“collaborate”旅途模式自便屡次.通过这种形貌不错抒发出自便复杂的正则旅途查询.

面前, PGQL仅有Oracle PGX一种兑现版块[49].对于PGQL最新版块1.1的语法和语义请参见文献[50].

2.5 G-CORE

G-CORE是由LDBC图查询言语职责组(LDBC Graph Query Language Task Force)遐想的属性图查询言语.G-CORE言语的遐想主义是充分模仿和和会各式已有图查询言语的优点, 在查询抒发力和求值复杂度之间寻求最好均衡[30].G-CORE与已有图查询言语比较:(1)查询的输入输出均是图, 澈底兑现了图查询言语的可组合性(composability); (2)将旅途行为与顶点和边同等进击的图查询处理基本元素.为此, G-CORE在属性图模子的基础上进行扩张, 界说了旅途属性图模子(path property graph model, 简称PPG).

界说3(旅途属性图). PPG是7元组G=(V, E, P, ρ, δ, λ, σ), 其中, (1) V是顶点的有限集合, E是边的有限集合, P是旅途的有限集合, V, E, P互不相交; (2)函数ρ:E→(V×V)将边域联到顶点对, 如ρ(e)=(v1, v2)默示e是从顶点v1到顶点v2的有向边; (3)设Seq(X)默示集合X中元素组成的序列, 函数δ:P→Seq(V$\cup $E)将旅途映射到顶点和边轮流组成的序列, 如p$\in $P, δ(p)=(v1, e1, v2, …, vn, en, vn+1), 其中, (ⅰ) vi$\in $V(1≤i≤n+1);(ⅱ) ei$\in $E, ρ(ei)=(vi, vi+1)或ρ(ei)=(vi+1, vi)(1≤i≤n); (4)设Lab是标签集合, 函数λ:(V$\cup $E$\cup $P)→Lab为顶点、边或旅途赋予标签; (5)设Prop是属性集合, Val是值集合, 函数σ:(V$\cup $E$\cup $P)×Prop→Val为顶点、边或旅途关联属性.

从PPG的界说不错看出, 旅途已与顶点和边同为图数据模子中的“一等公民”.与顶点和边相易, 旅途也不错有标签和属性, 旅途属性不错描写属于旅途的信息, 如旅途长度、导航支出等.底下给出一个G-CORE查询示例, 请对比例9和例10.

例11:列出演员“Leonardo DiCaprio”与距其有限多步“互助距离”演员之间的最短旅途及旅途长度.

PATH collaborate=()-[:acts_in]- > (:Movie) < -[:acts_in]-()

CONSTRUCT (x1)-/@p: collaborate_distance {distance:=c}/- > (x2)

MATCH (x1:Actor)-/SHORTEST p〈~collaborate*〉 COST c/- > (x2:Actor)

ON movie_graph

WHERE x1.name='Leonardo DiCaprio' AND x1!=x2

查询收场:

在G-CORE中, 每个查询均使用CONSTRUCT子句复返图行为查询收场, 这保证了查询的可组合性, 即一个查询的输出不错平直行为另一个查询的输入.PATH要津字模仿自PGQL, 用于界说旅途模式, 以组成自便复杂的正则旅途查询, 这里界说的旅途模式collaborate默示两名演员之间的互助关系, 即共同出演一部电影.G-CORE中@前缀教导的变量p默示存储旅途(stored path), 即归天存储在图数据库中的旅途; CONSTRUCT子句构建的图由存储旅途@p组成, @p的标签为collaborate_distance, 具有属性distance, 由顶点x1导航到顶点x2.MATCH子句匹配由演员Leonardo DiCaprio与其他演员(变量x2, x1!=x2默示不可是并吞演员)之间的统统有限多步“互助距离”中的最短旅途, 即p〈~collaborate*〉, 其中, p是旅途变量, ~collaborate是对PATH界说的旅途模式的援用, *是克林闭包; COST c默示最短旅途代价为c, 默许代价即旅途长度, c行为属性值保存到存储旅途@p的属性distance中.可见, 查询收场是一条齐备的旅途信息.

面前, G-CORE仅有一个开源的语法涌现器[51], 还没特等据库系统兑现.对于G-CORE的详实语法和语义请参见文献[52].

3 常识图谱存储不竭

起先先容基于关系的常识图谱存储机制, 然后给出两种典型的原生常识图谱数据库的底层存储.

3.1 基于关系的常识图谱存储不竭

关所有这个词据库面前仍是使用最多的数据库不竭系统.基于关所有这个词据库的存储决议是面前常识图谱数据的一种主要存储设施.本末节将按照时刻发展规矩挨次先容各式基于关系的常识图谱存储决议, 包括:三元组表、水平表、属性表、垂直诀别、六重索引和DB2RDF.

3.1.1 三元组表

三元组表(triple table)是将常识图谱存储到关所有这个词据库的最苟简、最平直的办法, 即是在关所有这个词据库中建树一张具有3列的表, 该表的模式为

triple_table(subject, predicate, object)

subject、predicate和object这3列分别默示主语、谓语和宾语; 将常识图谱中的每条三元组存储为三元组表triple_table中的一溜记载.

例12:图 7是图 2所示电影常识图谱对应的三元组表, 一共有16行, 限于篇幅, 仅列出前7行.

Fig. 7 Triple table: An example 图 7 三元组默示例

三元组表存储决议诚然下里巴人, 但三元组表的行数与常识图谱的边数特地, 其最大问题在于将常识图谱查询翻译为SQL查询后会产生三元组表的多半自贯串操作.举例, 例4的SPARQL查询翻译为等价的SQL查询后如例13所示.一般自贯串的数量与SPARQL中三元组模式数量相称.当三元组表领域较大时, 多个自贯串操作将影响SQL查询性能.

聘任三元组表存储决议的代表是RDF数据库系统3store[53].

例13:在三元组表存储决议中, 将例4的SPARQL查询转换为等价的SQL查询.三元组表的表名为t.

SELECT t4.object, t5.subject

FROM t AS t1, t AS t2, t AS t3, t AS t4, t AS t5

WHERE t1.subject=t2.subject AND t2.subject=t3.subject AND t3.subject=t4.subject

AND t4.object=t5.object AND t1.predicate='rdf:type' AND t1.object='Director'

AND t2.predicate='birthDate' AND t2.object > ='1950-01-01' AND t3.predicate='networth'

AND t3.object > 1.0E9 AND t4.predicate='directs' AND t5.predicate='acts_in'

3.1.2 水平表

水平表(horizontal table)存储决议相通至极苟简.水平表的每行记载存储常识图谱中一个主语的统统谓语和宾语.现实上, 水平表相称于常识图谱的邻接表.水平表的列数是常识图谱中不同谓语的数量, 行数是常识图谱中不同主语的数量.

例14:图 8是图 2中电影常识图谱对应的水平表, 共有4行、10列.

Fig. 8 Horizontal table: An example 图 8 水平默示例

在水平表存储决议中, 例4中的SPARQL查询不错等价地翻译为例15中的SQL查询.可见, 与三元组表比较, 水平表存储决议使得查询大为简化, 自贯串操作由4个减少到2个.

例15:在水平表存储决议中, 将例4的SPARQL查询转换为等价的SQL查询.水平表的表名为t.

SELECT t2.subject, t3.subject

FROM t AS t1, t AS t2, t AS t3

WHERE t1.type='Director' AND t1.birthDate > ='1950-01-01' AND t1.networth > 1.0E9

AND t1.directs=t2.subject AND t3.acts_in=t2.subject

然而水平表的污点在于:(1)所需列的数量等于常识图谱中不同谓语数量, 在真确常识图谱数据聚拢, 不同谓语数量可能为几千个到上万个, 很可能超出关所有这个词据库所允许的表中列数量上限; (2)对于一溜来说, 仅在极少数列上具有值, 表中存在多半空值, 空值过多会影响表的存储、索引和查询性能; (3)在常识图谱中, 并吞主语和谓语可能具有多个不同宾语, 即一双多接洽或多值属性, 而水平表的一溜一列上只可存储一个值, 无法搪塞这种情况(不错将多个值用分隔符贯串存储为一个值, 但这违抗了关所有这个词据库遐想的第一范式); (4)常识图谱的更新常常会引起谓语的加多、修改或删除, 即水平表中列的加多、修改或删除, 这是对于表结构的改变, 资本很高.

聘任水平表存储决议的代表是早期的RDF数据库系统DLDB[54].

3.1.3 属性表

属性表(property table)存储决议是对水平表的细分, 将同类主语存到一个表中, 惩处了表中列数量过多的问题.例16给出了图 2所示电影常识图谱对应的属性表存储决议, 分为director(导演)、movie(电影)和actor(演员)3个表.

例16:图 9是图 2中电影常识图谱对应的属性表存储决议, 共由3个表组成.

Fig. 9 Property table: An example 图 9 属性表存储决议示例

在属性表存储决议中, 例4中的SPARQL查询不错等价地翻译为例17中的SQL查询.该查询与水平表上的等价查询(例15)比较, t1变为了director, t2变为了movie, t3变为了actor, 由自贯串变嫌为多表贯串, 而且每个表对应于一个类型, 省去了类型(type列)的判断, 提高了查询的可读性.

例17:在属性表存储决议中, 将例4的SPARQL查询转换为等价的SQL查询.

SELECT movie.subject, actor.subject

FROM director, movie, actor

WHERE director.birthDate > ='1950-01-01' AND director.networth > 1.0E9

AND director.directs=movie.subject AND actor.acts_in=movie.subject

属性表既克服了三元组表的自贯串问题, 又惩处了水平表中列数量过多的问题.现实上, 水平表即是属性表的一种极点情况, 即水平表是将统统主语划归为一类, 因此属性表中的空值问题得到很大的缓解.但属性表仍存在如下一些污点:(1)对于领域稍大的真确常识图谱数据, 主语的类别可能有几千到上万个, 需要建树几千到上万个表, 这常常跨越了关所有这个词据库的限制; (2)即使在并吞类型中, 不同主语具有的谓语集合也可能互异较大, 会酿成与水平表中肖似的空值问题; (3)水平表中存在的一双多接洽或多值属性存储问题在属性表中仍然存在.

聘任属性表存储决议的代表系统是RDF三元组库Jena[55].

3.1.4 垂直诀别

垂直诀别(vertical partitioning)存储决议是由好意思国麻省理工学院Abadi等东说念主在2007年建议的RDF数据存储设施[56].该设施为每种谓语建树一张两列的表(subject, object), 表中存放常识图谱中由该谓语贯串的主语和宾语, 表的总额量即常识图谱中不同谓语的数量.例18给出了图 2所示电影常识图谱对应的垂直诀别存储决议, 9种谓语对应着9张表, 每张表都唯独主语和宾语列.

例18:图 10是图 2所示电影常识图谱对应的垂直诀别存储决议, 共由9个表组成.

Fig. 10 Vertical partitioning: An example 图 10 垂直诀别存储决议示例

在垂直诀别存储决议中, 例4中的SPARQL查询不错等价地翻译为例1中的SQL查询.该查询波及到5张谓语表的贯串操作, 其中有3个“subject-subject”等值贯串.由于表中的行都按subject列进行排序, 可快速履行这种垂直诀别决议中最常用的贯串操作.

例19:在垂直诀别存储决议中, 将例4的SPARQL查询转换为等价的SQL查询.

SELECT directs.object, acts_in.subject

FROM type, birthDate, networth, directs, acts_in

WHERE type.subject=birthDate.subject AND birthDate.subject=networth.subject

AND networth.subject=directs.subject AND acts_in.object=directs.object

AND type.object='Director' AND birthDate.object > ='1950-01-01' AND networth.object > 1.0E9

与之前基于关所有这个词据库的常识图谱存储决议比较, 垂直诀别有一些凸起的优点:(1)谓语表仅存储出面前常识图谱中的三元组, 惩处了空值问题; (2)一个主语的一双多接洽或多值属性存储在谓语表的多行中, 惩处了多值问题; (3)每个谓语表都按主语列的值进行排序, 好像使用归并列序贯串(merge-sort join)快速履行不同谓语表的贯串查询操作.

不外, 垂直诀别存储决议依然存在如下几个污点:(1)需要创建的表的数量与常识图谱中不同谓语数量特地, 而大领域的真确常识图谱(如, DBpedia、YAGO、WikiData等)中谓语数量可能跨越几千个, 在关所有这个词据库中爱戴如斯领域的表需要破耗很大支出; (2)越是复杂的常识图谱查询操作, 需要履行的表贯串操作数量越多, 而对于未指定谓语的三元组查询, 将发生需要贯串全部谓语表进行查询的极点情况; (3)谓语表的数量越多, 数据更新爱戴代价越大, 对于一个主语的更新将波及多张表, 产生很高的更新时I/O支出.

聘任垂直诀别存储决议的代表数据库是SW-Store[57].

3.1.5 六重索引

六重索引(sextuple indexing)存储决议是对三元组表的扩张, 是一种典型的“空间换时刻”战术, 其将三元组全部6种排列对应地建树为6张表, 即spo(主语, 谓语, 宾语)、pos(谓语, 宾语, 主语)、osp(宾语, 主语, 谓语)、sop(主语, 宾语, 谓语)、pso(谓语, 主语, 宾语)和ops(宾语, 谓语, 主语).不丢丑出, 其中spo表即是底本的三元组表.六重索引通过6张表的贯串操作不仅缓解了三元组表的单表自贯串问题, 而且提高了某些典型常识图谱查询的着力.

六重索引决议的优点有:(1)常识图谱查询中的每种三元组模式查询都不错平直使用相应的索引进行快速前缀范围查找, 表 2给出了全部8种三元组模式查询好像使用的索引; (2)不错通过不同索引表之间的贯串操作平直加快常识图谱上的贯串查询.

Table 2 Triple pattern queries and usable indexes in sextuple indexing 表 2 六重索引决议下三元组模式查询和可使用的索引表

六重索引存储决议存在的问题包括:(1)诚然部分缓解了三元组表的单表自贯串问题, 但需要破耗6倍的存储空间支出、索引爱戴代价和数据更新时的一致性爱戴代价, 跟着常识图谱领域的增大, 该问题会更加凸起; (2)当常识图谱查询变得复杂时, 会产生多半的贯串索引表查询操作, 依然不可幸免索引表的自贯串.

使用六重索引设施的典型系统有RDF-3X[58]和Hexastore[59].

3.1.6 DB2RDF

DB2RDF是由IBM于2013年建议的一种面向实体的RDF常识图谱存储决议[60, 61], 该决议是以往RDF关系存储决议的一种衡量与折中, 既具备了三元组表、属性表和垂直诀别决议的部分优点, 又克服了这些决议的部分污点.三元组表的上风在于“行维度”上的机动性, 即存储模式不会随行的加多而变化; DB2RDF决议将这种机动性扩张到“列维度”上, 行将表的列行为谓语和宾语的存储位置, 而不将列与谓语进行绑定.插入数据时, 将谓语动态映射存储到某列; 决议好像确保将相易谓语映射到并吞组列上.

DB2RDF存储决议由4张表组成, 即:dph表、rph表、ds表和rs表; 例20给出了图 2所示电影常识图谱对应的DB2RDF存储决议.dph(direct primary hash)是存储决议的主表, 该表中一溜存储一个主语(subject列)偏执全部谓语(predi列)和宾语(vali列), 0≤i≤k, k一般是关所有这个词据库支抓的表中最大列数量; 如果一个主语的谓语数量大于k, 则一溜不及以容纳下一个实体, 将不才一溜存储第k+1到2k个谓语和宾语, 依此类推, 这种情况叫作溢出(spill); spill列是溢出标志, 即对于一溜能存储下的实体, 该行spill列为0, 对于溢出的实体, 该实体统统行的spill列为1.举例, 在例20的dph表中, 实体James_Cameron溢出, 其余实体均未溢出.

对于多值谓语的处理, 引入ds(direct secondary hash)表.当dph表中碰到一个多值谓语时, 则在相应的宾语处生成一个唯一的id值; 将该id值和每个对应的宾语存储为ds表的一溜.举例, 在图 2的基础上添加三元组(James_Cameron, directs, Avatar), 这时, directs就成为多值谓语, 在例20的dph表中, 在其宾语列val2中存储id值lid:1;在ds表中存储lid:1关联的两个宾语Titanic和Avatar.

现实上, dph表兑现了列的分享:一方面, 不同实体的相易谓语老是会被分拨到相易列上; 另一方面, 并吞列中不错存储多个不同的谓语.比如, 主语Leonardo_DiCaprio和Kate_Winslet的谓语acts_in都被分拨到pred4列, 同期, 该列还存储了主语Titanic的谓语length.恰是由于DB2RDF决议具备“列分享”机制, 才使得在关系表中最大列数量上限的情况下不错存储远超出该上限的谓语数量, 也好像有用地惩处水平表决议中存在的谓语寥落性空值问题.在真确的常识图谱中, 不同主语常常具有不同的谓语集合, 举例, 谓语birthDate唯独东说念主(person)才具有, 谓语budget唯独电影(movie)才具有, 这亦然好像兑现列分享的原因所在.

例20:图 11是图 2所示电影常识图谱对应的DB2RDF存储决议(rs默示不祥).

Fig. 11 DB2RDF: An example 图 11 DB2RDF存储决议示例

从常识图谱数据模子的角度来看, dph表和ds施展实上存储了实体顶点(主语)的出边信息(从主语经谓语到宾语); 为了提高查询处理着力, 还需要存储实体顶点的入边信息(从宾语经谓语到主语).为此, DB2RDF决议提供了rph(reverse primary hash)表和rs(reverse secondary hash)表.

例21:在DB2RDF存储决议中, 将例4的SPARQL查询转换为等价的SQL查询.

SELECT t4.subject, t5.elm

FROM dph AS t1, dph AS t2, ds AS t3, rph AS t4, ds AS t5

WHERE t1.subject=t2.subject AND t2.val2=t3.lid AND t3.elm=t4.subject AND t4.val1=t5.lid

AND t1.pred1='type' AND t1.val1='Director' AND t1.pred3='birthDate' AND t1.val3 > ='1950-01-01'

AND t1.pred4='networth' AND t1.val4 > 1.0E9 AND t2.pred2='directs' AND t4.pred1='acts_in'

在DB2RDF决议中, 谓语到列的映射是需要要点磋议的问题.因为关系表中最大列的数量是固定的, 该映射的两个优化主义是:(1)使用的列的数量不要跨越某个值m; (2)尽量减少将并吞主语的两个不同谓语分拨到并吞列的情况, 从而减少溢出风物, 因为溢出会导致查询时自贯串的发生.

谓语到列映射的一种设施是使用一组哈希函数, 将谓语映射到一组列编号, 并将谓语偏执宾语存储到这组列中的第1个空列上; 在一个主语对应的一溜中, 如果存储某谓语(偏执宾语)时, 哈希函数算计得出的这组列中的统统列都被之前存储的该主语的谓语占用, 则产生溢出, 到下一溜存储该谓语.举例, 表 3给出了谓语到列映射的哈希函数表, 其中包括h1和h2两个哈希函数, 映射了5个谓语到列编号组.比如, 当存储到三元组(James_ Cameron, directs, Titanic)时, 谓语directs被h1映射到列pred2, 被h2映射到列pred3, 但这两列都已被占用, 这时产生溢出, 将谓语directs溢出到下一溜的列pred2中存储, 如图 11的dph表所示.

Table 3 Predicate-to-column hash function table 表 3 谓语到列映射的哈希函数表

如果不错预先获取常识图谱的一个子集, 则不错哄骗常识图谱的内在结构优化谓语到列的映射.设施是将谓语到列的映射转换为图着色(graph coloring)问题.将一个主语上出现的不同谓语称为共现谓语(co-occurrence predicates), 主义是让共现谓语着上不同颜料(映射到不同列中), 非共现谓语不错着上相易颜料(映射到并吞列中), 并使所用颜料数最少.需要指出的是, 诚然图着色是经典的NP难问题, 但即使是真确常识图谱, 其不同谓语总额亦然相对较少的(一般在几千个领域上).

如果在大领域真确常识图谱中(如DBpedia), 图着色所需颜料数量跨越了关所有这个词据表的列数上限m, 则凭证某种战术(如最频繁使用的前k个谓语)考中一个谓语子集, 使得该谓语子集到列的映射满足图着色要求; 对于不在该子聚拢的谓语, 再使用前边提到的哈希函数组战术进行映射.

DB2RDF存储决议照旧兑现到了最新的IBM DB2数据库系统中[61].

3.2 原生常识图谱存储不竭

不同于基于关系的存储决议, 原生常识图谱存储是指特地为常识图谱而遐想的底层存储不竭决议.不同原生常识图谱数据库的物理和逻辑存储层遐想与兑现也各有互异.本末节考中两种具有代表性的原生常识图谱存储不竭决议进行先容:一种是面向属性图的Neo4j存储; 另一种是面向RDF图的gStore存储.

3.2.1 Neo4j

Neo4j是面前最流行的属性图数据库, 其原生图存储层的最大特色是具有“无索引邻接(index-free adjacency)”性情.所谓“无索引邻接”是指, 每个顶点爱戴着指向其邻接顶点的平直援用, 相称于每个顶点都可看作是其邻接顶点的一个“局部索引”, 用其查找邻接顶点比使用“全局索引”省俭多半时刻.这就意味着图导航操作代价与图大小无关, 仅与图的遍历范围成正比.

为了兑现“无索引邻接”, Neo4j将边也行为数据库的“一等公民”(即数据库中最基本、最中枢的倡导, 如关所有这个词据库中的“关系”), 属性图的顶点、边、标签和属性被分开存储在不同文献中.恰是这种将图结构与图上标签和属性分开存储的战术, 使得Neo4j具有高着力的图遍历才智.图 12给出了Neo4j 2.2版块中顶点和边记载的物理存储结构(其他版块可能有变化), 其中每个顶点记载占用15字节, 每个边记载占用34字节.

Fig. 12 Physical storage structures of vertex and edge records in Neo4j 图 12 Neo4j中顶点和边记载的物理存储结构

顶点记载的第0字节inUse是记载使用标志字节, 默示该记载是正在使用中照旧照旧删除并可回登科来装载新记载; 第1字节~第4字节nextRelId是与顶点相连的第1条边的id; 第5字节~第8字节nextPropId是顶点的第1个属性的id; 第9字节~第13字节labels是指向顶点标签存储的指针, 若标签较少会平直存储在此处; 第14字节extra用于存储一些里面使用的标志信息.

边记载第0字节inUse的含义与顶点记载相易, 是默示是否正被数据库使用的标志; 第1字节~第4字节firstNode和第5字节~第8字节secondNode分别是该边的肇始顶点id和收场顶点id; 第9字节~第12字节relType是指向该边的关系类型的指针; 第13字节~第16字节firstPrevRelId和第17字节~第20字节firstNext RelId分别为指向肇始顶点向前一个和后一个边记载的指针; 第21字节~第24字节secPrevRelId和第25字节~第28字节secNextRelId分别为指向收场顶点向前一个和后一个边记载的指针; 指向前后边记载的4个指针形成了两个“关系双向链”; 第29字节~第32字节nextPropId是边上的第1个属性的id; 第33字节firstInChain Marker是默示该边记载是否是“关系链”中第1笔记载的标志.

Neo4j好像兑现顶点和边快速定位的要津是“定长记载(fixed-size record)”存储决议, 以及将具有定长记载的图结构与具有变长记载的属性数据分开存储.举例, 一个顶点记载长度是15字节, 如果要查找id为99的顶点记载所在位置(id从0运行), 则可平直到顶点存储文献第1485(15×99)个字节处拜谒(存储文献从第0个字节运行).边记载亦然“定长记载”, 长度为34字节.这么, 数据库已知记载id不错O(1)的代价平直算计其存储地址, 从而幸免了全局索引中O(logn)的查找代价.

图 13是图 5所示顶点v2和v3偏执出边e3、e4、e6和e7的Neo4j物理存储结构, 展示了Neo4j中各式存储文献之间是怎样交互的.存储在顶点文献中的顶点v2和v3均有指针(nextPropId)指向存储在属性文献中各自的第1个属性记载; 也有指针(nextRelId)指向存储在边文献中各自的第1条边, 分别为边e3和e4.若要查找顶点属性, 可由顶点找到其第1个属性记载, 再沿着属性记载的单向链表进行查找; 若要查找一个顶点上的边, 可由顶点找到其第1条边, 再沿着边记载的双向链表进行查找; 当找到了所需的边记载后, 可由该边进一步找到边上的属性; 还可由边记载启航拜谒该边贯串的两个顶点记载(图 13所示虚线箭头).需要细心的是, 每个边记载现实上爱戴着两个双向链表, 一个是肇始顶点上的边, 一个是收场顶点上的边, 不错将边记载遐想为被肇始顶点和收场顶点共同领有, 用双向链表的上风在于, 不仅可在查找顶点上的边时进行双向扫描, 而且支抓在两个顶点间高着力地添加和删除边.这些操作除了记载字段的读取, 即是定长记载地址的算计, 均是O(1)时刻的高着力操作.可见, 恰是由于将边行为“一等公民”、将图结构兑现为定长记载的存储决议, 赋予了Neo4j行为原生图数据库的“无索引邻接”性情.

Fig. 13 Physical storage structures of property graphs in Neo4j 图 13 Neo4j中属性图的物理存储 3.2.2 gStore

gStore将RDF数据图中每个资源的统统属性和属性值映射到一个二进制位串上.具体而言, 对于每个属性或属性值, gStore都界说一个固定长度的位串并将位串中统统位置为0.然后, 哄骗若干个预先界说的字符串哈希函数将属性或属性值按照标记符映射到若干个小于位串长度的整数值, 进而将位串上这些值所对应的位置置为1.图 14给出了图 2所示James_Cameron在gStore中所对应编码的示例, 每个属性都对应一个8位的位串, 每个属性值都对应一个12位的位串.每个属性都按照其标记符由2个字符串哈希函数映射到2个小于8的正整数.举例, type通过2个哈希函数分别被映射到3和8, 然后ntype对应的位串第3位和第8位就被置为1.同理, 每个属性值都按照其标记符由3个字符串哈希函数映射到3个小于12的正整数.如Director通过3个哈希函数分别被映射到3、8和10, 然后Director所对应的位串相应位置就被置为1.

Fig. 14 The encoding technique of gStore 图 14 gStore的编码技艺

gStore将统统位串按照RDF图结构组织成一棵签章树(signature tree).在签章树的基础上, 如果RDF常识图谱中两个实体之间有一条边, 那么这两个实体所对应的签章树上的点也连上一条边, 且这条边被赋上属性的编码.如斯, gStore中统统实体的编码就被组织成一种新的树形索引——VS*树.VS*树被分为若干层, 每一层都是RDF数据图的摘抄.图 15裸露了一个VS*树的示例.基于VS*树, gStore不错完成高着力的数据存储、更新与查询操作.当进行SPARQL查询处理时, 将每个查询中的变量在这个VS*树上进行检索, 找到相应的候选解, 然后再将这些候选解通过贯串操作拼接起来.

Fig. 15 VS*-tree 图 15 VS*树 3.3 常识图谱存储决议比较

表 4给出了本节前边先容的8种常识图谱存储决议的比较.

Table 4 The comparison of knowledge graph storage schemes 表 4 常识图谱存储决议的比较 4 常识图谱查询操作

诚然第2节中先容的各式常识图谱查询言语在语法和语义上有所互异, 甚而格调迥然, 但这些查询言语均具备两种基本的查询机制:图模式匹配(graph pattern matching)和图导航(graph navigation).此外, 常识图谱的分析型查询是面前若干图处理框架的内置操作.

4.1 图模式匹配查询

图模式匹配查询是图查询言语中最基本、最进击的一类图查询操作; 基本图模式(basic graph pattern, 简称BGP)匹配又是图模式匹配查询的中枢.底下给出基本图模式的界说, 这里仅磋议RDF图和属性图的众人图结构部分, 即常识图谱G=(V, E).

界说4(基本图模式(BGP)).给定常识图谱G, 其上的基本图模式Q被界说为

$ { \wedge }_{1{ \le _i} \le m}\left( {{S_i}, {p_i}, {o_i}} \right), $

其中, (1) si、pi和oi是常量或变量(1≤i≤m); (2) (si, pi, oi)是三元组模式(1≤i≤m); (3) $\wedge $默示逻辑合取.

BGP现实上即是图上三元组模式的合取, 因此也称为合取查询(conjunctive query).BGP匹配查询存在两种语义界说, 即子图同态(subgraph homomorphism)和子图同构(subgraph isomorphism).

界说5(BGP匹配的子图同态语义).给定常识图谱G=(V, E)和其上的BGP Q $\wedge $1≤i≤m(si, pi, oi), 设s=(si, …, sm), p=(pi, …, pm), o=(oi, …, om), BGP Q的子图同态语义界说为:(1)设σ是从s、p和o到G中顶点集V的映射; (2) (G, σ)‘Q当且仅当$\forall $i$\in $[1, m]有(σ(si), s(pi), σ(oi))$\in $E; (3) Q(G)是统统使(G, σ)‘Q成立的σ集合.

界说5给出的是BGP匹配的子图同态语义, Q中的不同变量不错映射到G中的并吞顶点.另外, 还有要求更为严格的子图同构语义.现将这两种语义归纳如下.

(1) 子图同态语义.该语义即是界说5对应的语义, 找出G中与Q存在同构关系的全部子图, 允许Q中多个不同变量映射到G中的并吞个顶点上.BGP子图同态语义是界说其他更严格语义的基础, 在数据库表面领域已有若干磋议职责[64-68].面前, SPARQL言语中的BGP聘任的即为子图同态语义[36].举例, 在例5中, 如果去掉FILTER (?x1!=?x2), 会新增两条匹配, 即?x1和?x2都映射到顶点Leonardo_DiCaprio和Kate_Winslet.

(2) 子图同构语义.该语义在子图同态语义上加多限制, 目的是使得G中的映射保抓Q的结构.按照不同的严格进程, 子图同构语义又分为全无相通语义(no-repeated-anything semantics)、顶点无相通语义(no-repeated- vertex semantics)和边无相通语义(no-repeated-edge semantics).

a) 全无相通语义.该语义是在界说5子图同构语义基础上加上s是单射(injective)映射的限制, 即BGP Q中的全部变量都映射到常识图谱的不同顶点或边上.诚然SPARQL默许聘任子图同态语义, 但在例5中使用额外的条目FILTER (?x1!=?x2)赢得子图同构全无相通语义.

b) 顶点无相通语义.该语义只限制s(si)和σ(oi)为单射映射, 即BGP Q中的不同顶点变量映射到常识图谱的不同顶点上, 允许不同边变量映射到常识图谱的相易边上.

c) 边无相通语义.该语义需要将界说5中的σ对顶点和边的映射加以区别对待, 对于pi再行界说σ(pi)为单射映射, 即BGP Q中的不同边变量映射到常识图谱的不同边上, 允许不同顶点变量映射到常识图谱的相易顶点上.面前, Cypher言语聘任该语义[29].

同态和同构语义的区别是测验一个匹配之内是否允许顶点或边的相通匹配, 还需要磋议另一个维度上的语义区别, 即常识图谱G的统统匹配收场Q(G)中是否允许相通.

(1) 集合语义(set semantics).Q(G)界说为匹配的集合, 即Q(G)中不可包含相通的匹配.

(2) 包语义(bag semantics).Q(G)界说为匹配的包, 即一个匹配相通出现的次数等于与该匹配对应的不同映射的数量.

现实上, 单就BGP自身来讲, 不会出现相通的匹配, 集合和包语义是等价的.但当BGP扩张为复杂图模式后, 相通匹配就会出现.底下谈论复杂图模式.

从关所有这个词据不竭角度来看, BGP对应于天然贯串.在BGP的基础上扩张投影、过滤(弃取)、贯串、交、差和可选(左外贯串)等其他关系操作, 形成复杂图模式(complex graph pattern, 简称CGP).

(1) 投影(projection).Q(G)复返的变量集合偏执匹配值称为Q的输出变量.BGP默许输出变量为Q中统统变量.投影操作复返BGP中变量的指定子集行为输出变量.相称于关系代数中的投影操作.

(2) 过滤(filter).指定变量参与的条目抒发式, 过滤CGP匹配收场数量.相称于关系代数中的弃取操作.

(3) 贯串(join).CGP Q1和Q2通过贯串操作组成更复杂的CGP Q3, Q3的输出变量是Q1和Q2输出变量的并集, Q3的匹配收场通过贯串Q1和Q2的匹配收场赢得, 即当Q1和Q2输出变量的杂乱映射到相易常量时, Q1和Q2的匹配收场好像进行贯串.相称于关系代数中的贯串操作.

(4) 并(union)和差(difference).CGP Q1和Q2的并(差)组成CGP Q3, Q3的匹配收场是Q1和Q2的匹配收场的并(差)集.相称于关系代数中的并和差操作.

(5) 可选(optional).CGP Q1和Q2的可选操作组成CGP Q3, Q3的匹配收场中不仅包括Q1和Q2的贯串收场, 而且包括Q1中与Q2贯串不上的收场, 即Q3中包括Q1的全部收场.相称于关系代数中的左外贯串操作.

照旧讲解BGP求值在各式语义下均为NP绝对问题.文献[69]通过将图同态(graph homomorphism)问题规约到BGP子图同态语义讲解了NP难; 文献[70]通过将子图同构(subgraph isomorphism)问题规约到BGP子图同构语义讲解了NP难.按照查询言语求值复杂度分析传统[71], 诚然BGP的组合复杂度(combined complexity)是NP绝对的, 但如果将BGP Q固定, 仅将常识图谱G行为输入, 其数据复杂度(data complexity)不仅是多项式的, 而且还能在对数空间复杂度内完成求值[72].

CGP求值的组合复杂度在SPARQL言语上有多半磋议职责.在集合语义下, 包含投影、过滤、贯串和并操作的SPARQL CGP的组合复杂度仍然是NP绝对的; 如果CGP还包含差和可选操作, 则其相称于关系代数的抒发力, 组合复杂度升到PSPACE绝对[71]; 差操作(SPARQL中的MINUS要津字)已被讲解可用可选、过滤和贯串操作模拟, 是以莫得差操作的CGP仍然是PSPACE绝对的[73]; 甚而仅包含贯串和可选操作的CGP亦然PSPACE绝对的[74].可见, 可选操作是酿成CGP高复杂度的根源.对于包语义下的SPARQL, 其求值问题的组合复杂度相通是PSPACE绝对的[74].面前, 尚枯竭对于其他常识图谱查询言语CGP复杂度接洽的表面磋议职责.

在图模式匹配查询的求值算法方面, 数据库领域对于BGP有着较长的磋议历史, 蓄积了多半职责.求值的经典设施有基于图遍历的Ullmann[70]、Nauty[75]和VF2[76], 但这些设施的履行着力并不适用于大领域图数据.一般地, 大领域图上BGP求值的战术有如下3种:(1)聘任基于相似度的不精准匹配(inexact matching)语义代替子图同态或同构语义, 典型设施包括文献[77-79]; (2)聘任近似解(approximate solutions)代替最优解(optimal solutions), 典型设施包括文献[80-82]; (3)保抓子图同态或同构的精准语义不变, 基于“空间换时刻”战术构建体式万般的图索引, 聘任索引削减子图匹配搜索空间, 将该类设施依期间规矩列出, 主要包括:GraphGrep[83]、gIndex[84]、Closure-tree[85]、FG-Index[86]、Tree+Delta[87]、TreePi[88]、GDI[89]、GCoding[90]、QuickSI[91]、GraphQL[92]、GADDI[93]、SPath[94]、SING[95]、GraphGrepSX[96]、Lindex[97]、PathIndex[98]和SQBC[99].

战术(1)放置了精准子图匹配, 战术(2)不可找到最优解, 均无法满足常识图谱上对精准查询的需求.战术(3)诚然保抓了查询语义, 但现存设施存在3个方面的问题:(1)大多数设施针对由若干小图组成的图集合, 每个图的顶点和边数为几十到几百, 集合中小图的数量为几千到几万(实在验中广阔使用的AIDS数据集), 这与常识图谱具有百万领域节点和上亿领域边的情形大不相易; (2)即使是针对单个大图建议的GraphQL、GADDI和SPath设施, 其好像处理的数据领域仍无法满足常识图谱大图数据的要求(如文献[93]中领域最大的实验数据顶点和边数分别为6 410和53 844, 文献[92, 94]中使用的实验数据顶点和边数分别为3 112和12 519);(3)构建索引的时刻和空间复杂度均为超线性的(如最坏情况下SPath设施构建索引的时刻和空间复杂度分别为O(nm)和O(n2), n和m分别为顶点和边数), 使用这些设施对常识图谱构建索引并不现实.值得细心的是, Fan等东说念主频年来建议了一系列BGP查询新设施[100-103].这些设施的中枢念念想是使用比子图同态或同构拘谨更弱的图模拟(graph simulation)和有界模拟(bounded simulation)语义界说BGP求值, 从而使所提算法的时刻复杂度降为立方级.现实上, 该类设施改变了精准BGP语义且莫得使用任何索引结构, 是以仍可归类为战术(1).

面向RDF图的图模式匹配查询设施聚拢于战术(3).(1)以RDF-3X[58]和Hexastore[59]为代表的六重索引设施会创建6种不同排列的三元组索引.其问题在于, 需将图模式匹配拆分为较多的贯串操作, 多半中间收场的贯串影响性能.(2)以GRIN[104]和DOGMA[105]为代表的结构索引设施以结构相似度行为度量目的, 将RDF图进行诀别并建树结构索引, 之后在结构索引而非原始RDF图上履行图模式匹配, 但索引爱戴代价较高.(3)以BitMat[106]和TirpleBit[107]为代表的位图存储设施诚然省俭了存储空间, 但数据更新爱戴代价较大, 且进行查询优化的解放度在一定进程上受到了制约.(4)以gStore[63]和chameleon-db[108]为代表的图索引与匹配设施, 将SPARQL BGP查询分为过滤和匹配两个要领, 过滤基于图索引, 匹配聘任子图同构算法, 幸免使用贯串操作.

4.2 导航式查询

在图模式匹配查询中, 匹配收场是常识图谱的子图, 其中的旅途长度是固定的.常识图谱上另一种进击的查询形貌是导航式查询, 其匹配的旅途收场不可预先详情, 需要按照图的拓扑结构进行导航.举例, 第3节中例5查询“具有有限多步互助距离”的两名演员, 例7查询“San Zhang平直和障碍坚忍的东说念主”, 例9查询“演员Leonardo DiCaprio与距其有限多步互助距离演员之间的全部旅途”等均为导航式查询.

最苟简的导航式查询是判断两个顶点之间是否存在一条旅途, 即可达性查询(reachability query).已有多半磋议职责求解可达性查询, 接洽综述请参见文献[109].在现实应用中, 常常进一步要求收场旅途满足某种拘谨, 其中最常用的是正则旅途查询(regular path query, 简称RPQ).

界说2(正则旅途查询(RPQ)).给定常识图谱G=(V, E), 其边上标签集合为Σ; 在G中从顶点v0到vm的旅途ρ为序列v0a0v1a1v2…vm-1am-1vm, 其中, vi$\in $V, ai$\in $σ, (vi, ai, vi+1)$\in $E.旅途ρ的标签为字符串λρ=a0...am-1$\in $Σ*.G上的RPQ Q被界说为

$ {\rm{(}}\mathit{x}{\rm{, }}\mathit{r}{\rm{, }}\mathit{y}{\rm{)}} $

其中, (1) x和y是常量或变量; (2) r是Σ上的正则抒发式, 其递归界说为r::=ε|a|r/r|r|r|r*, a$\in $Σ, /、|和*分别是招引接、并和克林闭包运算.

界说7(RPQ的自便旅途语义).给定常识图谱G=(V, E)和其上的RPQ Q(x, r, y), Q的自便旅途语义界说为:Q(G)是G中统统标签满足正则抒发式r的旅途集合, 即Q(G)={ρ|λ(ρ)$\in $L(r)}.

由于常识图谱G中不错有环, Q(G)中的匹配旅途集合可能是无尽的, 这种情况下, RPQ的自便旅途语义是不可算计的.在现实应用中, 需要对该语义作念出限制, 使RPQ求值是可兑现的.

(1) 自便旅途语义(arbitrary path semantics).该语义即界说7给出的Q(G)复返全部满足正则抒发式r的旅途.天然, 在该语义下, Q(G)可能包含无尽多条旅途; 即使是有限多条旅途(莫得环), 陈设统统旅途亦然不可行的(复杂度已被讲解是#P绝对[42]).但基于该语义界说的“存在式”语义只关注两个顶点对之间是否存在一条满足条目的旅途, 即Q(G)={(x, y)|存在从x到y的旅途ρ使得λ(ρ)$\in $L(r)}, 幸免了引起高复杂度的“数旅途”问题[42, 43], 在现实兑现中是可行的.举例, SPARQL属性旅途遴选“存在式”语义[36].

(2) 最短旅途语义(shortest path semantics).在该语义下, Q(G)复返满足正则抒发式r的最短旅途(或长度特地的若干最短旅途).举例, G-CORE中的正则旅途查询遴选的是该语义[30].

(3) 无相通顶点语义(no-repeated-node semantics).在该语义下, Q(G)复返满足正则抒发式r的旅途且每条旅途中无相通出现的顶点(每个顶点仅出现1次).无相通顶点的旅途称为苟简旅途(simple path).在一些现实场景中需要该语义, 举例, 在策动游览阶梯时, 一般不但愿拜谒一个处所多于1次.但该语义的求值复杂度早已被讲解是NP绝对的[110].

(4) 无相通边语义(no-repeated-edge semantics).在该语义下, Q(G)复返满足正则抒发式r的旅途且每条旅途中无相通出现的边(每条边仅出现1次).这时, 前边的例子变为允许拜谒一个处所多于1次, 然而不可走相通的阶梯.面前, Cypher言语聘任这种语义[29].

凭证不同需求, RPQ的输出不错分为以下几种情况.

(1) 布尔值.判断在Q(G)中两个给定顶点之间是否存在一条满足正则抒发式r的旅途; (2)顶点.复返Q(G)中旅途的起始和至极对集合; (3)旅途.复返Q(G)中的一条、多条或全部旅途; (4)图.将Q(G)中的全部或部分旅途整合为G的子图复返.

集合语义和包语义.对于RPQ输出为顶点的情况, 集合语义与包语义不同.在集合语义下, 顶点对(u, v)仅输出1次, 不管Q(G)中有几许条u到v的旅途.在包语义下, 顶点对(u, v)复返的次数等于Q(G)中u到v的旅途条数.基于前边的谈论, 包语义与自便旅途语义的结合现实上亦然不可行的, 因为包语义蕴含了“数旅途”, 其复杂度已被讲解是#P绝对的[42].

RPQ与BGP可结合在一王人形成CRPQ(conjunctive RPQ), 其界说是BGP的扩张, 即允许BGP中的边是RPQ.对于CRPQ的表面磋议请参见文献[67, 111, 112].文献[113]已讲解CRPQ的组合复杂度是NP绝对的.现实上, 由第2节照旧看出, CRPQ是一般常识图谱言语的中枢.在一些情况下, 需要在查询中指定旅途之间的某些关系(如比较旅途标签是否相易), 为此, 文献[113]还建议了ECRPQ(extended CRPQ)行为CRPQ的扩张, 何况讲解了ECRPQ的组合复杂度是PSPACE绝对的.在RPQ基础上扩张的抒发力更丰富的其他导航式查询体式包括:嵌套正则抒发式NRE(nested regular expression)[114]、正则数据旅途查询RDPQ(regular data path query)[115]和Datalog扩张[68].

RPQ的求值表面上可看作正则抒发式r对应的自动机与常识图谱G对应的自动机的相乘操作, 其复杂度为PTIME[110].Koschmieder等东说念主[116]建议使用“零散标签(rare-label)”设施对RPQ进行领会, 然后进行分段求值.该设施现实上遴选了分治战术, 但需要通过预处理预先详情“零散标签”, 查询处理聘任了导航式遍历设施.Fan等东说念主[117]在基于模拟语义的子图匹配查询基础上引入了RPQ查询的一个子集, 该职责对所提查询模子进行了完善的表面分析, 并给出了相应的履行算法, 其复杂度为立方级.Gubichev等东说念主[118]基于RDF-3X中的FERRARI索引在可达性查询的基础上扩张兑现了RPQ查询处理.Dey等东说念主[119]基于关所有这个词据库兑现了具有发祥保险(provenance-aware)的RPQ查询.Wang等东说念主[120]建议了大领域RDF图上的高着力发祥保险RPQ求值算法.

4.3 分析型查询

不同于图模式匹配和导航式查询, 分析型查询并不关注满足条目的图结构局部实例, 而是面向于度量统统这个词常识图谱的全局团员信息.苟简的分析型查询包括求学识图谱统计团员信息(如顶点和边计数)、顶点的度、图中的最大/最小/平均度、图的直径等.较复杂的分析型查询主如果图上算计密集型的一些分析和挖掘算法, 包括:

(1) 特征旅途长度(characteristic path length).图中统统顶点对之间最短旅途长度的平均值.形容一个图中顶点之间的关联进程.

(2) 连通重量(connected components).复返图中统统顶点子集, 这些集合中的顶点好像通过边互相达到.

(3) 社区发现(community detection).复返图中统统顶点子集, 这些集合中的顶点以某种界说在并吞社区中.

(4) 集合所有这个词(clustering coefficient).顶点的集合所有这个词是该顶点的邻居顶点互相贯串的概率.图的集合所有这个词是图中统统顶点的平均集合所有这个词.

(5) PageRank.形容了一个Web浏览者的就地游走行为.顶点的PageRank值默示Web浏览者拜谒到该顶点的概率.PageRank可行为图中顶点相对进击进程的度量目的.

关联图数据上分析与挖掘算法的详实先容请参见文献[121].对于大领域常识图谱, 分析型查询常常算计量雄壮, 需要使用分散式图处理框架兑现并行算计, 详见第5.3节.

4.4 常识图谱查询言语比较

表 5给出了5种常识图谱查询言语的语法、语义及接洽性情的详实比较信息, 包括:图模式匹配查询和导航式查询的语法和语义、分析型查询的支抓进程、查询可组合性、数据更新言语DML和数据界说言语DDL的支抓进程以及兑现系统等.对于SPARQL、Cypher和Gremlin的比较可进一步参见文献[9]; 对于Cypher、PGQL和G-CORE的比较可进一步参见文献[122].

5 常识图谱数据库不竭系统

本节起先给出面前主要常识图谱数据库不竭系统的简要先容, 包括:RDF三元组库和原生图数据库; 然后, 综述分散式图数据处理系统与框架; 临了, 先容图数据不竭系统的评测基准.

5.1 RDF三元组库

主要的开源RDF三元组数据库包括:Apache Jena、Eclipse RDF4J以及学术界的RDF-3X和gStore; 主要的生意RDF三元组数据库包括:Virtuoso、AllegroGraph、GraphDB、BlazeGraph和Stardog[123].

1.开源RDF三元组数据库:Jena

Jena[55]是Apache顶级表情, 其前身为惠普实验室诱导的Jena器用包.Jena是语义Web领域主要的开源框架和RDF三元组库, 较好地投诚了W3C模范, 其功能包括:RDF数据不竭、RDFS和OWL实质不竭、SPARQL查询处理等.Jena具备一套原糊口储引擎, 可对RDF三元组进行基于磁盘或内存的存储不竭.同期, 具有一套基于法则的推理引擎, 用以履行RDFS和OWL实质推理任务.

2.开源RDF三元组数据库:RDF4J

RDF4J[124]面前是Eclipse基金会旗下的开源孵化表情, 其前身是荷兰软件公司Aduna诱导的Sesame框架, 功能包括:RDF数据的涌现、存储、推理和查询等.RDF4J提供内存和磁盘两种RDF存储机制, 支抓SPARQL 1.1查询和更新言语.

3.开源RDF三元组数据库:RDF-3X

RDF-3X是由德国马克斯-普朗克算计机科学磋议所研发的RDF三元组数据库系统, 其起先收场逸表于2008年的数据库国外会议VLDB[58], 后经功能扩张和完善, 最新版块是GH-RDF3X, 源代码不错从GitHub高下载https://github.com/gh-rdf3x/gh-rdf3x.RDF-3X的最大特色在于其为RDF数据特地遐想的压缩物理存储决议、查询处理和查询优化技艺.

4.开源RDF三元组数据库:gStore

gStore[63]是由北京大学、加拿大滑铁卢大学和香港科技大学合股磋议表情诱导的基于图的RDF三元组数据库.gStore的存储层使用RDF图对应的签章图(signature graph)并建树“VS*树”索引以加快查找.将RDF图G中的每个实体顶点偏执邻居属性和属性值编码成一个二进制位串, 由这些位串行为顶点组成一张与RDF图G对应的签章图G*; 在履行SPARQL查询时, 将查询图Q也转换为一张查询的签章图Q*.为了支抓在G*上快速查找到Q*的匹配位置, gStore系统建树了“VS*树”索引, 其基本念念想是为签章图G*建树不同详实进程的摘抄图(summary graph); 哄骗“VS*”树索引提供的摘抄图, gStore系统不错大幅度缩小SPARQL查询的搜索空间.

5.生意RDF三元组数据库:Virtuoso

Virtuoso[125]是OpenLink公司诱导的生意搀杂数据库产物, 支抓关所有这个词据、对象-关所有这个词据、RDF数据、XML数据和文本数据的和解不竭, 其同期发布生意版块Virtuoso Universal Server(Virtuoso和解做事器)和开源版块OpenLink Virtuoso.Virtuoso诚然是不错支抓多种数据模子的搀杂数据库不竭系统, 但其基础源自诱导了多年的传统关系型数据库不竭系统, 因此具备较为完善的事务不竭、并发阻挡和齐备性机制.因为Virtuoso不错较为完善地支抓W3C的Linked Data系列左券, 包括DBpedia在内的许多洞开RDF常识图谱弃取其行为后台存储系统.

6.生意RDF三元组数据库:AllegroGraph

AllegroGraph[126]是Franz公司诱导的RDF三元组数据库.AllegroGraph对语义推理功能具有较为完善的支抓.除了三元组数据库的基本功能外, AllegroGraph还支抓动态归天的RDFS++推理机、OWL2 RL推理机、Prolog法则推理系统、时空推理机制、社会蚁集分析库、可视化RDF图浏览器等.

7.生意RDF三元组数据库:GraphDB

GraphDB[127]是由Ontotext软件公司诱导的RDF三元组数据库.GraphDB兑现了RDF4J框架的SAIL层, 不错使用RDF4J的RDF模子、涌现器和查询引擎平直拜谒GraphDB.GraphDB的特色是对于RDF推理功能的雅致支抓, 其使用内置的基于法则的“前向链(forward-chaining)”推理机, 由显式(explicit)常识经过推理得到导出(inferred)常识, 对这些导出常识进行优化存储; 导出常识会在常识库更新后相应地同步更新.

8.生意RDF三元组数据库:BlazeGraph

Blazegraph[128]是一个基于RDF三元组库的图数据库不竭系统, 在用户接口层同期支抓RDF三元组和属性图模子, 既兑现了SPARQL言语也兑现了Blueprints模范及Gremlin言语.Blazegraph的里面兑现技艺是面向RDF三元组和SPARQL的, 是“基于RDF三元组库的图数据库”.

9.生意RDF三元组数据库:Stardog

Stardog[129]是由Stardog Union公司诱导的RDF三元组数据库, 其支抓RDF图数据模子、SPARQL查询言语、属性图模子、Gremlin图遍历言语、OWL2模范、用户自界说的推理与数据分析法则、诬捏图、地舆空间查询以及多用编程言语与蚁集接口支抓.Stardog对OWL2推理机制具有雅致的支抓, 同期具备全文搜索、GraphQL查询、旅途查询、和会机器学习任务等功能, 好像支抓多种不同编程言语和Web拜谒接口.

5.2 原生图数据库

面前主要的原生图数据库有Neo4j、JanusGraph、OrientDB和Cayley.

1.最流行的图数据库:Neo4j

Neo4j[29]是由Neo技艺公司诱导的图数据库.不错说, Neo4j是面前流行进程最高的图数据库产物.Neo4j基于属性图模子, 其存储不竭层为属性图的节点、节点属性、边、边属性等元素遐想了特地的存储决议.这使得Neo4j在存储层对于图数据的存取着力优于关所有这个词据库.

2.分散式图数据库:JanusGraph

JanusGraph[130]是在原有Titan系统[131]基础上连接诱导的开源分散式图数据库.JanusGraph的存储后端与查询引擎是分离的, 可使用分散式Bigtable存储库Cassandra或HBase行为存储后端.JanusGraph借助第三方分散式索引库ElasticSearch、Solr和Lucene兑现万般型数据的快速检索功能, 包括地舆信息数据、数值数据和全文搜索.JanusGraph还具备基于MapReduce的图分析引擎, 可将Gremlin导航查询转换为MapReduce任务.

3.图数据库:OrientDB

OrientDB[132]起先是由OrientDB公司诱导的多模子数据库不竭系统.OrientDB诚然支抓图、文档、键值、对象、关系等多种数据模子, 但其底层兑现主要面向图和文档数据存储不竭的需求遐想.其存储层中数据记载之间的接洽并不是像关所有这个词据库那样通过主外键的援用, 而是通过记载之前平直的物理指针.OrientDB对于数据模式的支抓相对机动, 不错不竭无模式数据(schema-less), 也不错像关所有这个词据库那样界说齐备的模式(schema-full), 还不错稳健介于两者之间的搀杂模式(schema-mixed)数据.在查询言语方面, OrientDB支抓扩张的SQL和Gremlin用于图上的导航式查询; OrientDB的MATCH语句兑现了声明式的模式匹配, 这肖似于Cypher言语查询模式.

4.图数据库:Cayley

Cayley[133]是由Google公司工程师诱导的一款轻量级开源图数据库.Cayley的诱导受到了Freebase常识图谱和Google常识图谱背后的图数据存储的影响.Cayley使用Go言语诱导, 不错行为Go类库使用; 对外提供REST API; 具有内置的查询剪辑器和可视化界面; 支抓多种查询言语, 包括:基于Gremlin的Gizmo、GraphQL和MQL; 支抓多种存储后端, 包括:键值数据库Bolt、LevelDB, NoSQL数据库MongoDB、CouchDB、PouchDB、ElasticSearch, 关所有这个词据库PostgreSQL、MySQL等.

其他原生图数据库还包括:构造在Amazon云平台上的Amazon Neptune[134]、多模子图数据库Arango DB[135]、微软的Azure CosmosDB[136]、DataStax的Enterprise Graph[137]、Sparsity的Sparksee[138]以及TigerGraph[139]等.

5.3 分散式图数据处理系统与框架

在大数据时间, 分散式/并行技艺已成为大领域常识图谱数据不竭不可或缺的器用.面前, 领域为百万顶点(106)和上亿条边(108)的常识图谱数据集已不在少数[140].限制2019年1月LOD(linked open data, 通顺洞开数据)常识图谱发布的RDF图数据集算计1 234个, 其总领域面前虽莫得准确的统计数据, 但保守猜想达上千亿条三元组[141].LOD中许多单个数据集的领域已跨越10亿条三元组, 举例, 维基百科数据集DBpedia 2014为30亿条[142]、卵白质数据集UniProt为90.2亿条[143]、地舆信息数据集LinkedGeoData为200亿条[144].

频年来建议的面向大领域图数据的分散式系统与框架包括:基于分散式文献系统(如GFS[145])或基于Bigtable模子[146]的图数据存储层和基于MapReduce[147]、Pregel[148]及GraphLab框架[149]的图数据处理层.现存分散式/并行图数据不竭系统大多基于这些框架进行扩张, 其中包括:(1)基于MapReduce的系统:YARS2[150]、SPIDER[151]、SHARD[152]; (2)基于Bigtable的系统:Titan[131]、CumulusRDF[153]; (3)基于做事总线的系统: Blazegraph[128]; (4)基于内存存储的系统:Trinity[154]、Trinity.RDF[155].

大领域RDF图上的分散式查询处理设施引入了图分割和查询领会战术.文献[156]将RDF图诀别为若干分片, 每个分片的范围节点扩张到“n跳(n-hop)”邻居, 同期将SPARQL查询诀别为若干子查询进行并行求值.文献[157]将顶点偏执邻居界说为“顶点块”, 聘任启发式法则对顶点块进行分散式存储, 同期将查询进行领会, 达到增大并行度且减少通讯支出的目的.文献[158]建议的EAGRE设施基于边上的谓语信息对图和查询进行领会.文献[159]建议的TriAD设施聘任METIS设施将RDF图分割为若干片断, 每个片断在多个机器上存储, 同期爱戴一个包含诀别信息的摘抄图, 通过MPI框架的异步音信传递进行系统通讯.文献[160]建议的DREAM系统只对查询进行领会并不领会RDF图, 好像凭证领会后子查询的复杂度自稳健地分拨履行查询所需的机器数量.

在分散式图查询处理上, 基于部分求值(partial evaluation)技艺[161]已建议了一系列有用设施.最近, Fan等东说念主哄骗部分求值建议了图数据的可达性查询分散式版块[162]; Ma和Fan等东说念主哄骗部分求值建议了基于模拟语义的子图匹配的分散式版块[163, 164]; Peng等东说念主哄骗部分求值建议了SPARQL查询的分散式版块[165]; Wang等东说念主建议了基于部分求值的RDF图上RPQ分散式算法[166].

此外, 面前已有若干基于现存分散式算计框架的常识图谱查询处理职责.文献[167]展示的H2RDF+系统基于HBase分散式Bigtable存储库构建了三元组的六重索引.文献[168]给出的Sempala是基于分散式SQL-on- Hadoop数据库Impala和Parquet分散式文献形态的RDF图数据查询引擎.Lai等东说念主建议了基于TwinTwig结构领会的MapReduce分散式高效子图陈设算法, 但该算法仅用于无向无标签图[169, 170].Bi等东说念主进一步给出了通过尽可能推迟笛卡尔积履行来提高子图匹配着力的技艺[171].Schätzle等东说念主建议的S2RDF系统将SPARQL查询退换为Spark分散式算计框架上的RDD操作, 其离线建树了多半索引, 用于加快在线查询, 但对于大领域常识图谱, 索引构建时刻支出可能很高[172].文献[173]哄骗RDF图的语义和结构行为启发信息将查询图进行星形领会, 遐想了一种基于MapReduce的分散式SPARQL BGP匹配算法.He等东说念主建议的Stylus是一种哄骗强类型信息构建优化存储决议和查询处理的分散式RDF图存储库, 其底层基于键值库[174].Peng等东说念主在文献[175]中给出了一种好像凭证查询负载优化图诀别和存储的RDF图存储决议.Xin等东说念主给出了基于Pregel图算计框架的发祥保险RPQ分散式求值算法[176].开源表情Apache Rya是基于分散式列存储系统Accumulo诱导的RDF三元组库[177].开源表情Cypher for Apache Spark[178]是Neo4j公司诱导的用于将Cypher查询退换为Spark并行操作的模块.对于基于Pregel的分散式图处理框架的最新磋议推崇可参见文献[19].

5.4 常识图谱数据库不竭系统比较

表 6比较了常见的25种常识图谱数据库不竭系统, 包括许可证、数据模子、存储决议、查询言语、特色描写、最新版块和是否活跃.

Table 6 The comparison of knowledge graph database management systems 表 6 常奉告识图谱数据库不竭系统的比较

表 6不仅包括本节先容的RDF三元组库、原生图数据库和分散式图数据处理系统与框架, 还纳入了第3.1节中先容的基于关系的常识图谱存储决议的代表性系统.

5.5 评测基准

评测基准(benchmark)是客不雅评价数据库不竭系统性能的模范器用.关所有这个词据库有着名的TPC评测基准.常识图谱数据库不竭系统的评测基准仍处于发展完善阶段.面前, 通顺数据评测基准委员会(Linked Data Benchmark Council, 简称LDBC)是常识图谱数据不竭系统评测基准诱导的主要组织, 其成员包括了主要的图数据库公司和磋议机构[179].LDBC面前诱导了两个评测基准:社会蚁集评测基准(social network benchmark, 简称SNB)和语义出书评测基准(semantic publishing benchmark, 简称SPB).SNB遐想用于评测常识图谱数据库不竭系统的事务查询负载、分析查询负载和图分析算法; SPB遐想用于评测查询和更新搀杂负载并兼具一定的语义推理评测功能.不外, LDBC评测基准中的部分功能尚处于诱导阶段.

此外, 在LDBC成立之前, 学术界照旧诱导了若干RDF数据库评测基准, 包括:LUBM、SP2Bench、BSBM和DBPSB.LUBM[180]是最早的RDF评测基准, 不支抓SPARQL 1.1新性情, 也不支抓数据更新, 具备一定的推理评测才智; SP2Bench[181]是基于DBLP数据集构建的SPARQL评测基准, 不支抓更新; BSBM[182]基于电子商务数据模式, 是功能相对完善的SPARQL评测基准, 同期包括事务和分析型负载, 然而, BSBM数据集过于规整, 以致于基于关所有这个词据库的系统的评测收场均较优.DBPSB[183]使用基于DBpedia的真确数据集, 但其负载过于苟简, 只包括基本查询, 相通不支抓更新.WatDiv评测基准[184]的特色是好像支抓用户自界说生成测试数据的模式, 其查询负载凭证数据模式图上的就地游走产生, 分为线性查询、星形查询、雪花形查询和复杂查询4类.Link Bench[185]是基于Facebook酬酢蚁集真确数据和负载诱导的评测基准, 好像模拟Facebook真确分娩景色下的酬酢蚁集图数据库查询和更新操作, 但该评测基准已不再被爱戴.

表 7给出了本节先容的8种常识图谱数据不竭评测基准的比较, 包括发布机构、生成数据特色、查询负载特色和活跃进程.

Table 7 The comparison of knowledge graph data management benchmarks 表 7 常识图谱数据不竭评测基准的比较 6 当年磋议标的

面前, 常识图谱数据不竭的表面、设施、技艺与系统处于快速发展和诱导完善阶段.数据库学术和产业界对常识图谱数据不竭研发参预正在继续加多.本节将当年的磋议标的归纳如下.

(1) 常识图谱数据模子与查询言语的和解

面前, 常识图谱数据模子和查询言语尚不和解.磋议到关所有这个词据库的兴起与发展流行, 其中主要身分是具有精准界说的关所有这个词据模子和和解的查询言语SQL.和解的数据模子和查询言语不仅削弱了数据库不竭系统的研发资本, 而且裁减了用户遐想、构建、不竭和爱戴数据库的代价, 同期裁减了新用户的学习难度.

然而, 由于常识图谱的发展原因, 其数据模子与查询言语的和解存在着一定难度.其一, RDF图源于语义Web的发展而产生, 其在模范制定之初即面向Web上全局资源的默示、发布和集成, 其上还基于描写逻辑界说了RDF模式(RDF schema)言语和Web实质言语(OWL), 形成了一整套高档语义默示和推理机制; DBpedia、YAGO、WikiData等着名常识图谱现实上均是RDF形态.另一方面, 属性图来自于图数据库领域, 其顶点和边属性的方便默示机制弥补了RDF图的不及, 但面前仍未形成一致公认的严格数学界说, 比如, G-CORE言语为了提高旅途的地位还界说了旅途属性图.现时, 亟需界说和解的常识图谱数据模子, 既具有RDF图面向Web的优点(如使用URI唯一标记资源), 又具备属性图上便于数据存储的上风, 同期将已有RDF常识图谱数据映射退换为新数据模子形态, 行为真确的大领域常识图谱数据集, 种植和解数据模子的招供度.其二, 和解现存常识图谱查询言语近在眉睫.第2节列出的主要查询言语就有5种之多, SPARQL面向RDF图, 其余4种均面向属性图.常识图谱数据模子和解后, 势必需要制定和解的查询言语.面前, openCypher组织照旧发出了“GQL宣言”[188], 准备将Cypher、PGQL和G-CORE和会为属性图模范查询言语GQL.然而, 其中并未磋议RDF图的SPARQL言语.面进取述和解常识图谱数据模子, 研制和解常识图谱查询言语, 界说精准语法和语义, 是当年的一个进击磋议标的.

(2) 大领域常识图谱数据的分散式存储决议

第3节谈论的常识图谱存储不竭决议, 不管是基于关系的照旧原生的, 均是在单机系统上兑现的.大领域常识图谱数据的分散式存储的研发面前尚处于起步阶段.常识图谱数据的分散式存储濒临的第一个问题是大领域图数据的诀别.图诀别问题自身是一个经典的NP绝对问题.即使使用公认最优的METIS图诀别算法, 对于大领域图数据在单机上履行诀别也确切是不可行的.是以, 起先需要磋议面向大领域常识图谱数据的分散式图诀别算法, 该算法既要磋议按照常识图谱的图结构和常识语义信息行为图诀别模范, 尽可能地成心于支抓常识图谱查询的快速履行, 又要幸免算法复杂渡过高.其次, 在常识图谱诀别的基础上, 建议分散式存储决议.需要磋议:是面向OLTP和OLAP遐想两种不同存储决议, 照旧遐想不错均衡不同类型查询的和解存储; 可选的物理层兑现框架包括分散式关所有这个词据库存储层、分散式文献系统、分散式Bigtable系统和分散式键值存储库; 扩张单机版的RDF图或属性图存储决议, 使其稳健分散式物理存储底层是一种可选念念路.再次, 还需要面向常识图谱查询处理遐想不同的索引决议, 比如, 面向图模式匹配查询的索引、面向导航式旅途查询的索引和面向分析型查询的索引.

(3) 大领域常识图谱数据的分散式查询处理

诚然第5.3节先容了现存的常识图谱分散式查询处理设施、框架与系统, 但按照数据库系统的不雅点, 面前还莫得形成基于底层存储决议撑抓的分散式查询处理完善机制.大部分已有设施均是为了惩处某种特定查策画题而遐想的专用算法, 或者是基于MapReduce、Pregel、MPI等已有分散式处理框架而遐想的算法.从分散式数据库不竭系统的角度启航, 需要形成具备一整套逻辑和物理算子的分散式查询处理高效算法, 充分磋议存储和索引结构, 同期磋议分散式通讯支出, 进而形成一套得当常识图谱分散式查询的代价模子.在此基础上, 磋议常识图谱分散式查询优化设施.

(4) 常识图谱数据不竭对于实质和常识推理的支抓

常识图谱数据与传统关所有这个词据的一个最大区别是对实质的默示和内在的常识推理才智.举例, 在RDF图数据之上, 还有RDF模式(RDFS)和Web实质言语(OWL)的界说, 可用于默示丰富的高档语义常识, 同期界说了不同层面的推理功能, 即从已有常识推导出隐含常识.面前的常识图谱数据不竭还莫得充分磋议到对于实质和常识推理的支抓.如安在存储层和查询处理层支抓常识图谱高层实质的有用不竭和高着力的推理功能詈骂常有道理的磋议标的.对于面向常识图谱的常识推理最新磋议推崇可参见文献[187].

(5) 大领域常识图谱的更新爱戴

色狼窝

真确的常识图谱数据随时刻的推移会发生继续的更新变化.面前的常识图谱数据不竭系统有许多假定常识是只读的和单向追加的, 对于大领域常识图谱的更新爱戴基本莫得磋议.起先, 需要在常识图谱和解查询言语中特地为常识图谱更新遐想数据更新子言语; 其次, 在常识更新进程中, 常常会波及到多版块阻挡、一致性拘谨和不一致消解等多种问题.这些问题在常识图谱数据不竭系统中怎样惩处需要深远磋议.

(6) 大领域常识图谱的数据集成

对于多个单独爱戴的常识图谱数据库或者历史留传的常识图谱存在数据集成需求.面前, Linked Data技艺[189]是RDF图上进行数据集成的模范设施, 在多个合适Linked Data的RDF图上不错构建SPARQL联邦查询系统, 进行跨常识图谱的集成查询.但在新式分散式常识图谱数据不竭配景下, 仍然存在着若干需要磋议的问题, 比如, 分散式常识图谱数据库的不同集成形貌、联邦查询的性能优化和着力种植、面向不一致常识图谱的数据集成等.

7 追念

本文以数据模子的结构和操作要素为干线, 对面前的常识图谱数据不竭的表面、设施、技艺与系统进行了磋议综述:包括两种常识图谱数据模子和5种常识图谱查询言语; 先容了基于关系的和原生的常识图谱存储不竭; 谈论了常识图谱上的图模式匹配、导航式和分析型查询操作; 先容了RDF三元组库和原生图数据库这两类常识图谱数据库不竭系统, 描写了面前边向常识图谱的分散式系统与框架的近况melody marks 肛交, 给出了常识图谱评测基准的情况.临了, 瞻望了常识图谱数据不竭的当年磋议标的.