基于分块的本体索引

时间:2022-10-04 04:49:33

摘 要本体数量和规模的增大导致本体存储和访问成为制约本体应用的瓶颈。我们基于本体中类与类之间的关系,将本体图转换为本体类超图,通过对超图的划分得到分块,进行聚簇存储。实验证明这种切分方法对范围查询具有比较明显的效率提升。

【关键词】大规模本体 分块 索引 Porac

1 介绍

随着人们对本体的需求逐渐广泛,人们在本体构建中投入了更多的精力。因而,本体数量和本体规模这两个指标也有大幅度增长。这导致了许多新问题的出现。在本体规模小的时候,人们可以将它读到内存操作。而当本体规模增大后,人们无法将其一次性读入内存,需要借助外存设备存放它的结构信息,以便查询和更新。因此,人们开始研究本体在外存中的组织方式。本体由概念库(TBox)和事实库(ABox)两部分组成,概念库中存放概念-概念关系、属性-属性关系和概念-属性关系,事实库中存放实例-实例关系。关系由主语-谓词-宾语结构的三元组表示,于是本体就是三元组的集合。这类研究的着眼点就在于把三元组存放到关系数据库。

关系数据库的存储基础是表。把三元组存储到关系数据库可以说成设计系统的表模式,从而把三元组存放到对应的表中。如果把所有的三元组都存在一张表,会导致这张表太大(现有的一些本体可以达到百万条三元组)。本体查询的时候,对该表作多次自连接会导致系统效率降低。为了提高系统效率,研究人员开始考虑对这张大表作切分,把数据存放到小表。从数据切分的角度讲,不外乎垂直切分和水平切分两类。由于三元组只有三个字段,没有太大的余地进行垂直切分,所以研究的重点在水平切分。水平切分能保持三元组的结构,并把相同类型的三元组放到同一张表。

大量研究本体存储模式的工作只完成对TBox的切分,对ABox的切分没有作深入研究。随着本体研究的发展,大规模本体不断涌现。本体的规模越大,TBox数据所占的比重越小。一般而言,TBox数据所占比重基本不超过10%。因此,对ABox切分应该成为人们关注的热点。

最简单的ABox切分方法就是根据三元组属性将三元组分配到对应表。这种方法没考虑到三元组间的关联,对本体查询效率提升的帮助有限。而且,按属性切分方法的管理和使用不便,每创建和删除一个属性都要更改表结构,会增大系统管理的压力。而且,这种方法会导致关联密切的三元组散布在不同表,增加查询的负载。比如,描述个人邮箱、个人地址、个人简历的信息有密切关联,用户在查询时可能一起用到。如果根据属性切分会导致这些数据分布在不同表,导致查询时IO数量增加。

为解决这些问题,我们提出一个算法Porac(Partitioned on Relations Among Classes)。它基于类与类之间的联系在ABox中建立分块聚簇索引。我们先根据ABox中三元组主语所属类的关系将三元组集合划分成块,然后根据分块号建立聚簇索引,重新组织数据,以提高查询性能。

2 相关工作

我们最初对本体管理的研究侧重于在集中环境下存储OWL格式的本体,并探索如何将本体中的隐含信息物化存储于数据库中。随着语义Web应用的增加,本体的管理日益成为研究人员关注的热点。因此,应用的普及推动人们在本体存储和管理方面的研究不断深入。以下,我们将主要从两个方面(本体存储和本体查询语言)讨论本体存储和管理研究的进展。

对本体存储的研究仍然集中在对本体集中存储方面的研究。这方面的大部分工作集中在将本体存储在关系数据库中。根据是否做推理,又可将这类本体存储系统分两类,基于描述逻辑和基于规则。前者有InstanceStore、OWLIM、Minerva等。在InstanceStore中,数据库用于存储和检索,描述逻辑推理算法将隐含信息显性化,使用检查知识库一致性的算法对查询提供支持;OWLIM使用OWL描述逻辑程序知识库的推理闭包将RDF数据库的内涵信息物化存储;Minerva把描述逻辑转化成逻辑程序,然后预先计算TBox的包含关系,系统使用bottom-up的推理策略支持用户对ABox查询。

后者有DL-Lite、KAON2等,这类系统的特征是:先把描述逻辑构建符转变为规则;而后对查询采用前向链和后向链的策略进行处理。KAON2把描述逻辑知识库约简到一个析取的Datalog程序;DL-Lite把查询转变成合取的SQL查询的集合,交由SQL引擎处理,把推理复杂度降低到多项式复杂度。

