文档介绍：分类号 密 级
U D C 编 号
桂林电子科技大学
硕 士 学 位 论 文
题目 基于 OBDD 的描述逻辑推理算法研究
(英文) Research on OBDD-based Decision Algorithm for Description Logics
研 究 生 姓 名: 李德波
指导教师姓名、职务: 古天龙 教授
申 请 学 位 门 类: 工 学 硕 士
学 科、专 业: 计算机应用技术
提 交 论 文 日 期: 2011 年 4 月
论 文 答 辩 日 期: 2011 年 6 月 15 日
2011 年 6 月 17 日
独创性(或创新性)声明
本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成
果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其
他人已经发表或撰写过的研究成果；也不包含为获得桂林电子科技大学或其它教育机
构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已
在论文中做了明确的说明并表示了谢意。
申请学位论文与资料若有不实之处，本人承担一切相关责任。
本人签名： 日期：
关于论文使用授权的说明
本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在
校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校
后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权保
留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，
可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规
定)
本人签名： 日期：
导师签名： 日期：
摘 要
摘要
描述逻辑作为一类知识表示的形式化工具，在信息系统、软件工程、自然语言处
理等领域已得到了成功应用。特别是随着近年来语义 Web 的发展，描述逻辑更是扮
演着重要的角色，目前已成为语义 Web 本体语言 OWL 的逻辑基础。随着基于描述逻
辑的本体在 e-Science 和语义 Web 中的广泛应用，给描述逻辑将来的推理算法提出了
一系列的挑战，特别是在处理大规模问题时表现得尤为突出。 Tableau 算法是目前描
述逻辑中最主要的推理方法，但其并不是在所有情况下都表现最好。因此，有必要针
对不同特征的本体寻找相应地更合适的推理算法。
有序二叉决策图(OBDD)是一种基于图的数据结构，是布尔函数的一种压缩表示
形式，可以对信息进行高效压缩，能有效地处理大规模问题，在模型检测和验证等领
域已经得到了成功应用。结合 OBDD 的数据结构特点和 Tableau 算法在处理角色名较
多时具有的优势，本文做了基于 OBDD 和 Tableau 的描述逻辑推理算法相关研究，其
主要内容如下：
(1) 针对 OBDD 的数据结构特点，给出了基于 OBDD 的 SHOIQ 的 TBox 一致性
判定算法。该算法首先将 SHOIQ 知识库转化为可满足等价的 ALCIb 知识库，应用扁
平化规则进行预处理；接下来对 TBox 构造多米诺模型，然后将该模型转化为布尔函
数；最后将布尔函数转换为 OBDD 表示形式，并在其基础上进行可满足性判定。
(2) 针对基于 OBDD 的描述逻辑推理算法在处理角色名较多的本体时存在的局
限，结合 Tableau 算法在这方面的优势，给出了基于 OBDD-Tableau 的 ALCIO 的 TBox
一致性判定算法。该算法首先将 ALCIO 的 TBox 映射为命题层和模态层，用 OBDD
来进