知识图谱数据管理综述：模型、方法和系统

【摘要】随着人工智能的兴起，知识图谱被广泛认为是人工智能的基石。近年来，学术界和工业界构建并发布了越来越多的大规模知识图。知识图本质上是一个由实体、实体属性、实体间语义关系以及本体组成的大型网络。这种基于图的知识数据对传统数据管理理论和技术提出了巨大的挑战。本文介绍了知识图谱数据管理的研究现状，包括知识图谱数据模型、查询语言、存储方案、查询处理和推理。本文还将介绍各种知识图数据库管理系统的最新发展趋势。

【原文】Wang, X. and W. Chen (2020). Knowledge Graph Data Management: Models, Methods, and Systems. Web Information Systems Engineering （WISE 2020）: 3-12.

【DOI】https://doi.org/10.1007/978-981-15-3281-8_1

1 概况

知识图作为符号主义的最新发展，近年来被学术界和产业界广泛认为是人工智能的重要基石。目前，具有数百万个顶点( 10610^6 )和数亿条边( 10810^8 )的知识图是常见的。2019年3月发布的链接开放数据(LOD)云包含了大量超过10亿个三元组的知识图谱[2]，如DBpedia(>30亿个三元组)[1]、LinkedGeoData(>30亿个三元组)[3]、UniProt(>130亿个三元组)[6]等。各个领域大规模知识图的构建和发布给知识图数据管理提出了新的挑战。

一方面，以文件形式存储的知识图明显不能满足高层人工智能任务的查询、检索、推理、分析和各种应用需求；另一方面，传统数据库的关系模型与知识图的图形模型存在显著差异，关系数据库无法有效管理大规模的知识图数据。为了更有效地管理知识图，语义Web社区开发了专门存储RDF图的三元组存储；数据库社区开发了用于管理属性图的图数据库。

然而，知识图数据管理最大的问题是现有数据模型和查询语言不统一。目前还没有公认的主流知识图谱数据库系统，而大规模知识图谱的出现需要有效的数据管理基础设施。知识图对学习、识别、预测等人工智能任务的迫切需求要求开发大规模知识图的数据管理系统。在此背景下，知识图数据管理的理论和技术不仅是数据库领域的重要研究课题，也是下一代人工智能发展的基础性任务之一。

本文全面介绍了知识图数据管理的研究现状，包括知识图数据模型、查询语言、存储模式、查询处理和推理。描述了知识图谱数据管理系统的最新发展趋势。

2 数据模型

数据模型定义了数据的逻辑结构、数据操作和约束，并决定了数据管理所采用的有效方法。因此，数据模型对于存储管理、查询处理和查询语言设计至关重要。早期的几种图数据模型基本采用图论中的图结构（即 G=(V，E)G=(V，E) ，其中 VV 是顶点集，EE 是边集）作为数据结构[9]；知识图数据模型可以看作是传统图数据模型的扩展。知识图数据模型基于图结构，图结构使用顶点来表示实体，边来表示实体之间的关系。这种通用的数据表示自然可以描述现实世界中事物的广泛联系。目前，知识图数据模型主要有两种类型：RDF图模型和属性图模型。

（1）RDF图模型。

RDF（Resource Description Framework，资源描述框架）是用于在语义Web上表示和交换信息的标准数据模型，目的是使机器可理解[12]。在RDF图中，每个资源都有一个HTTP URI作为唯一标识符；RDF图被定义为一组有限的三元组 (s，p，o)(s，p，o)；每个三元组表示一条语句，其中 ss 是主语，pp 是谓语，oo 是宾语；(s，p，o)(s，p，o) 表示资源 ss 和 oo 之间存在连接 pp ，或者ss 具有值为 oo 的属性 pp。

（2）属性图模型。

与RDF图模型不同，属性图模型具有对顶点属性和边属性的内在支持。目前，属性图模型被图形数据库行业广泛采用，包括著名的图形数据库Neo4j[4]。最近，由图形数据库领域的学术界和产业界成员组成的关联数据基准委员会(LDBC)也在标准化基于属性图模型的图形数据模型和图形查询语言[8]。

