RDF-3X: a RISC-style Engine for RDF

ABSTRACT

这个论文写的是RDF-3X的引擎,一个基于SPARQL的实现，并超级高效,小心的设计出的追求RISC格式和流线型结构和的简洁的数据结构和操作。

1. 储存和索引3元RDF的通用解决方案,且完全不用做物理设计的调整。
2. 一个强力且简单的query处理器对最大可能性范围利用快速合并。
3. 一个用基于整个连接路径的统计对照表的耗费模型来选择最优合并顺序的query优化程序

RDF-3X与先前最先进的系统相比，在几个大规模数据集上进行测量，这些数据集具有超过5000万个RDF三元组和基准查询，包括模式匹配和长连接路径 基础数据图。

INTRODUCTION

Motivation and Problem

RDF数据结构已经存在了十年,它被设计为对于语义Web的模式松弛或甚至无模式的信息的灵活表示。到商业化的今天的电子世界，RDF也没有得到太多的关注，但RDF建立了强大的动力。语义网络风格的本身和知识是基于数百万现实来自维基百科和其它在线已经创建并可获取的来源。E-science数据容器以导入/导出的格式支持RDF,并也可以筛数据选(基于query),更引人注目的,是在生命科学领域。最终,Web 2.0平台的在线社区将RDF视为非专有交换格式,并将其作为构建信息混搭的工具。

在RDF格式中，所有的数据元素都表示为(subject,predicate,object) 三元组,有的是(subject,property,value)三元组,例如

• (id1, hasT itle, ”Sweeney T odd”),
• (id1, producedInYear, ”2007”),
• (id1, directedBy, ”T im Burton”),
• (id1, hasCasting, id2),
• (id2, RoleN ame, ”Sweeney T odd”), (id2, Actor, id11),
• (id1, hasCasting, id3),
• (id3, RoleN ame, ”M rs. Lovett”), (id3, Actor, id12),
• (id11, hasN ame, ”Johnny Depp”),
• (id12, hasN ame, ”Helena Bonham Carter”)

这样,注意到predicate和属性没有两样,并且这没有数据库模式,这种三元组的概念非常适合现在的随收随付(pay as you go),和实体关系模型相比,都有实体的属性和关系/谓语,所有的三元组放在一起可以看作一个巨大的层次结构图。

SPARQL查询语言是官方标准用来搜索RDF仓库。它支持三元组的conjunctions 和 disjunctions,在关系引擎中选择项目连接查询的对应项。比如我们可以得到Johnny Depp 的电影的title用 SPARQL查询语句:

Select ?title Where {
?m <hasTitle> ?title. ?m <hasCasting> ?c.
?c <Actor> ?a. ?a <hasName> "Johnny Depp" }

这里每一个点代表一个conjunction(join),整个查询也可以看做在RDF数据图中做图模式匹配,predicates 也可以是变量或者通配符,因此也允许未知模式的查询。

RDF驱动用于储存索引和查询已经有一些年了,尤其是the Jena frame-work by HP Labs 显著收到欢迎,and Oracle also provides RDF support for semantic data integration in life sciences and enterprises [11, 29]. However, with the exception of the VLDB 2007 paper by Abadi et al. [1], none of the prior implementations could demonstrate convincing efficiency, failing to scale up towards large datasets and high load. [1] achieves good performance by grouping triples with the same property name into property tables, mapping these onto a column store, and creating materialized views for frequent joins

管理大规模RDF数据需要很多技术挑战，包括储存布局,索引和查询过程。

1. (没有固定结构与实际的数量大变化频繁的矛盾)缺少全局模式和谓词名称的多样性对物理数据库设计提出了主要问题。原则上，可以依靠自动调谐“向导”来实现频繁的连接路径;然而在实践中，数据的不断发展的结构和不一致动态的工作量将这个问题变成一个复杂的西斯弗斯任务。
2. (join 查询多难预测 RDF为动态应用空间 需要适合的动态优化查询算法)通过RDF数据 - 三元组而不是整个记录或实体的细粒度建模 - 具有大量连接的查询将固有地形成工作负载的大部分，但连接属性比关系设置中的可预测性要差得多。这要求查询处理算法的特定选择，以及对复杂连接查询的仔细优化;但RDF是用于在数据空间上的即时应用程序，因此优化发生在查询运行时。
3. (需要统计来 找到 优化方案 不同优化方案的适应度差别大)由于连接顺序和其他执行计划优化需要数据统计来进行选择性估计，因此RDF引擎面临的问题是，在没有模式的情况下，统计信息收集的合适粒度是显而易见的。例如，在工作负载的where子句中出现的所有属性的单维直方图 - 关系系统中的最先进的方法 - 不适用于RDF，因为它错过了长连接链或大连接星的影响多对多关系。
4. (和XML样子像但是具体差别挺大)虽然RDF使用XML语法，而SPARQL涉及类似于XML路径表达式的搜索模式，但是RDF三元组形成图形而不是树的集合的事实是对更深入研究的XML设置的主要区别。

Contribution and Outline

本文为上述问题提供了一个全面，可扩展的解决以上问题的方案。 它提供了一个完整的系统，创造的RDF-3X（RDF Triple eXpress），从头设计和实现，专门用于管理和查询RDF数据。 RDF-3X遵循[24,39]中倡导的为特定应用领域设计和定制的数据管理系统可以通过两个数量级来超越通用主流系统的原理。 在这个论点的因素包括

1. 数据结构和算法的裁剪，而不是支持更多各种各样的方法
2. 更轻的软件脚印和开销，
3. 简化的系统内部优化和更容易配置 和自适应变化的环境（例如，数据和工作量特性）。

RDF-3X遵循这种RISC风格的设计理念[10]，设计用于支持RDF的“精简指令集”.RDF-3X基于三个原则：

