混合的本体原子分解方法
2015-04-14王昌龙冯志勇饶国政
王昌龙 ,冯志勇 ,王 鑫 ,饶国政
1.天津大学 计算机科学与技术学院,天津 300073
2.西北师范大学 计算机科学与工程技术学院,兰州 730070
1 引言
基于Web本体语言(Web Ontology Language,OWL)及其扩展版本OWL 2的本体在语义Web开发中扮演着最重要的角色[1]。同时,OWL本体也广泛应用在生物医学信息系统[2-3]以及其他的应用领域,如农业[4],天文[5],国防[6],地理[7]和交通[8-9]等。本体的广泛应用导致大规模本体逐渐增多,著名的大型本体如SNOMED CT和FMA,其包含的公理数已经超过1 000 000条。在生物医药本体库NCBO BioPortal中,很多单个本体的规模已经达到100 000,如GO,ChEBI,GALEN等[10]。伴随大规模本体的一个难题是复杂性问题。从推理方面看,用户只需要本体中的小部分知识,而本体中的大部分知识与个别子领域中具体的应用无关,在这种情况下,没有必要把整个本体都装入内存或通过网络传输;从认知方面看,本体工程师很难理解大规模本体的内部结构。
本体模块化是处理大规模本体问题的一种方法,它为抽取模块提供了理论基础和工具支持[11-12]。基于语法局部性的模块抽取算法能够在多项式时间内提供模块抽取服务,但该传统的模块抽取方法需要把整个本体装入内存。另外,这种方法需要检查每一个公理与目标模块的相关性[13-14]。最近提出本体原子分解(atomic decomposition)方法[15],克服传统的模块抽取方法的缺点:在原子分解的情况下,本体原子成为模块的基本构造组件,基于原子分解的模块抽取算法的时间复杂度为线性[16],模块抽取具有更高的效率;同时,在以分解的方式管理本体的情况下,可以根据需要部分加载本体[17]。
本质上,原子分解是识别本体模块的基本构件的过程——通过识别本体中高度关联的公理团(原子),依据这些原子之间的依赖关系来构造本体模块。原子分解本身仍然是一项计算量较大的工作。在利用原子分解技术实现本体模块化推理的时候,实验发现,对于一些大型的本体,如NCI,其原子分解的时间超过了5个小时[18-19]。文献[20]中的实证研究表明,超过10%的大型本体不可能在12小时内完成原子分解。传统的原子分解方法效率不高,其主要原因在于,该方法简单地将本体视为公理的集合,没有考虑公理的类型,也没有考虑本体的特性。另外,传统的原子分解方法直接依赖于模块抽取,很难实现并行化以充分利用当前流行的多核计算平台。
实际应用中的很多本体,其中的绝大部分公理属于EL类型,非EL公理只占极少数。如最新的医药生物本体NCI含有226 038条公理,其中,EL类型的公理为225 971条,占99.97%;蛋白质本体Protain含有46 698公理,其中的EL公理数为46 682,占99.97%[18]。EL本体具有一个重要的属性:EL本体的语法局部性模块抽取问题等价于相应有向超图中的可达性问题[21-23]。本体的有向超图模型为引入标准的图论算法及其并行机制提供了理论基础。文[21]研究表明,对于轻量级EL本体,基于有向超图的原子分解方法比传统的方法具有更高的效率,平均加速比超过100。但是,这种基于有向超图的原子分解方法只局限限于弱表达力的EL本体。
鉴于以上两种方法的互补特性,在本文中,联合本体的有向图表示模型和传统的原子分解方法对大型的强表达力本体进行原子分解。具体分为两步:首先,从原本体中分离出EL子本体OEL并表示为有向超图HEL,通过计算强连通分量,形成部分原子分解AEL;然后,利用传统的原子分解方法,将剩余的非EL公理加入部分分解AEL,得到完整的原子分解AO。
混合原子分解方法的优点表现两个方面:①可以直接使用现存的优化的原子分解算法;②将本体中的大部分EL公理表示为有向超图模型,方便使用标准的图论算法[24-25],有助于并行化以充分利用方便得到的多核计算平台。从优化的角度看,混合原子方法将大部分工作负载赋予高效的图论算法来处理,只把少部分工作委托给低效率的逻辑模块识别方法。
2 基础知识
OWL以描述逻辑(Description Logic,DL)为逻辑基础[26]。OWL 2对应描述逻辑SROIQ,后者是目前表达力最强的可判定描述逻辑[27]。OWL 2 EL(简称EL)为OWL 2的一个子语言,对应描述逻辑EL++,EL只允许使用有限的逻辑运算子,即合取(conjunction)和存在约束(existential restriction)[28]。为简单起见,本文使用描述逻辑的形式化描述。
描述逻辑采用模型论语义,详细描述可参阅文献[26]。描述逻辑本体的词汇包括概念名、角色名、个体名以及两个特殊的概念:顶概念T表示全域,底概念 ⊥表示空。公理(集)α包含的词汇记为S(α)。在描述逻辑本体中,通常采用模型保持性扩展(model conservative extension)来描述逻辑模块[14]。本体O与其关于种子词汇集∑的模块M(记为M(∑,O))蕴含相同的公理,这些公理由∑中的符号构成。由于最小模块的计算复杂性等同于推理难度,具有多项式计算复杂性的语法局部性模块(Syntactic Locality Module,SLM)成为最小模块的有效近似。语法局部性模块的类型x包括顶类型(Top)Τ、底类型(Bottom)⊥ 和星型(Star)Τ ⊥ *。如果α关于∑不具有x局部性(Locality),则α与∑相关,∑称为α的局部性符号集,公理α包含在模块Mx(∑,O)中。本文采用 ⊥型模块,直观上,⊥模块的计算方法是,把公理α中不属于种子符号∑的词汇替换为 ⊥,如果得到的公理为重言式,则α关于∑具有局部性,α不在模块M⊥(∑,O)中,文[14]实现了基于语法局部性的模块抽取算法。
本文使用惯用的图论术语。有向超图为二元组H=(V,E),其中V为顶点集,E为超边集。超边e为二元组e=(T(e),H(e)),其中T(e)和H(e)均为V的非空子集,分别表示e的头和尾。从节点v1可到达v2,记为v1→2,满足条件:①v2=v1;或② ∃e∈E,s.t.v2∈H(e)且∀v∈T(e)有v1→v。从顶点v1到vn的路径P径为序列 (v1,vn)=v1e1v2e2,…,en-1vn,满足vi∈T(ei),vi+1∈H(ei),(i=1,2,…,n-1)。如果vn∈T(e1),P(v1,vn)称为超环。在有向超图H中,如果节点v2和v1互相可到达,称v2和v1强连通。超图H中互相可到达的顶点集称为强连通分量(Strongly Connected Component,SCC)。
3 本体的原子分解
在模块抽取的过程中,不同的种子词汇可能产生相同的模块。以公理的词汇为种子符号,能够产生相同模块的所有公理构成的集合称为一个本体原子。为了方便理解原子分解算法(算法1)[15],对原子进行如下的形式化定义:
定义1(原子)给定本体O,公理集αt={α1,α2,…,αn}⊆O,如果M⊥(S(α1),O)=M⊥(S(α2),O)= ,…, =M⊥(S(αn),O),对于任意的公理β∈O{at},M⊥(S(β),O)≠M⊥(S(αi),O),i=1,2,…,n。称at为O的一个 ⊥ 原子1)在原子分解过程中,假设本体不含有全局公理和常言式[15]。。
原子表示语义高度关联的公理集,从逻辑模块的角度看,一个原子中的所有公理总是同时出现在某个模块中。原子类型与模块类型相关,用Ax(O)表示O的所有x类型原子的集合,则Ax(O)是O的一个划分,每个公理只出现在一个原子当中[17]。以原子at的词汇为种子符号的模块M(S(at),O)称为真模块2)真模块不能为两个或多个不相交模块的并。,记为Mat。实际上,如果α∈at,Mat与M⊥(S(α),O)一致[17]。根据真模块之间包含关系,原子之间的依赖关系定义如下:
定义2(原子依赖关系)a和b为本体O的两个原子,如果Ma⊆Mb,称原子b依赖a,记为b≥a。
由原子以及原子之间的关系构成的二元组(Ax(O),≥)称为本体的原子分解,记为AO。定义1和定义2分别蕴含了原子及其依赖关系的计算过程[17],如算法1所示。该算法的基本思想是,首先利用每一个公理的词汇为种子符号来识别模块,如果多个公理引起的模块相同,则这些公理构成一个原子,然后利用这些原子对应的真模块之间的包含关系建立原子依赖关系。具体地,算法1第3行除去本体中的全局公理,得到需要处理的公理集TodoAxioms,第4行GenAxioms表示所有原子中用来产生真模块的公理的集。余下分为两个独立的部分:第一部分(5~18行)创建所有的本体原子。以每一个公理a的词汇为种子符号抽取模块(第6行),并比较新模块和已经创建的模块,如果该模块已经存在,则公理α加入已有原子(10行);如果不存在以α为种子符号创建的模块,则为α创建新的原子(15行)。第二部分(19~25行)计算原子间的依赖关系:通过比较两个原子对应的真模块之间的包含关系来设置原子的依赖关系:如果原子a中的公理出现在为b原子创建的模块中,则b依赖a:b≥a。如果本体的规模为n,基于语法局部性的模块抽取算法的复杂度为O(n2)[13]。明显地,算法1中创建原子的复杂度为O(n4),如果本体的原子数目为m,则计算原子依赖关系的复杂度为O(m2)。一般地,原子总是包含多个公理,因此,本体原子分解算法中的大部分时间用于原子计算。算法1已经实现在OWL API的软件包OWLAPITOOLS中(http://owlapitools.sourceforge.net/)。
D.Tsarkov对算法1进行局部优化:创建原子时根据公理所属模块减少遍历空间;在创建原子的时候同时计算原子依赖关系[29]。该优化算法已实现在描述逻辑推理器 FaCT++中(http://code.google.com/p/factplusplus/)。在本文的实验中,将与FaCT++进行比较。
4 本体的有向超图模型
如前文所述,判断公理α关于种子词汇∑的 ⊥语法局部性的依据是,将α中不属于∑的词汇替换为 ⊥,检查得到的公理是否为重言式。对于大规模本体,该过程繁琐且计算量大。如果本体为轻量级的EL类型,判断公理的 ⊥语法局部性的过程可以进一步简化——由α的左边词汇S(L(α))或右边词汇S(R(α))与∑的包含关系来确定[22]:
命题1设α为EL公理,∑为词汇集,则
(1)如果α=(C⊆D),则α关于∑不具有语法局部性当且仅当S(L(α))⊆∑。
(2)如果α=(C≡D),则α关于∑不具有语法局部性当且仅当S(L(α))⊆ ∑ 或S(R(α))⊆ ∑ 。
直观上,如果公理α的形式为C⊆D,且该公理的左边词汇集S(L(α))为∑的子集,则α关于∑不具有语法局部性,即α与主题“∑”相关,α应该包含在以∑为种子符号的模块中;同样地,如果形如C≡D的公理α的左边词汇集S(L(α))或右边词汇S(R(α))包含在∑中,α必然包含在以∑为种子符号的模块中。因此,EL公理的词汇集之间的包含关系体现公理之间的逻辑关联关系,这种关系可用有向图来表示,称为公理依赖性超图(Axiom Dependency Hypergraph,ADH)[21,23]。ADH中的顶点表示本体的公理,ADH的边表示公理词汇集之间的包含关系。根据命题1,ADH的边蕴含了公理之间的依赖关系。用S⊥(α)表示公理α的 ⊥局部性符号集,如果α的形式为C⊆D,则S⊥(α)=S(L(α));如果α的形式为C≡D,S⊥(α)={S(L(α)),S(R(α))}。
定义3(EL本体的 ⊥局部性公理依赖超图)[21]。设O为EL本体,O的 ⊥局部性公理依赖超图(ADH)HO=(V,E),其中
V=O;
e=(T(e),H(e))∈E,当且仅当下面条件成立:
(1)H(e)={β};
(2)T(e)⊆V{β},对于X∈S⊥(β),满足 |T(e)|最小且X⊆S(T(e))。
这里,EL本体的公理依赖超图是针对 ⊥局部性定义的。顶点为本体的公理,边关联尾结点公理集{α1,α2,…,αn}和单个头结点公理β,使得β的 ⊥ 局部性符号集包含在α1,α2,…,αn的符号集中。最小性条件表明,为了覆盖β的 ⊥局部性符号,每个公理αi都是必须的。
定义3蕴含了将EL本体O表示为有向图的过程:对于每个头结点公理β∈O,寻找满足S⊥(β)⊆sig(T(e))的最小尾结点集。如果本体规模为n,将O表示为有向超图的计算复杂度为O(n2)。
将本体表示为有向超图之后,可以借助超图的可达性来识别本体中的 ⊥局部性模块。
命题2 设O为 EL本体,α∈O,则M⊥(S(α),O)={β|α可到达β}
EL本体中的原子对应公理依赖性超图中的强连通分量。
命题3设O为EL本体,SCCs(HO)表示超图HO中所有的强连通分量集,则A⊥(O)=SCCs(HO)。
EL本体中原子间的依赖性对应于超图HO中强连通分量之间的指向关系。对于S1,S2∈SCCs(HO),如果存在超边e=(T(e),H(e))使得H(e)⊆S1且H(e)⊆S2,称S1依赖S2,记为S1→S2。显然,→ 为偏序关系(自反、反对称和传递属性)。
命题4 设O为EL本体,a1,a2∈A⊥(O),S1,S2∈SCCs(HO),如果a1=S1且a2=S2,则a1≥a2当且仅当S1→S2。
根据命题1和定义3,如果有向超边e的头结点β为形如A⊆C(其中,A为概念名)的EL简单概念包含(Primitive Concept Conclusion,PCC)公理,则|S⊥(β)|=1,满足定义3的条件(2)的尾结点集T(e)最多包含一个公理,即|T(e)|≤1。更进一步,假如EL本体O只含有PCC公理,则其所对应的有向超图HO演化为常见的简单有向图——每一条边关联两个结点。
用有向超图表示EL本体之后,可以借助标准图算法来计算超图中的强连通分量及其依赖关系[27]。在创建本体的有向图模型的过程中,每条边的创建过程是独立的,因此,可采用并行算法来进一步优化。
5 混合的原子分解方法
在这一章中,联合传统的原子分解方法和有向超图模型对本体进行原分解。
5.1 算法描述
混合原子分解的基本思路是:首先从原本体O中分离出EL子本体OEL,构造OEL对应的有向超图HEL,从而得到该EL子本体的原子分解A⊥(OEL),然后利用递增式原子分解方法[17],将剩余非EL公理添加到部分分解A⊥(OEL)中,得到本体的全部分解A⊥(O)。算法2描述该混合原子分解方法的过程。算法2的第一部分(3行~6行)计算EL子本体的原子分解A⊥(OEL)。第二部分(7行~12行)添加剩余的非EL公理。由于局部性模块抽取过程的单调性,新公理的加入不会导致旧原子的分裂,但是会造成旧原子的合并,同时引起原子间依赖关系的变化[17]。因此,在添加非EL公理α的时候,首先从部分分解A⊥(OEL)中选取因添加公理而受到影响的原子AFF(O,α)(第9行),重新计算这部分原子(11行),然后再把重新分解的结果合并到原分解图中(12行)。算法2使用文献[17]中的两个算法作为子程序(9行、12行)。如果本体规模为n,其中EL公理数目为m,最坏情况下,算法2的计算复杂度为O((n-m)4)。
在基于语法局部性的模块抽取过程中,抽取的模块与公理的选择顺序无关[11]。本体原子分解的结果只受原子类型(Τ、⊥、Τ⊥*)影响,与分解原子时公理的选择顺序无关。一旦原子类型确定,本体O的原子分解唯一地对应于一个Hasse有向图[15]。在混合式原子分解方法中,首先选择EL公理创建原子,然后选择剩余的公理创建原子。因此,算法2是正确的。
5.2 算法实现与实验
使用 Java语言和OWL API(http://owlapi.sourceforge.net/),实现了算法2。为了能够直接使用标准的线性复杂度算法来计算强连通分量,只把EL本体中的PCC公理表示表示为有向超图。因此,对算法2的实现进行细微的修改:OEL只包含形如A⊆C的公理,Onon-EL包含形如A≡C的EL公理和所有的非EL公理。对于EL本体的有向超图表示和强连通分量的计算(算法2的第5和第6行),可采用Java的多线程机制实现并行处理,在实验中,使用4个线程。
所用的测试数据集均来源于国家医学生物本体中心(NCBO)的本体库BioPortal(http://bioportal.bioontology.org)。实验数据集包括10个本体,表1给出了这些本体的基本信息,包括本体名称、规模、EL公理数及其百分比、PCC公理数及其百分比,其中本体规模指的是逻辑公理的数目。实验环境为台式计算机(CPU为Intel XeonE5620 2.40 GHz,16核,32 GB内存,操作系统为WindowsServer2008R2Enterprise)。 Java版 本 为JDK1.7.0_09,设置参数XX:+AggressiveHeap,使得程序运行时可利用最大的物理内存。
表1 测试本体
实验结果如表2所示,其中第二列表示传统的原子分解算法消耗的时间,第三列为利用有向超图分解PCC公理的时间,第四列为添加剩余公理的时间,第五列为第三列和第四列之和,表示混合原子分解方法消耗的总时间,第六列为加速比(第二列和第五列的比值)。表中所有的测试结果数据均为5次试验的平均值,时间单位为毫秒。
表2 原子分解时间比较
5.3 实验结果分析
表2的统计数据表明,对于所用的数据集,混合的原子分解比传统的方法具有更高的效率。最大加速比达到18.05(EDAM),最小加速比为1.43(ICNP),效率平均提高6.7倍。下面对实验结果作进一步分析。
表2显示,除了ICNP和Dermlex,其余8个本体的原子分解加速比都在3倍以上。这进一步证实了前面的算法分析:在传统的原子分解算法中,时间开销主要分为两部分。一是创建本体原子的时间,假设本体的规模为n,计算本体原子的时间复杂度为O(n4);二是计算原子依赖关系的时间,如果本体原子的数目为m,计算原子依赖关系的时间开销为O(m2)。在实际的本体分解中,一个本体原子往往含有若干条公理,因此,计算原子的时间开销比计算原子关系的时间开销大得多。在混合的原子分解方法中,假设本体规模为x,将本体映射为有向超图的时间开销为O(x2),如果有向图的顶点数为n,边数目为e,从本体的有向超图模型中计算原子分解的时间开销为O(n+e)。在本体中大部分公理属于EL类型的情况下,计算量较大的原子分解工作由高效的有图计算模型完成,只有少数公理由低效的传统方法添加到部分分解中,如EDAM。而且,本体的有向超图表示过程和强连通分量的计算过程都可以并行化,进一步优化了算法。本体ICNP和Dermlex中含有较少的简单概念包含公理(分别为14.67%和24.96%),不能体现出基于有向超图的原子分解算法的优势。其余本体中含有的简单概念包含公理都超过50%,因此混合分解算法的加速效果更为明显。
影响添加剩余非PCC公理的因素主要为两个方面:首先是需要添加的公理数目。理论上,需要添加的新公理越多,消耗时间越多,例如本体ICNP和Dermlex。这一点已在上面段落中得到解释。其次是因为添加新的公理而受到影响的原子数量。添加公理过程中受影响的原子数目越多,需要重新计算新的原子和依赖关系消耗时间随之增多。最理想的情况是,在部分分解的基础上添加新的公理不会导致原子数目的变化,即新添加公理只会加入到已有原子中,既不会形成新的原子,也不会导致原有原子的合并,因此不再产生新的依赖关系。对于本体Hupson和ERO,尽管需要添加的新公理较少,分别为16.92%和11.22%,但加速比并不是成比例地提高,一种可能的解释是,新添加公理影响到更多已分解原子。之前的研究工作[18-19]中的部分实验正好验证了这个猜测:本体Hupson和ERO中,分别有87.99% 和89.88%的EL公理依赖于非EL模块。与之相比,体NCI和Protein分别有86.36%和94.17% 的EL公理在逻辑上属于独立的逻辑模块,新增加的公理不会影响这部分公理的原子。因此,尽管体NCI和Protein中的PCC百分数比Hupson和ERO小得多,但其原子分解加速比还是较为明显。
6 结论
本文联合本体的有向超图模型和基于局部性模块的传统方法对强表达力本体进行原子分解。在该混合的方法中,大部分负载分配给高效的有向超图计算模型,效率较低的传统方法只负责小部分计算工作。通过对生物医学本体的实证评估,本文提出混合方法比传统的方法具有较高的效率。
从两个方面进行后续的研究工作。首先,在EL本体的有向超图模型中,超边的数量较大,最坏情况为指数级[23],然而,大部分的边在计算原子分解时并不需要。如何去掉冗余的边,优化有向超图模型,是需要进一步研究的工作。其次,在实验中,为了直接使用现存有向图的算法,除去了形如“A≡C”的公理,如何调整修改现存论算法以便适用于所有的EL公理是一个值得研究的问题。
[1]Motik B,Patel-Schneider P F,Parsia B.OWL 2 Web ontology language structural specif i cation and functional-style syntax[J].W3C Recommendation,2009,27(65).
[2]Golbreich C,Zhang S,Bodenreider O.The foundational model of anatomy in OWL:Experience and perspectives[J].Journal of Web Semantics,2006,4(3):181-195.
[3]Rector A,Rogers J.Ontological and practical issues in using a description logic to represent medical concept systems:Experience from GALEN[C]//Proceedings of Reasoning Web,2006,4126:197-231.
[4]Soergel D,Lauser B,Liang A,et al.Reengineering thesauri for new applications:The agrovoc example[J].Journal of Digital Information,2006,4(4).
[5]Derriere S,Richard A,Preite-Martinez A.An ontology of astronomical object types for the virtual observatory[C]//Proceedings of the 26th Meeting of the IAU,2006,2(14):603-603.
[6]Lacy L,Aviles G,Fraser K,et al.Experiences using OWL in military applications[C]//Proceedings of the OWL:Experiences and Directions Workshop,2005,188.
[7]Goodwin J.Experiences of using OWL at the ordnance survey[C]//Proceedings of the OWL:Experiences and Directions Workshop,2005,188.
[8]Lécué F,Schumann A,Sbodio M L.Applying semantic Web technologies for diagnosing road traffic congestions[C]//Proceedings of ISWC,2012,7650:114-130.
[9]Lécué F,Tucker R,Bicer V,et al.Predicting severity of road traffic congestion using semantic Web technologies[C]//Proceedings of the 11th ESWC,2014.
[10]Matentzoglu N,Bail S,Parsia B.A snapshot of the OWL Web[C]//Proceedings of ISWC,2013.
[11]Cuenca Grau B,Horrocks I,Kazakov Y,et al.Modular reuse of ontologies:Theory and practice[J].Journal of Artificial Intelligence Research,2008,31:273-318.
[12]Stuckenschmidt H,Parent C,Spaccapietra S.Modular ontologies:Concepts,Theories and Techniques for Knowledge Modularization[Z].2009.
[13]Sattler U,Schneider T,Zakharyaschev M.Which kind of module should I extract?[C]//Proceedings of Decription logic Workshop,2009,477.
[14]Del Vescovo C,Klinov P,Parsia B,et al.Empirical study of logic-based modules:Cheap is cheerful[C]//Proceedings of International Semantic Web Conference,2013.
[15]Del Vescovo C,Parsia B,Sattler U,et al.The modular structure of an ontology:Atomic decomposition[C]//Proceedings of IJCAI,2011:2232-2237.
[16]Del Vescovo C,Gessler D,Klinov P,et al.Atomic decomposition and modular structure of bioportal ontologies[C]//Proceedings of ISWC,2011:130-145.
[17]Klinov P,Del Vescovo C,Schneider T.Incrementally updateable and persistent decomposition of OWL ontologies[C]//Proceedings of the OWL:Experiences and Directions Workshop,2012.
[18]Wang Changlong,Feng Zhiyong.A novel combination of reasoners for ontology classification[C]//Proceedings of the ICTAI,2013.
[19]Wang Changlong,Feng Zhiyong,Wang Xin,et al.ComRs:a novel combination of reasoners for ontology classification[C]//Biomedical Research International,2015,3.
[20]Horridge M,Mortensen J M,Parsia B,et al.A study on the atomic decomposition of ontologies[C]//Proceedings of ISWC,2014:65-80.
[21]Mart´ın-Recuerda F,Walther D.Towards fast atomic decomposition using axiom dependency hypergraphs[C]//Proceedings of Workshop on Modular Ontologies,2013:61-72.
[22]Suntisrivaraporn B.Polynomial time reasoning support for design and maintenance of large-scale biomedical ontologies[D].TU Dresden,Germany,2009.
[23]Walther F D.Fast modularisation and atomic decomposition ofontologiesusing axiom dependency hypergraphs[C]//Proceedings of ISWC,2014:49-64.
[24]Tarjan R E.Depth-first search and linear graph algorithms[J].SIAM Journal on Computing,1972,1(2):146-160.
[25]Sharir M.A strong connectivity algorithm and its applications to data flow analysis[J].Computers& Mathematics with Applications,1981,7(1):67-72.
[26]Horrocks I.Implementation and optimisation techniques[M]//The Description Logic Handbook:Theory,Implementation,and Applications,2003:306-346.
[27]Cuenca Grau B,Horrocks I,Motik B,et al.Owl 2:The next step for OWL[J].Journal of Web Semantics,2008,6(4):309-322.
[28]Baader F,Brandt S,Lutz C.Pushing the EL envelope[C]//Proceedings of IJCAI,2005,5:364-369.
[29]Tsarkov D.Improved algorithms for module extraction and atomic decomposition[C]//Proceedings of Description Logic Workshop,2012.