知识图谱（8）-存储和查询

date

Sep 25, 2022

slug

KG-Storage-and-Querying

status

Published

知识图谱的基石：解析RDF数据的存储与查询技术

参考：知识图谱发展报告（2022）下载链接 (访问密码: 2096)

知识图谱（Knowledge Graph）通过图（Graph）结构来描述现实世界中的“实体”、“属性”及实体间的“关系”，已成为AI领域不可或缺的基础设施。其背后强大的数据模型——资源描述框架（RDF），为海量、异构的网络资源提供了标准化的描述方式。然而，当知识图谱的规模从百万级增长到百亿甚至千亿级三元组时，如何高效地存储和查询这些数据，便成为一个核心的技术挑战。本文将深入探讨基于RDF模型的知识图谱存储与查询技术，剖析从传统关系型数据库方案到原生图数据库，再到面向未来的分布式系统的演进路径。

RDF与SPARQL：知识图谱的数据与语言

RDF是W3C制定的标准，用于描述网络资源。在RDF模型中，任何实体（如哲学家“亚里士多德”）、属性（如姓名）或事件都可以被看作一个“资源”，并通过唯一的国际化资源标识符（IRI）来标识。知识由一个个“陈述”构成，每个陈述都遵循一个简单的三元组（Triple）结构：（主体 Subject, 谓词 Predicate, 客体 Object）。

例如，在描述亚里士多德生平的事实中：

(Aristotle, placeOfDeath, Chalcis) 表示 “亚里士多德” 死于 “卡尔基斯”。

(Aristotle, name, "Aristotle"@en) 表示 “亚里士多德” 的名字是 "Aristotle"（英文）。

当海量的三元组汇集在一起时，就形成了一个庞大的RDF数据集。为了从中检索信息，W3C同样定义了标准的查询语言——SPARQL。它类似于关系数据库的SQL，允许用户通过声明式的语法来描述需要查询的数据模式。

从数据管理的角度看，RDF数据天然形成一个有向标记图：实体和字面值是图中的节点，而谓词则是连接节点的有向边的标签。因此，一个SPARQL查询的本质，可以被看作是在庞大的RDF数据图上，寻找与查询模式相匹配的子图（Subgraph Matching）。

关系型数据库的探索：用传统武器应对新挑战

在知识图谱技术发展的早期，研究者们自然地想到了利用成熟的关系型数据库（RDBMS）来存储RDF数据。这种思路的核心在于如何将RDF的三元组模型映射到关系模型的二维表结构上。

1. 简单三元组表 (Simple Triple Table)

这是最直观的方法：创建一个包含三列（Subject, Predicate, Object）的巨大表格来存储所有三元组。这种方法通用性好，但性能是其致命弱点。复杂的SPARQL查询通常需要对这张巨型表进行多次自连接（Self-Join），这在RDBMS中是极其昂贵的操作，导致查询效率低下。

2. 结构化存储的尝试：属性表

为了减少连接操作，研究者提出了**水平存储（Horizontal Schema）或属性表（Property Table）**方案。其思想是将每个主体（Subject）作为表中的一行，每个谓词（Predicate）作为一个列。这样，查询一个实体的多个属性就无需连接操作。然而，这种方法的弊端同样明显：

稀疏性：知识图谱中的谓词种类繁多，会导致表拥有大量列，而大部分单元格都是空值（NULL）。

多值问题：一个属性可能对应多个值（如mainInterest），在关系表中难以优雅地处理。

灵活性差：新增属性意味着需要修改表结构（ALTER TABLE），成本高昂。

Jena和Oracle等系统通过聚类或类型信息将相似的三元组组织到不同的属性表中，一定程度上缓解了问题，但并未从根本上解决。

3. 性能优化的策略：垂直划分与全索引

垂直划分 (Vertical Partitioning)：该策略为每个谓词（Predicate）创建一个独立的双列表（Subject, Object）。这种方法（如SW-Store采用）将自连接转化为了不同表之间的连接，效率有所提升。但其缺点是，当SPARQL查询中的谓词是变量时，该方法就难以应对了。

