图数据库介绍

图数据库怎么选、怎么存：从产品版图到 RDF 存储内核

小象实战讲义 · 知识图谱

上一节我们用 Apache Jena/Fuseki 把音乐知识图谱真正建了起来、跑出了 SPARQL 查询。但 Jena 只是众多图数据库中的一种：为什么有的系统单机就能装下十亿条三元组、有的主打企业级知识图谱平台、有的用起来和 SQL 数据库完全是两套思路？这一节视频一口气讲完了课件的两大部分：第二部分「图数据库介绍」（产品版图与选型）和第三部分「RDF 存储实现细节」（引擎内核机制）。相应地，本节回答两个层层递进的问题 ——第一，市面上的图数据库如何分类、各自适合什么场景、该怎么选型；第二，一个 RDF 图数据库内部到底怎样把海量三元组存下来，还能让 SPARQL 秒级返回。学完你会建立一张完整的图数据库选型地图，并能用现代 Python 亲手实现「属性图匹配与最短路径」「三元组表 self-JOIN」「字典编码与六排列索引」「三种存储布局对比」这些核心机制的最小可运行版本，从而真正看懂系统为什么快、又慢在哪。

💡 核心导读

• 图数据库按「是否为图原生存储」分成三条技术路线：基于关系数据库、基于 NoSQL、原生图存储；数据模型则分 RDF 三元组模型与属性图模型两大阵营。

• 开源（RDF4J、gStore）、商业（Virtuoso、AllegroGraph、Stardog）、原生属性图（Neo4j、OrientDB、Titan）定位各不相同；SPARQL 查 RDF，Cypher/Gremlin 查属性图。

• 「联邦（federation）」与「分布式（distributed）」是两种不同的横向扩展机制；选型用五个 Benchmark 指标量化，而不是看宣传口径。

• 图数据库做的是图查询（本质是子图匹配 + 查询优化），图计算做的是图性质迭代（PageRank、最短路径、社区发现），两者边界要清楚。

• RDF 存储内核沿一条主线演进：schema-free 三元组表 → 把 SPARQL 翻译成一串 self-JOIN 的 SQL → 字典编码字符串为整数 → 六排列聚簇索引 → Merge/Hash Join → RDF-3X 差分压缩 → 选择度估计选执行计划 → 用垂直分区 / 列存 / 属性表消除 self-JOIN。

1. 图数据库的分类版图：三条存储路线、两种数据模型

1.1 从 RDF4J 的一段 Java 代码说起

上一节在 Fuseki 里点鼠标建库，底层其实是一套可编程的 API。以开源框架 RDF4J（以及同为 Java RDF 框架、但相互独立发展的 Jena）为例，建一个内存库、写入三元组、序列化成 Turtle 的典型 Java 流程是：先建一个 MemoryStore（内存存储），通过命名空间（namespace）与本地名（local name）拼出 URI，用 ValueFactory 工厂创建字面量（Literal，带 xsd:string 等数据类型），再把一条条 Statement（即三元组）加进库，最后序列化输出。Turtle 里共享主语的多条三元组用分号 ; 缩写（等价于键值对的连续书写），a 是 rdf:type 的缩写。

这套 Java 工程是课程录制年代的主流写法，环境较重、不要求复现。本节稍后会用现代 Python 把其中与存储和查询相关的核心机制重写成可直接运行的最小示例，帮助你对照视频理解原理，而不必搭建陈旧的 Java 环境。

1.2 三条技术路线

所谓「图数据库」，实现方式并不只有一种。按「是否为图数据设计了专门的底层存储」，可以分成三类：

图数据库

├── 非原生（在通用数据库之上套一层 RDF/图 接口）

│   ├── 基于关系数据库

│   │   ├── 单三元组表（schema-free triple table，一张 S/P/O 三列表装下一切）

│   │   ├── 垂直分区（vertical partitioning，每个谓词一张两列表）

│   │   └── 属性表（property table，按实体聚成宽表）

│   └── 基于 NoSQL

│       ├── 键值型（如 Redis 风格）

│       ├── 文档型（如 MongoDB 风格）

│       └── 宽表 / 列存（如 HBase、Cassandra 风格）

└── 原生图数据库（native，为图专门设计存储结构）

    ├── 原生 RDF 存储（如 gStore 的专用图索引、RDF-3X 的六排列聚簇索引，仍是索引驱动）

    └── 原生属性图存储（如 Neo4j，典型特征是“免索引邻接”）

• 基于关系数据库的非原生方案：最直接的做法是建一张只有 (subject, predicate, object) 三列的「三元组表」，schema-free（无模式）—— 不管什么谓词、什么实体，统统塞进同一张表，连本体本身（Person 是类、works_for 是属性）也能当数据存进去。它最通用，但查询一个稍复杂的问题就要把这张大表和自己连接很多次（self-JOIN，后面会实测有多慢），于是又演化出垂直分区、属性表等改良布局。

• 基于 NoSQL 的非原生方案：键值、文档、宽列等 NoSQL 存储天然 schema-less、易横向扩展，在其上封装 RDF / 图接口可以借力其分布式能力，但要自己补齐事务、查询优化等能力。

• 原生图数据库：底层存储结构专门为图设计，但两条子路线的机制不同。 原生属性图（如 Neo4j） 让节点物理上直接持有邻接指针（免索引邻接，index-free adjacency），多跳遍历不必反复回表查索引，在高连通数据的路径查询上天然占优； 原生 RDF 存储（如 RDF-3X、gStore） 并不靠邻接指针，而是走专用索引路线（六排列聚簇索引、图索引，见第 5、6 节）。

1.3 两种数据模型：RDF 三元组 vs 属性图

除了存储路线，还要分清两种数据模型，它决定了你用什么查询语言：

两种模型可以相互映射：属性图里「边上的属性」在 RDF 中可以用 空白节点（BNode）或 Freebase 提出的复合值类型（CVT，compound value type） 重新表示。例如「特朗普在某时间段担任美国总统」，属性图直接在「担任总统」这条边上挂 start_date、end_date；RDF 则引入一个表示「任职事件」的空白 / CVT 节点，再连出人物、职位、起止时间。理解这条映射，后面看 Neo4j 时就不会觉得它和 RDF 是两个世界。

2. 开源与商业 RDF 图数据库

2.1 开源：RDF4J 与 gStore

