The RDF-3X engine for scalable management of RDF data----part1

本文由学者Thomas Neumann和Gerhard Weikum于2009/09/01在《The VLDB Journal 》联合发表

本文完整的系统RDF-3X，从最初为RDF数据的管理和查询而设计，具有精简索引和查询处理的RISC风格的结构。查询优化器为复杂查询选择最佳连接顺序，成本模型=整个连接路径的统计。RDF-3X优化了查询，还通过分段体系结构支持在线更新：推迟对主数据库索引的直接更新，将其应用于紧凑差异索引，以分批方式再将差异索引合并到主索引。

将三元组与相同属性名称映射到属性表中，映射到列存储，并创建频繁连接的实例化图。管理大规模RDF数据=存储布局+索引编制+查询处理：

缺少全局模式和谓词名称的多样性在数据库设计存在问题。

通过对RDF数据细粒度建模，具有大量联接的查询会构成部分工作负载。这要求特定选择查询处理算法并谨慎优化复杂的联接查询；

联接顺序和其他执行计划的优化需数据统计选择性估计。

RDF使用XML语法且SPARQL涉及类似于XML路径表达式的搜索模式。

RDF-3X实现基于三个关键原则：

物理设计在“大型三元组表”上创建的索引与工作负载无关，所有索引的总存储空间小于主数据。

查询处理器是RISC风格，主要依靠合并连接排序索引列表，可通过三元组表的“穷举式”索引实现。

查询优化器集中在生成执行计划时的连接顺序，采用动态规划计划枚举，并使用基于RDF特定统计概要的成本模型。

大多数RDF数据库不是只读的都是查询密集型的，但必须至少支持增量加载，甚至支持在线更新新三元组，用于注释现有数据。开发了一种暂缓索引更新的暂存体系结构处理RDF-3X用于快速查询的主动索引。更新是在工作空间和差异索引中收集，然后以批处理合并到主数据库索引。SPARQL查询对构成RDF数据图三元组的模式匹配查询，SPARQL引入两个查询修饰符：distinct关键字指定必须消除重复项，reduce关键字指定可以重复但无需消除。减少关键字的目标是通过允许优化帮助RDF查询，但查询输出存在不确定性。将RDF三元组映射到关系表上的三种方法：

通过创建“正确的”索引集可快速地处理合并联接，将所有三元组存储在压缩聚类B+树。三元组在B+树中按字典排序，将SPARQL模式转换为范围扫描。为了确保仅通过执行一次索引扫描就可在模式三元组的任何位置使用变量回答所有可能的模式，在六个单独的索引中保留S，P和O的所有六种可能排列。压缩方案受文本检索系统中反向列表方法的启发，概括为id三元组。对于压缩，在节省空间和CPU消耗之间需权衡解压缩或解释压缩项目，详细信息如下：
原创文章 19获赞 19访问量 2961 关注 私信 展开阅读全文
作者：Vito_otiV

part for RDF