随着语义Web的不断发展，建立在资源描述框架(RDF)^[1]之上的Web本体描述语言(OWL)已被广泛地应用于各种领域的本体建模和推理^[2]。由于基于描述逻辑的OWL无法对一般形式的规则进行描述，W3C将OWL子语言OWL DL、OWL Lite与RuleML相结合，提出了具备更强逻辑表达能力的语义Web规则描述语言SWRL^[3]，但其推理不可判定^[4]。目前，业界还没有一个专用的SWRL规则推理引擎，研究人员主要使用protégé工具的SWRLTab插件将OWL本体映射入Jess事实库，将SWRL规则映射入Jess规则库，并调用Jess规则引擎对已知OWL个体进行可判定的SWRL规则推理^[5]。同时，Pellet和KAON2等本体推理引擎也提供了在DL-safe限制^[6]下的可判定SWRL推理支持。但随着OWL本体数据量的不断增长，上述单机环境下运行的推理引擎由于需要将本体数据和规则载入内存，在对大规模本体数据进行SWRL推理时，存在计算性能和可扩展性不足等问题^[7]。另外，在语义Web数据管理研究领域，传统关系型数据库作为本体数据存储载体被广泛应用，并主要采用基于三元组的策略对本体数据进行存储。虽然学术界相继提出了垂直存储、水平存储和模式生成等优化方案，但依然存在数据存储可扩展性不足和查询效率低等问题^[8]。

自2007年Google和IBM提出云计算概念以来，云计算因其具备高性能、可扩展的海量数据计算和存储能力已经成为产业界和学术界在信息技术领域的最新研究方向^[9]。目前，基于GFS分布式文件系统模型^[10]、MapReduce分布式计算模型^[11]和BigTable分布式数据库模型^[12]实现的开源Hadoop平台^[13]已成为云计算研究领域最广泛使用的数据密集型计算和存储模型^[14]。

近年来，为解决传统语义Web数据管理和推理工具在处理海量本体数据时存在的不足，学术界逐步形成了以语义Web和云计算研究领域相结合的新研究方向^[15]。文献[16]提出了一个云计算环境下的分布式SPARQL本体数据查询框架，并证明了在处理大规模RDF本体数据查询时，该框架在可扩展性和查询效率等方面均优于传统工具和方法。为实现高性能和可扩展的语义Web本体推理，文献[17]提出了基于MapReduce的分布式本体推理引擎WebPIE，实现了云计算环境下的RDF图闭包计算及OWL Horst推理。文献[18]提出了一个基于HBase的分布式语义Web数据管理框架，通过与MySQL集群数据库进行对比实验，证明了云计算环境下的语义Web数据管理方法在可扩展性和数据查询效率等方面优于传统关系型数据库存储模式。但到目前为止，在应对大规模语义Web本体数据的SWRL规则推理方面，业界仍然缺少一种高性能、易扩展的解决方案。

因此，以Hadoop平台为基础，研究并提出了云计算环境下的SWRL规则分布式推理框架CloudSWRL。首先描述了框架的功能模块架构，设计了OWL本体在HBase中的存储策略，然后阐述了CloudSWRL框架中相关术语和解析模型定义，并以此为基础，提出了基于MapReduce的推理计划生成算法和在DL-safe限制下SWRL规则分布式推理算法。最后，通过进行对比实验和可扩展性实验，证明了在处理大规模OWL本体数据的SWRL规则推理时，CloudSWRL框架在计算性能和可扩展性方面均优于传统推理引擎。

1 框架功能模块架构设计

CloudSWRL框架以开源Hadoop云计算平台为基础，设计了数据预处理模块、规则解析模块、数据存储模块、推理计划生成模块和分布式规则推理模块。其功能模块架构设计如图 1所示。

以用户输入的OWL本体数据和SWRL规则作为数据源，数据预处理模块首先调用Jena API^[19]将基于XML格式的本体文件转换为三元组格式的N-Triple文件，并将其以数据流的方式导入HDFS^[13]。然后，根据研究的OWL本体存储策略，数据存储模块将三元组格式的本体数据并行地存入HBase数据库。规则解析模块将SWRL规则转换为定义的SWRL规则解析模型，并以此为输入，计算生成推理计划模型。最后，分布式规则推理模块根据推理计划和SWRL分布式推理算法，在MapReduce中计算并输出推理结果。