RDF4J（前身是 Sesame） 是一个处理 RDF 数据的 Java 框架（官网 rdf4j.org）：用简单可用的 API 实现 RDF 存储，支持 SPARQL endpoint，支持两种 RDF 存储机制（内存存储与原生磁盘存储），兼容所有主流 RDF 文件格式。它的底层存储与推理抽象层称为 SAIL（Storage And Inference Layer），上层提供 RDF API，并可与独立的 OWL API 等标准接口集成（OWL API 是单独维护的 Java 库，并非 RDF4J 内置实现），因此可以只替换底层存储后端、上层代码基本不动。Sesame 改名为 RDF4J 后，官方提供了迁移指南。

gStore 是北京大学邹磊老师团队用 C++ 实现的原生 RDF 图数据库（官网 gstore-pku.com，OpenKG 也将其作为工具收录），从图数据库的角度存储和检索 RDF 知识图谱：

• 支持 W3C 定义的 SPARQL 1.1 查询标准，覆盖课件列出的查询特性——含 UNION、OPTIONAL、FILTER 与聚集函数的查询，并支持有效的增删改操作；

• 单机即可支持 1 Billion（十亿）条三元组规模的数据管理 —— 要知道一张装了十亿行的普通关系表做查询会非常慢，而 gStore 仍能保持较快的 SPARQL 查询，适合存储百科类等大规模知识图谱；

• 后续还发展了分布式版本 gStore-D（distributed）。

2.2 商业：Virtuoso、AllegroGraph、Stardog

Virtuoso（OpenLink） 严格说不是一个「纯」图数据库，而是一个混合数据库：底层是一个虚拟化数据库引擎（Virtual Database Engine），在其上统一存储 RDF、关系（SQL）、XML、全文（free text）等多种异构数据模型，对外提供 HTTP/SPARQL 等接口，并可通过 ODBC/JDBC 驱动关联外部数据库，还支持 .NET、Java、C++ 等多种语言的运行时扩展。我们前面反复用到的 DBpedia，其公共 SPARQL endpoint 底层就是用 Virtuoso 存储的—— 这也是它最广为人知的落地案例。

AllegroGraph（美国 Franz 公司） 是一个现代、高性能、支持永久存储的商业图数据库，基于 RESTful 接入、支持多语言编程。Franz 公司有深厚的函数式语言背景（最早做 Lisp 编译器 / 解释器与 Allegro CL 开发环境），这给 AllegroGraph 带来几个鲜明特征：

• 不止增删改查与数据导入，还具备企业级能力：备份、数据恢复、日志回滚、分布式、安全、压缩、索引、全文本、事务、会话管理、查询优化、联邦（federation）；

• 推理能力丰富：除 SPARQL 外还支持规则推理、Prolog 推理、地理空间推理、社交网络分析（SNA，social network analysis）、时态推理，并在 RDFS 之上加入 OWL 公理，形成 RDFS++ 本体语言；支持用 Lisp/JavaScript 编写类似用户自定义函数（UDF）的存储过程；

• 提供 RESTful 接口，并兼容 Jena、RDF4J（Sesame）的 RDF API/OWL API，因此可以把后两者的底层存储平滑替换成 AllegroGraph，迁移成本低。

它在导入性能上常以 LUBM 基准演示：LUBM（Lehigh University Benchmark）是面向大学域的合成基准，构造大学、教授、课程、学生之间的关系（与本课的音乐图谱分属不同领域），生成 8000 所大学时约有十亿条三元组，AllegroGraph 导入约 36 分钟、每秒约 50 万条三元组，优化场景下可达百万级。

Stardog 面向的是 企业知识图谱（Enterprise Knowledge Graph） 平台，定位为「a Knowledge Graph Platform for the Enterprise」：一是整合各种来源的数据，二是让图内的知识表示可复用，三是做到企业级可扩展，四是提供丰富的上层接口，把机器学习、推理、规则等复杂性封装起来，使用者不必关心底层细节即可完成知识融合、查询、搜索与分析。如果你要做行业知识图谱的统一管理平台，Stardog 是值得重点考察的一类。

本节介绍的 Jena、RDF4J、Virtuoso、AllegroGraph 等多为课程录制年代的主流工程，版本迭代很快；学习时重点理解它们各自解决了什么问题、处在版图的哪个位置，具体版本号与参数以官方最新文档为准。

3. 原生属性图数据库：Neo4j 与同类

3.1 属性图、全文索引与 Neo4j 的基本能力

原生属性图数据库的代表是 Neo4j（neo4j.com）。它内置 Lucene 全文索引（Apache 的开源全文检索基石，Solr、Elasticsearch 等流行搜索引擎也都是在 Lucene 之上改造而来），核心特性包括：

• 支持属性图：节点（Nodes）和关系（Relationships）两种基本数据类型，二者都包含 key/value 形式的属性；节点通过关系相连，形成关系网络；

• 支持 ACID 事务、高可用（high availability）、REST API 接口；

• 官方资料给出的规模量级为可支持约 320 亿个节点、320 亿条关系、640 亿个属性。

属性图相比 RDF 的一个直观好处，是让「边」成为和对象同等重要的一等公民，并且很容易表达多元关系与时态信息（边上直接挂 start_date/end_date 等属性），不必像 RDF 那样借助空白节点或 CVT 展开。此外它还内建了一部分图计算能力（路径查找、A* 算法等）。

3.2 安装、端口与数据导入

官方提供 Docker 镜像，一条命令即可启动：

docker run -d -p 7473-7474:7473-7474 -p 7687:7687 neo4j

三个端口各司其职，记住它们的分工：

打开 Web 前端后，默认用户名 / 密码都是 neo4j，首次连接会要求改密码；顶部输入框用来执行脚本与查询，下方动态展示结果。数据导入有五种常见途径：① Cypher 的 CREATE 语句（一条数据写一个 CREATE）；② LOAD CSV 把数据转成 CSV 批量读取；③ 官方 Java API 的 Batch Inserter；④ 官方 neo4j-import 工具；⑤ 第三方开发的 Batch Import 工具。磁盘上则分为存储文件（store）与索引（index）两部分，索引里分别维护统计信息、id、label、节点、关系等。

3.3 查询语言：Cypher 与 Gremlin

Neo4j 不支持 SPARQL，而是用一门思路与之对应、同样基于图模式的声明式语言 Cypher（二者底层数据模型不同 ——SPARQL 面向 RDF 三元组图、Cypher 面向属性图，表达能力与标准地位也有差异，并非严格等价）；另有一门更偏遍历的语言 Gremlin：

• Cypher：描述「要找什么样的图模式」，用圆括号表示节点、方括号箭头表示关系，接近 SPARQL 的三元组模板拼查询图；

