基于最小解释的本体查询推理近似方法

摘要

本发明涉及一种基于最小解释的本体查询推理近似方法，属人工智能领域。方法的适用对象是表达能力强、应用范围广的datalog±本体。其特征在于将针对datalog±本体的查询自动转换成一组长度不超过用户指定阈值的最小解释，然后通过每个最小解释直接访问本体的ABox部分，得到各自的查询答案集合。这些集合的并集就是原查询答案集合的子集，其接近原集合的程度由最小解释的长度阈值所控制。方法的关键在于将datalog±本体的TBox部分自动编译成可以接收用户联合查询的Prolog程序，调用高效的Prolog系统自动计算所有长度不超过用户指定阈值的最小解释。方法整体的数据复杂度为多项式时间。本发明适用于各种基于datalog±本体的应用场合，为这些场合提供高效的信息查询服务。

说明书

技术领域

本发明涉及一种基于最小解释的本体查询推理近似方法，属于人工智能领域，适用于对大规模的datalog±本体进行查询推理。

背景技术

当前日益普及的万维网已经迈向Web3.0时代，其核心部分是语义Web，目标是提供一些机制让计算机可以理解和处理网页。本体作为语义Web的基础，日益受到人工智能和软件工程等学术领域的重视。本体是概念的显式表示。从人工智能的角度来看，本体可以表示为实体之间的逻辑关系。目前，基于本体的应用越来越多，尤其在生物医药领域已经涌现了一批采用大规模领域本体如SNOMED CT的实际应用。万维网联盟W3C组织于2004年提出了标准的Web本体语言OWL，于2009年提出了该语言的新版本OWL2，更是大大提升了本体的普及程度。Web本体语言OWL是一种逻辑语言，相当于一阶逻辑的可判定子集，依赖一阶逻辑的语义提供查询推理机制。不过，OWL或OWL2的表达能力略有不足，仅有一元和二元谓词，不能表示多于两个实体的关系，也不能表达复杂的一阶逻辑规则。

为了解决OWL和OWL2的表达问题，英国牛津大学Gottlob教授带领的学术团体提出了datalog±语言。传统datalog语言只允许不含函数项的Horn规则，而datalog±语言将Horn规则扩展成datalog±规则，允许规则头含有存在量词约束的变量。下面是datalog±规则的一个例子。

$>\exists Y.\mathrm{hasAuthor}(X,Y)\leftarrow \mathrm{Paper}\left(X\right)$>

该规则说明每篇文章X都有作者Y，而Y是不明确的。如果一条datalog±规则没有变量，并且只有规则头，则这条规则也称作事实。datalog±本体就是datalog±规则的集合，其中事实部分称作ABox部分，非事实部分称作TBox部分。

由于OWL本体可以转换成一阶逻辑规则集，datalog±本体与OWL本体是相似的。与OWL本体转换得到的一阶逻辑规则相比，datalog±规则不允许规则头含有多于一个原子，但是允许使用多元谓词，而不仅仅限于一元或二元谓词。datalog±语言能够表示多个实体之间的关系和复杂的一阶逻辑规则，大大拓展了本体语言的适用范围。但是，针对datalog±语言的查询推理不再是可判定的。也就是说，没有算法能够保证任意一个datalog±本体的逻辑推理能够在有限时间内完成。

以英国牛津大学Gottlob教授为代表的多位资深专家学者对datalog±语言进行了深入的研究，找出了若干个datalog±语言的可判定子集，比如线性规则集合(linear TGDs)等。这些可判定子集都有对应的查询重写方法，可以将一个联合查询(即由有限个原子以合取关系构成的查询)转换成有限个SQL查询，以这些查询访问ABox部分得到的答案集合的并集等价于给定查询的答案集合。也就是说，这些可判定子集具有数据复杂度多项式时间的查询推理算法，其中数据复杂度是仅以ABox中事实个数度量的复杂度。这个性质保证了某些datalog±本体具备高效的查询推理能力，能够扩展到很大的ABox，适用于大规模的实际应用。