2 基于HBase的OWL本体存储策略

作为BigTable模型的开源实现，HBase数据库以基于列的方式对数据进行分布式存储。HBase数据表使用行键(row key)对每行数据进行唯一性标识，并提供了类似B+树的高效索引。每个数据表中可定义多个列族(column family)，每个列族可由多个列(column)构成，并且列名及列数目可由程序动态任意指定^[20]。

在CloudSWRL框架中，OWL本体数据以三元组模式进行存储。根据SWRL推理规则的特点，框架将OWL个体断言集存储于数据表A_SP_O和A_PO_S中，将OWL术语集存储于表T_SP_O中，其存储模型如图 2和图 3所示。

T_SP_O表的行键由本体术语集三元组中的主语和谓语联合构成，对应的三元组的宾语值作为列名存储在列族中，以此减少数据存储空间。A_SP_O表与T_SP_O表具有相同的存储结构。A_PO_S表的行键由本体个体断言集三元组中谓语和宾语联合组成，所对应的主语以列名的形式存储。基于上述存储策略，通过结合HBase提供的Scan区域检索和Get数据检索机制，可实现本体数据的高效检索。

3 相关术语及解析模型

根据W3C对SWRL语言的定义^[3]，每条SWRL规则由规则前件(Body)和规则后件(Head)两部分组成。其中前件和后件均可由零或多个规则原子(Atom)的合取组成。SWRL规则的形式化描述如式(1)

$ ( \wedge _{i = 1}^nAto{m_i}) \to ( \wedge _{j = 1}^mAto{m_j}), $

(1)

其中n≥0，m≥0。规则原子可由C(x)、P(x, y)、sameAs(x, y)、differentFrom(x, y)或SWRL内置函数构成，其中x和y可为变量、OWL个体或数据常量，C代表OWL类描述，P表示OWL属性。在本体库Ω中，对规则原子C(x)，若有个体a为类C的实例，即C(a)成立，称a为C(x)的一个解释。同理，对规则原子P(x, y)，若有实例组(a, b)满足P(a, b)，称(a, b)为P(x, y)的一个解释。

为实现可判定的SWRL规则推理，CloudSWRL框架在DL-safe限制下对本体库中已知OWL个体和公理进行推理。目前，框架支持C(x)和P(x, y)类型的SWRL规则原子，并规定SWRL规则前件至少包含一个规则原子，规则后件中有且仅有一个规则原子。

由于SWRL规则原子与OWL类和属性存在一一对应关系，而基于RDF的OWL可用三元组形式描述，因此SWRL规则原子可用如表 1所示的映射关系表示为三元组形式，且具备相同的语义，其中?x和?y表示变量，a和b表示OWL个体或常量。

表 2描述了框架在进行SWRL规则原子的本体数据检索时，各类规则原子对应的HBase数据表和检索命令。

基于如表 1所示的映射关系，给出SWRL规则及其规则原子在CloudSWRL框架中的解析模型。

定义1  SWRL规则原子Atom，可用如表 1所示的映射关系，将Atom解析为规则原子解析模型A=(A(s), A(p), A(o))，其中A(p)为OWL本体属性，A(s)和A(o)可为变量、OWL个体或常量。

定义2  任一SWRL规则可用规则解析模型R=(B, H)表示，其中B为前件规则原子解析模型集合B={A₁, …, A_n}，(n≥1)；H为后件规则原子解析模型集合H ={A’}。

根据SWRL规则语义，对于任一SWRL规则，其含义为：如果前件中的所有规则原子同时成立，则后件一定成立^[7]。即当在本体库中存在至少一个解释使得SWRL前件规则原子同时成立时，那么也存在至少一个解释使得SWRL后件规则原子成立。