• Gremlin：更像面向对象的遍历语言，先选定起始节点（start），再一步步 match、traversal（遍历），返回一跳或多跳关联的对象或对象集合。

以官方自带的 Movie Graph 示例（内部集成 D3.js 做客户端图可视化，绿色节点是人、红色节点是电影，边分 ACTED_IN（出演）与 DIRECTED（导演））为例，两条典型 Cypher 如下：

// 查询和 Tom Hanks 有关的电影：RETURN 只投影人物 p 与电影 m 两个节点

// （MATCH 命中的边不会随节点自动返回，需要时要显式 RETURN 关系，或由前端按模式渲染）

MATCH (p:Person {name:"Tom Hanks"})-[:ACTED_IN|DIRECTED]->(m:Movie)

RETURN p, m;

// 求 Meg Ryan 与 Kevin Bacon 之间的最短路径；[*..6] 类似 SPARQL 1.1 属性路径的变长写法，

// shortestPath( ) 属于图计算能力，而不是普通图查询

MATCH (p1:Person {name:"Meg Ryan"}),

      (p2:Person {name:"Kevin Bacon"}),

      path = shortestPath((p1)-[*..6]-(p2))

RETURN path;

下面用纯 Python 标准库实现一个最小属性图，同时演示「Cypher 风格的子图匹配（图查询）」与「BFS 最短路径（图计算）」的区别 —— 这正是本节要反复强调的边界：

from collections import deque

# 属性图：节点带 label 和属性（key-value），边（relationship）本身也是一等公民

class PropertyGraph:

    def __init__(self):

        self.nodes = {}          # id -> {"label":..., "props":{...}}

        self.adj = {}            # id -> [(neighbor, rel, direction)]

    def add_node(self, nid, label, **props):

        self.nodes[nid] = {"label": label, "props": props}

        self.adj.setdefault(nid, [])

    def add_edge(self, u, rel, v):

        self.adj.setdefault(u, []).append((v, rel, "->"))

        self.adj.setdefault(v, []).append((u, rel, "<-"))   # 连通无向、方向有标记

    def find(self, label, **props):

        # 对应 Cypher MATCH (n:label {key:value})：按 label+属性定位起始节点

        return [nid for nid, d in self.nodes.items()

                if d["label"] == label and all(d["props"].get(k) == v for k, v in props.items())]

    def match_movies_of(self, person_name, rels=("ACTED_IN", "DIRECTED")):

        # MATCH (p:Person)-[:ACTED_IN|DIRECTED]->(m:Movie) RETURN p,m（子图匹配 = 图查询）

        rows = []

        for p in self.find("Person", name=person_name):

            for nb, rel, direction in self.adj[p]:

                if direction == "->" and rel in rels and self.nodes[nb]["label"] == "Movie":

                    rows.append((person_name, rel, self.nodes[nb]["props"].get("title")))

        return rows

    def shortest_path(self, a_name, b_name):

        # shortestPath( )：BFS 求两节点间最短路径（这一步属于图计算）

        a, b = self.find("Person", name=a_name)[0], self.find("Person", name=b_name)[0]

        q = deque([(a, [a])]); seen = {a}

        while q:

            cur, path = q.popleft()

            if cur == b:

                return path

            for nb, _, _ in self.adj[cur]:

                if nb not in seen:

                    seen.add(nb); q.append((nb, path + [nb]))

    def label_of(self, nid):

        return self.nodes[nid]["props"].get("name") or self.nodes[nid]["props"].get("title")

g = PropertyGraph()

for nid, title in [("m_apollo", "Apollo 13"), ("m_sleepless", "Sleepless in Seattle"),

                   ("m_thing", "That Thing You Do!")]:

    g.add_node(nid, "Movie", title=title)

for nid, name in [("p_hanks", "Tom Hanks"), ("p_meg", "Meg Ryan"), ("p_bacon", "Kevin Bacon")]:

    g.add_node(nid, "Person", name=name)

g.add_edge("p_hanks", "ACTED_IN", "m_apollo")

g.add_edge("p_hanks", "ACTED_IN", "m_sleepless")

g.add_edge("p_hanks", "ACTED_IN", "m_thing")

g.add_edge("p_hanks", "DIRECTED", "m_thing")   # That Thing You Do 由 Tom Hanks 自导自演

g.add_edge("p_bacon", "ACTED_IN", "m_apollo")

g.add_edge("p_meg", "ACTED_IN", "m_sleepless")

print("MATCH (p:Person{name:'Tom Hanks'})-[:ACTED_IN|DIRECTED]->(m:Movie)：")

for who, rel, movie in g.match_movies_of("Tom Hanks"):

    print(f"   {who} --{rel}--> {movie}")

path = g.shortest_path("Meg Ryan", "Kevin Bacon")

print("\nshortestPath(Meg Ryan, Kevin Bacon)：")

print("   " + " -> ".join(f"{g.label_of(n)}[{g.nodes[n]['label']}]" for n in path))

运行结果：

MATCH (p:Person{name:'Tom Hanks'})-[:ACTED_IN|DIRECTED]->(m:Movie)：

   Tom Hanks --ACTED_IN--> Apollo 13

   Tom Hanks --ACTED_IN--> Sleepless in Seattle

   Tom Hanks --ACTED_IN--> That Thing You Do!

   Tom Hanks --DIRECTED--> That Thing You Do!

shortestPath(Meg Ryan, Kevin Bacon)：

   Meg Ryan[Person] -> Sleepless in Seattle[Movie] -> Tom Hanks[Person] -> Apollo 13[Movie] -> Kevin Bacon[Person]

可以看到：子图匹配只是「按模式把符合的点和边取出来」（图查询），而最短路径要在图上做迭代搜索（图计算）——Meg Ryan 与 Kevin Bacon 没有直接合演，需要经 Tom Hanks 与两部电影中转，共 4 跳。

3.4 多模型数据库，与可插拔后端的 Titan

• OrientDB 是 Java 实现的开源 NoSQL 数据库管理系统，关键词是多模型（multi-model）：同时支持图（graph）、文档（document，类似 MongoDB）、键值（key-value，类似 Redis）、对象（object）与关系（relational）模型。当多种异构数据模型并存时它很方便，接口丰富但写入与查询需要较多技巧；它与 Neo4j 的性能对比在不同负载下各有胜负，需要自己实测。

• ArangoDB 是课件之外、思路与 OrientDB 类似的多模型数据库：既想要关系表 / 文档的 schema-less 灵活，又想在同一系统里表达图关系，建模方便，但单项性能未必最优。