不幸的是，由于查询推理的不可判定性，针对一般datalog±本体是不存在可终止的精确的查询推理算法的。因此我们只能诉诸于近似查询推理方法，其必须具备较低的计算复杂度，容易扩展到很大的ABox，以满足大规模实际应用的需要。

发明内容

本发明要解决的本体查询推理问题是：给定一个datalog±本体和一个针对该本体的联合查询，在数据复杂度多项式时间内找到给定查询答案集合的某个子集，作为查询答案集合的近似集。

本发明实现了一种基于最小解释的本体查询推理近似方法。该方法将针对datalog±本体的联合查询自动转换成一组长度不超过某个阈值的最小解释，然后通过每个最小解释直接访问本体的ABox部分，得到各自的查询答案集合。这些集合的并集就是原查询答案集合的子集。该子集接近原集合的程度由最小解释的长度阈值所控制：阈值越大，接近程度越高。

该方法的创新点在于最小解释的引入。给定一个datalog±本体和一个联合查询Q，Q在给定本体中的解释定义为含有变量的原子集合J，其既满足存在常量替换θ，使Jθ是给定本体的ABox的子集，又满足对于所有常量替换θ，若Jθ是给定本体的ABox的子集，则θ是Q在输入本体中的答案替换(answer substitution)。而Q在给定本体中的最小解释J定义为符合下面条件的解释：不存在Q在给定本体中的另一个解释J’和替换ρ，使J’ρ是J的多重集子集。

从上述定义可以得到以下结论：对于Q在给定本体中的任意最小解释J，满足Jθ包含于给定本体ABox的常量替换θ都是Q在给定本体中的答案替换；而对于Q在给定本体中的任意答案替换θ，都存在Q在给定本体中的最小解释J，使Jθ包含于给定本体的ABox。因此，通过Q在给定本体中的所有最小解释J访问给定本体ABox得到的答案替换集合(即由Jθ包含于给定本体ABox的常量替换θ构成的集合)的并集就等于Q在给定本体中的答案替换集合。我们将最小解释J中包含的原子个数称作J的长度。于是，通过Q在给定本体中所有长度不超过给定阈值的最小解释来访问给定本体ABox所得到的答案替换集合的并集就是Q在给定本体中的答案替换集合的子集。而该子集接近原集合的程度就由最小解释的长度阈值所控制。

本发明实现的方法包括以下步骤：

1.将输入datalog±本体的TBox部分编译成采用Tabling机制的Prolog程序，该程序可以接受用户提交的联合查询，并由高效的现有Prolog系统比如XSB解释执行。

2.每当用户提交一个联合查询Q和最小解释的长度阈值σ，该方法将查询转换成步骤1得到的Prolog程序可以接受的形式，触发Prolog系统计算所有长度不超过阈值σ的最小解释。

3.将步骤2计算得到的最小解释转换成SQL查询，对保存输入本体ABox部分的SQL数据库进行查询，得到各自的查询答案集合，然后计算这些查询答案集合的并集，得到用户查询标准答案集合的子集。

步骤1实现了将datalog±本体的TBox部分编程成Prolog程序的算法。算法得到的Prolog程序采用Tabling机制，以保证程序运行的可终止性。该程序可以接收用户提交的联合查询，并以查询驱动的方式高效计算所有长度不超过给定阈值的最小解释。由于在Prolog程序运行过程中，产生的最小解释候选个数与给定本体的ABox部分无关，而仅需要在筛选最小解释候选时访问ABox部分，因此最小解释的计算可以在数据复杂度多项式时间内完成。

步骤2实现了将用户给定联合查询转换为特定形式的算法。转换形式后的用户查询可以输入到步骤1得到的Prolog程序中，触发程序运行并输出用户查询的最小解释。

步骤3实现了将最小解释转换成SQL查询的算法。转换得到的SQL查询可以直接访问保存给定本体ABox部分的数据库，返回所有使给定最小解释包含于ABox部分的常量替换。