文献采用另一种方式降低推理复杂度。作者通过观察发现相似实例总用同样方式关联其他实例,抽取出摘要的ABox--A’。接着,使用过滤算法在A’中形成分块,生成A’的简化版,使得在A’分块上推理的结果与A上推理的结果等价,提高查询的效率。其想法与我们有相似之处,不过存在一个问题。即它只在95%以上的分块中只有一个实例的情形下有效,导致分块过多。本文拟通过针对所属类进行分块避免该问题。

尽管本体集中存储的研究在如火如荼地进行,本体分散存储的研究也一直有人关注。RDFPeers是一个支持P2P的RDF存储系统。它提出了一个本体分散存储的策略。当一个RDF元组插入到系统中,系统根据它的主语、宾语和谓词,使用一个全局共知的hash算法为该元组生成三个副本,存储在三个地方。而文献提出了两个算法QC和SBV扩展了RDFPeers对合取查询的支持。

而对本体查询语言的研究分两个方面。一方面是从描述逻辑的角度讨论如何扩展SPARQL以支持OWL数据,另一方面是完善SPARQL以支持用户灵活的查询要求。前一方面如:文献提出了一个基于SPARQL且支持OWL-DL特性的查询语言SPARQL-DL。后一方面的发展有文献提出来的基于用户优先度的SPARQL和文献提出的SPARQ2L语言。前者增加对查询结果优先度的描述,使得系统能把优先度高的结果排在前面。后者在扩展SPARQL使之支持用户查询两个对象之间是否存在某种直接或间接关系。

以上工作说明研究人员面临两个问题,一是降低因本体逻辑复杂性而产生的低效查询问题,二是利用本体内容的复杂性拓展对本体的使用。我们在CODERS基础上进行的分块存储本体的研究恰好契合了本体管理的发展方向。

3 Porac算法

3.1 基础

从文献的工作及自身的研究中,我们发现本体中实例与实例之间的关联较少。如果仅依靠实例的关系进行分块,会导致最终的分块数量较大,无法对ABox进行有效切分。因为,实例与实例的关系是通过类与类的关系相关联,我们改为根据实例所属类进行切分。

定义1(本体图).一个本体O可以被视为一张图G=(V,E,L,label),V是顶点的集合(主语或宾语),E是边的集合(谓词),L是标记的集合,label:(V,E)标记,label是一个标记函数,把节点和边映射到对应类和属性的名字。投影函数source:EV,target:EV返回边的源节点和目的节点。

定义2(本体类超图).一个本体类超图可以被视为G’=(V’,E’,L’,label’),V’是顶点的集合(类),E’是边的集合(谓词),L’是标记的集合,label’:E’标记,label’是一个标记函数,对节点和边作标记。

定义3(主语到类的映射).class:主语类,

(1)如果a是实例,class(a)=a的直属类,a的直属类指本体中显式声明的a所属类

(2)如果a是类,class(a)=a

定义4(本体图映射到本体类超图).f:GG’。

(1)如果v1∈V,v2∈V,且class(label(v1))=class(label(v2)),

那么f(v1)= f(v2)∈V’;

(2)如果e1∈E,e2∈E,

class(label(source(e1)))=class(label(source(e2))),

class(label(target(e1)))=class(label(target(e2))),

label(e1) = label(e2),

那么f(e1)=f(e2)∈E’;

(3)如果l1∈L,l2∈L,且l1=l2,那么f(l1)=f(l2)∈ L’

三元组可视为一条从主语(起始节点)指向宾语(终端节点)的边,属性即边的标记。属于相同类主语的对应节点视为节点集合v’,通过一个映射函数f,把节点映射到节点集合,把节点发出的边映射为从节点集发出的边。然后将节点集一一映射为超节点,将一个超节点发出的指向其他超节点的标记相同边映射为超边,映射过程使用定义4函数f。得到一张超节点与超节点关系的超图G’,称为本体类超图。如图1所示,左边是一个本体图的例子,右边是对应的本体类超图。

3.2 算法介绍

定义5(本体类超图G’中与节点相关联的三元组)

假定三元组t1=,节点v1’是本体类超图G’中的一个节点,如果class(subj)=l’(v1’),那么t1关联到v1’,我们记作R(t1)=v1’。

定义6(本体类超图G’中节点的关联三元组)

本体类超图G’中,节点v’的关联三元组记为tup(v’)={t|R(t)=v’,t是三元组}