1. 物理设计通过在单个“巨型三元组表”上创建适当的索引来独立于工作负载.RDF-3X不依赖于自动调整向导的成功（或限制），而是有效地消除了对物理设计调整的需要。它通过在构成RDF三元组的三个维度的所有6个排列上构建索引，并且附加地对所有三维二维和所有三个一维投影的计数聚合变体进行索引。每个索引都可以很好地压缩;所有索引的总存储空间小于主数据的大小。
2. 查询处理器是RISC风格的，主要依赖于对排序后的索引列表的合并连接。这可以通过三元组表的“穷举”索引来实现。事实上，所有处理都是仅索引的，并且三元组表仅仅虚拟地存在。运算符树被构造以便在最大可能程度上保留后续连接的有趣顺序[17];只有当这不再可能时，RDF-3X才会切换到基于散列的连接处理。这种方法可以在代码级别进行高度优化，并且与传统查询处理器相比具有低得多的开销。同时，支持SPARQL的各种重复消除选项，查询中的分离模式以及SPARQL所需的所有其他功能也非常有用。
3. 查询优化器主要关注执行计划生成时的连接顺序。它采用动态规划计划枚举，成本模型基于RDF特定的统计概要。这些统计包括数据图的路径中的频繁谓词序列的计数器;这样的路径是电位连接模式。与通用数据库系统中的查询优化器相比，RDF-3X优化器更简单，但在执行计划的选择性估计和决策方面更加准确。

这项工作的科学贡献是：

1. 用于RDF索引和查询的新颖架构，消除对物理数据库设计的需要，
2. 用于大规模连接查询在无结构的RDF三元组上的优化器，由新的对于RDF路径的选择性估计驱动，
3. 基于具有三个大数据集的实际测量的综合性能评估，示出了先前最好的发动机[1]的大增益（对于一些查询，通常为5和高达20） 。 RDF-3X的源代码和实验数据可根据要求提供非商业用途。

BACKGROUND AND STATE OF THE ART

SPARQL

SPARQL查询[36]是构成RDF数据图的三元组上的模式匹配查询。 除了语法糖，一个基本的SPARQL查询具有形式

select ?variable1 ?variable2 ...
where { pattern1. pattern2. ... }

其中每个模式由subject，predicate，object组成其中的每一个都是变量或文字。 查询模型是和样例一样：查询指定已知的文字并将未知数保留为变量。 变量可以出现在多个模式中，由默认连接。 查询处理器需要查找满足给定模式的所有可能的变量绑定，并将来自projection子句的绑定返回到应用程序。 请注意，并非所有变量都必须绑定（例如，如果变量只出现在projection中，而不是在pattern中），这将返回NULL。

该模式匹配方法限制了关于可能的执行计划的查询引擎的自由度，如以下示例所示：

select ?a ?c
where { ?a label1 ?b. ?b label2 ?c }

用户对通过?b可以连接的所有?a和?c感兴趣。 ?b本身的值不是projection子句的一部分。 不幸的是，模式匹配语义要求仍然需要计算所有的?b的绑定。 可能有多种方式从?a到?c，导致输出重复。 由于这通常不是用户/应用程序的意图，SPARQL引入了两个查询修饰符：distinct关键字指定必须删除重复项，而reduced关键字指定重复项可以但不必删除。 reduced关键字的目标显然是通过允许优化来帮助RDF查询引擎，但是使用减少的选项，查询输出具有非确定性。

然而，即使是创建所有重复的默认模式允许一些优化。 查询处理器不能忽略由于它们对重复项的影响而被投影掉的变量，但是它不必创建显式绑定。 只要我们能保证产生正确数目的重复，绑定本身是不相关的。 我们稍后将通过计数重复项的数量而不是产生重复项本身来使用此观察。

Related Work

大多数可公开访问的RDF系统将RDF三元组映射到关系表（例如，RDFSuite [2, 32], Sesame [8, 28], Jena [23, 46], the C-Store-based RDF engine of [1], and also Oracle’s RDF MATCH implementation [11]）。有两种极端的方式做到这一点：

1. 所有三元组存储在一个单一的，巨大的三元组表与通用属性主题，谓词，对象。
2. 三元组按其谓词名称分组，具有相同谓词名称的所有三元组存储在同一属性表中。可以使具有用于每个谓词名称的单独表的属性表的极端形式更加灵活，从而导致混合方法：
3. 基于对于相同实体类的谓词或工作负载中的同现（co-occurrence），通过谓词名称对三元组进行聚类;

每个簇属性表包含少量相关谓词的值，并且对于具有不频繁谓词的三元组，可以另外存在“剩余”表。集群属性表具有类别特定的模式，其具有在相应的RDF谓词之后命名的属性，并且其宽度可以从单个谓词（属性）到相同实体类型的所有谓词。

早期的开源系统如Jena [23,46]和Sesame [8,28]使用集群属性表，但将物理设计留给了应用程序调优专家。这些系统都没有报告任何性能基准，大型数据在千兆字节范围内有超过1000万个三元组。 Oracle [29]在[11]中报告了非常好的性能结果，但是似乎在很大程度上依赖于良好的调整，除了基本的三元组表之外，通过正确选择物化连接视图（创建的主题 - 属性矩阵）。 [1]目前最快的RDF引擎使用最小宽度属性表（即二进制关系），但将它们映射到列存储系统。 [41]给出了不同存储布局的一个很好的分类，并提出了中型合成数据和合成工作负载的系统性能比较。与[1]针对“巨 - 三元组表”方法的论据相反，我们的RDF3X系统显示了如何成功地使用具有优异性能的三元组表。

性能最佳的系统，Oracle和C-Storebased的引擎擎，依赖于这些视图上的物化连接路径和索引。索引本身是分别由底层RDBMS和列存储支持的标准索引。本地YARS2系统[19]提出了在6个单独的B +树或散列索引中的三元组及其所有嵌入子三元组（对和单值）的详尽索引。这类似于我们的方法，但是YARS2忽略了在subject, predicate, object（作为主要，次要和第三级排序标准）的规范顺序之外的排序顺序中索引三元组。对于HPRD系统[6]提出了一个非常相似的方法，并在Sesame系统中作为选项（创造的“三重指数”）[28]。 YARS2和HPRD似乎主要适用于简单的查找操作，并且对连接的支持有限;他们缺乏DBMS风格的查询优化（例如，不考虑任何连接顺序优化，虽然[6]认识到这个问题）。 [5]提出使用后缀数组索引整个连接路径，但不讨论优化此物理设计的查询。 [42]介绍了一种基于明智选择的“中心节点”的新型路径索引;该指数，创造的GRIN，在小到中等数据和手指定的执行计划表现出良好的性能。在[12]中也讨论了模式无关的“宽和稀疏表”的物理设计，没有具体考虑RDF。所有这些用于RDF索引和物化视图的方法都会产生一些形式的物理设计问题，并且没有一个解决了这些物理设计特性所产生的查询优化问题。

