一种基于RAL的RDF查询方案

摘 要:随着RDF的出现,其相应的查询语言也应运而生｡然而,这些语言都没有考虑RDF代数关系(RDF algebra,简称RAL),因此,这样的RDF查询语言通常没有使用APIs来描述它们的语义和优化问题,这对于RDF查询会导致一种低性能行为｡为此,为RDF查询语言和执行RDF查询优化提供一种RAL｡首先定义RAL的数据模型､然后呈现处理数据的运算和等价规则､最后描述应用RAL运算和等价规则来查询RDF的优化｡

关键词:资源描述框架(模式);资源描述框架(模式)查询语言;资源描述框架代数关系

中图分类号:TP311 文献标识码:A

1 引 言

近年来,随着语义web的出现,为了使其机器可理解,对元数据的描述和查询有很强的要求｡为此,W3C推出了RDF和RDFS｡RDF是一种基于XML的元数据描述框架,能定义概念之间的关系,描述易被机器理解的信息｡它提供的语义模型可用于描述Web上的任意资源及其类型,解决语义异构问题｡RDF模型虽网上资源赋予了基本的语义信息｡但RDF只定义了有限的基本的建模原语,它既没有给出定义新的属性词汇的机制,也没有给出定义这些属性以及资源之间新的关系的机制｡RDFS是RDF的扩展语言,它为RDF模型提供了类型系统支持,可以定义不同领域的核心词汇以及它们之间的关系,为领域知识的表达､交换和共享提供了语义支持｡虽然这二种语言为描述web元数据提供了一种标准规范,但查询RDF元数据的标准化语言仍是一个需解决的问题｡目前,研究组已研究出多种RDF查询语言(rdfDB､SeRQL､SPARQL等),这些语言在功能､形式等方面各具特点,为RDF元数据的查询提供了不同的方法｡但这些语言存在一个共同的缺点:没有考虑RDF代数关系,导致对RDF查询的性能较低｡为此,文中提出了RAL｡

2 数据模型

RDF模型的基本对象类型有:资源､属性和陈述｡有向标记图是RDF的基本数据模型｡其最基本的单位是陈述｡陈述是由主体､谓词､客体组成｡由此可见,现有的RDF数据模型缺乏代数关系的描述｡为此,下面使用代数关系来讨论RDF数据模型,描述RDF数据结构用RAL表示公式是如何被表达的｡

2.1 RDF 模型

设有集合:R(表示资源集合)､U(表示URIrefs集合)､B(表示空节点集合)､L(表示文字集合)､P(表示属性集合),在RDF层次中包含集合:R= U∪B,rdf∶Property∈U,P∈R,rdf∶type∈P,且U､B､L是两两相分离的｡

定义1一个RDF模型M是一个有限的三元组集合(也称陈述):MR×U×(R∪L)

定义2 一个RDF模型M的属性集合:P={p|(s,p,o)∈M∨(p,rdf∶type,rdf∶Property)∈M}

2.2 RDFS

RDFS通常把类组织为一种分级结构｡一个类是任何具有rdf∶type特性､并且该特性的值为rdfs∶Class的资源｡rdfs∶Class本身也是资源,而且也有一个rdf∶type特性,并且该特性的值为rdfs∶Class｡用类的集合C来扩展数据模型,使在RDFS层次结构中包含:CR,rdfs∶Resource∈C,rdfs∶Property∈C,rdfs∶Class∈C和rdfs∶Literal∈C｡

计算技术与自动化2007年6月第26卷第2期谢桂芳等:一种基于RAL的RDF查询方案定义3 一个RDF模型M的类集合是:C={c|(c,rdf∶type,rdfs∶Class)∈M}一个类可以是一个或多个类的子类｡RDFS规定:所有类是rdfs∶Resource的子类｡用户除了描述想要描述的类,还需定义刻画这些类的特性｡特性是用RDF类rdf∶Property以及RDFS特性rdfs∶domain､rdfs∶range和rdfs∶subPropertyOf来描述｡RDF中的所有特性都被描述为类rdf∶Property的实例｡因此一个新特性的描述是通过为它指派一个URIref,并使用一个值为rdf∶Property的rdf∶type特性来完成｡RDFS的rdfs∶range和rdfs∶domain特性用于进一步描述与应用相关的特性｡前者用于表明某个特性的值是给定类的实例或一个类型文字｡后者用于表明某个特性应用于指定的类｡当RDFS中这二个特性应用于某个RDF特性时,它们也会应用于该RDF特性的子特性｡RDFS提供了使用预定义的rdfs∶subPropertyOf特性来描述特性之间的特化关系的方法｡

2.3 完整模型

RDF语义学定义某一模型M的封闭式RDF和封闭式RDFS的方法是根据一个给定的推理法则的集合,在模型M中增加新的三元组｡称原始模型M为外延数据､最近产生的三元组为内涵数据｡封闭式RDF的推理法则为模型中的所有属性增加了rdf∶type属性｡ 封闭式RDFS的推理法则是rdfs∶subClassOf的传递性､rdfs∶subPropertyOf的传递性等｡应用这些推理法则的输出结果可能会触发其它的法则｡然而对于任何输入模型M,这些法则将会终止｡