Porac算法的目的是根据节点和节点的相关度将三元组集合划分成多个分块。在此基础上,使得每个分块中的三元组数量尽量接近,避免分块大小的不均衡导致查询效率的不稳定。Porac是一个基于出度和三元组个数的多层次分块算法。该算法基于定义6计算G’中每个节点关联三元组的平均数Avg。然后,取出n个出度最大的节点作中心节点,根据节点的出边做深度优先遍历,所有遍历到的节点都属于中心节点所在的分块。然后对中心节点所在分块进行层次划分。由于类图是一个弱连通图,从中心节点出发无法遍历到所有节点。因此,假定对分块A完成切分后,可能有一些孤立节点存在,Porac算法会把这些孤立节点归到分块A中。这样就得到了基于类的三元组分块

定义7(分块树)

当对一个分块P进行切分后,会产生一堆更细的分块p1、p2、…pn。P称为p1、p2…、pn的父分块。分块与父分块之间的联系形成了一棵树,我们称之为分块树。根据树的定义,我们就可以得到兄弟分块、分块树层次的定义。

在每个未完成分块中选取中心节点,做进一步的划分,直到未完成分块中不存在关联三元组大于Avg的节点或当前层次等于用户指定的分块树的高度。具体的算法图2所示。这个算法是一个递归执行的算法,每次对一个分块作切分。每当对一个分块作切分时,这个分块就增加一层。Porac的输入参数G’是类图、pid是待切分的分块号、level是该分块的层数、height是分块树的总高度、avg是类图G’中每个节点关联三元组的平均数。

在执行Porac之前,我们先把所有的节点都放在分块0当中,并计算类图G’中节点关联三元组平均数Avg,height是用户指定的分块树高度。分块的中心节点独自为一个分块,其他节点的组合形成它的兄弟分块。如果当前分块中,三元组的总数小于预先计算好的节点关联三元组平均数,或当前分块的层数等于用户指定的分块树高度,那么不对当前分块作进一步的切分。

以下我们讨论一些Porac算法中参数的选定。根据六度空间理论,我们强制分块树的最大高度为4。算法第4行的作用是计算当前分块中三元组的数量,算法中的partition返回节点所在分块的块号。第7行getCentersInPartition返回指定分块的中心节点,我们将在下一段介绍该函数依据的思想。由于在选取中心节点的时候,我们只选择关联三元组数目多于Avg的节点,为了尽量保证分块规模相当,我们让中心节点处于一个单独的分块。第10行curPid++的作用就是把中心节点的分块和该中心节点遍历到的其它节点的分块区分开来。第12行到第18行作一个深度优先遍历,找到一个中心节点关联的所有节点。第18行是一个递归调用,对该中心节点关联的节点作分块。

每个分块中具体取几个中心节点是根据本分块的层次、分块中关联三元组数大于Avg的节点数量这两个参数决定的。在进行分块之前,我们期望每一层的分块数量是相同的,兄弟分块包含的子分块数是相等的。根据这个假设,如果类图中节点总数是N,用户规定的分块数高度是h,那么初始中心节点的数量是。但是,为使分块中三元组大小均衡,将关联三元组数量大于avg的节点放在单独分块中。在考虑选择中心节点时,以本分块中关联三元组数量大于avg的节点数M和之间的最小值作为本分块内中心节点的个数。

得到每条三元组与分块的对应关系后,可根据三元组的分块号为三元组建立一个分块号索引,然后利用Oracle中的分区技术将分块数据写入对应分区,形成基于分块号的聚簇索引。

4 实验

我们用一台配备CPU Pentium-D CPU 2*2.8G、1G内存和一块160G硬盘的Dell机器作为实验平台,使用Oracle9i存储本体数据,使用LUBM和WORDNET本体作为实验数据,测试与分块前相比,分块后的数据对于一些典型查询的效率的影响。对于LUBM和WordNet,使用提供的典型查询,并作了适当的修改,因篇幅问题,此处不赘述。

图3是对LUBM作测试的结果,为了测试类层次结构不变的情况下关联三元组的增加对分块算法的影响,我们使用不同的LUBM数据集。我们以LUBM(1,0)为基准(称为LUBM std比较结果如图3.B),分别把数据数据缩小为1/15(因为LUBM1由15个等大的OWL文件组成,称为LUBM min)和扩大15倍(即LUBM(15,0),我们称为LUBM max),比较的结果分别如图3.A和图3.C所示。LUBM min的三元组数量只有6000多条,LUBM std的三元组数据量是78000多条,LUBM max的三元组数量是120多万条。

由于三个LUBM的分块结构都相同,因此只反映每个分块数据量变化对分块结果的影响。所以,我们又用WordNet做了一个实验,希望能反映出不同分块结构对分块后查询效率的影响。图3.D是对WordNet作分块后的比较。