定义3  对规则原子解析模型A，当A中仅存在一个变量v时，A在本体库Ω中的解释模型I(A)=(v, a)；当A存在变量v₁和v₂时，I(A)=((v₁, a), (v₂, b))。其中a, b为在本体库Ω中满足A中变量的OWL个体或常量，即A(a)或A(a, b)在Ω中成立。

定义4  规则解析模型R各规则原子解析模型存在变量v₁和v₂，若v₁同时存在于2个或多个规则原子解析模型A₁, …, A_n，(n≥2)，称v₁为A₁, …, A_n的共同变量；若v₂仅存在于一个规则原子解析模型A中，称v₂为非共同变量。

对SWRL规则原子解析模型A₁和A₂，在本体库Ω中，若A₁存在解释模型的集合U₁={I₁(A₁), …, I_j(A₁)}，(j≥1)，A₂存在解释模型的集合U₂={I₁(A₂), …, I_k(A₂)}，(k≥1)，当A₁和A₂存在共同变量v时，使得A₁和A₂同时成立的解释模型I(A₁, A₂)∈(U₁⋈_vU₂)，即对集合U₁和U₂进行以共同变量v为基准的连接操作；当A₁和A₂之间仅存在非共同变量时，I(A₁, A₂)∈(U₁×U₂)，即对集合U₁和U₂取笛卡尔集。因此，对规则解析模型R=(B, H)，B={A₁, …, A_n}，(n≥1)，H={A’}，前件规则原子解析模型集合B的解释模型I(B)∈({I(A₁)}…{I(A_j)}×{I(A_(j+1))}×…×{I(A_n)})，其中，A₁, …, A_j之间存在共同变量，A_(j+1), …, A_n中仅存在非共同变量。推理结果为H中规则原子解析模型A’变量对应的解释模型I(A’)∈{I(B)}。

由于MapReduce模型以键值对的形式对数据进行分布式计算，当规则中存在多个不同的共同变量时，SWRL推理需要由多个MapReduce任务(Job)组合完成。

定义5  推理计划模型L={job₁, …, job_n}，(n≥1)，其中job=(DS, {subjob₁, …, subjob_m})，(m≥1)，DS为标识符，当推理任务以HBase为数据源时，DS标识为D；当以HDFS为数据源时，DS标识为F。模型subjob=(Tag, {A₁, …, A_j})，(j≥1)，A为规则原子解析模型，Tag为标识符，当A₁, …, A_j中存在共同变量v时，Tag标识为v；当A₁, …, A_j中仅存在非共同变量时，Tag标识为Neg。

定义6  推理中间数据模型IKV为键值对，IKV= < (v, I[v]), ({A}, I({A}))>，其中v为变量名，I[v]为I({A})中变量v的值，I({A})为满足规则原子解析模型集合{A}的解释模型。

4 基于MapReduce的SWRL规则分布式推理算法

MapReduce编程模型中每个任务由在各个计算节点中运行的Map和Reduce函数组成。为尽可能减少任务数，提升推理效率，提出SWRL规则推理计划生成算法，并以此为基础，在提出MapReduce模型下的SWRL分布式推理算法。

4.1 推理计划生成算法

为实现云计算环境下基于SPARQL的本体数据分布式查询，文献[16]中给出对查询语句中变量v取E-count(v)值的定义，并基于贪心选择策略提出了查询计划的生成方法。笔者对该方法加以改进，提出一种针对SWRL规则的推理计划生成算法。该算法执行步骤如下

1) 输入SWRL规则解析模型R=(B, H)，B={A₁, …, A_n}，(n≥1)，H={A’}。计算B中共同变量cv₁, …, cv_i，(i≥0)，B中非共同变量nv₁, …, nv_j，(0≤j≤2n-i)。设集合CV、NV和U，对k=1, …, i，计算N_k←E-count(cv_k)，再执行CV←CV∪{ < cv_k, N_k>}。对l=1, …, j，执行NV←NV ∪{nv_l}。执行U←B。

