DSE精选文章 | SUMA:高效的支持OWL 2 DL的查询回答系统 SUMA:A Partial Materialization-based Approach to Scalable Query Answering in OWL 2 DL

Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办,数据库专业委员会承办,施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文,得到中新赛克赞助文章处理费。


文章介绍

       本体推理问答是一个公认的难问题,因为推理时间开销巨大,在实际应用中完全做到线上实时推理问答是非常困难的。本体物化通过扩展本体到一个近似的本体模型,将本体推理问答中的推理任务放在线下来预处理,从而减少线上问答的时间代价。近年来,本体物化已成为本体推理问答的一种重要的优化方法,因其线上高效的查询性能,使其具有广泛的实际应用前景。然而,现有的本体问答推理机不能解决无穷物化问题(本体的模型是无穷,这种情况是经常发生的),或者物化算法时间复杂度过高,只能处理中小型数据,或者需要额外的线上查询改写的时间消耗。为此,我们向大家推出查询回答系统SUMA,提供较高完备性的大规模数据的实时推理。该系统具有以下特点:

       高性能:SUMA采用低复杂度的物化算法并且为了加快事实和规则的匹配时间,为数据和规则构建三种类型的索引。

       大规模:SUMA支持单机亿级数据的实时推理。在24核180G内存的测试环境下,SUMA物化LUBM(1000)(1亿条元组)需要202s,物化UOBM(500)(1亿条元组)需要515s。预处理LUBM(1000)的时间总计为627s,是PAGOdA预处理时间的二分之一。预处理UOBM(500)的时间总计为966s,是PAGOdA预处理时间的六分之一。

       适应性:SUMA采用纯物化的方法进行查询回答,SUMA物化与查询独立,从无需对查询进行改写,也适合所有数据。

       完备性:SUMA通过添加额外的推理规则和数据结构来保留近似处理可能会丢失的部分OWL 2 DL语义。在所有测试查询中,以Pellet的查询结果为评估标准,PAGOdA在8个测试查询上得到的答案是不完备的,SUMA在所有测试查询上都是可靠完备的。

       简便性:SUMA提供推理接口,可以为任何系统提供推理服务,同时也可以整合任意ARQL查询引擎执行查询任务。

图片1

       

      SUMA包含四个模块:本体处理,存储,物化和线上查询。下面我们简要介绍四个模块的工作流程:

线下部分:

在物化之前预处理本体和数据

      存储模块通过Jena API解析元组,将字符型数据编码为整形ID。将编码后的三元组存储为元组表,同时为元组表构建三级索引。此时,本体处理器使用OWL API解析本体,改写器通过近似规则近似处理OWL 2DL公理。处理器通过与数据共享的字典对改写后的公理集进行编码,并存储为带有索引的公理表。

根据公理,对原始数据进行物化

      物化模块迭代的读取一个未处理的事实F并且判定F不为冗余数据(在sameAs语义下,不存在等价元组)之后,解析F的数据类型。假如F表达个体等价性,则sameAs模块通过自身的sameAs算法对其进行处理;假如F涉及函数属性或者逆函数属性,则根据推理规则生成新的个体等价或者抛出异常;最后一种通用模式,匹配F对应的所有公理,根据F将公理转换为绑定查询,对已知元组表通过索引进行快速查找。根据查询答案生成新的事实。

线上部分:

线上执行SPARQL查询

      查询处理器计算查询中限制变量的个数,模型匹配器根据查询处理器的输出结果选择物化模型,并将数据和查询传递给SPARQL查询引擎。

图片2

1. 物化算法

图片3

2. sameAs 算法


实验

      为了验证SUMA的性能,尤其指预处理时间(包含物化时间)和在无穷物化情况下的查询的完备性,我们通过对LUBM和UOBM本体添加额外的公理,构建无穷模型的测试本体LUBM+和UOBM+。在有穷模型和无穷模型上分别测试了SUMA的性能。实验结果表明SUMA在所有测试查询上都是可靠完备的,并且它只需要花费202s来物化LUBM(1000),515s物化UOBM(500)。(实验中所有测试本体和查询都已开源在https://github.com/SUMA-2019)

图片4

图3. 实验中使用的本体,数据和查询


完备性评估

       完备性测试是计算在确定性语义下,SUMA可以正确回答的查询数目。我们将Pellet的结果作为评估指标。实验结果表示对于所有的测试查询,SUMA都可以计算出所有的正确答案。而PAGOdA在LUBM+的五个测试查询(Q2,Q4, Q5, Q6,Q7)上和UOBM+的三个测试查询(Q1,Q2, Q3)上是不完备的。

预处理时间评估

      在测试预处理时间时,我们设置LUBM数据的增长步长为200,本体较复杂的UOBM数据的增长步长为100。下图给出了SUMA和PAGOdA预处理时间的对比:

图片5

4. LUBM预处理时间

图片6

5. UOBM预处理时间

       从图中可以看出,在所有LUBM和UOBM数据集上,SUMA的预处理时间都比PAGOdA更快,特别的,在三个UOBM数据集上,SUMA的预处理时间比PAGOdA快了七倍。


总结

       SUMA是一个支持OWL 2 DL本体的高效可扩展的查询回答系统。SUMA通过为事实和规则构建高效的索引,显著降低了离线物化成本。此外,低复杂度的物化算法使得SUMA能够支持大规模数据集的实时推理。


作者简介

图片7

秦笑宇,女,2021年获得天津大学工学硕士学位。主要研究方向为本体推理,目前任职于百度研发工程师。

图片8

张小旺,男,北京大学理学博士,天津大学智能与计算学部副教授、博士生导师,天津市青年特聘专家、天津大学北洋青年学者,天津市认知计算与应用重点实验室副主任、格里菲斯大学客座副教授。研究方向包括图数据库、知识图谱、人工智能等。个人研究兴趣主要围绕知识图谱标准语言SPARQL基础理论性问题(可满足性问题、布尔表达性问题和路径表达性问题)以及知识图谱分布式管理与推理系统,近年来,研究兴趣也包括知识表示学习及其应用。目前主持国家重点研发计划"云计算与大数据"和“精准医学”专项子课题2项,国家自然科学基金项目2项(青年,面上)等7项课题。在国内外学术期刊和会议上发表论文100余篇,获得ACM天津新星奖和天津大学沈志康奖教金。


期刊简介

图片9

Data Science and Engineering(DSE)是由中国计算机学会(CCF)主办、数据库专业委员会承办、施普林格 自然(Springer Nature)出版的Open Access期刊。为了迎合相关领域的快速发展需求,DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点,以大数据作为研究重点,征稿范畴主要包括4方面:(1)数据本身,(2)数据信息提取方法,(3)数据计算理论,和(4)用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录,CiteScore2020为4.9,在Computer Science Applications领域排名#181/693(73rd Percentile)。稿件处理费由赞助商中新赛克(Sinovatio)承担,欢迎大家免费下载阅读期刊全文,并积极投稿。

原文链接:

https://link.springer.com/article/10.1007/s41019-020-00150-0