本发明为一般的datalog±本体提供一种高效实用的查询推理方法。该方法具有以数据复杂度度量的多项式时间的计算复杂度，能够满足大规模实际应用的需要。该方法解决了datalog±语言在查询推理中不可判定的问题。代价是牺牲了查询结果的完备性，但结果的完备程度可以由最小解释的长度阈值所控制。

附图说明

附图是本发明提出的基于最小解释的本体查询推理近似方法的流程图。

具体实施方式

Gottlob教授等人在ICDE2011国际数据库工程大会中发表了论文《Ontological Queries：Rewriting and Optimization》，提出了在datalog±本体中进行查询推理的精确方法。这种方法穷尽地调用两类规则即可应用(applicability)规则和可约(factorizability)规则，根据给定datalog±本体的TBox部分将输入的联合查询重写成多个新查询，然后通过这些新查询直接访问给定datalog本体的ABox部分，得到各自的查询答案集合。这些查询答案集合的并集就等于给定查询的答案集合。由于重写得到的新查询可能含有无穷多个原子，该方法不能保证对于任意给定的datalog±本体，查询回答都能在有限时间内完成。

本发明对Gottlob教授等人的方法进行了以下改造，保证其可终止性和实用性。首先，本发明为重写得到的新查询引入一个长度限制，以牺牲完备性为代价，保证方法的可终止性。其次，本发明为重写得到的新查询引入某种最小性，以减少新查询的数量。具备这种最小性并且在给定本体的ABox中存在查询答案的新查询就是本发明提出的最小解释。最后，本发明将可应用规则和可约规则编译成Prolog系统接受的Prolog规则，调用高效的Prolog系统来进行查询推理。由于Prolog系统在解释执行Prolog规则时采用最左原子选择(leftmostselection)的消解策略，采用一般消解策略的可约规则是不能转换成等价的Prolog规则集合的。因此，本发明引入了一个递归过程来确保Prolog规则和可约规则的等价性。

本发明提出的方法采用下述步骤近似计算用户给定的联合查询在给定的datalog±本体中的查询答案。

步骤1：将datalog±本体的TBox部分编译成Prolog程序

该步骤是本发明的重点。具体的编译过程如下：

(1)构造给定本体的TBox部分中所有谓词的依赖图。图中结点是谓词，谓词1到谓词2存在有向边当且仅当存在某个datalog±规则，谓词1出现在规则头，而谓词2出现在规则体。若存在由谓词1到达谓词2的有向路径，则我们称谓词1依赖于谓词2。依赖于自身的谓词称作递归谓词。若某个谓词出现在某个规则头中，其某个参数是受存在量词约束的变量，则这个谓词称作存在谓词，其受存在量词约束的参数位置称作存在位置。在给定本体的ABox部分具有事实实例的谓词称作事实谓词。

(2)将所有谓词的名称映射为p1，p2，...的形式，并将所有递归谓词设置为Tabling谓词，以保证这些谓词在访问执行时是可终止的。在Prolog系统XSB中，Tabling谓词使用“：-table”指令来定义。

(3)构造Prolog规则接收用户查询和返回最小解释。该Prolog规则为：

query(L，A)：-assertz(visited(L，A))，encode(L，A，Q)，(call(Q)；result(L1，A1)，doable(L1)，not visited_variant(L1，A1)，query(L1，A1)).

query(L，A)中L是用户查询中包含的原子集合，A是查询中需要返回常量替换的查询变量集合。query(L，A)的定义中采用递归过程来保证下面(5)中产生的Prolog规则和Gottlob教授等人提出的可约规则的等价性。assertz(visited(L，A))声明visited(L，A)为真，即L和A的组合已经被访问过。encode(L，A，Q)中Q是Prolog语句，由L和A转换而成，具体过程见步骤2。该语句包含了编译后的用户查询，可以通过call(Q)执行。result(L1，A1)返回计算得到的最小解释候选L1和对应的查询变量集合A1。doable(L1)判定L1是否可以继续调用可约规则，相当于判定L1中是否含有存在谓词。visited_variant(L1，A)判定L1和A1的组合或其通过变量改名得到的组合是否已经访问过，即判定是否存在由L1和A1组合通过变量改名得到的满足visited(L2，A2)为真的L2和A2组合。通过穷尽地调用query(L，A)，即指令“：-query(L，A)，fail”，可以得到所有最小解释候选及其对应的查询变量集合。这些最小解释候选L1及其对应的查询变量集合A1可以通过result(L1，A1)获取。encode(L，A，Q)过程保证了若L1和A1转换得到的SQL查询(转换过程参见步骤3)在ABox部分有查询答案，则L1就是一个最小解释。