3 查询语言

知识图查询语言主要实现对知识图数据模型的查询操作。目前，RDF图上的查询语言是SPARQL，属性图上的查询语言包括Cypher、Gremlin、PGQL和G-CORE。对于查询语言的类型，除了Gremlin是过程性语言外，其他都是声明性语言。

（1）SPARQL

SPARQL是由W3C[14]开发的用于RDF知识图的标准查询语言。SPARQL借用了SQL的语法。SPARQL查询的基本单位是三元模式。多个三元模式可以形成一个基本的图模式。SPARQL支持多个操作符，以将基本图模式扩展为复杂图模式。最新的SPARQL1.1版本还引入了属性路径机制[15]来支持对RDF图的导航查询。

（2）Cypher

Cypher最初是在Neo4j中实现的属性图查询语言。与SPARQL一样，Cypher也是一种声明性语言。2015年，Neo4j推出开源项目OpenCypher(https://www.opencypher.org)，)，旨在标准化Cypher，并为其他实施者提供语法和语义参考标准。Cypher的一个主要特性是使用“ASCII ART”语法来表示图形模式匹配。

（3）Gremlin

Gremlin是一种由Apache TinkerPop图计算框架提供的属性图查询语言[5]。Apache TinkerPop被设计为访问图形数据库的通用API接口，其角色类似于关系数据库上的JDBC接口。Gremlin是一种图遍历语言，其执行机制是沿着图的有向边导航。这种执行方法决定了用户需要在Gremlin中指定导航步骤，因此Gremlin被归类为过程性语言。

（4）PGQL

PGQL是Oracle在2016年提出的一种关于属性图的声明性查询语言[18]，它支持图模式匹配查询和导航查询。与Cypher不同，PGQL完全支持正则路径查询语义；不同于SPARQL属性路径只支持由边标签组成的正则路径，通过定义路径模式表达式，PGQL还支持包含顶点标签条件和顶点（或边）属性比较的正则路径。PGQL在保持计算复杂度的同时，提高了属性图上规则路径查询的表达能力。

（5）G-CORE

G-CORE是LDBC图形查询语言任务组设计的属性图形查询语言[8]。G-CORE的设计目标是充分借鉴和整合现有各种图查询语言的优点，在查询表达能力和计算复杂度之间找到最佳的平衡点。与现有的图查询语言相比，在G-CORE中，查询的输入和输出都是图，完全实现了图查询语言的可组合性；在图查询处理中，路径被视为与顶点和边同等重要的基本元素。为此，G-CORE扩展了属性图模型，定义了路径属性图模型。

4 存储方案

目前的知识图存储方案主要有两种：基于关系的知识图存储、原生知识图存储。

4.1 基于关系的知识图存储

基于关系数据库的存储方案是知识图的主要存储管理方法。我们将按时间顺序介绍各种基于关系的知识图存储方案，包括：三元表、属性表、垂直分区、六元组索引和DB2RDF。

（1）三元表

三元表是具有三列的表，其模式是 tripletable(subject,predicate,object)triple_table(subject,predicate,object) 。知识图中的每个三元组被存储为三元组表格中的一行。虽然三元表方案简单明了，但三元表的行数与知识图的边数相同。最大的问题是，在将知识图查询转换为SQL查询后，将会有许多三元表的自连接（ self−joinsself-joins ）。3store是一个早期的RDF三元组存储，它实现了三元表方案[13]。

（2）属性表

属性表存储方案将相同类型的 subjectssubjects 存储在同一表中，并且将不同类型的 subjectssubjects 划分为不同的表。虽然属性表克服了三元表的自连接问题，但属性表的缺点是：a、大型真实知识图可能有数千种主题类型，这可能会超出关系数据库的限制；b、即使在同一属性表中，不同主题的谓词集合也可能存在较大差异，这将导致空值问题。Jena是一个典型的RDF三元组存储和库，它使用属性表方案[20]。

（3）垂直分区

此方法为每个 predicatepredicate 创建一个包含两列的表 (subject、object)(subject、object) 。该表存储由谓词连接的主语和宾语值。表的总数是知识图中不同谓词的数量。垂直分区的优点是：a、谓词表只存储知识图中出现的三元组，这解决了空值问题；b、每个谓词表按 subjectsubject 列的值排序，合并-排序 JoinJoin 可用于快速执行不同谓词表的 JoinJoin 操作。然而，垂直分区的主要缺点是要创建的表的数量等于知识图中不同谓词的数量，这可能会在大型知识图的关系数据库中产生额外的开销。SW-Store是第一个实现垂直分割方案的RDF数据库系统[7]。

(4)六元组索引

在该方案中，三元组的所有6个排列相应地被构建成6个表，即 SPO(subject,predicate,object)SPO(subject, predicate, object) 、POS(predicate,subject,object)POS(predicate,subject, object) 、OSP(object,subject,predicate)OSP( object,subject, predicate) 、SOP(subject,object,predicate)SOP(subject, object, predicate) 、PSO(predicate,subject,object)PSO( predicate,subject, object) 和 OPS(object,predicate,subject)OPS(object, predicate,subject ) 。六元组索引不仅通过六个表的连接操作缓解了三元组表的自连接问题，而且提高了一些典型知识图查询的效率。然而，六元组索引需要6倍的存储空间开销和索引维护成本。RDF-3X是使用六元组索引方案的典型系统[17]。

(5)DB2RDF

此方案是以前的RDF关系存储方案之间的权衡。三元表的优点是“行维”的灵活性，即存储模式不会随着行数的增加而改变；DB2RDF为“列维”引入了这种灵活性，在“列维”中，表的列用作 predicatepredicate 和 objectobject 的存储位置，而不将列绑定到 predicatepredicate 。在插入三元组时，predicatepredicate 被动态映射到列；该方案可以确保将相同的谓词映射到相同的列集。在DB2RDF中， predicatepredicate 到列的映射是一个需要考虑的重要问题。因为关系表中的最大列数是固定的，所以映射的两个优化目标是：a、 使用的列数不应该超过某个值m；b、应该最小化将同一 subjectsubject 的两个不同 predicatepredicate 分配给同一列，从而减少可能导致自连接的溢出。DB2RDF方案已经在最新的IBMDB2数据库系统中实现[10]。

4.2 原生存储方案

原生知识图存储专门设计了知识图的底层存储管理方案。

（1）Neo4j

Neo4j是目前最流行的属性图形数据库之一。它的原生图存储层最重要的特征是“无索引邻接”，这意味着每个顶点保持对其相邻顶点的直接引用[19]。因此，每个顶点都可以看作是其相邻顶点的“局部索引”，可以用来查找顶点的邻居，这比使用全局索引节省了很多时间。在Neo4j中，属性图的顶点、边和属性分别存储在不同的文件中。正是这种将图结构与图属性分开存储的策略使得Neo4j在图遍历中具有很高的效率。

（2）GStore

GStore的底层存储使用对应于RDF图的签名图，并建立VS树索引结构以加速查询处理[21]。在GStore中，每个顶点及其邻居被编码成一个二进制比特串，这些比特串作为顶点形成与RDF图 GG 相对应的标签图 G∗G^∗ 。VS树索引实际上是标签图 G∗G^* 的摘要图，可以极大地减少SPARQL查询的搜索空间。

5 查询处理

尽管知识图查询语言多种多样，但它们主要有两种基本的查询机制，即子图匹配和导航。此外，几个知识图谱数据库还支持将分析查询作为内置操作。

5.1 子图匹配查询

子图匹配查询是知识图查询操作中最基本的类型之一。而基本图模式(BGP)匹配是子图匹配查询的核心。

基本图模式（BGP）

给定一个知识图 GG ，其上的一个 BGP Q被定义为

⋀1≤i≤m(si,pi,oi)\bigwedge_{1 \leq i \leq m}\left(s_{i}, p_{i}, o_{i}\right)

其中：a) si，pi，ois_i，p_i，o_i 是常数或变量( 1≤i≤m1≤i≤m )；b）(si，pi，oi)(s_i，p_i，o_i) 是一个三元组模式；c) ∧表示逻辑合取（conjunction）。BGP实际上是图上三元组模式的合取，因此它也被称为合取查询。BGP匹配查询有两种语义定义，即子图同态和子图同构。