2) 计算cl←length(CV)，cl为集合CV中元素个数。当cl=0时，执行步骤4；当cl≥1时，对CV按E-count值进行升序排列，但若存在 < cv_s, N_s>∈CV和 < cv_t, N_t>∈CV，使得cv_s≠cv_t，N_s=N_t，则计算cv_s和cv_t在B中出现次数T_s和T_t，若T_s>T_t，将 < cv_s, N_s>在CV中排序优先于 < cv_t, N_t>，若T_s=T_t，再计算cv_s和cv_t在A_p(s)出现次数S_s和S_t，(p=1, …, n)，如果S_s>S_t，则将 < cv_s, N_s>在CV中排序优先于 < cv_t, N_t>。

3) 设集合Temp，参数e←1。设job_e标识符DS为D。对x=1, …, cl，取cv_x∈CV，A_p∈U, …, A_(p+q)∈U，(p≥1, q≥1)，且满足cv_x∈A_p, …, cv_x∈A_(p+q)。再执行subjob_x ←(cv_x, {A_p, …, A_(p+q)})，x←x+1，U←U-{A_p, …, A_(p+q)}，对z = p, …, (p+q)，若A_z中存在除cv_x以外的共同变量v_z且v_z∉Temp，执行Temp←Temp∪{v_z}。最后，对生成的x个subjob模型，执行job_e←(DS, {subjob₁, …, subjob_x})，L←L∪{job_e}，e←e+1。

4) 设集合W，计算nl←length(NV)，nl为集合NV中元素个数，并设job_e标识符DS为D。对y=1, …, nl，取nv_y∈NV，A_y∈B，满足nv_y∈A_y，执行W←W ∪{A_y}，U←U-{A_y}，计算e←e+1。

5) 计算c←length(Temp)，c为集合Temp中元素个数。当c≥1时，对r=1, …, c，取v_r∈Temp，A_d∈B, …, A_(d+g)∈B，(d ≥1, g ≥1)，满足v_r∈A_d, …, v_r∈A_(d+g)。执行subjob_r←(v_r, {A_d, …, A_(d+g)})，对u = d, …, (d+g)，若A_u中存在除v_r以外的共同变量v_u且v_u∉Temp，执行Temp←Temp∪{v_u}，c←c+1。设job_e标识符DS为F，对生成的r个subjob模型，执行job_e←(DS, {subjob₁, …, subjob_r})，L←L∪ {job_e}，计算e←e+1。

6) 设job_e标识符DS为F，对A′∈H，执行subjob←(Neg, H)，job_e←(DS, {subjob})，L←L∪{job_e}。

4.2 基于MapReduce的SWRL规则分布式推理算法

以推理计划模型L和HBase中OWL本体数据为输入，分布式规则推理模块实现基于MapReduce的SWRL规则分布式推理算法。该算法由5个函数构成：Main、DB_Map、File_Map、Reduce和Result_Map。其中，在Hadoop平台的Master节点中运行的Main函数负责推理任务的生成和调度，运行于各个计算节点的DB_Map、File_Map、Reduce和Result_Map函数执行具体的推理计算。上述函数的算法描述如下

Main：输入推理计划模型L，执行

1) 对L中所有规则原子解析模型A，当A(p)为rdf:type时，对A(o)=C，从HBase数据库T_SP_O表中查询出以C为根的子类层次结构树T，并对T按深度优先策略排列为{C, C₁, …, C_h}，(h≥0)，设A₁=(A(s), A(p), C₁), …, A_h=(A(s), A(s), C_h)，执行A←{A, A₁, …, A_h}；当A(p)为OWL属性P时，从HBase数据库T_SP_O表中查询出以P为根的子属性层次结构树T’，并对T’按深度优先策略排列为{P, P₁, …, P_l}，(l ≥0)，设A₁=(A(s), P₁, A(o)), …, A_l=(A(s), P_l, A(o))，执行A←{A, A₁, …, A_l }。

2) 计算ln←length(L)，ln为L中模型job个数，设HDFS文件夹JoinOut、TempOut、和DcarIn，设分布式缓存DC。