但是从结果看来,仅有查询2、查询6和查询7效果明显一些,其它查询由于速度比较快,因此看不出效果。下面我们逐一对这几个查询进行分析。在A中查询2由于返回的数据量中等,因此表现出很好的效果;而在B中查询2返回的数据量增加到1万多条,因此分块与未分块的效果差不多;在LUBM max中查询2的执行时间过长,已不在考虑范围中。因此,我们从查询2可以明显感觉出分块的效果随着数据量的增加而变好,到达最高点后下降,与不分块的效果差不多。查询6在图3.B和图3.C的比较中体现了效率扩张的趋势,查询7在图3.B和图3.C的比较中体现了效率收敛的趋势。而图3.D中,查询2的效果比较好是因为Wordnet中的数据比LUBM中的数据要分散一些,返回的结果没有那么多。

5 总结和下一步工作

本文提出一种基于实例与类的从属关系,将本体图转换为本体类超图,而后进行分割的方法,我们发现通过这样的划分,将本体中相关联的数据组织在一起,可以提高本体的查询效率。

下一步我们将针对Porac算法作进一步的完善。从我们的实验中我们可以看出,这种分块索引的效率优势会随着查询结果集的增加遵循从低到高再降低的过程。因此,我们需要作进一步的探索,结合实例的分布情况进行索引,并计算统计信息以提高查询的效率,及根据统计信息减少本体数据的修改对分块索引的影响。

参考文献

[1]李曼.本体库管理系统研究.博士学位论文[D].中国人民大学,2006(04).

[2]Sean Bechhofer,Ian Horrocks,and Daniele Turi.The OWL Instance Store: System Description.In Proceedings of CADE-20,LNCS 3632,pages 177-181,2005.

[3]Atanas Kiryakov,Damyan Ognyanov,and Dimitar Manov.OWLIM:A Pragmatic Semantic Repository for OWL.In Proceeding of International Workshop on WISE,LNCS 3807,pages 182-192, 2005.

[4]Jian Zhou,Li Ma,Qiaoling Liu,Lei Zhang,Yong Yu,and Yue Pan.Minerva: A Scalable OWL Ontology Storage and Inference System.In Proceedings of Asia Semantic Web Conference,2006.

[5]Diego Calvanese,Giuseppe De Giacomo, Domenico Lembo,Maurizio Lenzerini, and Riccardo Rosati.DL-Lite: Tractable Description Logics for Ontologies.In Proc.of the 20th Nat. Conf.on Artificial Intelligence, pages 602-607,2005.

[6]Boris Motik and Ulrike Sattler. Practical DL Reasoning over Large ABoxes with KAON2. In Miki Hermann and Andrei Voronkov,editors,Proc. of the 13th Int.Conf.on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2006),volume 4246 of LNCS,pages 227-241,Phnom Penh,Cambodia,November 13-17 2006. Springer

[7]Achille Fokoue, Aaron Kershenbaum, Li Ma,Edith Schonberg,and Kavitha Srinivas.The Summary Abox:Cutting Ontologies Down to Size.In Proc of the 5th International Semantic Web Conference,2006

[8]Min Cai,Martin Frank,Baoshi Yan, and Robert MacGregor.A Subscribable Peer-to-Peer RDF Repository for Distributed Metadata Management. Journal of Web Semantics,2(2):109-130,December 2004.

[9]Erietta Liarou,Stratos Idreos, and Manolis Koubarakis.Evaluating Conjunctive Triple Pattern Queries over Large Structured Overlay Networks. In Proc of the 5th International Semantic Web Conference,2006.

[10]Evren Sirin and Bijan Parsia. SPARQL-DL:SPARQL Query for OWL-DL. In OWLED 2007.http:///files/pdf/sparqldl.pdf

[11]Wolf Siberski,Jeff Z.Pan,and Uwe Thaden. Querying the Semantic Web with Preferences.In Proc of the 5th International Semantic Web Conference,2006.

[12]Kemafor Anyanwu,Angela Maduko and Amit Sheth. SPARQ2L:Towards Support for Subgraph Extraction Queries in RDF Databases. In WWW 2007,May 8-12, 2007,Banff,Alberta,Canada.

[13]Y.Guo,Z.Pan,and J.Heflin,“LUBM: A Benchmark for OWL Knowledge Base Systems,”J.Web Semantics,vol.3, no. 2,pp.158-182,2005.

作者单位

厦门理工学院计算机与信息工程学院 福建省厦门市 361012

上一篇:浅析汉日拟态词之异同 下一篇:如何做好中小学语文教学的有效衔接