论文部分内容阅读
OWL(Web Ontology Language)本体作为形式化的知识表示模型在语义网(Semantic Web)中扮演着至关重要的角色，为领域应用系统提供共享的词汇和概念性知识。OWL语言的理论基础是描述逻辑(description logics)，最新版本为OWL2，包括两个子语言OWL2DL和OWL2Full，以及三个轻量级易实现的Profiles。OWL2Full是表达能力最强的OWL子语言，但其强表达能力也导致了推理的不可判定，而OWL2DL则兼顾了表达能力和推理可判定性，因此为很多领域本体建模所采用，也出现了若干针对OWL2DL的高效推理机以支持领域知识推理和查询应答，如HermiT、Pellet、和RacerPro。然而由于元建模(meta-modeling)和数据集成(data integration)的需求，很多大型复杂本体实际上是属于OWL2Full的，如著名的常识本体OpenCyc、顶层本体SUMO和生物医学领域本体FMA和NCI，元建模是指本体中同一个名字具有多重身份的现象，比如类同时可以是属性或者实例，元建模也是导致推理不可判定的一个重要因素。相比于OWL2DL，目前对OWL2Full的推理研究及其少，也没有出现针对OWL2Full的推理机，因此，如何对语义网中现有的OWL2Full本体进行高效的推理和查询应答成为了一项巨大的挑战。 针对以上问题，我们在本文研究OWL2Full本体的推理和元查询应答(metaquery answering)。元查询是对目前流行的合取查询(conjunctive query)的扩充，其变量不仅可以出现在实例位置，也可以出现在类和属性的位置，通过元查询我们可以同时检索本体中满足查询条件的类、属性和实例。鉴于OWL2Full推理的不可判定性，我们的研究思路是探求OWL2Full的可判定的子语言，难点在于如何定义这样的子语言、并给出可靠和完备的推理和元查询应答方法。通过对语义网中实际存在的大规模的和复杂的OWL2Full本体进行分析，以描述逻辑作为基础，我们的主要成果包括以下几个方面: (1)针对语义网中大规模数据集Linked Open Data(LOD)，我们提出了OWL2Full的子语言Hi(DL-LiteA)。Hi(DL-LiteA)是对轻量级描述逻辑DL-LiteA在以下几个方面的扩充:(i)Hi(DL-LiteA)摈除了DL-LiteA中类名、属性名和实例名互不相交的约束;(ii)Hi(DL-LiteA)允许对函数属性进行子属性声明;(iii)Hi(DL-LiteA)去除了DL-LiteA的唯一命名约束。我们定义了Hi(DL-LiteA)的语法和语义，并给出了对Hi(DL-LiteA)本体进行可靠和完备的推理和元查询应答的方法，并由此得出Hi(DL-LiteA)的推理和元查询应答的数据复杂度和综合复杂度分别是LogSpace和PTime。 进一步地，为了高效处理像LOD这种超大规模的OWL2Full本体，受RDF哈希分割的启发，我们提出了对Hi(DL-LiteA)本体进行分而治之的推理和元查询应答方法，通过对Hi(DL-LiteA)本体和元查询进行分割，将Hi(DL-LiteA)本体的推理和元查询应答分解成多个独立的模块来进行。我们证明了该方法的可靠性和完备性，并在LOD中真实的数据集上验证了该方法的高效性。 (2)针对语义网中Horn-逻辑范畴内并且超出Hi(DL-LiteA)表达能力的OWL2Full本体，如OpenCyc和SUMO，我们提出了OWL2Full的子语言Hi(Horn-SROIQ)。Hi(Horn-SROIQ)是对目前表达能力最强的Horn-描述逻辑Horn-SROIQ的元建模扩充，其摈除了Horn-SROIQ中类名、属性名和实例名互不相交的约束。我们定义了Hi(Horn-SROIQ)的语法和语义，并给出了将Hi(Horn-SROIQ)的推理和元查询应答可靠和完备地规约为Horn-SROIQ内的推理和合取查询应答的方法。基于此方法，我们得出对Horn-SROIQ的元建模扩充并没有增加推理和查询应答的复杂度，即Hi(Horn-SROIQ)内的推理和元查询应答的数据复杂度分别为PTime和PTime-完全，综合复杂度分别为2ExpTime和2ExpTime-完全。 (3)针对语义网中生物医学领域的OWL2Full本体，如FMA和NCI，以及超出Hi(Horn-SROIQ)的表达能力并且不含枚举类的OWL2Full本体，我们提出了OWL2Full的子语言Hi(SRIQ)。H(SRIQ)是对SROIQ的比较重要的子语言SRIQ的元建模扩充，其摈除了SRIQ内类名、属性名和实例名互不相交的约束。我们定义了Hi(SRIQ)的语法和语义，并给出了将Hi（SRIQ）内的推理和元查询应答可靠和完备地规约为SRIQ内的推理和合取查询应答的方法。基于此方法，我们得出对SRIQ的元建模扩充并没有增加推理和查询应答的复杂度，即Hi(SRIQ)的推理和元查询应答的综合复杂度分别为2ExpTime和3ExpTime。 进一步地，针对大规模的Hi(SRIQ)领域本体，我们讨论了Hi(SRIQ)的一个子语言Hi(SRIF)，并给出了对Hi(SRIF)本体进行分而治之的推理和元查询应答方法。此方法通过对Hi(SRIF)本体和元查询进行分割，将Hi（SRIF）本体的推理和元查询应答分解成多个独立的模块来进行。我们证明了该方法的可靠性和完备性，并在实际的OWL2Full本体上验证了该方法的高效性。 (4)Hi(DL-LiteA)、Hi(Horn-SROIQ)、和Hi(SRIQ)内的元查询应答都是通过实例化元查询中的类和属性变量从而将元查询应答转换为合取查询应答来实现的，相比于合取查询应答，此过程不会增加复杂度，但会导致需要评估指数数目的合取查询。为此，我们提出了三个启发式规则来优化上述三个OWL2Full子语言内的元查询应答过程。这三个启发式规则分别是元查询的分割、子查询间的值传递、和检测无效的变量绑定，它们的目的都是减少在元查询应答时需要评估的合取查询的数目。我们给出了综合这三个启发式规则的元查询应答算法，并在实际的OWL2Full本体上验证了该算法的高效性。 Hi(DL-LiteA)是Hi(Horn-SROIQ)和Hi(SRIQ)的子语言，具有最弱的表达能力但同时也具有最低的数据复杂度，适合于需要处理大规模的数据集但同时对表达能力要求比较低的应用。Hi(Horn-SROIQ)与H(SRIQ)之间不具有包含关系，Hi(Horn-SROIQ)适合于需要一定规模的数据集和一定表达能力的应用，而Hi(SRIQ)适合于对表达能力要求比较高的应用，如需要表达类之间的并关系((U))。此外，Hi(Horn-SROIQ)支持枚举类，相比于不支持枚举类的Hi(DL-LiteA)和Hi(SRIQ)，对Hi(Horn-SROIQ)开发可靠和完备的分而治之的推理和元查询应答方法是一项更困难的任务，是我们未来的研究内容。