越来越多的知识实例数据开始表示成以三元组结构为基础的RDF格式。如何有效地存储和检索大规模的知识图谱数据集是一个重要的研究内容。

知识图谱是一种有向图结构，描述了现实世界中存在的实体、事件或概念以及它们之间的关系。对知识的持久化存储并提供对知识数据的高效检索是一个知识图谱系统必须具备的基本功能。本章首先介绍知识图谱的存储技术，按照存储策略的不同可以分为基于表结构的存储和基于图结构的存储。然后基于现有的知识图谱存储技术，介绍常见的形式化查询语言；最后，简要介绍知识图谱中的图搜索技术。

知识图谱的存储

知识图谱中的知识是通过RDF结构进行表示的，其基本构成单元是事实。每个事实是一个三元组(S,P,O)。

基于表结构的存储

  1. 三元组表

知识图谱中的事实是一个个的三元组，一种简单直接的存储方式是设计一张三元组表用于存储知识图谱中所有的事实。实际上，目前已有不少比较成熟的产品利用该形式存储知识图谱，包括Jena、Oracle、Sesame、3store、SOR、Rstar和Virtuoso。这种存储方式的有点是简单直接，易于理解；然而缺点也非常明显，主要有以下两点：

  • 整个知识图谱都存储在一张表中，导致单表的规模太大。对大表进行查询、插入、删除、修改等操作的开销很大，这将导致知识图谱的实用性大打折扣。
  • 复杂查询在这种存储结构上的开销巨大。由于数据表只包括三个字段，因此复杂查询只能拆分成若干简单查询的符合操作，大大降低了查询的效率。
  1. 类型表

为每种类型构建一张表，同一类型的实例存放在相同的表中。表的每一列表示该类实体的一个属性，每一行存储该类实体的一个实例。这种存储方式虽然克服了三元组表的不足，但是带来了新的问题：(1) 大量数据字段的冗余存储。(2) 大量的数据列为空值。

一种有效的解决方法是，在构建数据表时，将知识图谱的类别体系考虑进来。具体来说，每个类型的数据表只记录属于该类型的特有属性，不同类别的公共属性保存在上一级类型对应的数据表中，下级表继承上级表的所有属性。

基于类型表的存储方式根据类型对数据进行组织和管理，克服了三元组表面临的单表过大和结构简单的问题，但是也有明显的不足之处：

  • 由于类型表的不同字段表示了不同的属性或关系，因此在查询时必须指明属性或关系，无法做不确定属性或关系的查询。
  • 由于数据表是和具体类型对应的，不同类型的数据表具有不同的结构，因此在查询之前必须知道目标对象的类型才能确定查找的数据表。为了达到这一目的，系统需要维护一个”属性-类型“映射表，以便在进行属性查询时可以根据目标属性确定类型。
  • 当查询涉及不同类型的实体时，需要进行多表的链接，这一操作开销巨大，限制了知识图谱对复杂查询的处理能力。
  • 知识图谱通常包含丰富的实体类型，因此需要创建大量的数据表，并且这些数据表之间又具有复杂的关系，这为数据的管理增加了很大的难度。

关系数据库

上面介绍了基于表结构的不同的存储设计方式，数据的最终存储需要依赖具体的存储系统。关系数据库是典型的表结构存储系统。

基于图结构的存储

将实体看作节点，关系看作带有标签的边，那么知识图谱的数据很自然地满足图模型结构。因此，基于图结构的存储方式能够直接准确地反映知识图谱的内部结构，有利于对知识的查询。另外，以图的方式对知识进行存储，还可以借鉴图论的相关算法，有利于对知识的深度挖掘及推理。

  1. 基于图结构的存储模型

基于图结构的存储不按照类型来组织实体，而是从实体出发，不同实体对应的节点可以定义不同的属性。

节点可以定义属性，用于描述实体的特性。

常用的图数据库介绍

图数据库系统是实现基于图结构存储的典型系统。

图数据库的理论基础是图论，通过节点、边和属性对数据进行表示和存储。

常用的图数据库存储系统有Neo4j、OrientDB、InfoGrid、HyperGraphDB、InfiniteGraph等。