• 课件把 Titan 归在原生图数据库一类：定位弹性、可线性扩展数据与用户规模，支持数据分布、复制与容错，提供增删改查与一致性。其特点是支持各种可插拔的存储后端（storage backend）——可对接 BerkeleyDB 等键值存储，以及 HBase、Cassandra 等大数据生态，索引也可借助外部的 Lucene；同时对接 Spark、GraphX、Giraph 等大数据分析平台，既支持在线事务处理（OLTP）的增删改查，又能支撑在线分析处理（OLAP）。它架构复杂、安装维护成本高、上手慢，如果数据量不大、图谱专一、又没有复杂图计算需求，Titan 并不是轻量的选择。

3.5 联邦（federation）与分布式（distributed）不是一回事

横向扩展时这两个词经常被混用，但机制完全不同，务必分清：

联邦 federated database                    分布式 distributed database

┌──────────────┐                            ┌────────┐ ┌────────┐ ┌────────┐

│ 联邦查询引擎  │                            │ 分片 1  │ │ 分片 2  │ │ 分片 3  │

│  查询路由/分拆 │──查询──> 异构库 A/B/C...     │ 同构    │ │ 同构    │ │ 同构    │

│  结果再融合   │<─结果── （RDF/关系/NoSQL…）   │ schema  │ │ schema  │ │ schema  │

└──────────────┘                            └────────┘ └────────┘ └────────┘

强调：异构、可能同地、query 路由与分拆融合      强调：同构、因存不下而分片，片间尽量无 overlap，结果 UNION 合并

• 联邦（federation）：把异构的、彼此独立的数据库 / 知识库关联在一起（甚至物理上在同一处），核心是 query 的路由、分拆，以及结果的融合—— 把一个查询拆给各独立库分别执行，再把各库返回的结果二次融合后交给用户，它本质上是一种知识融合与跨源查询机制。

• 分布式（distributed）：参与的多为同构数据库，往往是因为单机存不下，才把数据分片存到不同地方、各片共享同一 schema，片与片之间的 overlap 尽量小甚至没有；其中简单的分片扫描结果用 UNION ALL 即可合并，而跨分片的连接、聚合还需要重分区（reshuffle）与协调，并不是一个 UNION 就能完成。

4. 怎么衡量与选型：Benchmark 五指标，以及图数据库 vs 图计算

4.1 常用 Benchmark：人造数据与真实数据

W3C 维护了一个 RDF 存储基准的汇总页（RdfStoreBenchmarking）。基准数据分两类：

• 人造（合成）数据：如 LUBM（Lehigh University Benchmark，大学 / 教授 / 课程 / 学生域，相对通用，并且会考察是否支持推理）；BSBM（Berlin SPARQL Benchmark，面向电商领域）。它们的好处是可以通过调节生成规模（100、1000、1 万、1 亿……）来压测可扩展性。

• 真实数据：如基于 DBpedia 的 SPARQL Benchmark，以及其他基于真实知识库构建的基准；也可以对真实图谱采样 5%、10%、20% 来模拟规模增长。

4.2 五个衡量指标

课件给出五个常用指标，选型时应围绕它们量化比较，而不是凭印象：

关于响应时间有两个关键概念：缓存（cache） 分系统缓存与数据库缓存；混合查询（mixed query） 会不断打乱缓存、使系统近似处于 冷启动（cold start） 状态（缓存里没有预存当前查询所需的最终或中间结果），更能反映真实负载。最终选型还要回到自己的场景：图谱规模有多大、读写要求多高、并发量多少、查询表达能力要多强。

4.3 图数据库（图查询）与图计算的边界

课件在章末专门做了区分，这也是本节的一条主线：

• 图查询（图数据库的本职）：包含图数据结构的存储（storage），以及在其上的查询。SPARQL（或 Cypher）本质都是子图匹配（subgraph matching）—— 从哪个节点出发、如何计算子图结果、以什么顺序连接各个三元组模式（triple pattern 的 JOIN 顺序），后者就是查询优化（query optimization）。

• 图计算 / 大图处理（big graph processing/computing）：对图做性质计算与迭代分析，例如最短路径、A* 算法、社交网络分析（SNA，属复杂网络）、实体链接里用到的类 PageRank 迭代算法；以及基于图的挖掘（graph-based mining）：频繁子图挖掘、社区发现（community detection）等。这类工作常跑在 Spark 的 GraphX、Apache Giraph 等分布式计算框架上。

简单说：图数据库回答「图里有什么、符合什么模式」，图计算回答「这张图整体有什么性质」。Neo4j 这类原生图库也会顺带提供 shortestPath 等少量图计算能力，但大规模图性质计算通常交给专门的图计算框架。

5. RDF 存储内核（一）：三元组表、SPARQL→SQL、字典编码与六排列索引

理解了产品版图，接下来钻进引擎内部：一个 RDF 数据库到底怎么存三元组、怎么执行 SPARQL。这部分是本节最硬核、也最能解释「为什么有的查询特别慢」的内容。

5.1 schema-free 单三元组表

最朴素的方案就是一张三列表 Triples(subject, predicate, object)，把所有三元组按行塞进去（Single Triple Table）。以课件该小节的演示数据（Katja / Martin / Ralf 三位教师）为例，Turtle 片段与对应的三元组表如下。为统一书写、便于在 Python/SQL 里处理，本节演示把课件里的 PhD_from 一律写作小写 phd_from；注意 RDF 的 URI 大小写敏感，真实工程中应与本体定义保持一致：

# Turtle（共享主语用分号缩写）

ex:Katja  ex:teaches   ex:Databases ;

          ex:works_for ex:MPI_Informatics ;

          ex:phd_from  ex:TU_Ilmenau .

# 展开成三元组表（schema-free，连本体也能当数据存：works_for 是属性、Person 是类）

subject      predicate     object

ex:Katja     ex:teaches    ex:Databases

ex:Katja     ex:works_for  ex:MPI_Informatics

ex:Katja     ex:phd_from   ex:TU_Ilmenau

ex:Martin    ex:teaches    ex:Databases

...          ...           ...

5.2 把 SPARQL 翻译成 SQL：本质是一串 self-JOIN

在单三元组表上，SPARQL 是如何变成 SQL 的？课件给了六条通用规则：

1. 每个三元组模式（triple pattern）翻译成三元组表上的一次（自）连接 ——(self-)JOIN；

2. 三元组模式之间的共享变量形成 JOIN 连接条件；

