基于知识图谱的查询语句重写机制及方法

刘思培, 蔡一凡, 曹玲玲, 侯海婷, 鲍家坤, 袁 鸯

(1. 北方信息控制研究院集团有限公司 总体部, 南京 211111； 2. 吉林大学 软件学院,长春 130012)

0 引 言

知识图谱首先由Google提出, 主要由模式层和数据层组成[1]。在知识图谱出现之前, 搜索引擎根据用户关键词搜索的结果以网页链接列表形式呈现, 然后根据用户在网页中点击自己想要的链接, 才会浏览到相关的具体内容。知识图谱改善了搜索引擎的搜索模式, 将关键词的搜索结果以一定的组织结构呈现, 比如三元组结构的图模式[2]。知识图谱除了可以优化搜索引擎外, 还被广泛用于知识问答系统中[3], 以帮助系统理解人类语言并作出推理, 从而提升用户体验。已有的知识图谱有WikiData[4], Yago[5]和Freebase[6]等。

目前, 知识图谱中的数据通常采用W3C(World Wide Web Comsortium)标准的RDF(Resource Description Framework)或OWL(Web Ontology Language)语言格式, 而用于查询RDF或OWL数据的语言标准主要有SPARQL(SparQL Protocol and RDF Query Language)和RDQL(A Query Language for RDF)两种。SPARQL专门用于访问和操作RDF数据, 是一种主流的查询语言[7], 因此笔者使用SPARQL作为知识图谱的查询语言进行查询重写研究。当信息表示为RDF或OWL后, 出于查询和推理的需要, 将这些数据相关的部分以一定形式存储, 而SPARQL可以通过图模式匹配的方式从这些数据中获得指定的部分。

笔者研究的目的是利用本体重写查询语句, 发现隐含关联模式。目前重写技术的研究主要分为基于相似度的重写[8]和基于本体规则的重写[9]。由于基于本体规则的重写结果更加准确且可解释, 因此笔者采用基于本体规则的重写。本体规则主要有RDFS(Resource Description Framework)和OWL两种, 都是用于描述RDF数据的, 而OWL相比RDFS的表达能力更丰富, 推理能力更强, 所以笔者采用基于OWL本体规则的查询语句重写。

1 SPARQL查询基础知识

1.1 知识图谱查询语言SPARQL

SPARQL是由RDF Data Access Working Group开发的本体查询语言, 语法结构类似于SQL, 查询包含三元组模型和实例[10]。SPARQL的部分关键词有： SELECT指定要查询的变量, WHERE指定要查询的图模式。以下是一个SPARQL查询语句的实例。

SELECT ?X WHERE

{?X rdf:type ub:GraduateStudent.

?X ub:takesCourse http://www.Department0.University0.edu/GraduateCourse0}

在RDF数据模型中, 主体为顶点, 主体与客体之间的边为它们之间的属性, 属性包括主体自身的属性和主体与客体之间的关系。SPARQL查询语言和RDF三元组一样, 同样可以被表示为图模式[2]。所以在RDF数据中查询, 可以看作是SPARQL根据RDF的图模式进行匹配, 找出所有满足条件的结果。例子中的?X rdf:type ub:GraduateStudent语句就是根据RDF的三元组模式找出所有满足rdf:type是ub:GraduateStudent的实体, 其中?X为主体, ub:GraduateStudent为客体, rdf:type为这二者之间的属性。

1.2 SPARQL与Prolog的转换

在生成查询重写语句前, 需要先将SPARQL查询语句转换为对应的Prolog语句。Prolog是一种逻辑编程语言, 语法风格与Horn逻辑子句[11]相似, 本质上是对事实和规则的描述性语言。由于重写机制主要采用了归结消解方法, 而Prolog就是基于归结原理的一种逻辑程序语言, 因此将SPARQL语言转换为Prolog语言, 方便用于查询语句重写的实现。归结会将原有查询语言中不必要和多余的条件消解, 从而可得到更多的推理结果, 同时还可以提高查询效率。最后将得到的Prolog语言的结果再转换为SPARQL, 即得到了想要的重写后的SPARQL查询语句。例如, 1.1节中的SPARQL查询可以转换为如下的Prolog语句：

?-GraduateStudent(X),takesCourse(X,http://www.Department0.University0.edu/GraduateCourse0).

2 查询重写机制与方法

2.1 查询重写机制

原本知识图谱的知识库包括事实集和规则集, 下面对规则集做出以下几点限制： 1) 数据之间的关系只要求隐式的对称, 比如研究生是学生, 但学生不一定是研究生, 也可以是本科生； 2) 在归结中要替换的子句仅限于简单的事实, 比如替换1.2节Prolog语句中的GraduateStudent(X), 而不替换takesCourse(X,teacherOf(X))中的teacherOf(X), 这是为了避免程序出现死循环, 导致无法得出结果； 3) 归结过程是子句单调减少的, 也就是说重写的过程是有终止的, 当所有满足条件的子句都匹配完后, 即得到了重写后的结果。