给定一个知识图 G=(V，E)G=(V，E) ，且 BGPQ=∧1≤i≤m(si，pi，oi)BGP Q= ∧_{1≤i≤m}(s_i，p_i，o_i) ，设 s^=(si，...，sm)\hat{s}=(s_i，...，s_m)， p^=(pi，...，pm)\hat{p}=(p_i，...，p_m) ，o^=(oi，...，om)\hat{o}=(o_i，...，o_m) ，定义了BGP匹配的子图同态语义为：a) 设 σσ 是从 s^，p^，o^\hat{s}，\hat{p}，\hat{o} 到顶点集 VV 的映射；b) (G,σ)⊨Q(G, \sigma) \models Q 当且仅当 ∀i∈[1，m]，(σ(si)，σ(pi)，σ(oi))∈E∀i∈[1，m]，(σ(s_i)，σ(p_i)，σ(o_i))∈E；c) Q(G)Q(G) 是使 (G，σ)⊨Q(G，σ) \models Q 为真的 σσ 的集合。

BGP的子图同构语义更加严格，对子图同态施加了限制，使得 GG 中的映射保持了 QQ 的结构。此外，在BGP的基础上扩展了投影、过滤(选择)、连接、交、差和可选(左外连接)等关系操作，形成了一个复杂的图模式（CGP）。已有研究证明，BGP求值在各种语义下是NP完全的。在子图匹配查询评价算法方面，数据库界对BGP的研究由来已久，积累了大量的工作。