3. 模式里的常量形成 WHERE 条件；

4. FILTER 条件形成 WHERE 条件；

5. OPTIONAL 子句形成外连接（OUTER JOIN）；

6. UNION 子句形成 UNION 表达式。

以这条查询为例（找两个人 a、b 在同一单位 u，且 a 博士毕业于 u，u 名字含「Saar」，并可选地带上 a 教的课 t）：

PREFIX ex: <http://example.org/>
SELECT ?a ?b ?t WHERE {

  ?a ex:works_for ?u .

  ?b ex:works_for ?u .

  ?a ex:phd_from  ?u .

  OPTIONAL { ?a ex:teaches ?t }

  FILTER(REGEX(STR(?u), "Saar"))

}

它被逐步翻译成对同一张三元组表取别名 P1、P2、P3、P4 的 self-JOIN SQL（OPTIONAL 对应 LEFT OUTER JOIN，FILTER 对应 REGEXP_LIKE/LIKE）：

SELECT R1.A, R1.B, R2.T FROM

( SELECT P1.subject AS A, P2.subject AS B

  FROM Triples P1, Triples P2, Triples P3

  WHERE P1.predicate='works_for' AND P2.predicate='works_for' AND P3.predicate='phd_from'

    AND P1.object=P2.object AND P1.subject=P3.subject AND P1.object=P3.object

    AND P1.object LIKE '%Saar%' ) R1

LEFT OUTER JOIN

( SELECT P4.subject AS A, P4.object AS T FROM Triples P4

  WHERE P4.predicate='teaches' ) R2

ON R1.A=R2.A;

下面用 Python 内置的 sqlite3 真实建表、跑这条 self-JOIN SQL，同时用 rdflib 跑同语义 SPARQL，验证二者结果一致 —— 这能让你直观看到「SPARQL 到 SQL」不是抽象概念，而是可执行的等价改写：

import sqlite3

from rdflib import Graph, Namespace

# 课件 Page81 Single Triple Table 的演示数据：教师 / 授课 / 就职单位 / 博士毕业单位

raw = [

    ("Katja",  "teaches",  "Databases"),

    ("Katja",  "works_for", "MPI_Informatics"),

    ("Katja",  "phd_from", "TU_Ilmenau"),

    ("Martin", "teaches",  "Databases"),

    ("Martin", "works_for", "MPI_Informatics"),

    ("Martin", "phd_from", "Saarland_University"),

    ("Ralf",   "teaches",  "Information_Retrieval"),

    ("Ralf",   "phd_from", "Saarland_University"),

    ("Ralf",   "works_for", "Saarland_University"),

    ("Ralf",   "works_for", "MPI_Informatics"),

]

con = sqlite3.connect(":memory:")

con.execute("CREATE TABLE Triples(subject TEXT, predicate TEXT, object TEXT)")

con.executemany("INSERT INTO Triples VALUES(?,?,?)", raw)

sql = """

SELECT R1.A, R1.B, R2.T FROM

( SELECT P1.subject AS A, P2.subject AS B

  FROM Triples P1, Triples P2, Triples P3

  WHERE P1.predicate='works_for' AND P2.predicate='works_for' AND P3.predicate='phd_from'

    AND P1.object=P2.object AND P1.subject=P3.subject AND P1.object=P3.object

    AND P1.object LIKE '%Saar%' ) R1

LEFT OUTER JOIN

( SELECT P4.subject AS A, P4.object AS T FROM Triples P4

  WHERE P4.predicate='teaches' ) R2

ON R1.A=R2.A

"""

print("SQL self-JOIN 结果（?a ?b ?t）：", con.execute(sql).fetchall())

EX = Namespace("http://ex.org/lubm#")

rg = Graph()

for s, p, o in raw:

    rg.add((EX[s], EX[p], EX[o]))

sparql = """

PREFIX ex: <http://ex.org/lubm#>

SELECT ?a ?b ?t WHERE {

  ?a ex:works_for ?u . ?b ex:works_for ?u . ?a ex:phd_from ?u .

  OPTIONAL { ?a ex:teaches ?t }

  FILTER(REGEX(STR(?u), "Saar"))

}

"""

for r in rg.query(sparql):

    print("SPARQL 结果（?a ?b ?t）：", (

        str(r.a).split("#")[-1], str(r.b).split("#")[-1],

        None if r.t is None else str(r.t).split("#")[-1]))

con.close()

运行结果：

SQL self-JOIN 结果（?a ?b ?t）： [('Ralf', 'Ralf', 'Information_Retrieval')]

SPARQL 结果（?a ?b ?t）： ('Ralf', 'Ralf', 'Information_Retrieval')

只有 Ralf 同时「就职于 Saarland、博士毕业于 Saarland」，且他教 Information_Retrieval。问题在于：一条查询里三元组模式越多，同一张大表就要和自己 JOIN 越多次。通用关系数据库本是为灵活、通用的存储设计的，并不擅长处理单表的多次 self-JOIN，还常常生成糟糕的执行计划。于是必须做三件事：该建哪些索引、如何缩小存储空间、如何选出最佳执行计划。

5.3 字典编码：把字符串压成整数

数据库不会直接存冗长的 URI / 字符串，而是维护一张很小、可常驻内存的字典（dictionary），把每个字符串映射为一个定长整数（通常 4–8 字节，多用哈希实现）：

<http://example.de/Katja>   -> 194760

<http://example.de/Martin>  -> 679375

<http://example.de/Ralf>    -> 4634

整数定长、比较与排序都快得多，字典本身很小可放内存。但代价是：哈希分配的 id 会破坏原有的字典序（lexicographic order）——SPARQL 当然可以用 FILTER 写大小比较（如 ?x > 10 && ?x < 100，这就是范围条件），但字典序一旦被哈希打乱，就没法再对字典/索引做有序区间扫描来高效满足这类范围条件，相关 FILTER 只能逐行回表过滤、代价更高 —— 这是工程上的一组权衡。

5.4 六排列聚簇索引（hexastore）：让任意三元组模式都能走索引

只有一张 SPO 排序的表不够用：三元组模式里常量出现的位置可能是 S、P、O 的任意组合。观察到「只有一个变量的三元组模式最常见」（如 Albert_Einstein invented ?x），做法是为 S、P、O 的六种全排列各建一份聚簇索引（clustered index），底层用 B+ 树支持有序访问：