(4)对每个存在谓词或事实谓词进行溯因规则的编译。溯因规则是产生最小解释候选的规则。因为最小解释候选仅包含事实谓词或者存在谓词，所以仅需要针对这些谓词进行溯因规则的编译。对于每个存在谓词或事实谓词p，构造下面的Prolog规则(该规则假定p是二元谓词)：

p(X，Y，VL，L1，L2，A)：-ok(L1)，sort([p(X，Y)|L1]，L2)，not pruned(L2，A).p(X，Y，VL，L1，L2，A)中X和Y分别是谓词p的两个参数，VL是当前Prolog目标中非首原子含有的变量集合，L1是输入的部分最小解释，L2是输出的部分最小解释，A是部分最小解释对应的查询变量集合。ok(L1)判定L1中原子个数是否小于给定的最小解释长度阈值。sort([p(X，Y)|L1]，L2)将p(X，Y)加入到L1的头部，并对更新的L1中所有原子作排序，得到L2。pruned(L2，A)判定目前是否已经产生过L3和A3的组合(通过result(L3，A3)得到)，满足存在变量替换ρ，使L3·ρ是L2的多重集子集并且A3·ρ＝A，即判定L2是否不可能为最小解释。

(5)对每个存在谓词或事实谓词进行可约规则的编译。这种可约规则是Gottlob教授等人提出的可约规则的一种简化。它只针对当前Prolog目标和当前产生的部分最小解释进行消解。因为最小解释候选仅包含事实谓词或者存在谓词，所以仅需要针对这些谓词进行可约规则的编译。对于每个存在谓词p，构造下面的Prolog规则(该规则假定p是二元谓词，且第二个参数位置是存在位置)：

p(X，Y，VL，L1，L2，A)：-not in(Y，VL)，Y＝＝X，length(L1，N)，member(p(X1，Y1)，L1)，not in(Y1，VL)，Y1＝＝X1，Y1＝＝X，Y＝＝X1，X1＝X，Y1＝Y，sort(L1，L2)，length(L2，N).in(Y，VL)判定Y是否在有序集合VL当中。Y＝＝X判定X和Y是否为不同的符号。length(L1，N)返回L1中的元素个数N。member(p(X1，Y1)，L1)取出L1中的一个元素p(X1，Y1)。该Prolog规则保证调用可约规则后，部分最小解释的长度不减小，以避免产生冗余的部分最小解释。对于每个事实谓词而非存在谓词p，构造下面的Prolog规则(该规则假定p是二元谓词)：

p(X，Y，L1，L2，A)：-length(L1，N)，member(p(X，Y)，L1)，sort(L1，L2)，length(L2，N).该Prolog规则同样保证调用可约规则后，部分最小解释的长度不减小，以避免产生冗余的部分最小解释。

(6)将TBox部分的每条datalog±规则进行编译。该过程相当于针对Gottlob教授等人提出的可应用规则进行编译。比如，针对下面的datalog±规则：

$>\exists Y.\mathrm{hasAuthor}(X,Y)\leftarrow \mathrm{Paper}\left(X\right)$>

假定在(2)中Paper已经映射为p1，而hasAuthor已经映射为p2，则该规则编译为：

p2(X，Y，VL，L1，L3，A)：-not ground(Y)，not in(Y，VL)，Y＝＝X，length(L1，N1)，

sort(VL，VL1)，p1(X，VL1，L1，L2，A)，sort(L2，L3)，length(L3，N2)，N2＞＝N1.该规则保证在调用p1(X，VL1，L1，L2)时VL1是有序的，这样可以减少需要Tabling存储的p1(X，VL1，L1，L2)的原子数目，降低内存消耗。此外，该规则还保证调用可应用规则后，部分最小解释的长度不减小，以避免产生冗余的部分最小解释。