对于查询优化，[11,29]和[1]利用与这些解决方案分层的SQL引擎一起提供的最先进的技术。 据我们所知，没有一个采用任何RDF本地优化。 [38]概述了代数重写的框架，但似乎性能增益的主要规则是推动选择低于连接; 没有考虑连接排序。 [20]具有类似的风格，同样忽视找到好的连接排序的关键问题。

最近，图上的SPARQL模式的选择性估计已经由[38]和[25]解决。方法[38]收集每个主题，每个谓词和每个对象（标签或值）的单独的频率统计;通过假设主语，谓词和对象分布在概率上是独立的来估计整个三元模式的频率。 [25]的方法通过在所选择的任意形状的图形模式的集合上建立统计来更加复杂。它将模式的选择转换为优化问题，并使用贪婪启发式。查询模式的基数估计识别统计存在的最大子模式，并且将它们与关于超级模式的统一性假设组合而没有统计。虽然[38]似乎太过于简单，不能产生准确的估计，方法[25]是基于一个复杂的优化问题，并依靠简单的启发式选择一组好的模式的总和结构。我们在RDF-3X中采用的方法捕获路径标签频率，从而超越[38]，但避免了计算的复杂性[25]。

STORAGE AND INDEXING

Triples Store and Dictionary

虽然大多数先前的，特别是最近的文献喜欢存储模式与属性表，我们决定采用概念上更简单的方法与单个，可能巨大的三元组表，我们自己的存储实现下面（相对于使用RDBMS ）。 这反映了我们的RISC风格和“无旋钮”设计理念。 我们克服了以前的批评，即通过创建“正确的”索引集合（见下文）和非常快速的合并连接处理（见第4节），三元组表会产生太多昂贵的自联接。

我们将所有三元组存储在（压缩的）聚类B +树中。三元组在B +树中按字典顺序排序，这允许将SPARQL模式转换为范围扫描。 在模式（literal1，literal2，?x）中，文字指定公共前缀，因此有效地进行范围扫描。 在对中等数量的叶页的单次扫描期间找到每个可能的?x的绑定。

因为三元组可以包含长字符串，所以我们采用使用字典+id映射替换所有字面量的方法（参见例如[11]）。这有两个好处：1）它压缩三元组存储，现在只包含id三元组，和2）它是查询处理器的一个伟大的简化，允许快速，简单，RISC式操作符（见第4.5节）。这些增益的小成本是两个附加的字典索引。在查询翻译期间，在查询中出现的文字被翻译成其字典id，这可以通过从字符串到id的标准B +树来完成。在处理查询之后，所得到的id必须被转换回文本作为应用/用户的输出。我们也可以在这个方向上使用B +树，但是我们实现了一个直接映射索引[14]。直接映射被调谐用于id查找并且导致更好的高速缓存命中率。请注意，这只是当查询产生很多结果时的问题。通常，先前的步骤（连接等）支配成本，但是对于具有许多结果字典查找的简单查询是不可忽略的。

id+字典的方式 提高效率

Compressed Indexes

在上面给出的索引范围扫描示例中，我们依赖于变量是后缀（即，对象或谓词和对象）的事实。 为了保证我们能够通过仅执行单个索引扫描来回答模式三元组的任何位置中的变量，我们在六个单独的维度中保持主语（S），谓词（P）和对象（O）的所有六个可能的排列 索引。 我们可以提供这种级别的冗余，因为我们压缩id三元组（下面讨论）。 在所有实验数据集上，所有索引的总大小小于原始数据。

由于六个索引中的每一个的排序规则顺序不同（SPO，SOP，OSP，OPS，PSO，POS），我们使用通用术语值1，值2，值3而不是主语，谓词， 不同列。 索引中的三元组通过（值1，值2，值3）（对于六个不同排列中的每一个）按字典顺序排序，并且直接存储在聚类B +树的叶页面中。

归类顺序使得相邻三元组非常相似：最邻近的三元组在值1和值2中具有相同的值，并且值3的增加趋向于非常小。 这个观察自然导致三元组的压缩方案。 代替存储完整的三元组，我们只存储三元组之间的变化。 这种压缩方案的灵感来自文本检索系统中的倒排列表[50]，但我们将其推广到id三元组而不是简单的id。 由于下面讨论的原因，我们只在单个叶子页面中应用压缩，而不是跨页面。

对于压缩方案本身，在压缩项目的解压缩或解释的空间节省和CPU消耗之间存在明显的权衡[45]。我们注意到，当压缩过于积极时，CPU时间开始成为一个问题，因此确定了一个字节级（而不是位级）压缩方案。我们计算每个值的增量，然后使用最小字节数来仅对增量编码。标题字节表示由以下值使用的字节数（图1）。每个值在0字节（不变）和4字节（delta需要完整的4字节）之间消耗，这意味着每个值有5个可能的大小。对于三个值，这些是5 * 5 * 5 = 125个不同大小的组合，其适合于报头字节的有效载荷。剩余间隙位用于指示小间隙：当仅值3改变，并且增量小于128时，其可以直接包括在报头字节的有效载荷中。这种小的delta是非常常见的，并且可以在我们的方案中由单个字节编码。

三元压缩伪代码

compress((v 1 , v 2 , v 3 ),(prev 1 , prev 2 , prev 3 ))
// writes (v 1 , v 2 , v 3 ) relative to (prev 1 , prev 2 , prev 3 )
if v 1 = prev 1 ∧ v 2 = prev 2
  if v 3 − prev 3 < 128
    write v 3 − prev 3
  else encode(0,0,v 3 − prev 3 − 128)
else if v 1 = prev 1
  encode(0,v 2 − prev 2 ,v 3 )
else
  encode(v 1 − prev 1 ,v 2 ,v 3 )
encode(δ 1 , δ 2 , δ 3 )
// writes the compressed tuple corresponding to the deltas
write 128+bytes(δ 1 )*25+bytes(δ 2 )*5+bytes(δ 3 )
write the non-zero tail bytes of δ 1
write the non-zero tail bytes of δ 2
write the non-zero tail bytes of δ 3

压缩的细节如上所示。算法计算前一个元组的增量。 如果它是小的，它被直接编码在标题字节中，否则它计算每个树值和调用编码的δi值。 编码用大小信息写头部字节，然后写入δi的非零尾部（即，它按字节写入i，但跳过前导零字节）。 这导致具有不同大小的压缩元组，但是在解压缩期间，可以容易地从报头字节重建大小。 由于所有操作都是逐字节的，解压缩仅涉及几个便宜的操作并且非常快。