• SPO、SOP、POS：覆盖所有「两常量一变量」三元组模式的最小索引集合。两常量落在 S/P/O 三个位置共有 C(3,2)=3 种组合：固定 S、P 时由 SPO（前缀 S,P）定位客体；固定 S、O 时由 SOP（前缀 S,O，在同 S 内按 O 排序）定位谓词；固定 P、O 时由 POS（前缀 P,O）定位主体。这三个索引的前两列恰好分别是 {S,P}、{S,O}、{P,O} 这三对，因此能对任意「常量两列、变量一列」的模式做两列前缀二分；
• PSO、OSP、OPS：余下三种排列，用于补齐「两变量一常量」（只固定一列）乃至全变量模式所需的各种单/双列排序顺序。

查询时三步走：① 在字典里查出常量对应的 id；② 在选定索引里用已知前缀二分定位（如 (16,24,0)）；③ 顺着前缀连续读取，结果天然就是排好序的。六份索引已经包含全部数据，原始三元组表本身甚至不再需要单独存储。下面用 Python 实现字典编码 + 六排列索引，并对不同三元组模式演示如何选索引：

import bisect

from itertools import permutations

triples_str = [

    ("Einstein", "invented", "Relativity"),

    ("Einstein", "invented", "Photoelectric_Effect"),

    ("Einstein", "won",      "Nobel_Prize"),

    ("Newton",   "invented", "Calculus"),

    ("Newton",   "won",      "Royal_Society_Medal"),

    ("Curie",    "won",      "Nobel_Prize"),

]

dictionary = {}

def encode(x):

    if x not in dictionary:

        dictionary[x] = len(dictionary) + 1      # id 从 1 开始（真实系统用哈希）

    return dictionary[x]

triples_id = [(encode(s), encode(p), encode(o)) for s, p, o in triples_str]

# 对 (S,P,O) 的 6 种全排列各建一份有序聚簇索引（B+ 树的可有序扫描近似）

ORDER = {(0, 1, 2): "SPO", (0, 2, 1): "SOP", (1, 0, 2): "PSO",

         (1, 2, 0): "POS", (2, 0, 1): "OSP", (2, 1, 0): "OPS"}

indexes = {}

for perm in permutations(range(3)):

    indexes[ORDER[perm]] = sorted(tuple(t[i] for i in perm) for t in triples_id)

def lookup(index_name, pattern):

    # 在指定索引上做前缀范围扫描：pattern 为该索引列顺序上的（常量或 None）前缀

    rows = indexes[index_name]

    prefix = tuple(x for x in pattern if x is not None)

    keys = [r[:len(prefix)] for r in rows]

    return rows[bisect.bisect_left(keys, prefix):bisect.bisect_right(keys, prefix)]

e, inv, newt, calc, nobel = (encode("Einstein"), encode("invented"), encode("Newton"),

                             encode("Calculus"), encode("Nobel_Prize"))

print("(Einstein, invented, ?x) 选 SPO，前缀 (e,inv)：", lookup("SPO", (e, inv, None)))

print("(Einstein, ?p, ?x)       选 SPO，前缀 (e)：    ", lookup("SPO", (e, None, None)))

print("(?s, invented, Calculus) 选 POS，前缀 (inv,calc)：", lookup("POS", (inv, calc, None)))

print("(对照 (?s,invented,Newton)：Newton 只作主体、从不作客体，POS(inv,newt) 命中为空：",

      lookup("POS", (inv, newt, None)), ")")

print("(?s, ?p, Nobel_Prize)    选 OPS，前缀 (nobel)： ", lookup("OPS", (nobel, None, None)))

运行结果：

(Einstein, invented, ?x) 选 SPO，前缀 (e,inv)： [(1, 2, 3), (1, 2, 4)]

(Einstein, ?p, ?x)       选 SPO，前缀 (e)：     [(1, 2, 3), (1, 2, 4), (1, 5, 6)]

(?s, invented, Calculus) 选 POS，前缀 (inv,calc)： [(2, 8, 7)]

(对照 (?s,invented,Newton)：Newton 只作主体、从不作客体，POS(inv,newt) 命中为空： [] )

(?s, ?p, Nobel_Prize)    选 OPS，前缀 (nobel)：  [(6, 5, 1), (6, 5, 10)]

5.5 JOIN 算法：为什么排序顺序如此重要

有了索引，连接三元组模式时用哪种 JOIN 算法，直接决定性能：

• 嵌套循环连接（Nested Loop Join）：最朴素的双重循环，在大表上代价很高；当某一侧输入很小、或内表连接列上有索引时（索引嵌套循环），现代引擎仍会使用它，但单纯的朴素嵌套循环一般不作为大表连接的首选；

• 归并连接（Merge Join）：当两个输入都按连接属性排好序时，顺序扫描两边、即时连接匹配项、跳过无匹配区间，内存占用小，并且支持流水线（pipelining），是首选；

• 散列连接（Hash Join）：当输入无序或排序列不对时，先对一个输入建哈希表、再扫描另一个输入去探测；它必须触碰每一条输入、且打断流水线。

这正是六排列索引要提供「各种排序顺序」的原因 ——让尽量多的 JOIN 能用上 Merge Join。

6. RDF 存储内核（二）：压缩、查询优化、更新与三种替代布局

6.1 RDF-3X 的压缩：差分 + 变长字节编码

原生 RDF 引擎 RDF-3X 为六份索引的存储压缩给出了经典方案。它把三元组按字典序排列后，对每条记录做两步压缩：

1. 逐属性计算差分（delta）：相邻三元组在 S、P、O 三个位置分别做差，排序后大量差值为 0 或很小；

2. 对每个差分三元组做变长字节编码（variable-byte encoding）：一个压缩单元约 1–13 字节，含 1 个 gap bit、7 bit 的 header，以及三段差分；当 gap=1（与上一条在同一前缀下连续）时第三段差分直接塞进 header、其余为 0；其余情况下 header 用 7 bit 记录三段差分各自的编码长度组合（5×5×5=125 种组合）。

在编码粒度上，字节级（byte-level）编码的压缩率几乎追平位级（bit-level，如 Gamma、Golomb、Rice）方案，但解压速度快约 10 倍；压缩始终在页（page）级别进行。课件给出的 Barton 数据集实测很能说明问题：5100 万条三元组、N-Triples 未压缩约 7GB，建好全部 6 个主索引后只有约 1.1GB，字节级编码解压约 3.2 秒；若再叠加 LZ77 可再压约 2 倍，但解压慢得多。这体现了「压缩率 vs 解压效率」的权衡。

6.2 查询优化与选择度估计