定义4 如果一个RDF模型M包含封闭式RDF和封闭式RDFS,则它是完整模型｡

用完整模型作为文中被提议的数据模型,且忽略RDF具体化和rdfs:seeAlso,rdfs:isDefinedBy,rdfs:comment和rdfs:label的属性｡图1呈现了不同绘画技术的RDF模式和实例｡图2是从一定程度上对图1稍微做了修改后的RDF模式｡

3 RAL基本运算

在RAL运算的表达过程中,使用图1中的RDF数据作为运算的输入｡假设所有的运算都了解定义4所定义的RDF完整模型｡各种被提议的运算能使用后缀″^″被定义,后缀″^″将会使运算忽略内涵数据｡定义RDF集合是节点的集合｡所有RAL运算因为集合是封闭的,所以RAL表达式能容易地被组成｡又因RAL集合没有顺序性,故这样会使一些二进制运算能够交换｡与相关的代数关系相比,RAL表达更有力,其运算形式是:o[f](x1,x2,…xn∶expre-ssion)｡这形式表示,对于每一个绑定到输入集合的一个元组的x, f(x)会被计算｡一个元组是通过获取每个输入集合x1,x2,…xn被形成的｡f可能是一个使用基本属性或被文中提议的运算之一的函数｡基于运算o的语义,对于每一个绑定x,应用于o的局部结果的f(x)被计算｡运算结果通过组合所有局部结果被得到｡为了易读的原因,我们使用二元运算中缀符号｡RAL运算有以下三种:

3.1 提取运算

提取运算检索来自输入结点集合(RDF模型所需要)的资源/文字｡如果运算没有定义表示文字结点,则这些节点完全被忽略｡它包括投影运算π､选择运算σ､笛卡尔积运算×､连接运算∞､并运算∪､差运算-､交运算∩｡

3.2 循环运算

循环运算在RAL中被用来控制一个功能或运算的重复应用｡它包括映射运算map[f]和级联星运算*[f]｡

3.3 构造运算

构造运算通过创造节点/边和重复使用旧的节点(尽可能没有一些边)及旧的边来建立一个新模型｡它包括创建结点运算cnode､创建边运算cedge､删除结点运算dnode､删除边运算dedge｡

4 RAL等价规则

使用代数关系表达式查询的好处是能够以满足某种需要的形式来重写这表达式｡例如一个从RQL到RAL的自动翻译器能使用RAL等价规则为查询优化意图来重写代数表达式｡

RAL的等价规则是由单值规则和相关的代数关系的等价规则产生的｡因篇幅有限,在此只列举在文中所用到的5条规则,其它规则略｡

5 RDF查询

利用RAL运算和等价规则,可以对RDF查询进行优化｡启发式查询优化是尽可能地基于推进选择运算/投影运算和优先使用最有限制性的选择,这样查询优化就像在相关的代数关系上下文中被执行一样｡为了能较好地说明RAL对RDF查询的有效性,文中以图2来描述查询处理及优化过程｡假设对图2要查询依字母顺序返回使用"Chiaroscuro"技术的画家的国家｡则查询处理及优化过程如下:

首先查询语法分析器产生图3所示的初始查询树｡在所有的查询树里,a表示在输入中,在图2的模式内被分类的所有资源的集合｡

然后只要操作数是可用的,查询处理模块就会处理这棵查询树中的一个节点｡这个节点将会被由处理结点的相关表达式产生的集合所替换｡当处理根节点时,执行结束｡最后的查询结果是处理根节点时所得到的集合｡在例子中,在初始查询树的执行期间,会产生一个在所有画家､绘画和技术之间的大的笛卡尔积｡使用规则(1)､(2)和(3)来推进选择,就能得到图4所示的查询树｡

最后,应用规则(1)､(2)､(3)､(4)和(5),并优先应用最有限制性的选择,可以对查询更进一步的优化,查询结果树如图5所示:

6 定量分析

为了更好地说明图5的查询树是最优化的,进行如下分析:假设图2中的实例有5种绘画技术､100名画家､1000幅画｡所有的画中只有100幅是使用“Chiaroscuro"绘画技术｡对每一棵查询树,计算由笛卡尔积产生的元素的数目｡

第一棵查询树为:1001000+51001000=600000

第二棵查询树为:1001000+10001=101000

第三棵查询树为:11000+100100=11000

上述结果表明:最有效的查询执行是最后一棵查询树,因为它的笛卡尔积产生的元素的数目最少｡

7 结束语

RAL是一种被定义为用来支持RDF查询语言的正则规范的RDF代数关系｡它给出的一系列运算符在被正则定义的RDF查询语言的提取和构造部分被使用｡与现有的 RDF 查询语言相比较,它的构造阶段没有被疏忽而且是语言规范的一部份｡作者今后的工作是:用有关的已有RDF查询语言和RAL的完整性来分析RAL的表达力,并将它的表达力与其他代数关系的表达力相比较,从而为RAL 的表达力提供一些洞察语言的真实力量｡另外,作者今后将进一步研究查询优化规则｡

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。