全索引策略 (Exhaustive Indexing)：为了极致加速连接操作，RDF-3x和Hexastore等系统提出为三元组的所有六种排列（SPO, SOP, PSO, POS, OSP, OPS）都建立索引。这使得任何连接模式都能通过高效的归并排序连接（Merge-join）来完成。然而，这种策略带来了巨大的存储开销，并且在分布式扩展方面存在天然的局限性。

回归图的本质：原生图模型的存储与查询

鉴于RDBMS方案的种种局限，研究界逐渐回归到RDF数据的图本质上，开发了原生图数据库（Native RDF Graph Database）。这类系统将数据原生作为图来存储，并设计了专门针对图的索引和查询算法。

gStore是这一领域的杰出代表。它将每个资源的属性和关系信息编码成一个二进制位串，称为签名（Signature）。然后，它将所有资源的签名组织成一棵高效的索引结构——VS-tree*。当处理SPARQL查询时，gStore首先利用VS*-tree快速过滤掉大量不相关的候选节点，极大地缩小了搜索空间，然后再在剩余的候选子图上执行精确的匹配。这种基于图结构整体信息的索引方式，在处理复杂查询时，相比传统系统展现出数量级的性能优势。

新兴技术与未来展望：分布式与新硬件

随着DBpedia、YAGO等知识图谱规模达到数十亿甚至上百亿，单机系统已难以为继，存储和查询技术正朝着分布式架构和利用新硬件的方向发展。

1. 拥抱新硬件与新理论

新硬件：研究人员开始利用GPU强大的并行计算能力（如TripleID-Q）和RDMA（远程直接内存访问）的高带宽、低延迟特性（如Wukong系统）来加速RDF查询处理。

最坏情况下最优连接 (Worst-case Optimal Joins)：源自数据库理论的AGM界为多表连接的结果集大小提供了一个紧密的上界。将这一理论应用于SPARQL查询优化，可以设计出连接顺序更优、中间结果集更小的查询计划，显著提升性能。

2. 从单机到分布式：应对海量数据

互联网本身就是一个巨大的、去中心化的知识图谱，这催生了对分布式RDF数据管理技术的需求。目前主要有三条技术路线：

基于现有云平台：利用Hadoop、Spark等成熟的分布式计算框架。这类方法（如S2RDF, Sparklify）将RDF数据转换并存储在HDFS或Parquet等分布式文件系统上，利用MapReduce或Spark SQL进行查询。它们提供了良好的可扩展性和容错性，但通常缺乏对RDF数据和SPARQL查询的深度优化。

基于数据划分的定制系统：这类方法的核心思想是将RDF图划分成多个子图，部署到不同计算节点上，目标是最小化查询时跨节点的通信。划分策略可以是数据驱动的（如利用METIS等图划分算法），也可以是查询日志驱动的（通过分析历史查询模式，将经常一起被访问的数据放在同一节点）。

联邦查询系统 (Federated Systems)：随着关联开放数据（LOD）的发展，网络上出现了大量独立的RDF数据源。联邦查询系统（如FedX）旨在对这些自治的数据源执行统一的查询。其核心挑战在于：如何在不移动原始数据的情况下，智能地将一个SPARQL查询分解成多个子查询，并分发到正确的数据源上执行，最后再将结果合并。

总结与启示

知识图谱的存储与查询技术经历了一条清晰的演进路径：从最初借助成熟但存在“水土不服”问题的关系型数据库，到回归数据本质、设计原生图数据库，再到如今为应对互联网级别的海量数据而发展的分布式系统。每一种技术路线都在特定的历史时期解决了关键问题，并为后续发展奠定了基础。

核心启示:

没有银弹：无论是关系模型还是图模型，单机还是分布式，每种方案都有其适用场景和优缺点。技术的选择应基于数据规模、数据特点、查询负载和性能要求进行综合权衡。

未来是分布式的：随着数据规模的持续膨胀，分布式架构是必然趋势。未来的研究重点将持续聚焦于更智能的数据划分策略、更高效的分布式查询优化以及与新硬件的深度融合，以真正释放海量知识图谱的巨大潜力。