软件学报  2019, Vol. 30 Issue (7): 2139-2174   PDF    
知识图谱数据管理研究综述
王鑫1,2, 邹磊3, 王朝坤4, 彭鹏5, 冯志勇1,2     
1. 天津大学 智能与计算学部, 天津 300350;
2. 天津市认知计算与应用重点实验室, 天津 300350;
3. 北京大学 计算机科学技术研究所, 北京 100871;
4. 清华大学 软件学院, 北京 100084;
5. 湖南大学 信息科学与工程学院, 湖南 长沙 410082
摘要: 知识图谱是人工智能的重要基石.各领域大规模知识图谱的构建和发布对知识图谱数据管理提出了新的挑战.以数据模型的结构和操作要素为主线,对目前的知识图谱数据管理理论、方法、技术与系统进行研究综述.首先,介绍知识图谱数据模型,包括RDF图模型和属性图模型,介绍5种知识图谱查询语言,包括SPARQL、Cypher、Gremlin、PGQL和G-CORE;然后,介绍知识图谱存储管理方案,包括基于关系的知识图谱存储管理和原生知识图谱存储管理;其次,探讨知识图谱上的图模式匹配、导航式和分析型3种查询操作.同时,介绍主流的知识图谱数据库管理系统,包括RDF三元组库和原生图数据库,描述目前面向知识图谱的分布式系统与框架,给出知识图谱评测基准.最后,展望知识图谱数据管理的未来研究方向.
关键词: 知识图谱     数据管理     数据模型     查询语言     存储管理     查询操作    
Research on Knowledge Graph Data Management: A Survey
WANG Xin1,2, ZOU Lei3, WANG Chao-Kun4, PENG Peng5, FENG Zhi-Yong1,2     
1. College of Intelligence and Computing, Tianjin University, Tianjin 300350, China;
2. Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300350, China;
3. Institute of Computer Science and Technology, Peking University, Beijing 100871, China;
4. School of Software, Tsinghua University, Beijing 100084, China;
5. College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
Foundation item: National Natural Science Foundation of China (61572353); Natural Science Foundation of Tianjin of China (17JCYBJC 15400)
Abstract: Knowledge graphs have become the cornerstone of artificial intelligence. The construction and publication of large-scale knowledge graphs in various domains have posed new challenges on the data management of knowledge graphs. In this paper, in accordance with the structural and operational elements of a data model, the current theories, methods, technologies, and systems of knowledge graph data management are surveyed. First, the paper introduces knowledge graph data models, including the RDF graph model and the property graph model, and also introduces 5 knowledge graph query languages, including SPARQL, Cypher, Gremlin, PGQL, and G-CORE. Second, the storage management schemes of knowledge graphs are presented, including relational-based and native approaches. Third, three kinds of query operations are discussed, which are graph pattern matching, navigational, and analytical queries. Fourth, the paper introduces mainstream knowledge graph database management systems, which are categorized into RDF triple stores and native graph databases. Meanwhile, the state-of-the-art distributed systems and frameworks that are used for processing knowledge graphs are also described, and benchmarks are presented for knowledge graphs. Finally, the future research directions of knowledge graph data management are put forward as well.
Key words: knowledge graph     data management     data model     query language     storage management     query operation    

知识图谱作为符号主义发展的最新成果, 是人工智能的重要基石.随着知识图谱规模的日益扩大, 其数据管理问题愈加重要.一方面, 以文件形式保存知识图谱无法满足用户的查询、检索、推理、分析及各种应用需求; 另一方面, 传统数据库的关系模型与知识图谱的图模型之间存在显著差异, 关系数据库无法有效管理大规模知识图谱数据.为了更好地管理知识图谱, 语义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)表示so之间具有联系p, 或表示s具有属性p且其取值为o.下面给出RDF图的严格定义.

定义1(RDF图).设UBL为互不相交的无限集合, 分别代表URI、空顶点(blank node)和字面量(literal).一个三元组(s, p, o)$\in $(U$\cup $BU×(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 $EPropVal为顶点或边关联属性, 如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 $EProp$\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), 如v4e1v1e5v5e8v2e3v3e4.

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(虽然v1v2也有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中元素组成的序列, 函数δ:PSeq(V$\cup $E)将路径映射到顶点和边交替组成的序列, 如p$\in $P, δ(p)=(v1, e1, v2, …, vn, en, vn+1), 其中, (ⅰ) vi$\in $V(1≤in+1);(ⅱ) ei$\in $E, ρ(ei)=(vi, vi+1)或ρ(ei)=(vi+1, vi)(1≤in); (4)设Lab是标签集合, 函数λ:(V$\cup $E$\cup $P)→Lab为顶点、边或路径赋予标签; (5)设Prop是属性集合, Val是值集合, 函数σ:(V$\cup $E$\cup $PPropVal为顶点、边或路径关联属性.

从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≤ik, 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给出了谓语到列映射的哈希函数表, 其中包括h1h2两个哈希函数, 映射了5个谓语到列编号组.比如, 当存储到三元组(James_ Cameron, directs, Titanic)时, 谓语directs被h1映射到列pred2, 被h2映射到列pred3, 但这两列都已被占用, 这时产生溢出, 将谓语directs溢出到下一行的列pred2中存储, 如图 11的dph表所示.