我们测试了压缩率和解压时间（以秒为单位）的逐字节压缩与文献中提出的许多逐位压缩方案[33]。 Barton数据集（见第6节）的结果如图3所示。我们的逐字节方案压缩几乎与最佳逐位压缩方案一样好，同时提供更好的解压缩速度。在IR系统中倒置列表中流行的Gamma和Golomb压缩方法执行得更糟，因为在我们的设置中，每当三重前缀发生变化时，间隙就可能很大。

我们还在我们的压缩方案之上试验了更强大的LZ77压缩。有趣的是，我们的压缩方案使用LZ77比原始数据压缩更好，因为增量编码在三元组中表现出共同的模式。附加的LZ77压缩大约减少索引大小两倍，但显着增加CPU时间，这对于复杂查询将变得至关重要。因此，RDF-3X发动机不使用LZ77。

压缩索引的一个重要考虑是每个叶页是单独压缩的。压缩更大的数据块导致更好的压缩（特别是与LZ77压缩相结合），但是逐页压缩有几个优点。首先，它允许我们寻找（通过B +树遍历）任何叶子页面，并直接开始读取三元组。如果我们压缩更大的块，我们经常需要解压缩前面的页面。第二，压缩索引的行为就像一个正常的B +树（有一个特殊的叶编码）。因此，可以像标准B +树中那样容易地进行更新。这极大地简化了压缩索引与其余引擎的集成，并保持其RISC性质。特别是，我们可以采用先进的并发控制和恢复方法进行索引管理，而无需任何更改。

以上新的index 按字节压缩法索引方法 比既有所有的方案效率更优 大小更小(具体方法见上面伪代码)

Aggregated Indices

对于许多SPARQL模式，索引部分三元组而不是完全三元组就足够了，如以下SPARQL查询所示：

select ?a ?c
where { ?a ?b ?c }

它计算通过任何谓词连接的所有?a和?c，和?b的具体是什么无关的。

因此，我们另外构建聚合索引，每个索引只存储三元组的三个列中的两个。更确切地说，它们存储两个条目（例如，主体和对象）以及聚合计数，即，该对在三元组的全集中的对数的数量。这对于三个可能的三个对中的每一个以及在每个排序顺序（SP，PS，SO，OS，PO，OP）中进行，从而添加另外六个索引。

计数是必要的，因为SPARQL语义。在输出中不会出现?b的具体值，但是需要对重复正确的计数。注意，聚合索引比全三重索引小得多;由六个附加索引导致的总数据库大小的增加是可以忽略的。

代替（值1，值2，值3），聚合索引存储（值1，值2，计数），否则它们被组织在B +树中，就像全三重压缩索引。叶编码略有不同，因为现在大多数变化包括值2中的间隙和低计数值。伪码如图4所示。

最后，除了三元组中的这些索引之外，我们还构建了所有三个包含just（value 1，count）条目的单值索引（编码类似）。虽然仅使用一个变量的三元模式可能很少，但单值索引非常小，并且它们可用简化了查询翻译。

QUERY PROCESSING AND OPTIMIZATION

Translating SPARQL Queries

编译SPARQL查询的第一步是将其转换为适合稍后优化的演算表示。我们构造一个可以被解释为关系元组演算的查询图表示。从SPARQL派生域演算会更容易，但元组演算更容易优化。

虽然SPARQL允许许多语法快捷方式来简化查询制定，但每个（连接）查询都可以被解析并扩展为一组三重模式。三元组的每个组件是文字或变量。解析器已经执行字典查找，即文字被映射到id。与域微积分类似，SPARQL指定必须为数据中每个出现的纯文本三元组生成变量绑定。当查询由单个三元模式组成时，我们可以使用第3节中的索引结构，并使用单个范围扫描回答查询。当查询由多个三元模式组成时，我们必须连接各个模式的结果。因此，我们在查询图表示上采用连接排序算法，如下面进一步讨论的。

每个三元模式对应于查询图中的一个节点。在概念上，每个节点需要对整个数据库进行适当的变量绑定和由字面量所引起的选择的扫描。虽然每个扫描都可以实现为单个索引范围扫描，但优化程序可能会选择不同的策略（见下文）。查询图中的边缘反映变量出现次数。当且仅当它们具有共同的（查询）变量时，连接两个节点。

当查询的projection子句包含distinct选项时，我们添加一个聚合运算符，以消除结果中的重复项。最后，我们添加一个字典查找操作符，将生成的ids返回到字符串。

Optimizing Join Ordering

优化SPARQL执行计划的关键问题是连接排序。关于这个问题有大量文献，通常基于各种形式的动态规划（DP）或随机化（例如，[13,15,26,34]）的解决方案。然而，RDF和SPARQL的固有特性创建了具有特别要求的属性的联接查询，这些属性没有通过现有技术直接解决：

1. PARQL查询往往包含星形子查询，用于组合同一实体的几个属性类属性。因此，必须使用可以创建浓密连接树（而不是专注于左深或右深树）的策略。
2. 这些星形连接发生在长连接路径的各个节点，通常在路径的开始和结束。 SPARQL查询可以轻松导致三元组之间的10个或更多联接（例如，参见第6节中的我们的基准查询）。因此，精确优化需要非常快速的计划枚举和成本估计，或者需要求助于启发式近似。
3. 我们希望利用我们的三重索引的特殊优势，鼓励大量使用合并连接（而不是哈希或嵌套循环连接），但这需要在生成连接计划时保持有趣的顺序非常小心。

他的第一个要求排除了不能生成所有可能的星形链组合的方法。第二个要求强烈建议快速自下而上的方法，而不是基于转换的自上而下的枚举。第三个要求排除了基于抽样的计划枚举（或随机化优化方法），因为这些不太可能为具有超过10个联接的查询生成所有顺序保留计划。事实上，我们期望最具竞争力的执行计划具有特定的形式：它们将尽可能长地使用保持顺序的合并连接，并且仅针对最后几个运算符切换到散列连接。

我们的解决方案是基于自下而上的DP框架[26]。它使用针对基本关系的扫描来生成其DP表，在我们的情况下是三重模式。播种是两步法。首先，优化器分析查询以检查在查询的其他部分中使用哪些变量绑定。如果一个变量未被使用，它可以通过使用聚合索引（参见第3.3节）被抛出。注意，该投影在概念上通过索引中的计数信息保留基数;我们在下面4.4小节中讨论这个问题。在第二步中，优化器决定使用哪些适用的索引。有两个因素影响索引选择。当三重模式中的文字形成索引键的前缀时，它们由范围扫描自动处理。否则，读取的元组太多，需要额外的选择。另一方面，不同的索引可以以适合稍后的后续合并连接的顺序产生三元组，这可能具有比读取太多元组更低的总成本。因此，优化器为所有索引生成计划，并使用计划修剪机制来决定是否早些时候可以丢弃其中的一些。