图1所示的推理模板中, 例如A(x)表示一个x是A的事实,P(x,y)表示x和y存在某种关系,f(x)表示与x有关的实体。寻找可行的匹配得出新的子句, 并返回所有新子句的集合。如果无法在任一模板中得到匹配, 则返回空集。

图1 推理模板Fig.1 Reasoning template

2.2 查询语句重写方法

其输入为一个合取查询Q和一个本体TBoxT, 输出为根据Q和T重写得出的若干条查询。算法首先将Q和T转换为一系列子句, 然后用将子句两两归结得出新的子句, 算法如下。

输入： 合取查询Q, TBox本体T

R=Ξ(T)∪{Q};

repeat

for all clausesC1,C2 inRdo

R=R∪ resolve(C1,C2);

end

until无法归结出新的子句

return{C|C∈unfold(ff(R)),andC的前件与Q相同}；

算法分为3步： 1) 子句化(clausification); 2) 饱和化(saturation); 3) 优化。

第1步, 将Q和T转换为一系列子句的集合Ξ(T)∪{Q}。Ξ(T)表示由T得到的子句的集合。TBox公理与逻辑子句的转换如表1所示。

表1 公理T与子句集Ξ(T)的转换

第2步, 算法反复对子句集中的子句进行两两归结, 以期得出新的子句。归结方法以两个子句C1、C2为输入, 通过在表1所示的推理模板中寻找可行的匹配得出新的子句, 并返回所有新子句的集合, 从而得到未优化的重写语句。

当所有子句都归结完成后, 对新的子句集进行优化。先将子句集中所有包含函数项的子句删除, 然后将剩余所有不包含函数项的子句ff(Q,T)(Q为查询语句,T为TBOX本体)在集合U上进行扩展, 其中子句集U中的子句包含以下形式： 1)A(x)←B(x); 2)A(x)←R(x,y); 3)A(x)←R(y,x); 4)R(x,y)←S(x,y); 5)R(x,y)←S(y,x)。例如：ff(Q,T)=P(x)←A(x),U中有A(x)←B(x), 设子句集R={ff(Q,T)}, 则R在U上扩展后产生了新的子句P(x)←B(x), 扩展后得到新的结果R∪{P(x)←B(x)}。最后, 将所有与查询语句Q中的子句不匹配的子句删除, 得到最终优化后的重写语句结果。

2.3 查询语句重写举例

