论文部分内容阅读
本体语言RDFS及OWL被广泛地用于知识库相关的应用中。本体推理作为支撑这些应用的重要服务在查询问答、本体调试、不一致性处理等方面扮演者重要的角色。另一方面,本体推理一般具有较高的复杂度,从而导致在大规模数据场景下难以实用。因此,随着越来越多的大规模真实本体数据集被发布,如何提升大规模本体推理的效率给研究者们带来了挑战。为了提升大规模本体推理的效率,已有的工作更多地采用并行技术设计新的推理算法并且实现高效的推理系统。现有的工作在大量实验的基础上论证了并行技术对大规模本体推理具有较好的效率提升作用。然而,从时间复杂度的角度分析,对于“并行技术是否能提升本体推理效率”这个问题并不能一概而论。本文通过实验证实,存在本体使得并行技术不能有效地提升推理任务的效率。另一方面,诸多著名的数据集,如YAGO,被已有的工作证明:针对其的并行推理具有较高的推理效率;然而,这些数据集却是由非大规模易处理(non-scaling-tractable)的本体语言表示的,即其推理问题在最坏情况是串行的,或者问题复杂度在多项式完全之上。基于以上讨论,为使得并行技术更好地服务于大规模本体推理,本文以本体推理的大规模易处理性(scalable-tractability)为核心展开研究,探讨并寻找对于怎样的本体而言,其推理问题是大规模易处理的,或者是在Nick’s Class(NC)复杂度类中的,从而更好地给出大规模本体推理方法。本文将给出一系列性质;基于这些性质,进一步设计和优化推理算法,以适应于大规模数据处理场景;开发者和用户也可以利用这些性质构建领域本体,使得其推理问题在理论上被保证是大规模易处理的。针对以上问题,本文主要进行以下研究:1)研究datalog推理任务(即datalog评估计算)的大规模易处理性,也就是考察满足怎样性质的datalog程序其推理任务在NC复杂度类中。本文以datalog语言作为研究本体推理任务的基础工具。因为现有工作研究给出的datalog推理算法其复杂度都是多项式完全的,为了研究datalog推理任务的大规模易处理性,这一部分研究给出处理datalog推理任务的NC算法。进一步,基于“可达性问题具有NC复杂度”性质,提出利用单源推导路径优化datalog推理算法。针对上述NC算法给出对应的大规模易处理类,即该类中的datalog 程序都可以由上述NC算法完成推理任务。2)探讨两类重要本体推理任务的大规模易处理性以及具体的推理方法:物化任务(materialization)和分类任务(classification)。针对物化任务,研究两个在实际中应用广泛的本体语言DL-Lite和DHL(Description Horn Logic)语言。本文研究给出结论:DL-Lite的两个最核心的子语言DL-Litecore 和DL-LiteR是大规模易处理的。对于DHL语言,存在非大规模易处理的情形。基于对该类情形的分析,提出了 DHL语言使用上的约束条件,使得满足这个约束的DHL本体,其物化任务都可被NC算法处理,也就是满足了大规模易处理性。接着,本文进一步地将对于DHL的研究结论推广到它的一个扩展语言DHL(o),该扩展语言允许复杂角色包含公理(complexrole inclusion axioms)。基于上述约束条件以及DHL(o)大规模易处理性的理论结果,本文给出优化后的物化任务推理算法。3)针对分类任务,研究本体语言OWLEL的核心语言+。该部分首先研究εL+语言的一个子语言,并且证明该子语言的分类任务可在LogSpace复杂度内被规约到DHL(o)语言的物化任务;也就是说,该子语言只要满足针对DHL(o)语言提出的相应约束便可保证其分类任务是大规模易处理的。接着,本文将研究完整的εL+语言,在DHL(o)语言约束上进一步给出针对εL+语言的约束条件,使得其分类任务是大规模易处理的。本文进一步利用上述约束条件以及单源推导路径优化εL+分类任务的推理算法。4)在实验部分,考察诸多知名的基准数据,大型知识库以及从不同数据源收集而来的真实本体。通过考察,本文发现这些本体中有很大一部分满足本文研究中提出的约束,也就是说,针对它们的推理任务是大规模易处理的。本文进一步验证了存在本体使得并行技术无法提升其推理效率。为验证本文给出的大规模推理方法,优化实现了上面两部分提出的物化任务和分类任务推理算法,并将它们分别与目前知名的推理系统(具体为RDFox,CEL和ELK)进行比较;所使用的测试数据也是从不同领域收集而来的真实本体。实验结果表明了,本文的两个系统相较于所对比的推理机,在处理大规模易处理的本体上具有更高的效率。