修剪主要基于估计的执行成本。也就是说，优化器为每个生成的计划调用成本模型，并修剪由廉价替代品支配的等价计划。这种修剪机制依赖于订单优化[35]来决定计划是否可以被另一个计划支配。由于优化器可以对所有三重排列使用索引，它可以按任意顺序生成元组，这使得合并连接非常有吸引力。因此，如果计划更昂贵，但产生可以在以后使用的有趣的顺序，则保留计划。注意，排序不仅通过索引扫描创建，而且还通过选择引起的功能依赖性创建，因此顺序优化组件是不重要的[35]。从种子开始，通过连接较小问题的最佳解决方案创建更大的计划。在此过程中，所有属性处理逻辑实现为对可用等价类的推理，而不是单个变量绑定。每个计划将为每个等价类产生至多一个绑定。这既简化了流水线断路器前面的隐式投影，并允许自适应传递连接条件的检测（即a = b ^ b = c⇒a = c）。

从种子开始，通过连接在查询图[26]中相邻的较小问题的最优解来创建更大的计划。 当查询包含由于FILTER谓词而产生的其他选择时，它们将尽快置于贪婪，因为它们通常价格不贵。 如果选择真的很昂贵，可以更好地将其集成到[9]中提出的DP运算符放置，但是我们没有进一步调查。 我们沿着这些线实现的DP方法非常快，并且能够为具有多达20个三元模式的连接查询计算精确的成本最优解。 我们测量了典型SPARQL场景的优化时间（以毫秒为单位），其中两个实体由星形子查询选择并通过连接模式链连接。 结果示于图5中。

Handling Disjunctive Queries

虽然连接查询更常用，但SPARQL还允许某些形式的析取。 UNION表达式返回由两个或多个模式组生成的绑定的并集。如果有任何结果，OPTIONAL表达式返回模式组的绑定，否则返回NULL值。在这种情况下，模式组是三重模式的集合，可能包含UNION和OPTIONAL表达式本身。

在优化期间，我们将UNION和OPTIONAL中的模式组视为嵌套子查询。也就是说，我们首先优化嵌套模式组（可能递归地），然后在外部查询的优化期间将它们视为具有特殊成本/基数的基本关系。对于UNION，我们添加模式组结果的并集，就像它是一个基本关系一样，对于OPTIONAL，我们使用外连接将结果添加为基本关系。

原则上，可以更积极地优化这些查询，但是最有趣的优化需要使用旁路计划[37]或其他非树结构的执行计划，这超出了本工作的范围。这些优化只会为复杂的查询付出代价;当分离元素很简单时，我们的嵌套优化方案产生最优解。

Preserving Result Cardinality

标准SPARQL语义要求产生正确数量的变量绑定，即使它们中有许多是重复的。 然而，从处理的角度来看，应该避免生产和保留重复的额外工作。

我们通过在查询处理期间跟踪每个元组的多重性来解决这个问题。 对非聚集索引的扫描总是产生1的多重性，而聚合索引将复制的数量报告为多重性。 连接运算符乘以多项式以获得每个输出元组的重复数。 注意，如果我们可以静态地推导出它在子计划中必须是1，我们可以可选地关闭多重跟踪。 当结果呈现给应用程序/用户时，输出运算符根据指定的查询语义（distinct，reduced或standard）解释多重性。

Implementation Issues

我们的运行时系统包括典型的代数运算符（merge-join，hash-join，filter，aggregation等）。与其他系统的一个显着区别是，我们的运行时系统是非常RISC风格的：大多数运算符只处理整数编码的id，消费和产生id元组流，比较id等。除了简化代码，这种减少的复杂性允许整洁的实现技巧。

例如，考虑使用B +树迭代器访问物理数据的索引扫描算子，将三元模式与数据进行比较。三元组中的每个条目都是必须生成或绑定到文字的id属性，如果它在前缀中会影响开始/停止条件，或者如果未绑定的条目先到达，则意味着选择。而不是在运行时检查这些不同的条件，我们可以在查询编译时处理它们。每个条目都是id属性或文字。在三元组中有三个条目，这意味着有八种可能的组合。使用具有索引扫描算子的八个不同实现的单个方法接口，我们可以大大减少系统代码中的条件分支的数量。除了速度更快，每个专业操作员都更简单，因为它现在只实现其设置所需的逻辑。注意，我们只需要专门化步骤逻辑，每个专业化的代码少于10行。

这种RISC风格的简化型系统和简单，快速的操作系统的组合导致非常好的CPU性能。在我们的第6部分的评估中，我们包括温热缓存时间来演示这些效果。我们意识到这些类型的代码调优问题通常不被重视，但对于现代硬件的高性能至关重要。

SELECTIVITY ESTIMATES

查询优化器在寻找最低成本执行计划时依赖其成本模型。 特别地，估计的基数（以及因此选择性）对计划生成具有巨大的影响。 虽然这是数据库系统中的标准问题，但RDF数据的无模式性质使统计数据生成复杂化。 我们提出两种统计。 第一个，专门的直方图，是通用的，可以处理任何种类的三重模式和联接。 它的缺点是它假定谓词之间的独立性，这通常在紧密耦合的三元模式中不成立。 因此，第二个统计量计算数据中的频繁连接路径，并为大型连接提供这些路径的更准确的预测。 在查询优化期间，我们使用连接路径基数（如果可用），否则假设独立性并使用直方图。

Selectivity Histograms

虽然三元组在概念上形成具有三个列的单个表，但是在各个列上的直方图不是非常有用，因为大多数查询模式接触三元组的至少两个属性。相反，我们利用我们的聚合索引，这完全适合于计算三种模式选择性：对于每个文字或字面对，我们可以得到匹配三元组的确切数量与一个索引查找。不幸的是，这不足以估计连接选择性。此外，我们希望将成本模型的所有辅助结构保留在主存储器中。因此，我们进一步聚合索引，使得每个索引适合单个数据库页面并包括有关连接选择性的信息。

