模糊RDF数据的一种查询语言扩展

赵羽晗，胡 磊

(南京航空航天大学 计算机科学与技术学院，江苏 南京 211100)

0 引 言

资源描述框架(RDF)是W3C推广的标准数据模型，用于表示Web上可用资源的有关信息。RDF遵循互操作性、可扩展性、演进和权力下放的W3C设计原则，应用于生物网络、社会网络、大型知识库等多个领域。因此，大量的RDF存储库已经被创建，并且一再被观察到，数据库社区面临着应对RDF细节的新挑战。然而，一些数据本质上是模糊的或不精确的，因为它们的值在现实应用中是主观的。需要模糊地表达或描述信息[1]。然而，从机器的角度来看，以这种方式呈现信息并不熟练。因此，研究数据模型和不精确或不确定性的具有不同策略的组合是重要的[2]。因此在文献[3]中，基于模糊集理论，提出了一项模糊RDF数据模型，用来表达信息中的不确定性。考虑了RDF图，其中数据是通过附加到边或节点的内在加权值来描述的，这个权重可以表示任何渐进的概念。

目前在语义网领域一直致力于RDF数据处理解决方案的开发，如存储、查询、维护等等，由于数据量巨大，数据的异质性、模糊性和广泛的连通性，对这些RDF图的各种查询的高效应答是最重要的问题之一[4]。作为RDF查询语言的官方W3C推荐标准SPARQL[5]，对于RDF数据模型起着与SQL在关系数据模型中相同的作用。它提供了基本的功能，以便通过图模式查询RDF数据[6-7]。但是传统的SPARQL缺乏一些表达性和可用性的功能，这在实际应用中是非常重要的。

在这些情形的驱动下，已经研究出了可以表达信息中丰富模糊性的模糊RDF数据模型[8]，应该定义新的更灵活的查询语言。目标是扩展SPARQL，以便支持灵活查询清晰和模糊的RDF图形数据库(当数据不精确时)。

该文提出了一种扩展SPARQL的模糊查询语言。该语言可以更有效地对模糊RDF数据进行查询，对传统的SPARQL图模式进行了模糊扩展，并将模糊量化语句集成到扩展后的模糊查询中，这使得资源中的模糊性在用户搜索过程中得到表达，使得结果更满足用户的需求。然后采用文献[9]中Yager基于OWA的解释来对查询进行评估，最后讨论了该查询的具体实现方法和流程。

1 模糊RDF模型

介绍了一种模糊RDF数据模型的形式化，这是基于模糊图[10]在模糊集理论中的特征定义的。

简而言之，模糊RDF数据模型的基本结构是一个图表。设V为有限的顶点集，E⊂Vi×Vj为一组边缘，L:V∪E→Σ为从顶点和边缘到称为标签的字符串集合Σ的映射。四元组GM=(V,E,Σ,L)是有向标记图。假设M是由(s,p,o)∈U∪B×U×U∪L∪B表示的一组RDF三元组。从M到GM的转换函数包括对每个(s,p,o)∈M的以下两个步骤：

(1)将顶点vs，vo加到V并分配L(vs)=s，L(vo)=o；

(2)向E中添加一个有向边(vs,vo)并分配L(vs,vo)=p。应该注意的是，图形结构仅简要描述了RDF数据模型的结构特征，忽略了RDF数据模型的顶点和边缘的模糊内容。下面是更详细的模糊RDF图形数据模型的正式定义。

定义1(模糊RDF数据图)：模糊RDF数据图G由六元组(V,E,Σ,L,μ,ρ)表示。这里

(1)V是一组有限的顶点；

(2)E⊂Vi×Vj是一组有向边，其中Vi,Vj⊂V；

(3)Σ是一组标签；

(4)L:V∪E→Σ分别为顶点和边缘分配标签的函数；

(5)μ:V→[0,1]是V的模糊子集；

(6)ρ:E→[0,1]是模糊子集μ的模糊关系。注意∀vi,vj∈V， ρ(vi,vj)≤μ(vi)∧μ(vj)，其中∧代表最小值。

在定义1中，图G的每个顶点vi∈V具有对应于RDF三元组数据集中的对象或客体的一个标签L(vi)。此外，vi,vj∈E是从顶点vi到顶点vj的有向边，边的标签L(vi,vj)对应于RDF三元组中的谓词。顶点的标签值与模糊度相关联，指示顶点取标签的可能性，并且与每个边缘相关联的模糊值表示顶点之间对应关系的不一致量。

模糊RDF数据图可以包含模糊顶点(相应的边)和清晰顶点(相应的边)，作为0或1度的模糊顶点(相应的边)可以被认为是清晰的。同样的，一般RDF图是最简单的模糊RDF数据图，其中μ:V→{0,1}，对于所有的vi∈V，且ρ:V×V→{0,1}，模糊RDF图是清晰RDF图的一般化。