和成熟的关系数据库相比，图数据库的发展较晚，相关的标注及技术尚不完善，在实际使用中可能会遇到一些棘手的问题，因此在选用数据库时除了需要考虑数据库本身的特性、性能等因素以外，还需要考虑数据库的易用性、技术文档的完整性等因素。

知识图谱的检索

常见形式化语言

  1. SQL语言
  • 数据插入
  • 数据修改
  • 数据删除
  • 数据查询
  1. SPARQL语言
  • 数据插入：INSERT DATA 三元组数据
  • 数据删除：DELETE DATA 三元组数据
  • 数据更新：删除+插入
  • 数据查询
    • SELECT 变量1 变量2 … WHERE 图模式 [修饰符]
    • ASK 图模式
    • DESCRIBE 资源或变量 [WHERE 图模式]
    • CONSTRUCT 图模式 WHERE 图模式

图检索技术

由于知识图谱中的数据在逻辑上本身就是一种图结构，因此基于图结构的存储方式能够直观灵活地对知识进行表示和存储。然而利用图模型来构建知识图谱也有不可忽视的缺陷，标准的图查询算法复杂度较高，如何提高图查询的效率称为知识图谱研究的重要问题。

图是数学中的概念，一个图G可以用二元组(V,E)表示，记\(G=(V,E)\)。其中，V是顶点的集合，E是顶点之间边的集合。图查询的任务是在给定的图数据集中查找给定的查询图，其核心问题是判断查询图是否是图数据集的子图，因此也称为子图匹配问题。以下给出该问题的形式化定义：

子图匹配问题是指在给定查询图Q和目标图集\(D={G_1}\)的条件下，在D中找出所有与Q同构的子图。

子图同构问题是图论中一个古老的难题，其数学上的定义如下：

图\(G_1(V_1, E_1)\)和图\(G_2(V_2,E_2)\)的子图同构，当且仅当存在一个双射函数\(f:V_1 \to V_2\)，对于\(G_1\)的任意一条边\(e(v_1, v_2) \in E_1\)，都有\(e'(f(v_1), f(v_2)) \in E_2\)。

子图同构的问题已经被证明是一个NP完全问题，目前尚不存在多项式时间复杂度内可解决的算法。和数学中标准的图结构不同，知识图谱中的图结构具有丰富的标签信息：(1) 图中的节点有标签信息，例如实体类型信息；(2) 图中的边同样包含标签信息，例如关系类型信息。虽然子图同构判定问题的算法复杂度很高，但是在实际应用中匹配算法的运行时间通常都在可承受范围之内，主要有两方面的原因：一方面知识图谱中的图结构通常不会特别复杂，只有少数节点之间有边相连，因此并不会触发子图匹配算法的最坏情况；另一方面，利用知识图谱中丰富的标签信息可以有效降低算法的搜索空间。

  1. 子图筛选

图索引技术是实现子图筛选的有效方法。与信息检索中的索引机制类似，图索引是在数据预处理阶段进行的。其基本原理是首先根据图上的特征信息建立索引，在进行子图匹配时，根据查询图上的特征能够快速地从图数据库中检索得到满足条件的候选子图，避免在全部子图上进行匹配操作。基于路径的索引和基于子图的索引是最常见的两种图索引方法。

基于路径的索引方法将知识图谱中所有长度小于某特定值的路径收集起来，并根据这些路径为图数据库中的子图建立倒排索引。在进行图匹配时，首先从匹配图中抽取具有代表性的路径，然后利用索引检索获得所有包含这些路径的候选子图，最后再候选子图上进行同构测试获得最终的结果。这种索引方式的优点是图的路径获取简单直接，因此构建索引比较方便。但是问题也比较明显，随着路径长度的增加，路径数目呈指数级增长，对于大规模知识图谱来说，需要索引的路径数目过于庞大，不仅耗费巨大的存储空间，也增加了检索的时间；另外，不同路径对于子图的区分性差异很大，区分性低的路径对于降低搜索空间的效果有限。

  1. 子图同构判定

子图同构是一个经典的NP难题，尚且不能确定是否存在多项式复杂度的算法。Ullmann算法是实践中常用的一种判定子图同构的算法，它能够枚举出所有的同构子图，因此也叫做枚举算法。