就像聚合索引一样，我们构建六个不同的统计信息，一个用于三元组中条目的每个顺序。从聚合索引开始，我们将具有长度为2的相同前缀的所有三元组放置在一个桶中，然后合并最小的两个相邻桶，直到总直方图足够小。这近似于等深度直方图，但避免将桶边界置于具有相同前缀的三元组之间（预期相似）。

对于每个桶，然后计算图6所示的统计量。前三个值 - 三元组的数量，不同的2-前缀的数量和不同的1-前缀的数量 - 被用于估计单个三元模式的基数。注意，这仅仅给出扫描基数，即，所扫描的三元组的数量，其确定索引扫描的成本。当字面量不是索引前缀的一部分并且稍后通过选择测试时，真正的结果基数（其影响后续运算符）实际上可能会降低。在这种情况下，我们通过重新排序文字来导出结果基数（并获得准确的预测），使所有文字都在前缀中。

如果桶中的三元组根据指定的连接条件连接到数据库中的所有其他三元组，则下一个值是连接伙伴的数量（即结果基数）。由于有九种方法来组合来自两个三元组的属性，我们预先计算了九个基数。例如，条目o = s是有效的

|{b|b ∈ current bucket} 1 b.object=t.subject {t|t ∈ all triples}|

这些值在连接与桶完全匹配的模式时会提供完美的连接大小预测。通常情况不是这样，因此我们假定查询条件之间是独立的，并且乘以所涉及的谓词的选择性。 （这种独立性假设是用于可追踪性的最先进的查询优化器的标准）。

Frequent Paths

上面讨论的直方图具有相当的准确性，并且适用于所有种类的谓词。他们的主要弱点是他们假设谓词之间的独立性。两种相关谓词通常出现在SPARQL查询中。首先，三种模式的“星”，其中具有不同谓词的多个三元模式共享相同的主题。这些用于选择特定主题（即，基于相同实体的不同属性的实体）。第二，三元模式的“链”，其中第一模式的对象是下一模式的主题，同样具有给定的谓词。这些链对应于长连接路径（跨不同实体）。由于这两种情况是常见的，我们另外构建专用统计信息以具有用于这样的查询的更准确的估计量。

为此，我们预先计算数据图中的频繁路径，并为它们保留精确的连接统计信息。这里的频率指的是具有相同标签序列的路径。注意，我们对于链和星使用术语路径，在两种情况下结构是相似的。我们通过谓词p 1，…，p的序列来表征路径P. 。 。 ，在其遍历中看到。使用SPARQL语法，我们定义一个（链）路径P p 1 ,…,p n as
P p 1 ,…,p n := select r 1 r n+1 where { (r 1 p 1 r 2 ).(r 2 p 2 r 3 ). . . . (r n p n r n+1 )}

星形路径定义类似，p 1 , . . . , p n在这种情况下是不排序的。我们计算最频繁的路径，即具有最大基数的路径，并实现它们的结果基数和路径描述p 1，…。 。 。 ，p n。使用此信息，我们可以准确地预测查询中出现的频繁路径的连接基数。同样，我们希望将这些统计信息保存在主内存中，从而计算最常见的路径，以便它们仍然适合单个数据库页面。在我们的实验中，我们可以在一个16KB页面上存储大约1000个路径。

FrequentPath(k)
// Computes the k most frequent paths
C 1 = {P p |p is a predicate in the database}
sort C 1 , keep the k most frequent
C = C 1 , i = 1
do
C i+1 = ∅
for each p 0 ∈ C i , p predicate in the database
if top k of C ∪ C i+1 ∪ {P p 0 p } includes all subpaths of p 0 p
C i+1 = C i+1 ∪ {P p 0 p }
if top k of C ∪ C i+1 ∪ {P pp 0 } includes all subpaths of pp 0
C i+1 = C i+1 ∪ {P pp 0 }
C = C ∪ C i+1 , sort C, keep the k most frequent
C i+1 = C i+1 ∩ C, i = i + 1
while C i 6 = ∅
return C

找到最常见的路径需要小心。虽然看起来这是一个标准的图表挖掘问题，但是该研究线中的普遍方法[16,44,49]，例如基于众所周知的Apriori频繁项目集挖掘算法，不是直接适用的。

与Apriori设置不同，我们的RDFpath意义上的常见路径不一定包含频繁的子路径。考虑具有两个星形链路群集的图，其中所有端节点分别通过谓词（边缘标记）p 1和p 2连接到它们各自的星形中心。现在考虑在两个星形中心之间具有谓词p 3的单个边。在这种情况下，路径P p 3将不频繁，而路径P p 1，p 3，p 2将是频繁的。因此，我们不能简单地使用Apriori算法。

我们的RDF设置中的另一个问题是周期，这可能导致看似无限长，无限频繁的路径。我们通过两种手段解决这个问题。首先，我们要求如果要保持频繁路径P，其所有子路径也必须保持。这对于查询优化目的是必需的，因为我们可能必须将长连接路径分解成较小的连接，并且它简化了频繁路径计算。第二，我们不是通过它们的结果基数而是通过它们的不同节点的数量对频繁路径进行排序。在树中，这两个是相同的，但是在循环的存在下，我们不对节点计数两次。

路径挖掘算法的伪代码如图7所示。它从长度为1的频繁路径开始，通过附加或前置谓词来放大它们。当新路径本身频繁并且其所有子路径仍然保持时，我们添加它。当没有新的路径可以添加时，我们停止。请注意，虽然伪代码显示了一个嵌套循环以方便表示，但我们实际上在实现中使用了一个join和一个group-by操作符。对于我们在实验中考虑的数据集，1000个最常见的路径可以在几分钟内确定。

Estimates for Composite Queries

为了估计整个复合查询的整体选择性，我们将直方图与频繁路径统计相结合。具有具有对象字面量的三元模式的中间节点的长连接链被分解为最大长度的子链，使得只有它们的末端节点具有带有文字的三元模式。例如，像

?x 1 a 1 v 1 . ?x 1 p 1 ?x 2 . ?x 2 p 2 ?x 3 . ?x 3 p 3 ?x 4 .
?x 4 a 4 v 4 . ?x 4 p 4 ?x 5 . ?x 5 p 5 ?x 6 . ?x 6 a 6 v 6