此外，在此模型中，模糊RDF图的每个顶点和边缘与一个隶属度值相关联，即，三元组的每个元素都存在模糊值，如图1所示。

图1 模糊RDF三元组

2 SPARQL扩展

2.1 语义和语法

下面，介绍一种模糊的RDF查询语言，它使用模糊图模式扩展SPARQL图模式。

在语义上，扩展依赖于之前模糊RDF数据模型的相关定义。在语法上，扩展了经典的SPARQL，允许模糊图模式出现在WHERE子句中，而模糊条件出现在FILTER子句中。如SPARQL 1.1[11]中所定义，模糊正则表达式接近属性路径，并且它涉及模糊的结构属性(例如模糊图上的距离)。

首先，介绍一些关于模糊量词的重要概念。由于存在模糊量词，因此能够根据自然语言对量词进行建模。在文献[12]中，Zadeh将量词区分为绝对量词(例如五个以上)和相对量词(例如很多)。绝对量词指的是一个数字，而相对量词指的是一个比例。一个绝对量词由从整数或实数范围到[0，1]的μQ函数表示，而相对量词是从[0，1]到[0，1]的μQ映射。在这两种情况下，如果恰好X中的j个元素完全满足条件A，而X中的其他元素完全不满足A时，则将该值μQ(j)定义为语句“Q X are A”的真值。

现在，考虑在模糊RDF图数据库上使用类型为“Q B X are A”的模糊量化语句。其中，量词Q由模糊集合表达，该模糊集可以表示相对量词(例如很少)或绝对量词(例如超过五个)，B是连接到节点x的模糊状态，X是RDF图中的一组节点集，A表示模糊条件。这种语法的一个例子是：“很少有演员出生在休斯顿，他们出演的电影收视率高，票房低。”

下面给出模糊SPARQL语言中模糊量化查询的一般语法形式。

DEFINE ...

SELECT ?var