同一个 SPARQL 查询，三元组模式的连接顺序不同，中间结果规模可能差几十上百倍（课件用 1000→100→50 与 1000→1000→100→50→5 等不同计划对比）。一个好的查询优化器，核心是为索引扫描（三元组模式）和 JOIN 准备选择度估计器（selectivity estimator）：预估每一步会产出多少中间结果，从而选出代价最小的计划。

• 标准关系数据库通常为每个属性维护直方图（histogram），并假设属性之间相互独立 —— 这在 RDF 上过于粗糙、不精确；

• RDF-3X 改用聚合索引做精确计数，并为三元组块（页）维护额外的 JOIN 统计信息；在假设三元组模式之间相互独立的基础上，还会预计算数据中频繁路径的精确统计。这些统计信息决定了每一步选哪个索引、用哪种 JOIN、按什么顺序连接。

6.3 数据更新：差分索引（Differential Indexing）

SPARQL 1.1 已包含更新（update）语法。RDF-3X 针对更新有三个现实假设：查询远多于更新；更新绝大多数是插入、很少删除；不同应用可能并发更新。据此设计了 差分索引（Differential Indexing） 的暂存（staging）架构。

术语辨析：这里的「差分索引（Differential Indexing）」与 6.1 压缩里的「差分（delta/gap）编码」只是中文都译作『差分』，二者毫无关系——6.1 的差分是把相邻排序记录在 S/P/O 上做差、用于压缩存储；本节的差分索引是把新增写入暂存成一份增量索引、查询时再与只读主索引合并，是更新机制。一个服务于磁盘体积，一个服务于写入吞吐，读到『差分』二字要分清指哪一个。

• 每个应用的插入先写进各自的 Workspace（工作区），常驻内存，在查询时按需（on-demand）建立临时索引；

• 某应用的一批插入完成后，再把工作区合并（merge）进主索引；

• 删除不直接改主数据，而是「再插入一条带 deleted 标志的同样元组」，并改造扫描 / 连接算子，让它们在执行时把差分索引与主索引合并。

这种「主索引只读 + 增量暂存 + 定期合并」的思路，和 Elasticsearch 在数据持续插入时实现近实时搜索的方式异曲同工。

6.4 垂直分区、列存与属性表：为消除 self-JOIN 而设计

单三元组表的痛点是大量 self-JOIN。基于三条观察 ——谓词的种类并不多、三元组模式里谓词通常是固定的、经常需要取某个谓词的全部三元组—— 衍生出三种更贴近关系库、也更省 JOIN 的布局：

（1）垂直分区（Vertical Partitioning）：为每个谓词建一张两列（subject, object）表（如 works_for(S,O)、teaches(S,O)、phd_from(S,O)）。同一列数据同构，并避免了大量 self-JOIN；此时前述查询只需在 works_for 表自身、phd_from 表之间做少量等值连接，谓词已经固化进表名，不再需要 predicate='works_for' 这样的过滤。

（2）列存（Columnstore）：进一步把每张表的每一列单独存储（如 PhD_from:subject 与 PhD_from:object 两个列向量）。优点是只访问 subject 或只访问 object 时很快、表示非常紧凑；缺点是同时需要 S 和 O 时要把列重组回来，且对「谓词是变量」的三元组模式效率低。压缩上让 subject 只存一次、各列保持相同行序（必要处补 NULL），再用 bit 向量、区间编码等手段消除 NULL。

（3）属性表（Property Table）：按 RDF 类型或聚类算法，把谓词相似的实体聚成一张关系宽表（列即谓词，如 subject | teaches | PhD_from），实在放不下的多值 / 稀疏三元组进入一张「leftover triples（剩余三元组）」表。它更符合关系库习惯、用宽表上的选择（selection，相当于预连接 pre-join）替代了大量 JOIN—— 这正是「宽表上多列条件比多表连接廉价快速」的原因；缺点是可能产生很多 NULL、多值属性难处理、查询映射依赖 schema、schema 变更代价高。

下面沿用同一组教师演示数据，实测三种布局回答同一问题（「列出每位教师的就职单位与其所授课程」）所需的扫描与连接次数，直观看到 self-JOIN 是如何被一步步消除的：

data = [

    ("Katja",  "works_for", "MPI_Informatics"), ("Katja",  "teaches", "Databases"),

    ("Martin", "works_for", "MPI_Informatics"), ("Martin", "teaches", "Databases"),

    ("Ralf",   "works_for", "Saarland_University"), ("Ralf", "teaches", "Information_Retrieval"),

    ("Ralf",   "works_for", "MPI_Informatics"),    # Ralf 有两个单位 -> 多值属性

]

# 布局 A：单三元组表。works_for 与 teaches 是同一张表的行，需 self-JOIN（嵌套循环）

def plan_single_table(rows):

    wf = [(s, o) for s, p, o in rows if p == "works_for"]

    tc = [(s, o) for s, p, o in rows if p == "teaches"]

    out, scans, joins = [], 0, 0

    for a, u in wf:

        scans += 1

        for b, t in tc:          # 每条 works_for 都要再扫一遍 teaches

            scans += 1; joins += 1

            if a == b:

                out.append((a, u, t))

    return out, scans, joins

# 布局 B：垂直分区。每个谓词一张 (S,O) 两列表，只需两表间等值定位，无全表 self-JOIN

def plan_vertical_partition(rows):

    wf = sorted((s, o) for s, p, o in rows if p == "works_for")

    tc = dict((s, o) for s, p, o in rows if p == "teaches")

    out, scans, joins = [], 0, 0

    for a, u in wf:

        scans += 1; joins += 1   # teaches 表按 S 直接定位

        if tc.get(a):

            out.append((a, u, tc[a]))

    return out, scans, joins

# 布局 C：属性表（宽表）。同实体谓词聚成列，一次 SELECTION（pre-join），多值进 leftover

def plan_property_table(rows):

    wide, leftover = {}, []

    for s, p, o in rows:

        if p == "works_for" and s in wide and "works_for" in wide[s]:

            leftover.append((s, p, o))

            continue

        wide.setdefault(s, {})[p] = o

    out, scans, joins = [], 0, 0

    for a, col in wide.items():

        scans += 1               # 宽表选择，无 JOIN

        if "works_for" in col and "teaches" in col:

            out.append((a, col["works_for"], col["teaches"]))

    return out, scans, joins, leftover

for name, fn in [("A 单三元组表(self-JOIN)", plan_single_table),

                 ("B 垂直分区(两列谓词表)", plan_vertical_partition)]:

    res, scans, joins = fn(data)

    print(f"布局{name}：{len(res)} 行｜扫描 {scans} 次｜连接 {joins} 次")