具有属性谓词a 1，a 4，a 6，v 1，v 4，v 6和关系谓词p 1至p 5的将被分解为p 1 -p 2 -p 3和p 4 -p 5和每个主题选择a 1 -v 1，a 4 -v 4和a 6 -v 6。我们使用频繁路径统计来估计两个连接子链的选择性以及用于选择的直方图。然后，在没有任何其他统计量的情况下，我们假设不同的估计量在概率上是独立的，导致具有每个子链和每个选择估计的乘积公式作为因子。如果不是像?x 6 a 6 v 6这样的简单属性值选择，我们具有星形图案诸如?x 6 a 6 u 6 . ?x 6 b 6 v 6 . ?x 6 c 6 w 6具有属性a 6 ,b 6 , c 6和对应的对象文字u 6，v 6，w 6，我们将首先使用星的频繁路径统计调用星形模式的估计器，然后将它们与产品形式中的其他估计值组合。

EVALUATION

General Setup

为了评估RDF-3X的性能，我们使用了具有不同特性的三个大数据集，并将查询运行时与其他方法（下面讨论）进行比较。所有实验在具有2Ghz Core 2 Duo处理器，2GBytes内存并运行64位Linux 2.6.24内核的Dell D620 PC上进行。对于冷缓存实验，我们使用/ proc / sys / vm / drop caches内核接口删除所有文件系统缓存，然后重新启动各个被测试的系统。我们重复了所有查询五次（包括删除缓存和系统重新启动），并获得最佳结果，以避免操作系统活动造成的工件。对于温暖的缓存，我们运行查询五次，而不删除缓存，再次采取最佳的运行时。
我们的主要比较是在[1]中提出的基于列存储的方法，已经被证明是高度优于所有其他基于DBMS的方法在该文件。我们实现了[1]中描述的方法，但使用MonetDB 5.2.0 [27]作为后端，而不是CStore，因为C-Store不再维护，不在我们的硬件/操作系统平台上运行。 C-Store网页http://db.csail.mit.edu/projects/cstore/建议使用MonetDB，而MonetDB工作正常。注意，我们的设置使用的硬件比[1]特别是硬盘是比在[1]中使用的非常快的RAID慢6倍，传输ca.顺序读取中为32 MB / s。考虑到这个因素6，MonetDB的性能数据与[1]中的C-Store数字相当。对于一个查询（Q6），MonetDB明显快于6（14s对10s），而另一个（Q7）明显更慢（61s对1.4s），但是MonetDB的整体性能比预期的要慢，因为硬盘较慢。

作为RDF-3X的第二个对手，我们使用PostgreSQL 8.3作为字符串字典和（主语，谓词，对象），（谓词，主语，对象）和（谓词，对象，主语）索引的三重存储。这模拟了Sesamestyle [8]存储系统。我们还尝试了当前版本的具有内置RDF支持的领先商业数据库系统，但是在其他系统的运行时间附近无法获得可接受的性能。当使用自己的RDF查询语言，尽管尝试几个自动调整选项，它执行速度比PostgreSQL三元组存储，即使对于简单的查询，并且无法在合理的时间执行更复杂的查询。因此，我们从演示中省略了它。
除了这些基于DBMS的对手之外，我们尝试了来自语义网络社区的几个可用作开源代码的系统。不幸的是，没有一个缩放到我们使用的数据集大小。我们首先尝试了惠普实验室语义网计划中出现的流行的Jena2系统[46]。我们使用Jena版本2.5.5与SDB 1.0包装程序和Apache Derby 10.3.2.1，但无法在24小时内导入我们的三个数据集。从文件增长来看，系统持续变慢，似乎没有在合理的时间内终止。我们还尝试了Yars2 [19,48]，但是再次无法在24小时内导入我们的任何数据集。最后，我们尝试了Sesame 2.0 [8,28]，它应该是最快的语义Web系统之一。 Sesame 2.0能够在13小时内导入Barton数据集，但后来需要ca.对于前两个查询中的每个查询为15分钟，并且由于更复杂的查询的过多的内存使用而崩溃。

请注意，MonetDB和RDF-3X都可以在不到半小时内导入数据集，并且可以按秒的顺序运行查询。 其他语义Web方法通常假定RDF数据适合主存储器，这不是这里的情况。 因此，下面的所有实验都只考虑RDF-3X，基于列存储的MonetDB顶层方法和基于PostgreSQL的三元组存储。 独立于数据库系统，下面讨论的每个数据集首先被带入因子分解形式：一个文件具有表示为整数三元组的RDF三元组和一个从整数到字面量的字典文件映射。 所有三个系统使用相同的文件作为输入，将它们加载到事实表和字典中。 第二阶段的加载时间和数据库大小如图8所示.MonetDB大小是加载后的初始大小。 运行基准后，大小为2.0 / 2.4 / 6.9 GB。 显然MonetDB根据需要构建一些索引结构。

Barton Dataset

对于第一个实验，我们使用Barton库数据集和在[1]中提出的查询作为基准。我们按照[1]中所述处理数据，使用Redland解析器将其转换为三元形式，然后将三元组导入我们的RDF-3X系统。在[1]中，作者修剪了数据，由于C-Store的限制（他们删除所有三元组包含超过127字节的字符串和一些三元组与大量的加入合作伙伴）。我们保留完整的数据，并将其直接导入所有三个系统。总体上，数据包括51,598,328个不同的三元组和19,344,638个不同的字符串。原始数据为RDF（XML）格式的4.1 GB，三重形式的7.7 GB，以及包含所有索引和字符串字典的RDF-3X存储库中的2.8 GB。
我们使用[1]的查询作为我们的实验，但是由于它们在SQL中给出，我们不得不在SPARQL for RDF-3X中重新组织它们。附录A显示所有查询。我们的测量结果如图9所示。我们还包括查询集的几何平均值，它通常用作基准（例如，TPC）中的工作负载平均值度量，并且比极端异常值比算术平均值更具弹性。
第一个观察是，RDF-3X对所有查询执行得比MonetDB好多了，MonetDB本身的性能比PostgreSQL好得多（如[1]中所述）。我们首先讨论RDF-3X与MonetDB的结果。在比较冷缓存时间和热缓存时间时，很明显，磁盘I / O对总体运行时间有很大的影响。 RDF-3X由于其高度压缩的索引结构而简单地读取较少的数据，因此在冷高速缓存的情况下优于MonetDB的典型因子为2至5，有时超过10。在暖缓存的情况下，差异通常较小但仍然很大（因子2，有时高得多）。一个有趣的数据点是查询Q4，其在构造的连接对方面相对昂贵，并且其中RDF-3X甚至在CPU主导的热缓存情况下表现非常好。此外，我们观察到除了I / O和CPU使用率之外的第三个关键方面是内存消耗。查询Q5有一个非常大的中间结果。 MonetDB显然在主存储器中实现这些中间结果的部分。因此，只有少数数据库页面可以进行缓冲，这极大地损害了热缓存行为。