5.2 导航查询

导航查询是知识图上另一种重要的查询类型。匹配路径的大小无法预先确定，需要根据底层知识图进行导航。导航查询的最简单形式是确定两个顶点之间是否存在路径，即可达性查询。在实际应用中，导航查询的结果路径往往需要满足一定的约束条件，其中最常用的是规则路径查询(RPQ)。

常规路径查询（RPQ）

给定知识图 G=(V，E)G=(V，E) ，其边上的标签集 ΣΣ ，GG 中从顶点 v0v_0 到 vmv_m的路径 ρρ 是序列 v0a0v1a1v2...vm−1am−1vmv_0a_0v_1a_1v_2...v_{m−1}a_{m−1}v_m ，其中 vi∈Vv_i∈V ，ai∈Σa_i∈Σ ，(vi，ai，vi+1)∈E(v_i，a_i，v_{i+1})∈E 。路径 ρρ 的标签是 λ(ρ)=a0...am−1∈Σ∗λ(ρ)=a_0...a_{m−1}∈Σ∗ 。GG 上的 RPQ Q可定义为：

(x，r，y)(x，r，y)

其中：a) xx 和yy 是常量或变量；b) rr 是 ΣΣ 上的正则表达式，递归地定义为 r::=ε∣a∣r/r∣r∣r∣r∗，a∈Σr::=ε|a|r/r|r|r|r^∗，a∈Σ，// ，∣,|, 和 ∗∗ 分别是串联、交替和Kleene闭包。

给定一个知识图 G=(V，E)G=(V，E) 和 RPQQ=(x，r，y)RPQ Q=(x，r，y) ，QQ 的任意路径语义被定义为 Q(G)Q(G) 是G中的路径集合，该路径的标号满足正则表达式 rr ，即 Q(G)=ρ∣λ(ρ)∈L(R)Q(G)={ρ|λ(ρ)∈L(R)} 。由于知识图 GG 中可能存在循环，因此 Q(G)Q(G) 中的匹配路径集可以是无限的。在这种情况下，RPQ的任意路径语义是无法计算的。在实践中，需要限制语义才能使RPQ评估可计算。RPQ的求值理论上可以看作是正则表达式 rr 对应的自动机与知识图 GG 对应的自动机的乘法运算，其复杂度为PTIME[16]。

5.3 分析查询

