（计算机软件与理论专业论文）rdf查询中非强制匹配问题研究.pdf

摘要 摘要 资源描述框架( r e s o u r c ed e s e r i p t i o nf r a m e w o r k , r d f ) 是描述w e b 资源的标准数据 模型。由于w e b 数据的半结构化特性，r d f 查询语言应该提供对半结构化数据的查询 机制。w 3 c 新近提出的s p a r q l 语言( 草案) 中的非强制匹配就是这种查询机制，本 文着重研究s p a r q l 中非强制匹配的查询处理技术。在分析s p a r q l 中非强制匹配的 语法和语义、总结现有非强制匹配查询处理方法及其不能处理多重和嵌套非强制匹配的 缺陷的基础上，本文提出一种实现非强制匹配查询的处理算法，该算法不仅支持简单非 强制匹配，而且支持多重非强制匹配和嵌套非强制匹配，以及复杂的多重嵌套非强制匹 配，并且从理论上分析该算法的时间复杂度。在算法设计与理论分析的基础上，本文设 计实现了支持非强制匹配查询的原型系统r o m q s ，用于用户提交s p a r q l 查询和所要 查询的r d f 图、执行查询、浏览查询结果。为进行实验验证，本文设计了大量不同规 模的包含不完全、不规则信息的r d f 图，并针对这些r d f 图设计了一组s p a r q l 非强 制匹配查询；通过将这些查询在r o m q s 中的执行结果与理论上的正确结果相比较，验 证了非强制匹配查询处理算法的有效性；基于大量的实验数据，分析了非强制匹配查询 处理算法的时间复杂度；将r o m q s 与其他r d f 查询系统进行比较，验证了r o m q s 具有能够处理多重和嵌套非强制匹配的功能优势。 关键词：非强制匹配；查询处理；多重非强制图模式；嵌套非强制图模式；r d f 查询 s p a r q l a b s t r a c t r e s o u r c ed e s e r i p t l o nf r a m e w o r ko f ) i sas t a n d a r dd a t am o d e lf o rd e s c r i b i n gw e b l e s o u r c e s s i n c ew e bd a t a 黜s e m i - s t r a c t u r e di nn a t u r e ) f i l lr d fq u e r yl a n g u a g es h o u l d p r o v i d eam e c h a n i s mf o rq u e r y i n gs e m i - s t r u c t u r e dd a t a t h eo p t i o n a lm a t c h i n gi ns l a r q l ( d r a f t ) w h i c hi sa l lr d fq u e r yl a n g u a g ea n dp r o p o s e db yw 3 cr e c e n t l yi sj u s ts u c haq u e r y m e c h a n i s m t h i sp a p e rl a y se m p h a s i so nt h eq u e r yp r o c e s s i n gt e c h n o l o g yf o ro p t i o n a l m a t c h i n gi ns p a r q l a f t e ra n a l y z i n gt h es y n t a xa n ds e m a n t i c so fs p a r q l so p t i o n a l m a t c h i n ga n ds u m m a r i z i n ge x i s t i n gq u e r yp r o c e s s i n gm e t h o df o ro p t i o n a lm a t c h i n ga n di t s d e f i c i e n c i e s , t h i sp a p e rp r o p o s e sl l nq u e r yp r o c e s s i n ga l g o r i t h mw h i c hs u p p o r t sn o to n l y s i m p l eo p t i o n a lm a t c h i n gb u ta l s om u l t i p l ea n dn e s t e do p t i o n a lm a t c h i n g , a sw e l l 勰c o m p l e x m u l t i p l en e s t e do p t i o n a lm a t c h i n g , a n da n a l y z e st i m ec o m p l e x i t yo ft h ea l g o r i t h mi nt h e o r y o nt h eb a s i so fa l g o r i t h md e s i g na n dt h e o r e t i ca n a l y s i s t h i sp a p e rd e s i g n sa n di m p l e m e n t s 觚 p r o t o t y p es y s t e mi 王o m q sf o ro p t i o n a lm a t c h i n gq u e r y , w h i c hs u p p o r t sf o ru s e r ss u b m i t t i n g o fs p a r q l q u e r i e sa n dr d fg r a p h st ob eq u e r i e d ，e x e c u t i n gq u e r i e s ，b r o w s i n gq u e r yr e s u l t s f o rc a r r y i n go u te x p e r i m e n t a lv a l i d a t i o n , m a n yr d fg r a p h sw i t hd i f f e r e n ts i z ew h i c hc o n t a i n i n c o m p l e t ea n di r r e g u l a ri n f o r m a t i o n1 t 1 ed e s i g n e d , a n dag r o u po fs a r q lo p t i o n a l m a t c h i n gq u e r i e sa l ea l s od e s i g n e da g a i n s tt h e s er d fg r a p h s t h r o u g hc o m p a r i n gr o m q s s e x e c u t i n gr e s u l t s w i t ht h e o r e t i c r i g h tr e s u l t s ，t h ev a l i d i t yo fo p t i o n a lm a t c h i n gq u e r y p r o c e s s i n ga l g o r i t h m i sv a l i d a t e d b a s e do n am a s so f e x p e r i m e n td a t a , l i m ec o m p l e x i t yo f t h e a l g o r i t h m i s a n a l y z e d t h r o u g hc o m p a r i n gr o m q sw i t ho t h e rr d fq u e r ys y s t e m s ， r o m q s sa d v a n t a g eo ff u n c t i o n a l i t y , t h a ti sb e i n ga b l et op r o c e s sm u l t i p l ea n dn e s t e d o p t i o n a lm a t c h i n g , i sv e i l f i e d k e yw o r d s ：o p t i o n a lm a t c h i n g ；q u e r yp r o c e s s i n g ；m u l t i p l eo p t i o n a lg r a p hp a t t e r n ；n e s t e d o p t i o n a lg r a p hp a t t e r n ；r d fq u e r y ；s l a r q l 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实， 本人负全部责任。 论文作者( ：j 舡7 叼年，月们 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光 盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。 论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ：互4 卑力哕年 歹 月心日 第一章绪论 1 1 研究背景 第一章绪论 经过十多年的迅速发展，今天的w e b 已成为一个庞大的，而且越来越大的信息仓 库。当前w e b 可以被称为第二代w e b ，第一代w e b 是手写的h t m l ( h y p e r t e x tm a r k u p l a n g u a g e ) 页，第二代w e b 的网页可以由机器生成，称之为动态网页。手写的h t m l 页和后来发展起来的动态网页都缺乏对内容语义的描述能力，计算机仅限于传送和表示 信息，并不能真正帮助人类处理信息。 w e b 创始人t m b e m e r s - l e e 首次于1 9 9 8 年提出了语义w e b ( s e m a n t i c w e b ) 的构 想【1 1 。t i mb e m e r s l e e 指出【2 j ：语义w e b 是当前w 曲的扩展，旨在将信息表示为计算机 能够理解和处理的形式，从而使人和机器可以更好地协同工作。作为下一代w e b ，语义 w e b 使w 曲上的信息具有计算机可以处理的语义，用以实现信息在语义层次的互操作 能力，从而使计算机和人类能够更好地协同工作。语义w e b 的基础结构如图1 - 1 所示。 其中，资源描述框架( r e s o u r c ed e s c r i p t i o nf r a m e w o r k ，r d f ) f 3 是w 3 c 提出的用于描 述w e b 资源元数据的标准模型和语言，它提供一个通用的框架来保证w e b 应用之间可 以无损地交换信息。 图1 1 语义w 曲基础结构 r d f 使用一种简单的数据模型来表示w e b 信息，并且它的形式语义为其提供了可 靠的推理基础。正是这些优点，使越来越多的应用使用r d f 来表示和集成信息。随着 r d f 在w e b 上的广泛应用，不仅标准的信息表示格式很重要，而且标准的信息访问方 式也变得越来越重要，而查询几乎是任何基于r d f 的应用都必需的基础功能【4 】。然而， r d f 标准发布到今天已经有几年时间，仍没有正式通过的r d f 查询语言标准。各学术 第一章绪论 机构、语义w e b 研究者和w 3 c 组织都正致力于r d f 查询语言标准的研究，不少组织 已经提出了自己的查询语言方案，例如r d q l t 那、r q l t 6 、s e r q l l 7 1 和t r i p l e t 8 1 等。 r d f 本质上是一个半结构化的数据模型，适合表示w e b 上不完全、不规则的信息。 因此，r d f 查询语言也应该提供相应的机制来处理半结构化数据的查询。然而，权威综 述与相关研耕9 】【l o 1 1 1 】【1 2 1 表明，现有的r d f 查询语言都普遍缺乏对某些r d f 本质特征的 支持，最典型的就是r d f 数据模型的半结构化特征。为了定义一种标准的r d f 查询语 言和r d f 数据访问协议，w 3 c 于2 0 0 4 年3 月成立了r d f 数据访问工作组，s p a r q l ” 是这个工作组新近发布的r d f 查询语言( 工作草案) 。与其他r d f 查询语言相比， s p a r q l 将重点集中在基本的图匹配问题和语言的使用技术上，s p a r q l 中的非强制匹 配或称为可选匹配( o p t i o n a lm a t c h i n g ) 是一种典型的半结构化数据的查询模式。 s p a r q l 语言的出现吸引了不少组织和机构，他们已经逐渐在自己的r d f 查询系 统中加入对s p a r q l 的支持，但很少有系统能够完全支持s p a r q l 中的所有查询模式。 对于非强制匹配，基于当前普遍采用的基于关系数据库的r d f 数据存储方案，已有的 查询处理方法是将非强制匹配操作转换为关系数据库上的左外连接操作【1 4 】【1 5 】【1 6 1 。这种 方法仅适合于简单非强制匹配，不能推广应用到多重或嵌套非强制匹配。对于复杂的非 强制匹配查询，至今还没有有效的算法公开发表。而对于其他的r d f 存储方案，至今 亦未见相应的非强制匹配查询处理方法提出。本文研究r d f 查询中的非强制匹配问题 有较大的理论与实际意义。 1 2 研究目标和内容 r d f 数据模型通常称为r d f 图( r d fg r a p h ) 1 3 j ，它是三元组( t r i p l e ) 的集合。s p a r q l 使用图模式( g r a p h p a t t e r n ) 来描述一个r d f 查询，查询求解的过程就是用图模式对r d f 图进行匹配的过程。在用传统的基本图模式( b a s i cg r a p hp a t t e r n ) 1 3 1 17 】对r d f 图进行查 询匹配时，查询的解是强制匹配此图模式所得的解，每个变量在解中都要绑定一个r d f 词汇( t e r m ) 。但由于w e b 数据的半结构化特征，不能假设所有r d f 图的结构都是完全 的、规则的，所以用传统的基本图模式进行查询匹配时经常会损失一些不完全的信息， 而这些信息往往是有价值的。 s p a r q l 中的非强制匹配查询是通过定义非强制图模式( o p t i o n a lg r a p hp a t t e r n ) 1 3 1 来实现的，非强制匹配的过程就是用非强制图模式匹配r d f 图的过程。它是这样一种 匹配方式( 即图模式) 1 3 】一一当r d f 图中的某些信息能被非强制图模式中的某个( 些) 部分( 即非强制部分) 。匹配时，就将这些信息加入到匹配强制部分所产生的解中，形成 最终解；但当非强制部分不能被匹配时，也不会影响整个查询解的产生【l3 1 。例如图1 2 中的s p a r q l 简单非强制匹配查询，按照非强制匹配查询的语义，它查询人的姓名( 强 第一章绪论 制匹配) ，与此同时如果有这个人的邮箱信息，就返回其邮箱，如果没有也会不影响其 姓名的返回( 非强制匹配) 。 图1 - 2 $ p a r q l 简单非强制匹配查询举例 由于一个非强制图模式可以有多个非强制部分( o p t i o n a l 部分) ，这样就会出现 多重非强制图模式；又由于非强制图模式的非强制部分本身也可以是一个非强制图模 式，这样就会出现嵌套非强制图模式。本文研究的问题就是s p a r q l 查询中各种类型非 强制图模式匹配的查询处理问题，具体研究基于r d f 关系数据库存储的非强制匹配查 询处理算法及其实现技术，主要研究内容包括： ( 1 ) 研究并总结现有的r d f 存储和查询技术，分析它们各自的优点和不足；研究现有公 开发布的支持非强制匹配的查询工具，分析它们对非强制匹配查询的支持程度和处 理方法，特别研究它们的处理方法能否扩展应用到多重和嵌套非强制匹配。 ( 2 ) 研究s p a r q l 中非强制匹配查询的语法和语义；在此基础上，提出( 多重、嵌套) 非强制图模式的树型表示( 模式树) 和查询处理算法，并从理论上分析算法的正确 性和时间复杂度。 ( 3 ) 设计并实现一个原型系统，用于实验验证所提出的非强制匹配查询处理算法的可实 现性和有效性，并实验验证算法的时间复杂度。 1 3 研究意义 r d f 图可以表示不完全、不规则的信息，一个资源拥有的信息，另一个资源不一定 有，或者信息的描述方式可能不同。传统描述查询的方式是精确描述，不能表达这种不 完全、不规则的信息。s p a r q l 查询中的非强制图模式完善了传统的查询模式，它使用 关键字o p t i o n a l 来描述那些可以有也可以没有的信息，从而在一定程度上解决了 r d f 这种半结构化数据的查询描述问题。由于非强制图模式不同于以往的查询模式，它 的匹配方式也不同于传统的精确匹配，所以设计一个非强制匹配查询的处理算法对实现 s p a r q l 中的非强制匹配查询是十分必要的。非强制匹配查询的实现使用户可以无损 地、灵活地使用r d f 这样的半结构化数据，有利于w e b 上基于r d f 的应用实现。 第一章绪论 1 4 本文组织 本文由正文( 六章) 、参考文献和附录所组成。正文的内容组织安排如下： 第一章绪论。介绍本文的研究背景、研究目标和内容、研究意义。 第二章当前技术现状综述。介绍r d f 图模型，总结当前的r d f 存储方案及查询 技术，分析现有的非强制匹配查询处理方法及其不足。 第三章非强制匹配查询处理。根据s p a r q l 语言规范对非强制匹配查询的定义和 描述，详细介绍非强制匹配的相关概念，提出非强制图模式的基本子模式 和模式树的概念，在此基础上，提出一种非强制匹配查询处理算法，用于 处理各种典型的非强制图模式的匹配问题，并从理论上分析算法的时间复 杂度。 第四章r o m q s 的设计与实现。通过对r d f 非强制匹配查询的需求分析，设计实 现一个非强制匹配查询系统原型r o m q s ，用来实现本文所提出的非强制 匹配查询处理算法。 第五章案例研究与实验分析。通过典型的s p a r q l 非强制匹配查询来测试所开发 的原型系统r q m q s 的查询功能，从而验证本文所提出的非强制匹配查询 处理算法的可实现性、有效性和时间复杂度。 第七章总结与展望。总结研究成果，展望下一步研究目标。 第二章当前技术现状综述 第二章当前技术现状综述 本章对当前相关技术现状进行分析和总结，包括r d f 相关概念、r d f 存储方案与 查询技术、非强制匹配相关概念、现有的非强制匹配查询处理方法及其不足等。 2 1r d f 相关概念 r d f 是w 3 c 提出的用于描述w e b 资源信息的标准模型和语言，它主要用于描述 w e b 资源的元数据。r d f 用于信息需要被应用程序处理，而不是仅仅显示给人观看的场 合。它提供了一种用于表达信息、并使其能在应用程序间交换而不丢失语义的通用框架。 可以从以下几个方面理解r d f 模型： 从资源描述的角度。r d f 基于这样一种思想：将一切事物视为资源，用w e b 标识 符来标识资源，用简单的属性( p r o p e r t y ) 及属性值( v a l u e ) 来描述资源。对资源的一 个描述称为一个陈述( s t a t e m e n t ) 。 从数据模型的角度。r d f 图模型是将关于一个或多个资源的陈述表示为一个由节点 和有向弧组成的图。其中，有向弧的起始节点表示资源，有向弧表示属性，有向弧的终 止节点表示属性值。图2 - 1 就是一个简单的r d f 图。 图2 - 1 r d f 图举例 从数据本质的角度。r d f 图本质上是一个三元组的集合。一个三元组由主语 。( s u b j e c t ) 、谓语( p r e d i c a t e ) 和宾语( o b j e c t ) 组成。其中，主语对应所要描述的资源， 谓语对应资源的属性，宾语对应属性的值。每个三元组对应r d f 图中的一条弧，且这 个弧的起始节点和终止节点分别对应三元组的主语和宾语。 第二章当前技术现状综述 构成r d f 图的基本元素包括统一资源标识符( u n i f o r mr e s o u r c ei d e n t i f i e r s ，u i u s ) 、 字面量( 1 i t e r a l ) 和空白节点( b l a n k n o d e ) ，它们统称为r d f 词汇。在r d f 图模型中， 主语可以是u r i 或空白节点，宾语可以是u r 、空白节点或字面量，谓语只能是u r i 。 ( 1 ) 统一资源标识符：w e b 资源的唯一标识，是对u r l 的一般化。可以用于标识w e b 上的任何事物，即使有时它们不能直接从w e b 上获取。如图2 1 中的f o a l ：p e r s o n 和m a i l t o ：a l i c e e x a m p l e o d m 都是u r i 。 ( 2 ) 空白节点：在现实世界中有些数据的形式比较复杂，例如在描述一个人的地址时， 可能需要一个由街道、城市、国家和邮政编码组成的结构。像这样的结构化数据 信息在r d f 中是通过以下方式描述的：把这些属性值聚集起来看成一个资源，作 为地址属性的值。对于这个聚集所得到的资源可以用一个空白节点表示，它没有 u r i 标识。例如图2 1 中最上面的两个节点就是空白节点。 ( 3 ) 字面量：这种r d f 词汇是用其字面上的内容作为属性值来描述一个资源。除了表 示字面量的字符串本身内容以外，字面量的数据类型和语言等信息也是非常重要 的。在r d f 中可以使用x m l s c h e m a 数据类型描述字面量，并且x m l s c h e m a 支 持r d f 应用自定义数据类型。例如图2 - i 中的”a l i c e ”和”b o b ”就是字面量。 在语法形式上，r d f 提供了一种称为r d f x m l 的语法来书写和交换r d f 图。与 r d f 三元组的简略记法不同，r d f x m l 是书写r d f 的规范性语法，详细定义可见 r d f x m l 语法规科1 8 】。在这样的语法规定下，每个r d f 图都可以序列化为一个x m l 文档，但序列化的方法不唯一。另外，简明的r d f 语法形式是t u r t l e ( t e r s er d ft r i p l e l a n g u a g e ) ，它以三元组为中心，详细定义可见t u r t l e 语法规耐1 9 】。为了描述的清晰性， 本文采用t u r t l e 语法形式来描述文中的r d f 范例，而在具体的实现时本文采用 r d f x m l 语法形式，这两种r d f 语法形式在描述能力上是等价的。 2 2r d f 存储方案 较为简单的一种r d f 数据存储方法是使用x m l 数据库存储r d f 数据。但一个r d f 图可以序列化为多个不同的x m l 文档，并且查询依赖于r d f 图的x m l 表示，所以这 种存储方式不便于对r d f 数据的查询【1 0 】【l l 】。 当前大多数r d f 查询系统，如j e n a 2 0 】【2 1 】、3 s t o r e 矧、r e d l a n d t 2 3 1 和s 舒锄e f 2 4 1 等，均 使用传统的关系数据库来存储r d f 数据、实现r d f 查询，以便利用数据库系统成熟和 优良的性能 2 5 】【2 6 】【2 7 】【2 8 】。按照所采用的关系模式不同，基于关系数据库的r d f 存储主要 有以下几种方案。 第二章当前技术现状综述 一三元组存储 三元组存储( 又称垂直表存储) 1 2 2 2 4 2 5 2 7 2 9 方式是将所有的r d f 三元组存储在一 个t f i p l 船关系表中，三元组的主语、谓语和宾语分别存储在t n p l 锚表的三个列中。通 常还会有几个表分别存储名空间、资源的u r i 和字面量等信息。这种存储方式不区分实 例信息和模式信息，因此无论查询实例信息还是模式信息都要遍历整个表，从而降低了 查询的效率。另外，模式信息和实例信息混和在一起给利用模式信息进行推理带来了困 难。三元组存储是当前r d f 存储和查询系统最为常用的存储方式，例如j f f l l a 2 1 1 、3 s t o r d 2 2 1 、 s e s a m d u 都采用了这种存储方式。 一基于r j ) f 模式的存储 基于r d f 模式的存储 2 4 2 5 1 1 2 6 2 7 方式是为每个使用r d f 模式定义的属性建立一个 单独的属性表来存储拥有该属性的资源和其属性值，为每个使用r d f 模式定义的类也 建立一个单独的类表来存储该类的实例信息。因此，在匹配三元组模式时，只需要遍历 该三元组模式的谓语所对应的属性表，并不需要遍历所有的三元组，从而提高了查询效 率。此外，基于r d f 模式的存储方式以类和属性为中心，很容易将r d f 数据和r d f 模式信息分开，从而有利于使用r d f 模式信息进行推理。但这种存储方式是在r d f 模 式的基础上存储r d f 数据，所以不能处理没有模式信息的r d f 数据。另外，在数据的 更新方面，向采用三元组存储方式存储的r d f 图中增加一个陈述只需在t r i p l e s 表中增 加一个元组；而在基于r d f 模式的存储中，增加一个陈述可能引进一个新属性，从而 需要增加一个属性表。在数据库操作中，基表增加操作比元组增加操作代价要高得多。 因此，基于r d f 模式的存储方式不利于数据更新。当前也有较多的r d f 存储和查询系 统支持基于r d f 模式的存储方式，例如，j e n a 和s e s a m e 。 水平表存储 水平表存储【2 5 】【2 9 1 方式也是使用一个关系表来存储r d f 图的所有数据。与三元组存 储方式不同的是，水平表存储方式下的r d f 图中的每个资源对应了关系表的一个元组， r d f 图中的属性对应表的列名，表的一个元组记录了一个资源所具有的全部属性的属性 值。这种存储方式中表的列数比较多，并且由于资源不一定拥有所有的属性，所以这种 存储方式是稀疏的。 一基于路径的存储 当前r d f 存储方式大多是将r d f 图拆分成三元组的集合，在进行图模式匹配时又 要将这些三元组连接起来。当图模式中包含的三元组模式很多时，就需要进行多次连接， 使套询效率降低。基于此，最近a k i y o s h im a t o n o 等人提出了基于路径( p a t h - b a s e d ) 的 r d f 关系数据库存储方式i3 1 】，这种存储方式是设计一种存储模式将r d f 图中的路径 存储在关系数据库中。当图模式中包含长路径时，基于这种存储方式的查询效率比较高。 第= 章当前技术现状综述 2 3r d f 查询技术 2 3 1 图模式及其匹配 当前大部分r d f 查询语言都使用“图模式”来描述r d f 查询，查询求解的过程就 是用图模式对r d f 图进行匹配的过程，即图模式匹配【1 7 】【3 2 】【3 3 】。因此图模式又称为查询 模式。现对相关概念定义如下： r d f 图 通过2 i 节的介绍可知，r d f 图本质上是三元组的集合。一个三元组由主语、谓语 和宾语组成。其中，主语可以是统一资源标识u r i 或空白节点，宾语可以是u r i 、空白 节点或字面量，谓语只能是u r i 。 图模式 由于r d f 图数据模型的本质，r d f 查询语言也必须是能够描述r d f 图的语言，图 模式就是描述r d f 图的一种有效方法口3 】f 3 3 】【3 钔。图模式用r d f 词汇和查询变量描述所要 查询r d f 图的一个子图，它在结构上与r d f 图类似，只不过构成它的基本元素除了可 以是r d f 词汇也可以是变量。 一模式解 当图模式匹配到r d f 图的某个子图时，查询变量与之所对应r d f 词汇之间的绑定 关系就是图模式匹配r d f 图的解，称为模式解( p a t t e r ns o l u t i o n ) b 3 。一个图模式可能 匹配r d f 图的多个子图，这样一个图模式就会有多个模式解，所有这些模式解的总和 称为图模式的匹配结果。形式定义如下： 定义2 - 1 给定一个r d f 图g 和一个图模式p ，_ p 匹配g 的一个模式解或简称为p 的解， 是一个置换函数s ：巧一t o ，其中，巧是j p 的变量集，不是r d f 词汇集的一个子集。s 满足：令s ( p ) 是把p 中的每个变量v 巧用s ( t o 来置换所得到的一个r d f 图， 则s ( p ) g ；如果某个变量不在s ( v ) 的定义域中，贝t j s ( v o ) = v o 。另外，尸匹配 g 的所有模式解的集合称为p 的匹配结果。 一基本图模式 基本图模式【1 3 】1 1 7 】是三元组模式( t r i p l e p a t t e r n ) 和制约束( v a l u e c o n s t r a i n t ) 的集合。 其中，一个三元组模式类似于一个r d f 三元组，只不过其主语、谓语和宾语都有可能 是变量；一个值约束是一个关于变量和r d f 词汇的布尔表达式。用基本图模式进行查 询时，查询的解是强制匹配此图模式所得的解，每个变量在解中都要绑定一个r d f 词 汇。基本图模式是传统r d f 查询语言最为常用的查询模式。 第二章当前技术现状综述 2 3 2r d f 查询语言 随着r d f 的广泛使用和语义w e b 技术的深入研究，许多学术机构、语义w e b 的研 究者和w 3 c 组织都提出了自己的r d f 查询语言方案，可以将这些查询语言分为以下几 类【9 】f 1 0 】： r d f 数据查询语言：这类r d f 查询语言简单的把r d f 看作是三元组数据，不 考虑它们的模式信息，除非在r d f 数据中显示的包含了这些信息。这类语言是 当前最为流行的r d f 查询语言。s q u i s h q l 、r d q l 、t r i q l ，以及w 3 c 新近发 布的s p a r q l 语言都是这种类型的查询语言。 _ 基于r d f 模式的查询语言：这类r d f 查询语言将r d f 数据和r d f 模式信息 进行了区别r q l 、s e r q l 和e r q l 都属于这种类型。 一起源于x m l 查询语言的r d f 查询语言：这类r d f 查询语言通过查询序列化 r d f 图得到的x m l 文档来达到查询r d f 图的目的，例如x p a t h 、x s l t 、x q u e r ) , 和w s a ( 3 5 】等。 推断查询语言：这类r d f 查询语言除了可以查询r d f ( s ) ，还具备一定的推理功 能，例如n 3 q l ，r - d e v i c e 3 6 】和t r i p l e 等 在以往公开发布的r d f 查询语言中，只有v e r s a 和s e r q l 两种语言提供了内置的方法 来支持半结构化数据的查询【9 】o 另外，国内也有相关研究【3 8 】，并提出了一种支持半结构 化数据的查询语言。s p a r q l 是w 3 c 新近发布的r d f 查询语言，其中的非强制匹配是 典型的半结构化数据查询模式。 2 3 3s p a r q l s p a r q l 语言以以往s q l 风格的r d f 查询语言为基础，将焦点集中在了基本图匹 配问题上。与大部分r d f 查询语言一样，s p a r q l 也使用图模式来描述一个r d f 查询， 图模式定义在s p a r q l 查询的w h e r e 子句中。与其他r d f 查询语言相比，s p a r q l 主要有两个创新之处：第一，s p a r q l 提供了多种复杂的查询模式( 图模式) 的构建方 法；第二，s p a r q l 提供了多种查询结果形式。另外，s p a r q l 描述的查询只是针对 r d f 的数据层，并不考虑数据的元信息，从而不支持推理。 在s p a r q l 查询语言中，除基本图模式外还有以下五种复杂图模式f 1 3 】【3 7 】： ( 1 ) 组图模式( g r o u pg r a p hp a t t e r n ) ：简单地将几个图模式并列在一起，组图模式的任 何一个解都要满足组成组图模式的所有图模式。 ( 2 ) 值约束( v a l u ec o n s t r a i n t ) ：对代表字面量的变量进行限制的一种图模式，可以用 第二章当前技术现状综述 来进一步筛选查询结果。语法上用关键字f i l t e r 表达，例如图模式f i l t e r ( ? p r i 3 0 ) 是限制变量p r i c e 的数据类型是整型，值小于3 0 。 ( 3 ) 非强制图模式( o p t i o n a l g r a p h p a t t e r n ) ：非强制图模式是由一组图模式昂，丑，只所 组成的一种图模式，图模式晶的匹配结果被图模式日，只的匹配结果依次非强制 地扩充，最终形成非强制图模式的匹配结果。语法上用关键字o p t i o n a l 表达。 ( 4 ) 选择图模式( a l t e r n a t i v e g r a p h p a t t e r n ) ：由，1 个图模式异 = l ，2 ，n ) 所组成的一种 图模式，匹配选择图模式时只要匹配任意一个曰即可。语法上用关键字u n i o n 表达。 ( 5 ) 命名图上的图模式( p a t t e r no nn a m e dg r a p h s ) ：用来为查询模式指定所要查询的 r d f 图。语法上用关键字g r a j p h 表达。 s p a r q l 提供了四种查询方式【1 3 1 1 3 7 1 ，不同的查询方式均利用图模式匹配r d f 图得 到的模式解，进一步形成以下几种不同形式的查询结果。 ( 1 ) s e l e c t ：s q l 风格的r d f 查询语言中最为常见的查询方式，s e l e c t 子句指定 了所要查询的变量。模式解是图模式中所有变量和r d f 词汇之间的绑定关系，而 s e l e c t 查询方式的查询结果中的每个查询解是模式解在s e l e c t 指定的查询变 量上的投影。一个图模式可能有多个模式解，因此s e l e c t 查询也可能有多个解， s e l e c t 查询的结果就是这些解的集合。 ( 2 ) c o n s t r u c t ：从已知的r d f 图构建一个新的r d f 图的查询方式。c o n s t r u c t 子句用来定义一个r d f 图模板( g r a p ht e m p l a t e ) ，图模板在结构上是一个三元组 模式的集合。c o n s t r u c t 查询仍然匹配w h e r e 子句中所定义的图模式、得到 匹配结果( 模式解的集合) 。将r d f 图模板中的变量替换为它们在模式解中的值， 就会得到一个r d f 图。匹配结果中的每个模式解都可以根据r d f 图模板构建一 个r d f 图，所有这些r d f 图合并在一起就是c o n s t r u c t 查询的查询结果。 ( 3 ) d e s c r i b e ：对资源的描述，其查询结果是与一个或多个资源相关的r d f 图。 d e s c r i b e 子句用来指定待描述的资源，可以用u r j 常量，也可以用代表资源的 变量，变量的值由w h e r e 中图模式的模式解来确定。 ( 4 ) a s k ：用来测试一个图模式是否有模式解的查询方式。如果匹配到模式解，则返 回布尔值“y e s ”，但不返回解的具体信息；如果匹配不到模式解，则返回布尔值 “n o 。 本文所研究的问题是非强制图模式的匹配问题，对于其他图模式暂不涉及。另外， 由于s e l e c t 查询方式是最为典型的查询方式，其他查询方式的查询结果只是在 s e l e c t 方式查询结果的基础上进行重构，故本文的所有设计和实现也只考虑s e l e c t 这种查询方式。 第二章当前技术现状综述 2 3 4 基于关系数据库的r d f 查询处理 数据的查询的方式依赖于数据的存储方式，当前大多数r d f 查询系统均使用传统 的关系数据库来存储r d f 数据，所以在对r d f 数据进行查询时，现有的查询系统也都 利用了关系数据库成熟的实施和优良的性能，尤其是数据库强大的查询优化能力。基于 关系数据库的r d f 查询处理方法的主要思想是将一个r d f 查询映射为对关系数据库的 s q l 查询【2 1 】瞄】【3 9 】。传统的基于关系数据库的r d f 查询处理仅涉及s p a r q l 中基本图 模式的匹配，本文总结了从s p a r q l 基本图模式匹配查询到s q l 查询的映射规则。假 设r d f 数据以三元组存储方式存储在t r i p l e s 表中，映射规则如表2 1 所示： 表2 - 1从s p a r q l 基本图模式匹配查询到s q l 查询( 关系代数操作) 的映射规则 p a r q l 查询语旬的元素 ，。 s q l 查询操作( 关系代数操作! ，蠢、瘘。翼 w h e r e 子句中图模式中的三元组模式 对t r i p l e s 表的选择操作 图模式中多个三元组模式之间的共有主语 宾语变量关系 t r i p l e s 表上的相应列之间的自然连接操作 f l i t e r 语句中变量的值约束对图模式匹配结果的选择操作 s e l e c t 子句对查询结果的投影操作 依据上面的映射规则，按照一定的转换算法，将一个r d f 查询转换为对t r i p l e s 表的s q l 查询，然后对s q l 查询结果进行一定的处理，就可以得到r d f 查询的结果。现有的r d f 查询系统对这种查询方法的实现已经相当成熟。 2 4 非强制匹配查询及其处理方法 2 4 1s p a r q l 中非强制匹配查询的语法 s p a r q l 的语法结构类似于以往s q l 风格的r d f 查询语言。按照s p a r q l 语言规 范，非强制匹配查询的语法格式如下： p r e f i xn a m e s p a c e l n a m e s p a c e 2 】 s e l e c t ? v a r i a b l e l ? v a r i a b l e 2 】 【f r o md e f a u l t g r a p h 】 w h e r e p o o p t i o n a l p 1 ) o p t i o n a l 尸2 ) 】) 其中，p r e f i x 声明名空间，s e l e c t 指定需要返回的查询变量，f r o m 指定所要查询 的r d f 图，w h e r e 子句用非强制图模式描述查询条件，关键字o p t i o n a l 用来构建 非强制图模式，p 0 、p 1 和p 2 是图模式，可嵌套定义。 第二章当前技术现状综述 由于组图模式、选择图模式和命名图上的图模式是s p a r q l 语言规范中提出的新型 查询模式，至今还没有成熟的解决方案，因此为了将研究重点放在非强制图模式的匹配 问题上，本文假设：非强制图模式中的图模式岛、p l 和p 2 不会是组图模式、选择图模 式或命名图上的图模式 2 4 2 非强制匹配的含义 通过上一节中对s p a r q l 非强制匹配查询语法的描述，s p a r q l 是用关键字 o p l l o n a l 来定义非强制图模式的。末被定义在o p t i o n a i ，中的图模式是强制匹配的， 其匹配r d f 图所得到的解中的每个变量都要绑定一个r d f 词汇。定义在o p t i o n a l 中的图模式是非强制匹配的，当其能匹配r d f 图中的某些信息时，就将这些匹配到的 信息加入到强制匹配所产生的解中；但当其不能匹配时，也不影响强制匹配的解作为最 终的解。非强制匹配的解也是查询变量与r d f 词汇之间的绑定关系，只不过解中的某 个( 些) 变量可以不绑定值。对于图l 之中的非强制匹配查询，如果它所要查询的是图 2 1 中的r d f 图，则查询结果如下所示： n a m b o x ”a l i c e m a i l t o ：a l i c e e x a m p l e t o m ”b o b ” 在这个查询结果中共有两个解，其中第二个解中的变量m b o x 没有绑定值，这说明在r d f 图中没有b o b 的邮箱信息，但这不影响其姓名( 变量n a m e ) 的返回，这就所谓的对半 结构化数据的非强制匹配查询。 如果一个非强制图模式只有一个o p t i o n a l 语句，也就是说这个o p