res, scans, joins, leftover = plan_property_table(data)

print(f"布局C 属性表(宽表 SELECTION)：{len(res)} 行｜扫描 {scans} 次｜连接 {joins} 次｜leftover {len(leftover)} 条：{leftover}")

运行结果：

布局A 单三元组表(self-JOIN)：4 行｜扫描 16 次｜连接 12 次

布局B 垂直分区(两列谓词表)：4 行｜扫描 4 次｜连接 4 次

布局C 属性表(宽表 SELECTION)：3 行｜扫描 3 次｜连接 0 次｜leftover 1 条：[('Ralf', 'works_for', 'MPI_Informatics')]

从 A 到 C，连接次数从 12 降到 4 再降到 0，操作越来越廉价；代价也清晰可见：属性表把 Ralf 的第二个单位挤进了 leftover，且带来更多 NULL、绑定了 schema。没有一种布局在所有方面最优，这正是存储引擎要按负载权衡的地方。

6.5 其他方案与开放挑战

除上述主流布局，学术界还有不少探索：把 RDF 数据当作带位向量压缩的稀疏矩阵（BitMat）；把 RDF 转成 XML 后用 XPath、XQuery 处理；在图数据库上做双模拟（bi-simulation）或使用专用图索引结构（如 gStore）。而开放挑战依然存在：支持不同蕴涵机制（entailment regime）的 SPARQL、SPARQL 1.1 的分组 / 聚合 / 更新新特性、面向用户的查询结果排序（高效 top-k 算子、结构化查询的打分）、集中式 RDF 引擎的能力边界，以及不确定 RDF 数据的处理 —— 知识抽取与挖掘得到的三元组往往带概率、并不精确，这就通向了概率数据库（probabilistic databases），也和我们后面知识抽取章节的不确定性天然呼应。

📝 动手练一练

1. 概念辨析（判断对错并说明理由）：

   ① 「原生图数据库在任何查询上都一定比基于关系库的 RDF 存储快。」

   ② 「联邦数据库和分布式数据库本质上是同一种横向扩展技术。」

   ③ 「Neo4j 的 shortestPath() 和 SPARQL 的子图匹配 WHERE { ?s ?p ?o } 都属于图查询，没有区别。」

   ④ 「字符串字典编码之后，基于字典序的范围扫描（RANGE）通常会变得更快。」

2. 动手：为三元组模式选索引并验证。给定六排列索引（SPO/POS/OSP/SOP/OPS/PSO），先口述下面三个三元组模式各应走哪个索引、用哪些列做前缀，再运行代码验证你的判断：(Newton, won, ?x)、(?s, ?p, Calculus)、(Einstein, ?p, Nobel_Prize)。

import bisect

from itertools import permutations

triples = [("Einstein", "invented", "Relativity"), ("Einstein", "won", "Nobel_Prize"),

           ("Newton", "invented", "Calculus"), ("Newton", "won", "Royal_Society_Medal")]

dic = {}

enc = lambda x: dic.setdefault(x, len(dic) + 1)

tids = [(enc(s), enc(p), enc(o)) for s, p, o in triples]

ORDER = {(0,1,2): "SPO", (0,2,1): "SOP", (1,0,2): "PSO",

         (1,2,0): "POS", (2,0,1): "OSP", (2,1,0): "OPS"}

idx = {ORDER[pm]: sorted(tuple(t[i] for i in pm) for t in tids) for pm in permutations(range(3))}

def scan(name, pat):

    rows, pref = idx[name], tuple(x for x in pat if x is not None)

    keys = [r[:len(pref)] for r in rows]

    return rows[bisect.bisect_left(keys, pref):bisect.bisect_right(keys, pref)]

print("(Newton,won,?x) SPO：", scan("SPO", (enc("Newton"), enc("won"), None)))

print("(?s,?p,Calculus) OPS：", scan("OPS", (enc("Calculus"), None, None)))

print("(Einstein,?p,Nobel) SOP：", scan("SOP", (enc("Einstein"), enc("Nobel_Prize"), None)))

本章小结

• 版图：图数据库按存储分「基于关系库 / 基于 NoSQL / 原生图」三条路线，按数据模型分 RDF 三元组与属性图两大阵营；开源看 RDF4J、gStore，商业看 Virtuoso、AllegroGraph、Stardog，原生图数据库看 Neo4j、OrientDB、Titan（Titan 支持多种可插拔存储后端、对接大数据生态），另有 ArangoDB 等多模型数据库。

• 语言与扩展：RDF 用 SPARQL，属性图用 Cypher（声明式）/Gremlin（遍历式）；联邦是异构库的查询路由与融合，分布式是同构库的分片与 UNION，二者不可混为一谈。

• 选型：用 Load Time、Repository Size（线性可扩展）、Query Response Time（区分缓存 / 冷启动与混合查询）、Throughput（QPS）、Inference Support 五个指标，结合规模、读写、并发、表达能力做判断；基准分人造（LUBM、BSBM）与真实（DBpedia）两类。

• 边界：图数据库做图查询（子图匹配 + 查询优化），图计算做图性质迭代（PageRank、最短路径、社区发现，工具如 GraphX、Giraph）。

• 存储内核主线：单三元组表把 SPARQL 翻译成 self-JOIN 的 SQL；字典编码把字符串压成整数；六排列聚簇索引让任意三元组模式都能有序前缀扫描；Merge Join 优于 Hash Join；RDF-3X 用差分 + 变长字节编码压缩、用选择度估计选计划、用差分索引应对更新；垂直分区、列存、属性表则用不同方式消除 self-JOIN，各有 NULL、多值、schema 绑定上的代价。

📋 行动清单

• 在本地跑通本节 4 段 Python：属性图匹配与最短路径、三元组表 self-JOIN（SQL 与 SPARQL 对拍）、字典编码与六排列索引、三种存储布局对比，确认输出与讲义一致。

• 不看讲义默画一条链路：三元组表 → SPARQL 翻译成 self-JOIN SQL → 字典编码 → 六排列索引 → Merge/Hash Join → 压缩与查询优化 → 垂直分区/列存/属性表，并说出每一步解决什么问题。

• 用五个 Benchmark 指标，为两个假想场景各写一份选型结论并说明理由：①单机十亿条百科类 RDF 三元组、重 SPARQL 与推理；②业务团队的小规模社交关系数据、重多跳路径推荐。

—— 小象教研组