对于没有存在量词约束的datalog±规则，编译更加简单。比如，针对下面的规则：

reaches(X，Z)←reaches(X，Y)，reaches(Y，Z)

假定在(2)中reaches已经映射为p3，则该规则编译为：

p3(X，Z，VL，L1，L4，A)：-length(L1，N1)，append_sort([Y，Z]，VL，VL1)，p3(X，Y，VL1，L1，L2，A)，remove_ground(VL，TVL2)，sort(TVL2，VL2)，p3(Y，Z，VL2，L2，L3，A)，sort(L3，L4)，length(L4，N2)，N2＞＝N1.

append_sort([Y，Z]，VL，VL1)将Y和Z添加到VL中，并对更新的VL1中所有变量作排序，得到VL1。添加Y和Z的原因是当执行p3(X，Z，...)时，当前Prolog目标将会添加本规则体中后续的原子p3(Y，Z，...)，因此Y和Z必须添加到当前Prolog目标中非首原子含有的变量集合中。remove_ground(VL，TVL2)将VL中的常量删除，得到TVL2。它和sort(TVL2，VL2)保证在调用p3(Y，Z，VL2，L2，L3)时，VL2是有序的。该规则同样保证调用可应用规则后，部分最小解释的长度不减小，以避免产生冗余的部分最小解释。

步骤2：将联合查询转换成Prolog程序接受的形式

该步骤实质上是步骤1中encode(L，A，Q)过程的实现。encode(L，A，Q)将构成联合查询的原子集合L及其对应查询变量集合A转换成call(Q)可以接受的Prolog语句Q。该语句包含编译后的联合查询，可以调用步骤1中产生的Prolog规则执行。执行后得到的最小解释候选及其对应的查询变量集合将保存在形式为result(L1，A1)的Prolog声明中。比如，假设联合查询如下：

$>\exists Y.\mathrm{hasAuthor}(X,Y),\mathrm{publishesIn}(X,\mathrm{China})$>

该联合查询寻找所有在中国出版的具有作者的资料。假定在步骤1的(2)中hasAuthor已经映射为p2，而publishesIn已经映射为p3，并且China在存储ABox的数据库中映射为ID＝1的个体，则Prolog程序将调用encode([p2(X，Y)，p3(X，1)]，[X]，Q)过程。这个过程将Q赋值为下述Prolog语句：

p2(X1，X2，[X1]，[]，L1，[X1])，p3(X1，1，[X1]，L1，L2，[X1])，sort(L2，L)，

not pruned(L，[X1])，(inv_prune(L，[X1])；assertz(result(L，[X1])))，fail.语句中所有查询谓词(这里是p2和p3)的第三个参数都设成由联合查询中自由变量和后续查询谓词中出现的变量所构成的变量集合，而最后一个参数都设成查询变量集合。sort(L2，L)对最小解释候选L2中包含的原子作排序，得到L。not pruned(L，[X1])表示不存在L3和A3的组合(通过result(L3，A3)得到)和变量替换ρ，使L3·ρ是L的多重集子集并且A3·ρ＝[X1]。这意味着仅有满足not pruned(L，[X1])为真的集合L才有可能是最小解释。inv_prune(L，[X1])将所有形式为result(L3，A3)的满足下面条件的Prolog声明删除：存在变量替换ρ，使Lρ是L3的多重集子集并且[X1]ρ＝A3。inv_prune(L，[X1])实质上是通过L和[X1]的组合将所有已经保存的不可能是最小解释的候选删除。assertz(result(L，[X1]))添加Prolog声明result(L，[X1])，表明L是一个最小解释候选而[X1]是其对应的查询变量集合。保留字fail确保Q中所有Prolog原子穷尽地执行，以产生所有最小解释候选及其对应的查询变量集合。

步骤3：将最小解释转换成SQL查询，执行查询，合并查询答案

