海量 RDF 数据管理

本文是对论文 邹磊, 陈跃国. 海量 RDF 数据管理[J]. 中国计算机学会通讯, 2012, 8(11): 32-43. 1 的总结。因为要做的一个面向知识库的问答,发现RDF 格式是知识库的主要格式,所以找了这篇文章对 RDF 现状进行大致了解。

RDF 数据管理研究现状

  • 基于关系数据模型的方法
    • 简单三列表: 构建一张三列表(Subject,Property,Ob-ject),将所有的 RDF 三元组都放在这个表中
      • 很好的通用性,性能差
    • 水平存储:一个 RDF 主体表示为 数据库表中的一行
      • 大量的列
      • 表的稀疏性
        • 空值不仅增 加了存储负载还会带来其他问题比如增加索引 大小、影响查询效率。文献24~26详述了空值带来 的问题
      • 水平存储存在多值性问题
        • 而真实数据往往并不符合这个限制条件
      • 数据变化可能带来很大的更新成本
    • 属性表
      • 聚类属性表(clustered property table)
        • 每一 类定义一个单独的数据库表
      • 属性类别表(property-class table)
        • 属性类别表将所有的 [ 实体按照 RDF :type来分类每一类用一个张水平表 来表示。这种组织方式要求每个实体都必须有一个 RDF :type属性
      • 优点
        • 在于可以减少查询时主体- 主体间的自连接代价,从而极大地提高查询效率
        • 属性相关的属性值存储在 一列中,可以针对该列的数据类型设计一些存储策 略来减少存储空间
      • 缺点
        • 属性表的缺陷使其除了某些特殊应用以外没有更广泛的应用
        • 大部分查询都会涉及多个表的连接或合并操作,性能下降
        • RDF 数据由于来源庞杂其结构性较差属性和主 体间的关联性不强类似的主体可能并不包含相同 的属性。空值的问题随之出现
    • 二元存储
      • 在垂直分割的结构下三元组表被重写为N张包含两列的表N等于 RDF 数据中属性的个数
      • 缺点
        • 这种存储方式增加了 表连接的运算数,运算代价大
        • 表的增多增加了数据更新的难度
    • 全索引策略
      • 提高简单三列表存储的查询效率
        • 其一,对于 SPARQL 查询中的每个查询 三元组模式,都可以转换成对于某个排列组合上的 范围查询
        • 其二,全索引的好处在于可以利用合 并连接降低连接的复杂度
      • 缺点
        • 不同的三元组其主体/属性/属性值可能重 复,浪费了存储空间
        • 当SP ARQL查询复杂时, 其连接操作的查询代价依然不可忽略
        • 随着 数据量增长,表的规模会不断膨胀,系统的性能下 降严重
        • 由于 数据类型多种多样,无法根据特定数据类型进行存 储优化,可能会造成存储空间的浪费
  • 基于图数据模型的方法
    • 利用图模型来设计 RDF 存储与查询也存在难以 解决的问题:第一相对于普通的图模型 RDF 图 上的边具有标签并可能成为查询目标;第二典 型的图算法时间复杂度较高需要精心的设计以降 低实时查询的时间复杂度
    • 有若干相关研究的评论
    • 优点在于: (1)图结构能够直接映射 RDF 模型,避免了为适应 存储结构对 RDF 数据进行转换;(2)查询 RDF 数据 的语义信息需要重构 RDF 图,以图结构存储 RDF 数 据避免了重构。
  • 海量分布式的 RDF 存储查询引擎

    面向 RDF 的关键词检索

  • 直接检索 RDF 数据图
    • 在 RDF 数据图上定位包含检索 词的斯坦纳树(Steiner tree)
      • 斯坦纳树是满 足根节点到每一个关键词节点都存在一条路径的子 树
    • 额外的索引结构来存 储关键词可达性信息
      • 关键词至节点 的最短距离,给定一个关键词,得到能到达关键词 的所有节点及最短路径
      • 索引是节点至关键 词的最短距离,给定节点和关键词,在O(1)时间内 得到最短距离
  • 结构化查询转换
    • 转换成结构化的查 询语句(如 SPARQL )
      • 1. 匹配查询关键词到 RDF 图的边或者顶点上
      • 2. 在模式信息的辅助 下,找到查询关键词之间的关联,确定用户的查询 对象
      • 3. 构造符合语法规则的结构化查询语句 并将其排序返回
      • 评价: 直接检索 RDF 数据 图的方法需要建立大量的索引结构,并且一般忽略 RDF 的属性信息,无法处理用户将属性或关系名作 为关键词查询的情况,但它直接在 RDF 图中构造查 询结果返回,查询粒度细,不需要背景知识和 RDF 模式信息的支持
    • 特兰(Tran)
      • 在模式图 上找到包含用户查询关键词的最小子图,得到top-k 个子图
      • 结合数据图将这些子图映射成合取查询语句,这些查询会翻译成 SPARQL 查询语句,进行数据库的查询操作并返回结果
      • 评价: 基于模式图的结构化查询转换 方法不需要建立大规模的索引,但依赖 RDF 模式信息,确定查询关键词之间的关联,出于查询语句转换精度的考虑,有时还需要人工干预
Comments
Write a Comment