RDF图数据管理的关键技术研究

论文摘要

语义Web使跨应用、企业和团体的数据共享与重用成为可能,而RDF是语义Web的基础,其数据模型是RDF图。与已有数据模型不同,RDF图是有向超图,能够表达隐含语义,富含文本信息,且规模庞大。这些特点造成RDF图数据管理中存在存储设计难度大,查询处理复杂且效率低,查询结果排序困难等问题。针对以上问题,本文对RDF图数据管理中的若干关键技术展开研究。首先,本文研究了隐含数据查询过程中的自反传递闭包计算问题,提出了一种基于有向图素数编码标记机制的方法:PLSD。PLSD将任意有向图上结点间可达关系(属性的自反传递性)计算转化为标记中整数的整除关系计算。与传统基于forward chaining和backward chaining的推理相比,PLSD能够更有效地实现RDF图中自反传递闭包的计算。实验表明PLSD优于同类其它标记机制。其次,针对RDF图的有向超图特点,本文提出了一种原生的RDF图存储方法:PI。该方法能够有效避免由数据模型不一致而导致的数据模型转换开销。它还具有降低存储空间开销,易于实现各种图论算法,聚簇存储RDF图有向边等特点。PI存储上结合PLSD等推理策略的语义查询系统,在LUBM测试基准实验中综合性能指标要高于对比系统。对于RDF图中的文本信息,本文提出以资源文档为索引和查询基本单位的细粒度关键词查询方法。克服了以RDF文档为单位的粗粒度关键词查询方法难与语义查询结合的问题,提高了语义查询和关键词查询的综合查全率和查准率。最后,在查询结果排序方面,提出在本体层次上对概念与关系重要性的排序方法CARRank。基于CARRank实现了实例数据层资源全局重要性排序和结合查询结果相似度与资源全局重要性的综合排序。CARRank算法利用本体中概念和关系相互增强的迭代方式计算概念重要性和关系权重,避免了对资源统计信息的依赖。并给出了其收敛性的理论证明和实验检验。实验验证了基于CARRank算法的概念重要性排序与关系权重的合理性。原型系统在中文新闻等领域的成功应用验证了本文工作的价值和意义。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 语义Web 与RDF
• 1.2 RDF 图及其数据管理
• 1.2.1 RDF 图
• 1.2.2 RDF 图的特点
• 1.2.2.1 RDF 图是有向超图
• 1.2.2.2 含有隐含的数据
• 1.2.2.3 富含文本信息
• 1.2.2.4 具有网络规模的数据
• 1.2.3 RDF 图数据管理及其挑战
• 1.3 论文的主要工作
• 1.3.1 研究思路与研究内容
• 1.3.2 主要创新点
• 1.3.3 论文组织
• 第2章 基于素数编码机制的有向图可达关系计算
• 2.1 引言
• 2.2 相关工作
• 2.2.1 基于产生式规则推理的有向图可达关系计算
• 2.2.2 基于标记机制的有向图可达关系计算
• 2.3 相关知识
• 2.4 有向无环图情况下的素数编码标记机制
• 2.4.1 简单形式
• 2.4.2 完整形式
• 2.4.3 优化技术
• 2.4.3.1 最小公倍数
• 2.4.3.2 拓扑排序
• 2.4.3.3 叶子结点的标记
• 2.5 任意有向图情况下的素数编码标记机制PLSD
• 2.6 实验
• 2.6.1 实验设计
• 2.6.2 实验结果与分析
• 2.6.2.1 标记空间占用与构造时间开销
• 2.6.2.2 典型查询的响应时间
• 2.6.2.3 查询选择率对性能的影响
• 2.6.2.4 可扩展性
• 2.6.2.5 更新代价
• 2.7 小结
• 第3章 RDF 图的原生存储及语义查询
• 3.1 引言
• 3.2 相关工作
• 3.2.1 RDF 图数据管理中的存储设计相关工作
• 3.2.2 RDF 图数据管理中的查询处理相关工作
• 3.2.2.1 查询表达语言
• 3.2.2.2 查询处理方法
• 3.2.2.3 隐含数据的查询/推理
• 3.3 基于有向超图表示的RDF 图原生存储
• 3.4 基于RDF 图原生存储的语义查询
• 3.4.1 推理的实现
• 3.4.2 基于扩展SPARQL 运算符的逻辑查询计划
• * 语义一致性约束的查询优化策略'>3.4.3 基于pD^*语义一致性约束的查询优化策略
• 3.4.4 物理查询实现
• 3.4.4.1 基于RDF 图遍历的数据访问
• 3.4.4.2 结点值索引
• 3.4.4.3 PLSD 索引
• 3.4.4.4 三元组有序索引
• 3.5 实验与分析
• 3.5.1 实验设计
• 3.5.2 实验结果与分析
• 3.5.2.1 数据加载时间和库大小
• 3.5.2.2 查询完备性和可靠性
• 3.5.2.3 查询响应时间
• 3.5.2.4 综合性能
• 3.6 小结
• 第4章 细粒度的关键词索引与查询
• 4.1 引言
• 4.2 相关工作
• 4.3 细粒度关键词查询模型
• 4.4 相似度计算方法
• 4.4.1 扩展向量空间模型的相似度计算
• 4.4.2 利用 RDF 图结构信息的相似度计算
• 4.5 索引结构与查询处理
• 4.5.1 索引结构
• 4.5.2 查询处理
• 4.6 实验与分析
• 4.6.1 实验设计
• 4.6.1.1 数据集
• 4.6.1.2 查询语句
• 4.6.1.3 评估方法
• 4.6.2 实验结果分析
• 4.7 小结
• 第5章 基于本体链接分析的资源排序
• 5.1 引言
• 5.2 相关工作
• 5.2.1 传统链接分析算法
• 5.2.2 语义 Web 中的链接分析算法
• 5.3 基于链接分析方法计算本体中概念与关系的重要性
• 5.3.1 链接分析模型与相关定义
• 5.3.1.1 相关定义
• 5.3.1.2 本体设计的意识流模型
• 5.3.2 概念与关系相互增强的链接分析算法CARRank
• 5.3.3 迭代收敛性证明
• 5.3.4 实验分析
• 5.3.4.1 实验设计
• 5.3.4.2 排序结果比较
• 5.3.4.3 收敛性比较
• 5.4 资源的全局重要性与查询结果的排序
• 5.4.1 资源的全局重要性
• 5.4.2 考虑全局重要性和查询结果相似度的综合资源排序
• 5.4.3 实验结果
• 5.5 小结
• 第6章 RDF 图数据管理原型系统及应用
• 6.1 引言
• 6.2 SWARMS 系统
• 6.2.1 SWARMS 整体结构
• 6.2.2 RDF 数据管理模块的设计
• 6.2.3 RDF 数据管理模块的实现
• 6.3 SWARMS 的应用
• 6.3.1 软件项目领域
• 6.3.2 中文新闻领域
• 6.3.3 社会网络分析领域
• 6.4 小结
• 第7章 结论和进一步的研究工作
• 7.1 论文总结
• 7.2 进一步的研究工作
• 插图索引
• 表格索引
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果