3) 对i=1, …, (ln-1)，job_i∈L，执行DC←job_i，当job_i标识符DS为F时，设置File_Map数据源为TempOut，执行File_Map和Reduce函数；当job_i标识符DS为D时，计算sn←length(job_i)，sn为job_i中subjob个数，对j=1, …, sn，计算an←length(subjob_j)，an为subjob_j中规则原子解析模型个数，对x=1, …, an，A_x∈subjob_j，生成A_x对应的数据表Table_x及查询命令Comd_x，执行Q←Q∪{(Table_x, Comd_x)}。设DB_Map数据源为Q，当subjob_j的Tag值为任一共同变量时，执行DB_Map和DB_Reduce函数，当subjob_j的Tag值为Neg时，仅执行DB_Map函数。

4) 对i=ln，设Result_Map函数数据源为HDFS文件夹JoinOut和DcarIn，并执行Result_Map函数。

DB_Map：根据集合Q，检索得到规则原子解析模型在本体库中的解释数据集DL={data₁, …, data_n}，其中data为OWL个体或常量的a或二元组(a, b)，执行

1) 当n=0时，终止计算；当n≥1时，读取DC中job模型，对i=1, …, n，data_i∈DL，根据data_i对应的Table和Comd，取data_i在job中对应模型A_i和subjob_i，当data_i=a时，执行I_i (A_i) ←(v, a)，当data_i=(a, b)时，执行I_i (A_i) ←((v₁, a), (v₂, b))，当subjob_i标识符Tag为共同变量名v时，执行IKV_i← < (v, I_i[v]), (A_i, I_i (A_i))>，当subjob_i标识符Tag为Neg时，执行IKV_i← < (v, I_i (A_i)), (A_i, I_i (A_i))。

2) 对i=1, …, n，当subjob_i标识符Tag为共同变量名v时，将IKV_i传递给Reduce函数；当subjob_i标识符Tag为Neg时，将IKV_i输出到DcarIn文件夹中A_i.out文件。

File_Map：输入TempOut中IKV模型的集合KL={IKV₁, …, IKV_n}，执行

1) 若n≥1，读取DC中4模型，计算sl←length(job)，sl为job模型中subjob个数。

2) 对i=1, …, n，若IKV_i键中存在变量v∈subjob_k，(1≤k≤sl)，将IKV_i传递给Reduce函数。

Reduce：输入具有相同键的推理中间数据模型IKV₁, …, IKV_u，执行

1) 若u≥1，读取DC中模型job，根据IKV₁, …, IKV_u键中变量名v，取job中对应subjob模型，计算cnt←length(subjob)，cnt为subjob中规则原子解析模型个数，设集合E₁, …, E_cnt，分别用于存放A₁, …, A_cnt的解释模型。

2) 对i=1, …, u，取IKV_i中解释模型I({A_i})的变量v或(v₁, v₂)，当v或(v₁, v₂)∈A_j时，执行E_j←E_j∪{I({A_i})}，(1≤j≤cnt)。

3) 计算E₁⋈ E₂ ⋈… ⋈ E_cnt，得同时满足subjob中各规则原子解析模型的解释模型I₁(E₁, …, E_cnt), …, I_r(E₁, …, E_cnt)。当r=0时，终止运行Reduce函数；当r≥1时，对k=1, …, r，若I_k (E₁, …, E_count)中存在仍未进行连接操作的变量v_k，构造推理中间数据模型IKV_k= < (v_k, I(v_k)), ({A₁, …, A_cnt}, I_k(E₁, …, E_cnt))>，当job标识符DS为D时，输出IKV_k到TempOut；当job标识符DS为F且I_k (E₁, …, E_cnt)中不存在仍未进行连接操作的变量时，将I_k(E₁, …, E_cnt)输出到JoinOut。

Result_Map：输入JoinOut和DcarIn文件夹中解释模型，执行

1) 设集合Result，从JoinOut中读取解释模型集合JI={I₁, …, I_n}。从DcarIn各个文件中读取解释模型集合DI₁, …, DI_m，若n≥1且m≥1，计算>Result←JI×DI₁×…×DI_m；若m=0且n≥1，执行Result←JI；若n=0且m≥1，计算Result←DI₁×…×DI_m。