由于笔者是针对OWL规则集的推理, 即只输入Ontology定义, 与本体实例数据无关, 因此, 它只能处理不包含实例的查询语句(类似〈http://www.University0.edu〉的语句)。将LUBM提供的14条测试查询语句[12]用SPARQL语句中不包含实例的第9条语句进行重写。

先将SPARQL语句转换为Prolog形式, 然后通过Requiem重写, 第 9条语句只生成了一条新语句, 再将重写后的Prolog语句转换回SPARQL语句。

原始的SPARQL语句：

PREFIX rdf:〈http:∥www.w3.org/1999/02/22-rdf-syntax-ns#〉

PREFIX ub:〈http:∥swat.cse.lehigh.edu/onto/univ-bench.owl#〉

SELECT?X,?Y,?Z

WHERE

{?X rdf:type ub:Student.

?Y rdf:type ub:Faculty.

?Z rdf:type ub:Course.

?X ub:advisor?Y.

?Y ub:teacherOf?Z.

?X ub:takesCouse?Z}.

在University0_0.owl数据集上的查询结果：

重写后的SPARQL语句：

PREFIX rdf:〈http:∥www.w3.org/1999/02/22-rdf-syntax-ns#〉

PREFIX ub:〈http:∥swat.cse.lehigh.edu/onto/univ-bench.owl#〉

SELECT?X,?Y,?Z

WHERE

{?X ub:advisor?Y.

?X ub:takesCouse?Z.

?Y ub:teacherOf?Z.}

重写后的查询结果为：

可以看到比原来多出了8条结果。原来的查询语句翻译为： 要找这样的X,Y,Z, 学生X听老师Y教的课程Z。在数据集中, 只有UndergraduateStudent的type是学生, 而GraduateStudent的type是people, 其实际也是学生, 有属性takesCourse, 所以重写后的语句简化了, 删除了X,Y,Z的类型约束, 输出了更多结果。

这是由于查询重写会根据本体定义对原本的查询语句进行优化和扩展, 会删除其中冗余的限定条件, 因此重写后的语句复杂度总是低于原有的查询语句, 从而在能获得更多查询结果的同时提高了查询效率。

3 测 试

3.1 测试样例

利用LUBM提供的数据生成器[12], 根据Ontology生成大量关于大学语义的数据。为便于随后的测试, 分别生成了1、2、5、10所大学的数据。生成的数据是OWL格式, 1所大学对应的OWL文件大约有10～20个, 以1所大学为一个集合, 批量处理每所大学的数据。表2列出了各组数据的大小。

表2 大学数据集大小比较

笔者首先测试了1所大学的数据, 将原语句和重写后的查询语句得出的查询结果作出了对比。例如, 对语句Query6[12]进行重写, 比较原始语句和重写后的结果。

原语句直接使用SPARQL语句查询, 得到的结果为5 916, 即原语句查询University0这所大学有5 916个学生。

下面对Query6查询语句重写, 重写后生成的Prolog语句包括：

?-Person(X),Course(Y),takesCourse(X,Y) .

?-ResearchAssistant(X),Course(Y),takesCourse(X,Y) .

?-TeachingAssistant(X),Course(Y),takesCourse(X,Y) .

?-Person(X),GraduateCourse(Y),takesCourse(X,Y).

?-ResearchAssistant(X),GraduateCourse(Y),takesCourse(X,Y).

?-TeachingAssistant(X),GraduateCourse(Y),takesCourse(X,Y).

?-GraduateStudent(X).

?-Student(X).

?-UnderGraduateStudent(X).

分别得到参加Course的Person有21 489个, ResearchAssistant有1 099个, TeachingAssistant有827个, 参加GraduateCourse的Person有3 738个, ResearchAssistant有1 099个, TeachingAssistant有827个, GraduateStudent有1 874个, UndergraduateStudent有5 916个, Student有5 916个。

综合分析以上数据, ResearchAssistant,TeachingAssistant都属于Person, 参加Course的Person都可以称为Student, 而GraduateCourse属于Course, GraduateStudent和UnderGraduateStudent都属于Student, 且Student属于Person, 因此Query6的重写语句的查询结果为21 489个学生。

通过以上对比发现, 1所大学对Query6语句的查询, 原语句的查询结果为5 916个, 重写语句的查询结果为21 489个, 比原来多了15 573个结果, 挖掘出了更多的语义信息, 达到了预期。

3.2 查询结果与比较

表3为原语句和重写语句查询结果对比。从表3可以看出, 语句Query2和Query14没有得出更多查询结果, 这是由于Query2语句在去除了冗余条件的情况下, 限定条件依然很多, Query14语句请求查找UndergraduateStudent的实体, 但UndergraduateStudent这个条件已经不包含子类了, 所以这两条语句都无法挖掘出更多信息, 原语句查询已经足够。而其他语句都挖掘出了比原语句更多的信息, 重写Query6的查询结果大约是原语句的4倍, Query9大约是原语句的2倍, 总体看重写后比原语句得到更多的语义信息。表4为原语句和重写语句的查询时间对比。

表3 原语句和重写语句查询结果对比Tab.3 The comparison of results between original and rewritten queries (ms)

表4为原语句和重写语句查询时间对比结果。由表4可以看出, 除了语句Query9, 重写后的语句查询时间总体上比原语句的查询时间多, 但效率上没有太明显的差距, 因此笔者的重写实现是可行的。

表4 原语句和重写语句查询时间对比Tab.4 The comparison of time consuming between original and rewitting queries (ms)

4 结 语

笔者实现了查询结果与用户查询请求之间的语义级匹配, 满足用户的查询需求。笔者的解决方案是在本体规则的基础上, 利用Prolog逻辑程序对SPARQL查询语句进行重写。笔者提出的基于知识图谱的重写查询语句, 基于原有的查询语句语义, 保证在不破坏原有语义的基础上, 能挖掘出更多隐含的语义信息。在执行效率方面, 重写后的查询时间消耗代价是可接受的。从实测结果中可知： 对不明确的查询语句, 重写后可以得出更多的查询结果, 对明确的查询语句不能得出更多结果, 但查询效率更高。