与子图匹配和导航查询不同，分析查询不关心满足查询的图结构的本地实例，而是专注于度量整个知识图的聚合信息。简单的分析查询包括知识图（如顶点和边数）、顶点度、图中的最大/最小/平均度、图的直径等统计聚合。比较复杂的分析查询主要是计算密集型的图分析和挖掘算法，包括特征路径长度、连通分量、社区检测、聚类系数、PageRank等。

6 推理

推理是知识库所特有的功能，而不是通用数据库。知识图上的推理可以从已有的知识中获取新的知识，甚至挖掘隐藏的知识。目前，知识图推理方法大致可以分为基于规则的推理和基于学习的推理[11]。知识图推理的主要应用包括知识图补全、问答和推荐系统。从知识图数据管理的角度来看，知识图存储和查询处理对推理的支持等方面仍有很多未探索的工作要做。

7 系统

现有的知识图库管理系统大致可以分为三类，即基于关系的系统、RDF三元库和原生图形库。表1列出了几种常见知识图库管理系统的比较。

image-20210409233448723

8 结论

本文简要回顾了当前知识图数据管理的模型、方法和系统，包括数据模型、查询语言、存储方案、查询处理、推理和知识图数据库系统。

参考文献

  1. Dbpedia. https://wiki.dbpedia.org/. Accessed 29 Nov 2019
  2. The linked open data cloud. https://lod-cloud.net/. Accessed 29 Nov 2019
  3. Linkedgeodata. http://linkedgeodata.org/. Accessed 29 Nov 2019
  4. The neo4j manual v3.5. https://neo4j.com/docs/developer-manual/current/. Accessed 29 Nov 2019
  5. Tinkerpop3 documentation v.3.4.4. https://tinkerpop.apache.org/docs/current/reference/. Accessed 29 Nov 2019
  6. Uniprot. https://www.uniprot.org/. Accessed 29 Nov 2019
  7. Abadi, D.J., Marcus, A., Madden, S.R., Hollenbach, K.: SW-store: a vertically partitioned DBMS for semantic web data management. VLDB J. 18(2), 385–406(2009)
  8. Angles, R., et al.: G-CORE: a core for future graph query languages. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1421–1432.ACM (2018)
  9. Angles, R., Gutierrez, C.: Survey of graph database models. ACM Comput. Surv.(CSUR) 40(1), 1 (2008)
  10. Bornea, M.A., et al.: Building an efficient RDF store over a relational database. In:Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 121–132. ACM (2013)
  11. Chen, X., Jia, S., Xiang, Y.: A review: knowledge reasoning over knowledge graph. Expert Syst. Appl. 141, 112948 (2019)
  12. Cyganiak, R., Wood, D., Lanthaler, M., Klyne, G., Carroll, J.J., McBride, B.: RDF 1.1 concepts and abstract syntax. W3C Recomm. 25(02) (2014)
  13. Harris, S., Gibbins, N.: 3store: efficient bulk RDF storage (2003)
  14. Harris, S., Seaborne, A., Prud’hommeaux, E.: SPARQL 1.1 query language. W3C Recomm. 21(10), 778 (2013)
  15. Kostylev, E.V., Reutter, J.L., Romero, M., Vrgoˇ c, D.: SPARQL with property paths. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9366, pp. 3–18. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25007-6_1
  16. Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235–1258 (1995)
  17. Neumann, T., Weikum, G.: RDF-3X: a RISC-style engine for RDF. Proc. VLDB Endow. 1(1), 647–659 (2008)
  18. van Rest, O., Hong, S., Kim, J., Meng, X., Chafi, H.: PGQL: a property graph query language. In: Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, p. 7. ACM (2016)
  19. Robinson, I., Webber, J., Eifrem, E.: Graph Databases: New Opportunities for Connected Data. O’Reilly Media, Inc., Sebastopol (2015)
  20. Wilkinson, K., Wilkinson, K.: Jena property table implementation (2006)
  21. Zou, L.,Özsu, M.T., Chen, L., Shen, X., Huang, R., Zhao, D.: gStore: a graph-based sparql query engine. VLDB J.- Int. J. Very Large Data Bases 23(4), 565–590(2014)