2) 读取DC中模型job，取job中后件规则原子解析模型A’。根据A’中变量，从Result解释模型中取得对应的变量值，得到推理结果I(A’)，并输出到HDFS文件ResultOut。

5 实验

由于目前没有专用于SWRL规则引擎性能测试的SWRL规则集和OWL本体数据集，采用被学术界广泛应用于本体推理和查询性能测试的LUBM本体数据集^[21]，并根据LUBM的术语本体，设计了如表 3所示的测试规则。为验证CloudSWRL框架的推理性能，进行了CloudSWRL与Jess和Pellet推理引擎的对比实验，以及通过递增计算节点来验证CloudSWRL框架可扩展性的实验。

5.1 对比实验

在对比实验中，使用LUBM工具分别了生成了如表 4所示的本体数据集。将Jess 71p2和Pellet 2.3.0推理引擎部署于配置为双核64位E7200 CPU，DDR2 6 GB内存，4TB硬盘存储空间，安装64位Windows操作系统的计算机之上，并为Java虚拟机分配5 GB内存空间。同时，将CloudSWRL框架及Hadoop 0.20.2平台Master节点部署于Pentium 4 CPU、1.5 GB内存、320 GB硬盘空间，并安装Ubuntu10.10操作系统计算机上，设置了8台分布式计算和HBase数据存储节点，每台节点配置为Pentium 4 CPU、1.5 GB内存和80 GB硬盘空间，分配Java虚拟机内存512 MB。Master节点及八台计算节点通过100 Mb/s的局域网互连。通过分析对比实验推理输出，对测试规则R₁和R₂，各测试推理工具均生成相同推理结果。统计由本体加载用时、规则加载用时、推理用时和输出用时组成的计算总用时，如表 5和表 6所示。

对比实验结果表明，在单机环境和分布式环境的硬件配置总体相当的前提下，当输入本体数据量较小时，基于Tableau算法的Pellet推理引擎具有较好的计算性能，而Jess规则引擎由于需要进行本体和规则的映射，在占用大量内存空间的同时推理性能与Jess和CloudSWRL存在差距。但随着输入本体数据量不断增加，CloudSWRL框架较Jess和Pellet推理引擎在处理大规模本体数据时，计算性能上存在明显优势。

5.2 框架可扩展性实验

可扩展性实验以1 GB的LUBM本体数据集及R₁和R₂测试规则作为输入，实验硬件环境与5.1节中对比实验相同。计算节点数分别设置为2、4、6和8台，其实验结果如图 4所示，其中横轴表示计算节点数，纵轴表示推理总用时，单位为S。

框架可扩展性实验结果表明，对相同输入数据，当云计算环境中计算节点数逐步递增时，框架具备更强的计算能力，推理用时逐步降低。即当需要处理海量本体输入数据时，可通过扩展计算节点数来获得更佳的推理性能。

综合对比实验和可扩展性实验结果，不难得出，CloudSWRL框架在对大规模本体数据进行SWRL规则推理时，在计算性能和可扩展性方面优于传统SWRL推理工具。

6 结论

由于传统单机环境下运行的SWRL推理工具在计算性能和扩展性等方面存在瓶颈，提出了云计算环境下的SWRL规则分布式推理框架CloudSWRL。以Hadoop平台的MapReduce编程模型和Hbase分布式数据库为基础，设计了OWL本体数据在HBase中的存储策略，定义了框架中相关解析模型，提出了基于MapReduce的推理计划生成算法和在DL-safe限制下SWRL规则分布式推理算法。对比实验和可扩展性实验结果表明，CloudSWRL框架较传统的Jess和Pellet推理引擎在处理大规模语义Web本体的SWRL规则推理时，具备更好的计算性能和可扩展性。

在后续研究工作中，除了进一步对CloudSWRL框架推理性能进行优化以外，还将引入SWRL规则sameAs、differentFrom和内置函数，以实现对更复杂SWRL规则推理的支持。