PostgreSQL对此数据集有问题，因为此基准的查询的性质。 几乎所有查询都是聚合查询（通常通过谓词聚合），结果基数很大，这需要昂贵的字典查找。 对于其他更自然的RDF查询，PostgreSQL的性能更好，我们将在接下来的两个小节中看到。
为了了解Yars2风格的系统如何扩展，我们实验禁用所有聚合索引。 这使几何平均值增加到9.52秒（冷）和1.04秒（暖），这显着慢于RDF-3X。 这仍然比其他系统快得多，特别是由于我们的运行时系统和查询优化器。

Yago Dataset

Barton数据集是相对同质的，因为它描述了库数据。作为第二个数据集，我们因此使用Yago [40]，它包括从维基百科提取的事实（利用维基百科的信息框和类别系统），并与WordNet词库集成。 Yago数据集包含40,114,899个不同的三元组和33,951,636个不同的字符串，消耗3.1 GB作为（因式分解）三元组转储。 RDF-3X需要2.7 GB的所有索引和字符串字典。作为查询，我们考虑了三种不同的应用场景 - 面向实体，面向关系，以及具有未知谓词的查询 - 并导出八个基准查询，如附录A所示。这些查询比Barton查询更“自然”，因为它们是标准的SPARQL没有任何聚合和明确给定的谓词。另一方面，查询要大得多（需要更多的多对多连接），因此更难以优化和执行。
结果如图10所示。再次，RDF-3X显然胜过冷和暖缓存的其他两个系统，典型的因子为5到10.这里的PostgreSQL执行得比MonetDB好多了。这很可能是由于MonetDB中的连接顺序差。 warmcache运行时间几乎与冷缓存时间一样高，这表明MonetDB创建了大量的中间结果。
一般来说，这个数据集对于查询优化器来说更具挑战性，因为查询更复杂，选择性估计非常重要。在测试我们的系统时，我们注意到选择性误估可以很容易导致这个数据集减速10-100倍。 RDF-3X在运行时执行和优化器选择执行计划方面表现出极好的性能。

LibraryThing Dataset

作为第三个数据集，我们使用了LibraryThing书籍社交网络www.librarything.com的部分爬网。它包含9989个用户，5,973,703个不同的图书（由这些用户个人拥有）以及用户分配给这些图书的标记。总的来说，数据集由36,203,751个三元组和9,352,954个不同的字符串组成，其原始格式为1.8 GB，RDF-3X为1.6 GB。这个数据集的一个特殊性是具有异构链接结构。在我们的RDF表示中，每个标记都映射到一个谓词，将用户链接到她标记的图书。由于不同标签的数量非常大，数据集包含338,824个不同的谓词，而其他两个数据集分别仅包含285和93个不同的谓词。虽然其他映射到RDF可能是可能的，但我们使用这种非示意性方法作为所有竞争系统的压力测试。
此数据使得RDF-3X的压缩更加困难，并且对MonetDB造成严重的问题。 MonetDB无法处理338,824个表，在文件系统中创建数百万个文件，并一直交换。因此，我们为此数据集使用MonetDB的混合存储方案。我们分割了[1]中描述的1000个最常用的谓词，并将剩余的三元组（大约12％）放在一个大的三元组表中。我们再次构造了三种查询：面向书，面向用户，浏览书和用户链（参见附录A）。与Yago数据集相反，几百万三元组中出现的谓词很少，这降低了连接排序决策的影响。另一方面，数据本身是非常不均匀的，使得选择性更难以预测。

结果如图11所示。在某些情况下，RDF-3X表现很好，优于对手的典型因素为至少5和大于30。 MonetDB和PostgreSQL之间没有明确的赢家。总体MonetDB似乎表现更好，但它崩溃了两次。它拒绝执行查询B3（“太多变量”），可能是因为它包括三个模式与可变谓词（因此至少3000次扫描）。在查询C2中，由于缺少磁盘空间，它在15分钟后崩溃，因为它实现了一个20 GB的中间结果（这是整个数据库大小的10倍）。查询A3由于其高运行时间而突出。
它与相对非选择性的谓词（书籍作者等）执行许多连接，这是昂贵的。其他“困难”查询（B3，C1，C2）本身并不那么难，他们只是需要正确的执行计划选择。例如，B3会找到所有标记为英语，法语和德语的图书的用户。 PostgreSQL通过收集用户拥有的所有图书对来启动此查询，这是非常昂贵的。另一方面，RDF-3X的优化器选择一个计划，收集每个标签的用户与这些书，然后加入结果，这是更有效率。

CONCLUSION

本文提出了RDF-3X引擎，一个RISCstyle架构，用于对大型RDF三元组存储库执行SPARQL查询。正如我们的实验表明，RDF-3X的性能优于以前最好的系统。特别地，它解决了模式数据的挑战，并且与其对手不同，非常好地处理具有大量多样性的属性名称的数据。导致这些性能提高的RDF-3X的显着特征是：1）详尽但非常节省空间的三重索引，消除了对物理设计调整的需要，2）以非常快的合并连接为中心的简化的执行引擎，3）智能查询优化器，它选择成本最优的连接排序，并且甚至对于长连接路径（涉及10到20个连接）也可以有效地执行此操作; 4）基于提供给优化器成本模型的频繁路径的统计信息的选择性估计器。
我们未来的工作包括进一步改进查询优化器（例如，基于魔术集）以及支持超出当前SPARQL标准的RDF搜索功能。沿着后一行，一个方向是允许更强大的通配符模式的整个路径，在XPath后代轴的精神，但图形而不是树。已经提出了扩展SPARQL的建议[3]，但还没有实现。第二个方向是基于应用特定的评分模型提供查询结果的排名。这需要top-k查询处理，并对算法和查询优化提出具有挑战性的问题。最后，完整的SPARQL支持需要一些额外的信息，特别是打字信息。我们认为这可以包括在字典中，但确定最佳编码相对于运行时性能和压缩率需要更多的工作。

总结

现有的储存方式

• RDF Triples
• by predicates

RDF3X

• B+ tree
• string/literal -> id ,Dictionary
• RISC style reduced complexity
• 6-index && compressed index (chunk to leaf level compressed ?) && store changes between index because of the neighboring index are similar
• aggregated index