一种面向普适计算环境的语义化推理存储技术研究

论文摘要

计算模式正向以人为中心的普适计算模式发展,应用程序出现了新的行为特征和需求。作为以服务应用程序为目标的基础软件,操作系统必须作出相应的改变,才能据此提供更高效的服务并满足新的需求。另一方面,众多新的研究成果也为达成这一改变提供了支持,即使不考虑计算模式的改变,这些成果也将强力的推动操作系统的改善。本文就操作系统的一个方面——数据存储展开研究。通过使用RSS(RichServants Service Model)模型进行分析可知,普适应用需要智能的数据存储服务,而传统的文件系统存在丢失数据之间语义信息的问题,不能满足这一需求。为解决这一问题,本文研究为数据存储系统添加形式化的数据语义信息表示和推理能力。结合知识表示的研究成果,本文使用描述逻辑语言SI作为语义信息的表示语言并实现其推理机制。在推理时,针对角色逆,本文分析现有Block策略所存在的问题,提出了回环Block策略,据此给出了SI Tableaux算法并证明其为SI语言的判定算法。基于Copy On Write思想给出了COW推理树,有效地提高推理内存使用率,并在其基础上实现了Baekjump技术。为快速发现推理中的冲突,提出了一种新的优化手段——冲突概念集缓冲优化。给出了SI语言的增量式推理以处理频繁的概念增加和删除操作。实验结果表明,这些技术有效地提高了推理性能,所获得的推理机能够胜任语义存储系统的推理任务。本文对高性能闭合序列挖掘算法Bide进行了深入探讨。给出并证明了闭合序列前缀中任意一个项目的后向扩展事件(BEE)项目交集随前缀的生长单调不增的定理,并据此对BEE累计操作进行了优化。修改了频繁闭合序列模式的表示形式,定义了闭合序列树并阐述了它的三个性质。同时发现当新增输入串中不同时包含前缀串和频繁项目时,两次连续挖掘的结果是相同的,本文给出了相应的定理和证明,据此实现了增量式频繁闭合序列模式挖掘算法BideInc。实验表明BideInc提高了动态输入串数据库上闭合序列的挖掘性能,可挖掘存储系统中的数据相关性,用于指导数据块的预取操作。在上述研究成果的支持下,给出了SRSS(Sematic Reasoning Storage System)系统的运行时架构、数据存储视图和存储系统物理架构;也给出了内核态推理机KDLE(Kernel Description Logic Engine)的架构。研究结论表明,存储数据语义信息并向系统添加推理能力是切实可行并能满足复杂的应用需求的。本研究所作的工作也表明操作系统在普适计算环境下将有深刻的变化和发展。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 普适计算理想模型RSS
• 1.2.1 普适计算研究现状
• 1.2.2 RSS模型定义
• 1.2.3 RSS模型表达能力
• 1.2.4 区分类似技术
• 1.2.5 发现新的研究问题
• 1.3 存在的问题
• 1.4 研究目标与意义
• 1.5 研究内容
• 1.6 研究现状
• 1.6.1 语义信息相关
• 1.6.2 存储系统智能化
• 1.7 论文架构
• 第2章 描述逻辑基础与综述
• 2.1 引言
• 2.2 语法
• 2.3 推理任务
• 2.3.1 TBOX推理
• 2.3.2 ABOX推理
• 2.4 推理算法
• 2.4.1 结构化算法
• 2.4.2 Tableaux算法
• 2.4.3 处理GCI
• 2.4.4 Block
• 2.5 开放世界语义
• 2.6 优化技术
• 2.6.1 延迟展开
• 2.6.2 规范化
• 2.6.3 一致性缓冲
• 2.6.4 Backjump
• 2.6.5 GCI吸收
• 2.6.6 语义分支搜索
• 2.7 ABOX推理优化
• 2.8 查询语言
• 2.9 应用情况
• 2.10 语言族
• 2.11 本章小结
• 第3章 SI Tableaux算法
• 3.1 引言
• 3.2 内核态推理机的意义
• 3.3 描述逻辑语言SI
• 3.4 SI Tableaux算法
• 3.4.1 一般Block策略
• 3.4.2 回环Block策略
• 3.4.3 算法
• 3.4.4 算法证明
• 3.4.5 例子
• 3.4.6 实验
• 3.5 本章小结
• 第4章 推理机实现与优化
• 4.1 引言
• 4.2 COW推理树
• 4.2.1 逻辑节点和物理节点
• 4.2.2 智能指针
• 4.3 SI Backjump优化
• 4.3.1 基本操作
• 4.3.2 冲突多来源性
• 4.3.3 冲突分发
• 4.3.4 Backjump判断
• 4.4 冲突概念集缓冲
• 4.4.1 概述
• 4.4.2 冲突信息聚散
• 4.4.3 冲突概念集构造
• 4.4.4 收集算法
• 4.4.5 复合冲突
• 4.5 增量推理
• 4.5.1 概念来源
• 4.5.2 来源循环
• 4.5.3 避免重复推理
• 4.5.4 处理回环关系
• 4.5.5 概念删除算法
• 4.6 概念衍生结构
• 4.7 实验
• 4.7.1 实验环境
• 4.7.2 优化推理实验
• 4.7.3 增量推理实验
• 4.7.4 实验分析与结论
• 4.8 本章小结
• 第5章 增量式闭合序列挖掘
• 5.1 引言
• 5.2 相关工作
• 5.3 Bide算法
• 5.4 BideInc算法
• 5.4.1 BEE计算优化
• 5.4.2 BideInc算法
• 5.5 实验
• 5.6 本章小结
• 第6章 语义存储系统架构
• 6.1 引言
• 6.2 SRSS存储系统
• 6.2.1 数据语义信息存储
• 6.2.2 SI表示数据语义信息
• 6.2.3 存储系统架构
• 6.2.4 SRSS物理架构
• 6.2.5 查询处理
• 6.3 推理机KDLE架构
• 6.4 推理服务
• 6.4.1 推理机服务
• 6.4.2 新增接口
• 6.5 数据预取
• 6.5.1 挖掘时机
• 6.5.2 预取机制
• 6.6 中断同步锁ISLock
• 6.6.1 中断处理的特点
• 6.6.2 锁结构
• 6.6.3 锁操作
• 6.6.4 性能测试
• 6.7 本章小结
• 第7章 结论
• 7.1 主要工作概述
• 7.1.1 主要工作与结论
• 7.1.2 创新点
• 7.2 未来工作展望
• 参考文献
• 附录A:KDLE关键字
• 附录B:KDLE语法
• 攻读博士学位期间主要的研究成果
• 致谢