论文部分内容阅读
OWL是W3C提出的Web Ontology语言,用于描述Web资源。OWL-Lite是OWL的一个子语言,它包含了OWL大部分的构造符,提供了较强的语义表达能力,同时与OWL的其它子语言相比,其推理具有较低的计算复杂度。OWL-Lite的推理分为Tbox和Abox两种,Tbox仅与Ontology相关,一般可以由现有的推理引擎来支持,Abox因为涉及大规模的实例数据,而现有的推理引擎都是基于内存的设计,只能支持小规模的实例数据,因此需要一种新的方法来支持在大规模实例数据上的Abox推理。 本文讨论了大规模OWL-Lite数据的Abox推理方法,将推理算法分为初始数据集推理和增量推理两大类。初始数据集推理是针对系统中不存在推理数据的情形,由于对单规则的推理过程代价非常大,因此需要在推理过程中尽可能避免冗余的规则推理过程,从这个角度出发,提出了基于规则静态关联、基于规则动态关联以及基于规则分组排序的推理优化算法,并给出了算法分析以及算法描述。从实验结果来看,这些优化的推理算法是推理完整的,即不存在遗漏的推理过程,并且相对于基本的推理算法,基于规则静态关联的算法减少了部分冗余的规则推理过程,但由于规则静态关联只是规则关联的一个必要条件,因此还存在优化的空间,基于规则动态关联的算法根据特定数据集以及规则静态关联关系来准确地确定规则关联,从而完全地避免了冗余规则的推理。由于OWL-Lite的Abox推理规则整体上体现出一种偏序关系,根据这种偏序性对规则进行推理可以将匹配某些规则的数据作集中推理,相比于分散推理的做法,它减少了数据匹配规则的次数,因此具有较高的推理效率。基于这种想法,提出了基于规则分组排序的推理算法,从实验结果来看,该算法是所有推理优化算法中性能最佳的算法。 增量推理算法针对系统中已经存在大量推理完全数据的情形,如果直接使用基于分组排序推理算法,会对大量已经推理过的数据进行重复的推理,因此我们一方面对前面的算法进行了扩展,使得在推理过程中必然有新数据参与,从而避免旧数据的重复推理;另一方面我们提出了基于规则模式共用的推理算法,由于新数据相对于系统中已有的数据,在数量上往往是比较小的,因此将它们缓存到共用的模式中既可以避免旧数据的重复推理,又可以减少数据匹配模式的次数。从实验结果来看,基于规则模式共用的推理算法不仅保证了推理完整性,而且在性能上要优于扩展推理算法。 Abox推理产生的推理数据是依赖于显示数据的,在用户删除显示数据时,需要维护推理数据与显示数据的一致性,本文讨论了基于数据依赖关系的Abox推理更新维护算法,该算法的一个重要前提就是统计数据的依赖关系。已有的工作使用了Backward Chaining算法统计数据依赖关系,在有大量实例数据存在的情形下,该方法的计算代价非常高,本文提出了在推理过程中统计数据依赖的方法,并证明了它的完整性。 推理规则的数量不仅影响推理数据所占用的存储空间,而且影响更新维护的复杂度,将部分规则的推理以查询改写的方式来实现不仅可以节省存储空间,减小更新维护的复杂度,还可以实现为用户量身定制的推理需求,本文讨论了基于查询改写实现单规则推理、多规则推理等方面的问题,并提出了支持多规则推理的优化方法。 本文最后介绍实现的OWL-Lite数据管理系统OrientX/Ontology,介绍了其体系结构、推理实现方法等,并讨论了一些相关工作。本文讨论的推理算法可用于改进此类系统中推理模块的运行效率。