WHERE {

B(?var, ?X)

GROUP BY ?var

HAVING (Q(?X) ARE ( A(?X) )

}

DEFINE子句用于定义由Q表示的模糊量词和在模糊条件下的模糊形容词。SELECT子句确定应在解决方案集中返回哪些变量，以?var表示。B(?var, ?X)和A(?X)是SPARQL模式，使得变量?var和?X连接在B中，并且?X满足A。

例1：假设有一个查询旨在检索所有满足条件的导演(?person)，他所执导的许多具有较高利润的电影(?film)都受到高度关注，并且演员Jack极有可能参演了他的电影。可以使用模糊SPARQL表示如下：

DEFINEASC many AS (1,5)

DEFINEASC high gross AS (10,100)

DEFINEASC highly regarded AS (5,20)

DEFINEASC high probability AS (0,1)

SELECT ?person WHERE {

?film directBY ?person.

?film starring Jack.

FILTER (Jack IS high probability)}

GROUP BY ?person

HAVING many(?film) ARE

( ?film audience rating ?r.

?film box office ?b.

FILTER (?r IS highly regarded&& ?b IS high gross) )

其中DEFINEASC子句定义了递增的隶属函数(许多、高利润、高关注度和高概率)。如果存在任何递减的隶属函数，也可以使用DEFINEDSC子句。在此查询中，?person对应于?var，?film对应于?X，WHERE子句中的前三行对应于B，HAVING子句中的内容对应于A。

在定义了模糊SPARQL的量化查询语法之后，则需要对SPARQL图模式进行一定的扩展。标准SPARQL的图模式为若干个三元组组成的图形化表示，根据以上提出的模糊SPARQL语法，一个模糊SPARQL查询F(x)可以定义为(N,E,B(x,y),A(y),f(y))。

其中，N为模糊RDF图的顶点且x,y∈N，x即目标变量，y为查询中与x有关的节点；E为模糊RDF的有向边；B(x,y)和A(y)是两个为与x相关的顶点或边分配的函数映射，它们可以是常量、变量或者预定义的模糊隶属函数，一般在FILTER子句中表示；f(y)为模糊量词函数，附加于与x相关的顶点或边，在HAVING子句中表示。

由第一节可知，模糊RDF图模型的表示为GF=(N,E,Σ,L,μ)。联系模糊定量查询F(x)的定义，节点x和边e满足三元组模式(s,p,o)的对应，隶属函数B(x,y)的值由μx和μy(y由查询语句确定)计算得出，函数A(y)的值代入μy计算；f(y)则是对中间结果集的一个筛选，由分组后中间结果集的数量对模糊量词的满足程度来决定，按从高到低的结果排序。

2.2 评估策略

当尝试计算语句“Q X are A”的真实值时，必须确定满足A的X元素集的基数。如果A是布尔谓词，则该基数是精确整数k，并且“Q X are A”的真实值是μQ(k)。如果A是一个模糊谓词，则无法精确地建立基数，因此应该计算去建立一个不精确参数的函数值μQ所对应的量化。

现在从文献中介绍一种方法来解释“Q B X are A”形式的量化语句，该方法通过考虑量词适用的集合是模糊的来概括“Q X are A”的情况。在文献[9]中，Yager提出通过蕴含值μB(x)→KDμA(x)的OWA聚合来计算类型“Q B X are A”的语句的真实值，其中→KD代表Kleene-Dienes蕴含a→KDb=max(1-a,b)。

可以使用上述公式来解释模糊SPARQL查询的模糊量化语句。为了检索初始查询的B部分的元素，使之与需要计算最终满意程度的变量?var和?X匹配，应该将原始查询派生到下面给出的中间查询Finter中。对于每对(?var，?X)，检索计算μB和μA所需的所有信息，即与关系相关的模糊度和在B(?var，?x)和A(?X)中涉及的节点属性值的组合。分别由UB和UA表示。

SELECT ?var ?XUBUA

WHERE {

B(?var, ?X)

OPTIONAL {A(?X)}

}

通过简单的后处理步骤，可以根据UB和UA来计算满意度μB和μA。如果可选部分与给定的答案不匹配，则μA=0。为简单起见，我们接下来考虑Finter的结果是由与查询匹配的四元组(?var,?X,μB,μA)构成。

3 实现流程

本章讨论与所提出的方法有关的实施问题。必须考虑两个方面：(1)模糊RDF图的存储；(2)模糊SPARQL查询的评估。

第一点提出的问题比较容易解决，因为可以使用将模糊度附加到三元组的泛化机制。关于模糊SPARQL查询的评估，可以考虑两种体系结构。第一个解决方案是在数据管理系统内部实现一个特定的查询评估引擎。这个方案的优点是直接在查询引擎中实现的优化技术应该使得系统对查询处理非常高效。这个方案最大的局限性是，在分布式体系结构中对模糊SPARQL查询的评估意味着在每个SPARQL端点上都需要有可用的模糊SPARQL查询评估器，这在具体应用中是不现实的存在。

另一种更现实的架构是在一个标准的SPARQL引擎(端点)上增加一个模糊SPARQL软件层。这个层主要包含一个查询编译器，它产生一个用于检索适当数据的(清晰的)SPARQL查询，一个用于计算满意度的(依赖于查询的)函数和一个用于排序答案的(依赖于查询的)函数。

为了处理该查询，建议在标准的经典SPARQL引擎上使用软件附加层。该软件是SURF，在Jena语义网的Java框架内实现，用于创建和处理RDF图。SURF能够评估包含模糊量化语句的模糊SPARQL查询，在前面已经给出了模糊SPARQL的特定语法。它主要由两个模块组成。

(1)预处理模块，即查询编译器，它根据Yager基于OWA的方法，生成与查询相关的函数，通过这些函数能够计算并针对每个返回的答案。它还可以生成清晰的SPARQL查询，并将其发送到SPARQL查询引擎以检索计算和计算所需的信息。编译使用文献[13]中引入的推导原理。

(2)后处理模块，该模块首先对元素进行GROUP BY，然后计算，并为每个返回的答案进行排序，如果在初始模糊查询中已指定阈值，则对它们进行过滤。

这种体系结构如图2所示。

图2 SURF体系结构

对于“Q B X are A”类型的量化查询，原则是首先评估从原始查询导出的模糊查询Finter。对于来自Finter的结果的每个元组x，返回与条件A和B相关的满意度，分别由μB和μA表示。可以使用μB和μA的值根据定量查询评估公式计算最终满足度μ。目前，Yager基于OWA的方法[14]已经实施，并且要使用的解释的选择是通过系统的配置工具完成的。最后，得到一组按满意度降序排列的答案。

4 结束语

现实世界中存在着大量的不确定信息，因此RDF数据模型中模糊信息的表达是如今数据库方面重要的研究领域，而对这些模糊数据的有效查询是非常重要的一项工作。该文提出了一项针对SPARQL查询语言的扩展，这使得查询之前介绍的模糊RDF数据模型成为可能。通过模糊图模式扩展了标准SPARQL的图模式，在查询中融入模糊量词，给出了模糊SPARQL查询语言的语法和语义。还给出了针对模糊量化查询的一种评估策略，最后讨论了该查询的具体实现的方法和流程。

目前仍然处在对互联网中不确定信息处理的初级阶段。将来的工作有必要更深入地讨论模糊查询的精确性和全面性，以保证用户检索到的结果是符合需求的。此外，还要探索用其他方式或者在更复杂的条件下扩展查询语言，并对其进行更细致的评估，最终找到在实际应用中最有效的模糊信息处理方式。