（计算机应用技术专业论文）通用sparql查询引擎设计.pdf

摘要 随着s e m a n t i cw e b 研究和w e b 2 0 应用的发展，r d f 数据被大 量地发布。w 3 c 发布的s p a r q l 查询语言和数据访问协议，担负着 统一r d f 查询和数据访问标准的重任。 课题旨在设计实现一个可部署到各种r d f 平台上的通用 s p a r q l 查询引擎- - s q e n g i n e 。其主要功能是解释执行s p a r q l 表 达式。论文在以下几个方面展开研究： 提出了s q e n g i n e 的通用性实现策略。s q e n g i n e 基于抽象数据 接口访问底层r d f 数据，具有不依赖于具体数据访问方法的独立性； 通过适配器对抽象数据接口和具体数据访问方法进行匹配，以实现 可部署性。 为s q e n g i n e 设计了前后端分离的系统结构。前端进行语法分 析，分析结果以抽象语法树( a s t ) 的形式输出；后端则基于抽象语法 树进行r d f 数据查询。 在充分研究抽象语法树和l l ( 1 ) 分析方法的基础上，设计了一个 可以生成抽象语法树的l l ( 1 ) 语法分析算法。 设计实现了基于抽象语法树的查询算法，其中运用了面向对象 程序设计的思想和方法，使系统具有良好的结构。根据“针对接口 编程 的思想，设计各a s t 节点的逻辑功能和数据接口；应用g o f 的“访问者模式 和“抽象工厂模式”，将a s t 节点的逻辑功能实 现从a s t 节点类中独立出来；设计出一种基于r d f 三元组通配符 匹配的递归查询算法。 分析了适配器的设计，并将s q e n g i n e 装配到了j e n ar d f 平台 上。最后进行系统测试，结果证明：s q e n g i n e 能有效地解释执行 s p a r q e 查询，但是与j e n a 系统自带的s p a r q l 解释模块对比， s q e n g i n e 的解释执行速度稍慢，有待进一步改进提高。 关键字r d f ，s p a r q l ，s p a r q l 查询引擎，设计模式，l l ( 1 ) 语法分析 a bs t r a c t w i t ht h ed e v e l o p m e n to fr e s e a r c ho fs e m a n t i cw e ba n da p p l i c a t i o n o fw e b 2 0 ，r d fd a t ah a v eb e e nw i d e l ys p r e a d s p a r q lq u e r yl a n g u a g e a n dd a t aa c c e s sp r o t o c o li s s u e db yw 3 ct a k e st h ee s s e n t i a lr e s p o n s i b i l i t y t ou n if o r mt h es t a n d a r do fr d fq u e r ya n dd a t aa c c e s s t h er e s e a r c ha i m sa td e s i g n i n gag e n e r a ls p a r q lq u e r ye n g i n e ( s q e n g i n e ) ，w h i c hc o u l d b e d e p l o y e d o nv a r i o u s k i n d so fr d f p l a t f o r m s ，t h em a j o rf u n c t i o no fs q e n g i n ei st oi n t e r p r e ta n de x e c u t e s p a r q le x p r e s s i o n t h ep a p e ri sc o n c e r n e dw i t ht h ef o l l o w i n gr e s e a r c h t h ep a p e rg i v e sad e s c r i p t i o na b o u tt h ei m p l e m e n ts t r a t e g yo f s q e n g i n eg e n e r a l i z a t i o n s q e n g i n eb a s e d o na b s t r a c td a t ai n t e r f a c e a c c e s s e su n d e r l y i n gr d fd a t aa n ds h a r e si n d e p e n d e n c eo nc o n c r e t ed a t a a c c e s sm e t h o d d e p l o y m e n tc o u l db ea c h i e v e db ym a t c h i n gt h ea b s t r a c t d a t ai n t e r f a c ea n dc o n c r e t ed a t aa c c e s sm e t h o dw i t ha na d a p t e r t h e s y s t e ms t r u c t u r es e p a r a t i n gt h ef r o n te n d sa n db a c ke n d sh a sb e e n d e s i g n e d ：f r o n te n d sc o u l de x e c u t es y n t a xa n a l y s i sa n dt h er e s u l t s a r e o u t p u ti nt e r mo fa b s t r a c ts y n t a xt r e e ( a s t ) w h i l eb a c k e n d sb a s e do n a s te x e c u t er d fd a t aq u e r y b a s e do nc o m p l e t er e s e a r c ho na s ta n dl l ( 1 ) a n a l y s i s ，al l ( 1 ) s y n t a xp a r s i n ga l g o r i t h mi sd e s i g n e d ，w h i c hh a st h ea b i l i t yo fp r o d u c e a st t h ed e s i g ni m p l e m e n t sq u e r ya l g o r i t h mb a s e do na s t ，u s i n gt h e a p p r o c h e so fo b j e c t o r i e n t e dp r o g r a m m i n gd e s i g n ，w h i c he n s u r e st h e s y s t e mas o u n ds t r u c t u r e a c c o r d i n gt o “p r o g r a m m i n gt oa ni n t e r f a c e ”， a s tn o d ec l a s s sl o g i cf u n c t i o na n dd a t ai n t e r f a c eh a v eb e e nd e s i g n e d ； b yu s i n gg o f s v i s i t o rp a t t e r n a n d a b s t r a c tf a c t o r yp a t t e r n t h e 1 0 9 i cf u n c t i o ni m p l e m e n t so fa s tn o d ec l a s sc o u l db ei n d e p e n d e n tf r o m a s tn o d ec l a s s ar e c u r s i v eq u e r ya l g o r i t h mc o u l db ed e s i g n e db a s e do n m a t c h i n gw i t hw i l d c a r d st oap a r t i c u l a rr d ft r i p l e s t h ed e s i g nf o rt h ea d a p t e rh a sb e e na n a l y z e d ，s q e n g i n eh a sb e e n d e p l o y e do nt h er d fp l a t f o r m ，a n dt h es y s t e mh a sb e e nt e s t e d t h e r e s u l to ft e s tp r o v e s ：s q e n g i n ec o u l di n t e r p r e ta n de x e c u t esp a r q l q u e r ye f f i c i e n t l y , b u tc o m p a r i n gw i t hs p a r q li n t e r p r e t i n g m o d e l f i x e di nj e n as y s t e m t h es p e e di sal i t t l es l o w e r , w h i c hn e e d si m p r o v i n g k e yw o r d sr d f ，s p a r q l ，s p a r q lq u e r ye n g i n e ，d e s i g n p a t t e r n ，l l ( 1 ) s y n t a xp a r s i n g i i 图表索引 图1 1r d f 图模型示例2 图2 1s q e n g i n e 引擎定位9 图2 2r d f r e s o u r c e 接口1 1 图2 3 适配器保证引擎的可部署性1 2 图2 4 通用的s q e n g i n e 1 3 图2 5 编译器的前后端结构一1 4 图2 - 6s q e n g i n e 的工作过程15 图2 7s q e n g i n e 系统总体结构图1 6 图3 1a s t 节点的c o m p o s i t e 模式2 1 图3 2 语法分析程序的任务2 2 图4 1 各a s t 节点之间的逻辑关系3 0 图4 2 实际的s e l e c t 查询接口一3 3 图4 3s q e n g i n e 中的访问者模式：3 4 图4 4 抽象工厂模式创建逻辑对象一3 6 图4 5 查询被解析后生成的抽象语法树一4 0 图5 1s q e n g i n e 的包结构4 7 图5 2j e n a 各组成部分的关系4 8 v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其它单 位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均 已在论文中作了明确的说明。 作者签名：区蠡日期：z 0 0 7 年1 1 月7 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文，允许学位论文被查阅和借阅；学校可以公稀学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省 有关部门规定送交学位论文。 作者签名：盟 导师签名： 同期：2 o 口7 年1 1 月7 同 硕l j 学位论义第一章绪高 1 1 研究背景 第一章绪言 1 1 1w w w 数据表达方式的局限性 万维网( w o r l dw i d ew e b ，w w w 或w e b ) 起源于欧洲的一个国际核能研究 院( c e r n ) ，t i m eb e m e r s l e e 结合超文本和因特网的研究成果，提出了一份关 于信息管理的研究计划，1 9 9 0 年1 2 月建立了第一个万维网的原形系统。w w w 为信息的发布和获取提供了一个全新的网络服务平台。力维网从诞生至今已经 有十多年的历史，其应用发展十分迅速，特别是信息量呈级数增长。 万维网信息数量大、分布复杂，人们不能不倚重于搜索引擎来检索自己所 需的信息，这种需求也推动了搜索引擎的发展，使得搜索的效率更高。但是， 现有的搜索引擎采用的检索技术从本质上讲仍然是基于关键词匹配的技术f 2 1 ， 检索质量差强人意。检索技术之所以没有质的飞跃，是因为当前力维网在数据 表达方式上存在着缺陷。 早期使用的h t m l 语言的数据组织方式以及所表达的页面信息，主要面向 用户直接阅读，没有将信息的表现形式、内在结构和表达内容相分离，因而不 利于计算机处理。到了九十年代的中期，采用x m l ，x l t 等技术，实现了数据 内容与表现形式的分离。x m l 的出现也使得不同类型的数据表示成统一格式成 为了可能，使得x m l 成为应用之间或者机器之间共享数据的一种有效方式。 x m l 及其相关技术的发展极大地促进了信息表达和交换过程中语法描述上的 统一，但是x m l 描述的数据却缺乏统一的语义。总的来说，无论是h t m l 语 言还用x m l 技术都不具备表达统一语义的能力，因此限制了计算机在信息检 索中的自动分析处理以及进一步智能化的信息处理能力。 对信息语义表达能力的需求，导致了r d f ( r e s o u r e ed e s c r i p t i o nf r a m e w o r k ) 资源描述框架的产生，w 3 c ( t h ew o r l dw i d ew e bc o n s o r t i u m ) 推荐以r d f 标 准来解决x m l 的语义局限性p 。 1 1 2r d f 资源描述框架 1 、r d f 数据模型 r d f 提出了一个简单的模型用来描述数据及其语义，r d f 数据模型的基本 思想是：被描述的资源具有一些属性( p r o p e r t y ) ，而这些属性各有其值( v a l u e ) ， 那么可以通过对资源的属性和属性值的陈述( s t a t e m e n t ) 来描述资源【4 】。 坝i ：学位论文 第一章绪高 r d f 数据模型可以表示为带标记的有向图模型。r d f 图模型的基本结构 是：节点边一节点，图1 1 表达了“h t t p ：n z h a n g s a n 网站的创建者是z h a n g s a n ” 这样的语义。 h t t p ：z h a n g s i md i c ：c r e a 衙卜z h a n g s a n 图1 1r 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 ) ，其中 将被描述的资源称为主体( 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 的数据模型可以作为其他任何复杂关系模型的基础模型。 2 、r d f 语法 r d f 三元组和r d f 图为描述资源提供了数据模型，这种r d f 数据模型必 须要用一定的语法形式表示出来，以便进行数据存储和数掘交换，理论上r d f 可以用任何适当的语法来描述，但x m l 是w e b 上数据表示和交换的标准，因 此r d f 有一个基于x m l 的语法，称为r d f x m l 。r d f x m l 是w 3 c 推荐的 标准，但是却非常繁琐难以学习。这也是r d f 在实际应用备受争议的所在。r d f 还有一些其他的表示法，如简洁的基于x m l 的t r i x 语法【引、基于文本的t u r t l e 语法 9 】等等。 3 、r d f 应用 t i m b e r n e r s l e e 在x m l 2 0 0 0 大会上，提出了s e m a n t i cw e b 的概念，期待 s e m a n t i cw e b 能够解决网络上资源语义缺乏的不足。b e m e r s l e e 这样描述 s e m a n t i cw e b ：所谓s e m a n t i cw e b 并不是重新建立一个全新的网络，而是对当 前万维网的扩展，使得其上的信息具有良好的定义，促进人与计算机的合作【1 0 1 。 r d f 成为s e m a n t i cw e b 表达资源语义信息的基础，随着s e m a n t i cw e b 研究的 发展，r d f 得到了广泛的应用1 。 近年来w e b 2 0 的应用得到了极大的发展。尽管w e b 2 0 并不要求使用r d f 模型来描述数据，但在数据的语义表达这一本质问题上w e b 2 0 与s e m a n t i cw e b 的需求是一致性的 1 2 】。所以我们可以看到r d f 数据在w e b 2 0 应用同样得到了 发展，如r s s l 0 1 和f o a f 2 词汇表的应用。 1 r d fs i t es u m m a r y ( r s s ) 1 0 是一个轻量级多目的町扩胜几数据描述和l 卅步( s y n d i c a t i o n ) 格式，遵循w 3 c 的r d f 规范，足万维刚i ：最广泛的r d f 应用之一。 2f o a f ( f r i e n d - o f - a - f r i e n d “朋友的朋友”) 是一个r d f 词汇表，f o a f 是管理社区的重要工具。 2 顾i ：学位论文第一章绪高 1 1 3 r d f 查询与s p a r q l 语言 r d f 数据查询和数据访问标准的制定工作，滞后于r d f 数据定义和存储 标准。在r d f 存储模式出现后的相当长的时间内，查询r d f 数据还没有任何 标准，所以在各种商业项目和丌源项目上，很多开发者设计出多种用于访问r d f 数据的查询语言，在文献 1 3 】记载着不少于2 0 种的r d f 查询语言，文献 1 4 1 5 1 6 对各种r d f 查询语言进行了比较，这些语言缺乏共同的语法和语义 标准，因而制约了r d f 应用系统的可移植性。 s p a r q l ( s p a r q l p r o t o c o la n dr d fq u e r yl a n g u a g e ，语义网协议与r d f 查询语言的递归式缩写) 是一种面向r d f 数据模型的查询语言和数据访问协 议，用于访问任何可以映射到r d f 模型的数据资源( 本地的或远程的) 1 7 儿1 8 】【19 1 。 s p a r q l 规范由w 3 c 的r d f 数据访问工作组( d a w g ) 丌发，己被w 3 c 指 定为候选推荐标准。但是s p a r q l 目前还只是一个只读语言，还不支持r d f 数据的修改和更新等功能，这是d a w g 工作组下一步的研究重点。 缺乏数据查询和访问标准的事实，同样出现在w e b 2 0 的应用中。大多数 w e b 2 0 应用程序和服务都使用r e s t 协议或接口。人们可以通过h t t p 和可操 作的数据表示方法与一个w e b 2 0 应用或服务进行交互。采用r e s t 建立w 曲 应用和服务的方式，远胜于r p c 风格的接口。但是，也存在一些问题：r e s t 提供了一个操作标准集如( g e t , p u t p o s t , d e l e t e ) ，而没有提供标准的数 据操作语言。有人认为，s p a r q l 同样可以作为w e b 2 0 的标准来使用，尽管通 常w e b 2 0 的资源表示采用x m l 而不是r d f 模型，但是只要支持s p a r q l 查 询，且能把这种s p a r q l 查询映射到s q l 查询或其它的系统支持的查询上即 可。 总之，无论是从s e m a n t i cw 曲这种尚处于理论研究的技术，还是w e b 2 0 这种流行应用上来看，s p a r q l 作为一个数据访问标准都具有十分重要的意义。 但是s p a r q l 语言仅仅可以描述查询，而不能实现查询。为实现s p a r q l 描述 的查询功能，必须要有能够解释s p a r q l 查询语句，并执行查询操作的引擎的 支持，这就是本课题研究的内容。 1 2 国内外研究现状 1 2 1 国外研究现状分析 国外关于s p a r q l 的研究主要体现在以下几个方面： 1 、s p a r q l 应用的研究 随着s p a r q l 被w 3 c 推荐为侯选标准，各种r d f 应用系统都丌始采用 s p a r q l 语言来描述查询，这是一种发展趋势。 硕i ：学位论义第一章绪高 2 、s p a r q l 理论基础的研究 为满足研究和分析的需要，人们一直在致力于构建r d f 查询和语义推理的 形式化框架。自s p a r q l 问世以来，这些研究工作也针对s p a r q l 语言展开。 文献f 2 0 h 各关系代数理论应用到s p a r q l 查询的研究上，通过适当修改关 系代数操作符以适应r d f 和s p a r q l 查询的需要。用关系代数表示s p a r q l 查询有利于将现有的关于数据查询设计与优化的研究成果运用到s p a r q l 实现 上去，也有益于在基于关系数据库的d r f 存储中简化s p a r q l 查询处理 将s p a r q l 查询映射为s q l 查询。 文献 2 1 】则讨论了s p a r q l 的形式化语义和计算的复杂度，为s p a r q l 的 深入分析提供了形式化的工具。如，鉴别和推理出不同构造器之j 、r j 的关系，分 辩查询中多余的和矛盾的概念，研究s p a r q l 查询的计算复杂度和表达能力， 以及与数据库操作相关问题，如查询的重写和优化等。 3 、对s p a r q l 语言进行扩展的研究 任何一门查询语言的表达能力总是有限的，不同的领域对查询语言的表达 能力有不同的要求。国外在这方面进了广泛而深入的研究，并提出多种s p a r q l 语吉的扩展方案。 ( 1 ) i s p a r q l 语言：在s p a r q l 的基础上增加“相似匹配操作符”，从而 使其具有描述“不精确匹配( i m p r e c i s em a t c h e s ) ”的能力【2 2 】 【2 3 1 。由于当前不同 的组织和个人发布的信息往往是重叠的，因此由不同数据源组成的海量知识库 中存在大量的相似数据实体。为此，提出了不精确匹配的概念，即基于语义的 查询，不仅应该能检索出精确匹配的数据，也需要具备检索相似数据的能力。 ( 2 ) s p a r q 2 l 语言：在各种分析领域中，常常需要提取实体之问的关系， 即r d f 数据图中的路径信息，但是s p a r q l 并不具备描述路径检索的能力。 文献 2 4 1 提出通过添加路径变量和路径变量约束表达式来扩展现有的s p a r q l 语言，使其支持对r d f 数据图进行路径检索，即所渭的s p a r q 2 l 语言。另外， 多数r d f 系统基于内存模式处理r d f 数据，只能完成细粒度的路径检索，而 不适应粗粒度r d f 图的路径检索。对此，文献 2 4 】还设计了一种新的查询计算 框架，以支持在磁盘存储的r d f 图中进行路径信息计算。 ( 3 ) s p a r q l u p d a t e 语言：s p a r q l 目前还是只读语言，文献 2 5 】提出 了s p a r q l u p d a t e 语言，添加u p d a t e 操作符扩展以现行的s p a r q l 语言，使 其能同时描述r d f 数据读和写操作。 4 、s p a r q l 查询处理和优化的研究 s p a r q l 查询处理与r d f 的存储密切相关，大多数的r d f 存储系统都是 基于关系数据库的系统。国外关于s p a r q l 查询处理的研究比较地多集中在 4 硕i j 学位论义 第一章绪高 s p a r q l 到s q l 的映射研究，特别是一些复杂的s p a r q l 查询特性的s q l 映 射研究。如，文献 2 6 就提出了一种有效的o p t i o n a l 图模式的映射算法。将 s p a r q l 映射到s q l 的处理方式也引发出对查询效率的深入探讨，j 下如一个合 理的s q l 查询表达式可以成数量级地提高数据库查询效率，同样在将s p a r q l 查询转化为关系数据库的操作时，也必须考虑优化处理，以提高s p a r q l 查询 效率，文献 2 7 1 讨论了这种优化处理。 在实际应用中，通用的r d f 平台并非直接采用上述s p a r q lt os q l 映射 机制进行s p a r q l 查询处理。如j e n a 2 8 】平台，尽管它有一个s q l 映射机制后 台，但是前台的s p a r q l 处理仍然是通过其r d fa p i 提供的r d f 数据访问接 1 2 1 来实现的。r e d l a n d 2 9 】平台也是一样，它对s p a r q l 查询的处理是基于其r d f 数据的内存模型进行的。导致这种情况的原因与r d f 存储方式的多样性有关。 早在s p a r q l 提出之前，人们就已经对r d f 数据存储方式进行了深入的研究， 且提出了不同的r d f 存储方式。如，对于小型的r d f 数据可直接使用x m l 或n 3 文本文件存储，或将r d f 数据作为图存储在对象数据库中【3 0 】等等。因此， 一个通用的r d f 支持平台会将不同的r d f 存储( 持续化存储模型) 统一映射为内 存模型( 非持续化存储模型) ，然后基于内存模型对r d f 数据进行操作。对外则 提供一个操作其内存模型的简单r d f 数据访问接口。在这种情况下，查询语言 描述的复杂查询最终也通过这个接口实现，这也是本文拟采用的设计策略。 在文献 3 1 上列出了2 0 余种s p a r q l 查询处理系统和引擎，如：r a p 是一 个p h p 软件包，用于分析、搜索、处理和存储r d f 数据，它同时支持s p a r q l 和r d q l 查询；a r q 是惠普实验室丌发的j e n a 框架的查询引擎，它同时支持 s p a r q l 和r d q l 查询语言；k a o n 2 的o w l d l 推理引擎也支持部分s p a r q l 查询；r a s q a l 是r e d l a n d 框架的查询引擎，它支持s p a r q l 和r d q l 查询语言 等等。这些s p a r q l 查询引擎一般都基于某个确定的r d f 存储平台，这种设 计的优势就在于它是为相应r d f 平台量身定制，可以针对相应平台进行代码优 化，因而具备较高的执行效率。但是这种查询引擎的问题是可移植性差，所以 存在大量重复的研究与开发。 1 2 2 国内研究现状分析 1 、r d f 查询语言的研究 随着r d f 数据应用的普及，国内关于r d f 查询语言的研究逐渐深入。主 要体现在以下几个方面：对现有查询语言的改进和应用时的优化( 如文献 3 2 】) ； 提出一种新的查询语言( 如文献 3 3 】， 3 4 】) 以及研究r d f 查询到s q l 的转换( 如 文献 3 5 ) 等。 特别也有一些涉及到r d f 查询语言的处理实现的研究，如文献 3 6 中，分 倾f j 学位论文第一章绪高 析了如何构建一个以x r q l 为查询语言的r d f 引擎( n s r e ) 的体系结构，并简 要地探讨了相关的实现技术；文献 3 7 则讨论了基于r d f 的查询引擎系统架构 的设计。 2 、s p a r q l 语言的研究 s p a r q l 查询语言在2 0 0 5 年才由w 3 c 推出，并且还没有形成最后的标准， 国内有关s p a r q l 的研究相对较少，且主要是s p a r q l 查询的应用。如，文献 f 3 8 i t 论了利用r d f 本体图扩充s p a r q l 查询，使其具备本推理能力，但它 给出的并不是对s p a r q l 语言功能的扩展，而是将s p a r q l 用于本体推理的一 种处理技巧；文献 3 9 讨论了一个本体知识库的自然语言查询接1 5 1 ，这个接口 的主要功能就是将自然语言提问转换为s p a r q l 查询。 关于s p a r q l 查询处理，浙江大学的网格实验室进行了相关的研究。该实 验室丌发的d a r t g r i d 4 0 】 【4 u 是一个语义数据库网格系统，s p a r q l 查询支持是其 一项功能。d a r t g r i d 处理s p a r q l 查询的本质仍然是将其映射为一系列的s q l 查询。这种针对具体系统设计的s p a r q l 查询处理引擎并不具备通用性。 1 3 主要研究内容和意义 1 3 1 研究目标 s p a r q l 语言提供了一个有效的访问r d f 数据的抽象接口，隐藏了r d f 存储和访问的细节，使应用系统的丌发者在丌发基于r d f 数据的智能系统时， 能在较高的层次上专注于系统功能的实现，而不必拘泥于底层r d f 数据的访问 细节。但是s p a r q l 语言仅能描述查询而不具备解释功能，为此需要丌发 s p a r q l 查询的解释引擎来解释执行其描述的查询。 本课题的目标是：设计并实现一个通用s p a r q l 查询引擎器。为讨论的方 便将它命名为s q e n g i n e ( s p a r q lq u e r ye n g i n e ) 。s q e n g i n e 的主要作用是为 r d f 平台提供s p a r q l 查询表达式的解析执行功能。s q e n g i n e 的通用性意味 着s q e n g i n e 具有不依赖于具体r d f 服务平台的独立性，同时又具有装配到任 一具体r d f 平台上的可部署性。 1 3 2 研究内容 为了实现上述目标，课题研究的内容主要集中在以下几个方面。 1 、通用s p a r q l 查询引擎总体结构分析 研究s p a r q l 查询引擎的通用性实现策略以及s p a r q l 查询解释功能的设 计思路，并在此基础上提出引擎系统的总体设计方案。 6 坝卜学位论文第一章绪高 2 、语法分析器的设计 语法分析器以抽象语法树( a s t ) 为输出结果。为此，需规划s p a r q l 语 言的所有a s t 节点，并分析设计a s t 节点的结构，然后要选定一种合适的语 法分析方法，设计出可以生成抽象语法树的语法分析算法。 3 、基于抽象语法树的查询算法设计 s q e n g i n e 引擎以抽象语法树为查询对象，基于抽象语法树的查询算法必然 由树中的节点协作完成。为此需进行三个方面的研究：一是对各a s t 节点的数 据功能和逻辑功能进行规划；二是分析a s t 节点数据功能和逻辑功能的实现方 法；三是设计基于抽象语法树的查询算法。 4 、查询引擎适配器设计 适配器是s q e n g i n e 引擎与r d f 服务平台进行无缝连接的关键，这部分研 究主要分析如何针对具体的r d f 平台设计s q e n g i n e 引擎适配器。 1 3 3 研究的意义 1 、在当前众多s p a r q l 查询引擎并存在的情况下，s q e n g i n e 引擎的独立 于具体r d f 平台的通用性特点，使其具有跨平台安装的能力。 2 、s q e n g i n e 引擎的设计思路和实现方案，对于今后类似的研究有一定的 借鉴作用。 3 、s p a r q l 本身并不完善，目前它仅仅是一个只读语言，还不能支持r d f 数据的修改。s p a r q l 要成为r d f 查询标准还有一定的距离，本课题的研究可 持续跟踪s p a r q l 规范的发展。 1 4 论文结构 全文共分五章： 第一章绪言：从课题背景分析入手，引出课题研究目标设计一个通用 的s p a r q l 查询引擎( s q e n g i n e ) ，然后详细讨论了国内外相关研究的现状， 最后分析课题研究内容和意义。 第二章总体设计：从s q e n g i n e 功能分析入手，深入讨论了通用性实现策 略，然后分析引擎的工作流程并设计出系统的总体结构。 第三章语法分析器设计：规划s p a r q l 语言的所有a s t 节点，并分析这 些a s t 节点的结构。在深入讨论s p a r q l 的l l ( i ) 分析方法的基础上，设计出 可构造抽象语法树的l l ( 1 ) 分析算法。 第四章基于抽象语法树的查询算法设计：首先根据s p a r q l 语义分析a s t 节点的功能，a s t 节点的数据接1 1 1 和逻辑接口设计；然后深入讨论a s t 节点的 7 硕i j 学位论义第一章绪高 逻辑接口实现方法；最后分析基于抽象语法树的查询算法。 第五章引擎部署与测试：分析s q e n g i n e 引擎的文件系统组织，引擎适配 器设计，最后对引擎的j 下确性和性能进行测试。 第六章总结论文贡献、指出现在工作的局限性，有待改进的方面，并展望 s p a r q l 的发展及下一步的工作。 硕i j 学位论义 第一二章总仆设计 2 1 系统功能分析 第二章总体设计 2 1 1 需求分析 s q e n g i n e 引擎是一个通用的s p a r q l 查询表达的解释执行程序。其功能需 求可描述下： 1 、s p a r q l 查询表达式语法分析 客户输入s p a r q l 查询表达式，s q e n g i n e 引擎能对查询表达式进行语法分 析。对于不符合s a p r q l 文法的表达式输出异常，对于合法的查询表达式，输 出语法分析结果。 2 、解析执行查询意图 根据语法分析结果，分析查询意图，并解释执行r d f 查询，输出查询结果。 3 、满足通用性要求 s q e n g i n e 引擎本身不具备r d f 数据管理功能，需要其它r d f 平台的支持， 且该平台需提供简单的r d f 数据读取接口。为满足通用性要求，s q e n g i n e 引 擎不对r d f 平台的数据接口提出任何约束，即s q e n g i n e 引擎可以运行在任意 r d f 平台上。 总之，s q e n g i n e 引擎可以装配到任一r d f 平台上，为r d f 平台提供 s p a r q l 查询表达式的解析执行功能。s q e n g i n e 引擎与具体的r d f 平台的关 系如图2 1 所示： _ 1 。 。一 r d fa p p l i c a t i o n 一一一 。 r e s ui t s p a r q lq u e r y 一 丫5 a 哼n e n 5 s q e n g i n e 、。 “ 一 丫 r d fs e r v e r 一。 一一 一一丫一j 一 7 r d fs t o r e 【、一， 、 图2 - 1s q e n g i n e 引擎定位 o 顾i 学位论文第一二章总f 水设计 2 1 2 需解决的问题 1 、系统的通用性问题 由上述分析知，s q e n g i n e 引擎不是一个独立完整的r d f 平台，它需要利 用具体r d f 平台提供的数据访问接口。现有多种r d f 存储管理平台，如j e n a 、 s e s a m e 和k n o i 等，它们提供的r d f 数据访问接口各不相同。因此必须设计 一种通用性实现方案，使s q e n g i n e 能方便地装配到不同的r d f 平台上。 2 、语法分析程序设计 s p a r q l 查询表达式的语法分析是实现数据查询的日订提。语法分析程序的 设计有比较成熟的编译理论支持，存在众多的语法分析方法可供借鉴使用。为 此，需要根据s p a r q l 文法特点以及各种语法分析算法的设计难度、运行效率， 选择合适的语法分析方法。并设计出可解释s p a r q l 表达式的语法分析算法。 3 、查洵的解释代码设计 生成查询的解释执行代码是s q e n g i n e 引擎的设计难点。一方面，需要根据 语法分析结果设计查询代码的构造方法；另一方面，要根据r d f 平台提供的数 据访问接口设计合理的算法。 以下将先分析引擎通用性实现策略和查询功能实现策略，然后在此基础上 确定系统的整体结构。 2 2 通用性实现策略 通用性是s q e n g i n e 区别于其它s p a r q l 查询引擎的最重要的特点，要实 现s q e n g i n e 的通用性，必须满足两个要求：一是独立性要求，即独立于具体 r d f 平台；二是可部署性要求，即易于部署到具体的r d f 平台上。 2 2 1 独立性实现策略 独立性意味着该系统应该有一个不依赖于底层具体的r d f 平台的设计方 案。为实现这一思想可借助面向对象程序设计中的“依赖倒置”原则。 所谓依赖倒置是指：高层不应该依赖于低层；抽象不应该依赖于细节【4 2 1 。 在传统的设计中，如结构化设计中，总是倾向于使高层的模块依赖于低层的模 块、策略依赖于实现细节等等。依赖倒置即是把这种传统设汁的依赖关系倒置 过来。事实上，这种依赖关系的倒置f 是面向对象设计的标志所在。更进一步， 依赖倒置原则要求类依赖于抽象类而非具体类，因为具体类往往是不稳定的。 s q e n g i n e 位于r d f 平台之上，它需要使用r d f 平台提供的简单的r d f 数据访问方法( m e t h o d ) 来实现复杂的s p a r q l 查询。根据依赖倒置原则， s q e n g i n e 的实现不能依赖于某一具体r d f 平台提供的r d f 数据访问方法。所 l o 顾i ：学位论文第二章总体设计 以在设计中，s q e n g i n e 使用一个抽象的r d f 数据接口( i n t e r f a c e ) 访问底层 r d f 服务，并把这个抽象的r d f 数据接口称为r d f r e s o u r c e 。 图2 2 所示是r d f r e s o u r c e 接口，其包含如一fr d f 数据访问方法： r d 爪e s o u r c e + g e t s t a t e m e n t s o + g e t d e f a u l t s t a t e m e n t s o + h a s s t a t e m e n t o + h a s d e f a u l t s t a t e m e n t 0 图2 - 2r d f r e s o u r c e 接口 从具名r d f 图( n a m e dg r a p h ) 读取r d f 三元组的方法： g e t s t a t e m e n t s ( v a l u es u b j ，u r ip r e d ，v a l u eo b j ，u r ig r a p h ) ； 功能：从具名 ( n a m e dg r a p h ) g r a p h 中取出与 匹配的三 元组集，并约定这三个参数有一个或几个为空即意味着它是通配符。 从缺省r d f 图( d e f a u l tg r a p h ) q b 读取r d f 三元组的方法： g e t d e f a u l t s t a t e m e n t s ( v a l u es u b j ，u r ip r e d ，v a l u eo b j ) ； 功能：从缺省图中取出与 匹配的三元组集，这三个参数 缺省时的约定同上。 判断具名r d f 图中是否有指定的三元组的方法。 h a s s t a t e m e n t ( v a l u es u b j ，u r ip r e d ，v a l u eo b j ，u r ig r a p h ) ； 功能：如果具名图g r a p h 中有与 ) g f l 匹配的三元组，则 返回“真”，否则返回“假