该步骤将由result(L，A)得到的各个最小解释候选L及其对应的查询变量集合A转换成SQL查询，访问存储给定本体ABox部分的数据库，得到各自的查询答案集合，并计算这些查询答案集合的并集，作为标准查询答案集合的近似集。这个步骤不显式验证最小解释候选是否为真正的最小解释，因为该验证也是通过转换后的SQL查询完成的。当且仅当转换后的SQL查询存在查询答案时，对应的最小解释候选是真正的最小解释。因此，非最小解释对最终的查询答案集合没有影响，可以采用与最小解释相同的方式进行处理。在转换的过程中，最小解释候选L中包含的原子将编译成SQL查询语句的from子句和where子句，而其对应的查询变量集合A将编译成SQL查询语句的select子句。比如，当L为[p1(X1)，p3(X1，1)]而A为[X1]时，本步骤将生成下述SQL查询：

select distinct p1.arg1as X1from p1，p3where p3.arg1＝p1.arg1and p3.arg2＝1；

为了验证本发明提出的方法，实验过程将IBM中国研究院在第3届欧洲语义Web大会(ESWC2006)中发布的UOBM-Lite1和UOBM-Lite10基准本体改造成datalog±基准本体。该改造合并了逻辑相等的个体，并删除了TBox中一条不能转换成datalog±规则的公理。改造后的UOBM-Lite1本体和UOBM-Lite10本体的TBox部分均有137条datalog±规则，而ABox部分分别有245826和2096763个事实。以开源软件Pellet(2.2版本)作对比，验证本发明提出的方法针对所有基准查询的回答近似程度。这些基准查询一共有13个，都是IBM中国研究院在第3届欧洲语义Web大会(ESWC2006)中公开发布的。而Pellet是目前为止能够精确回答这些基准查询的公开软件。所有实验结果均在一台具有2.8GHz双核CPU和16G内存的安装Win7(64位)系统的台式机上取得。

下表1列出了Pellet针对改造后的UOBM-Lite1本体和UOBM-Lite10本体回答13个基准查询的时间和答案数，显示出Pellet实现的精确方法难以处理某些基准查询，比如查询8和查询11至少需要数分钟，而查询13至少需要数小时。对于同一查询，针对UOBM-Lite10的查询回答时间是针对UOBM-Lite1的查询回答时间的上十倍。这说明精确方法的可扩展性(scalability)不太好。

表1Pellet实现的精确方法回答13个基准查询的时间(以毫秒计算)和答案数

下表2列出了针对UOBM-Lite1和13个基准查询，本发明提出的近似方法基于1到5的最小解释长度阈值进行查询回答的时间、产生的答案数及其占完整答案的比例。该表仅列出本发明提出的近似方法在一分钟内的执行情况。

表2本发明方法针对UOBM-Lite1回答13个基准查询的时间(以毫秒计算)、答案数及其占完整答案的比例(前面带*号的答案数是在一分钟时间内产生的查询答案数量)

下表3列出了针对UOBM-Lite10和13个基准查询，本发明提出的近似方法基于1到5的最小解释长度阈值进行查询回答的时间、产生的答案数及其占完整答案的比例。该表仅列出本发明提出的近似方法在一分钟内的执行情况。与表2比较，本发明提出的近似方法并没有因为本体ABox中事实的大量增加而明显消耗更多的查询回答时间。这表明本发明提出的近似方法具有很好的可扩展性。

表3本发明方法针对UOBM-Lite10回答13个基准查询的时间(以毫秒计算)、答案数及其占完整答案的比例(前面带*号的答案数是在一分钟时间内产生的查询答案数量)

实验结果表明，本发明提出的本体查询推理近似方法在长度阈值较小的情况下可以快速产生大部分的查询答案，并且容易扩展到很大的ABox。在实际中，用户可以采用逐渐增大长度阈值的方式反复调用本发明提出的近似方法来计算查询答案，直到超出自己可以接受的时间时终止方法的运行。然后，以最近两次调用方法得到的查询答案的并集作为标准查询答案集合的近似集。这种方式能够快速得到大部分的查询答案。