（计算机系统结构专业论文）基于sparql的分布式语义查询处理.pdf

浙江大学硕士学位论文 摘要 摘要 在互联网飞速发展的背景下，海量数据是互联网发展的必然结果，而大规模 数据的开放式共享则是网络时代的必然需求。由于系统的定制性和历史原因形成 的数据封闭性、数据孤岛等难题严重阻碍了科学数据的有效共享。 为了解决异质异构数据的集成与共享，浙江大学网格实验室致力于利用语义 与网格技术来解决这个难题，并歼发出d a r t g r i d v 3 语义数据库网格系统。 d a r t c a i d v 3 利用基于语义视图的语义映射和查询重写的思想，解决传统数据 资源语义化的关键问题，实现分布式数据库的语义集成。作为一个发展中的内核 平台，d a r t c a i d v 3 仍有些地方需要完善。首先是提高分布式查询的效率，其次 完善d a r t g r i d 内核对s p a r q l 语法的支持。 本文在分析原有d a r t c r r i d v 3 内核基础上，借用传统分布式数据领域中半连接 操作的思想，提出了基于s p a r q l 的分布式语义查询优化算法，并介绍了具体的 实现过程。同时，对于部分新增s p a r q l 语法的设计和实现，本文也给予了具体 的介绍。 d a r t c n i d v 3 内核是一个坚持面向实际应用的语义数据网格系统。基于v 3 内 核，我们开发了数据库全文检索引擎和w e b 查询处理系统，有效地解决了中医药 领域科学数据库的集成与共享。 关键词：分布式计算，语义技术，s p a r q l ，d a r t g r i d ，异质异构数据集成 浙江大学硕士学位论文 a b s t r a c t i np l e s e r w 圮o fw e b ，o n ec f i t i c a lc h a l l e n g ei sh o wt og l o b a l l yp u b l i s h , s c a m l a s s l y i n t e g r a t ea n dt r a n s p a r e n t l yl o c a t eg e o g r a p h i c a l l yd i s t r i b u t e dd a t a b a s er e s o u r c 圯$ w i t l l s u c h ”o p e n ”s e t t i n g s w 曲s c a l ed a t a b a s ei n t e g r a t i o nh a sb e e no n eo ft h em a i nd n v i n g f o t e e sf o rb o t hs e m a n t i cw 曲r e s e a r c ha n dg r i dd e v e l o p m e n t d a r t g r i d v 3p r o p o s e sas e m a n t i c - b a s e da p p r o a c ha n dp r o v i d e sas e to ft o o l sa n d m i d d l e w a l et os u p p o r tt h eg l o b a ls h a r i n go f d a t 曲a s er e s o u r c e su s i n gg r i da sp l a t f o r m a n dd y n a m i c a l l yi n t e g r a t e si n f o r m a t i o nf r o ma u t o n o m o u sl o c a ld a t a b a s e sm a n a g e db y h e t e r o g e n e o u sd a t a b a s em a n a g e m e n ts y s t e m si nd y n a m i c ，o p e na n dm u l t i i n s t i t u t i o n a l e n v i r o n m e n t f o raq u e r yi n v o l v i n gm o r et h a no n ed a t a b a s e , g l o b a lq u e r yo p t i m i z a t i o ns h o u l d b ep e r f o r m e dt oa c h i e v eg o o do v e r a l ls y s t e mp e r f o r m a n c e b e c a u s ct h e r ea r es o m e f u n d a m e n t a ld i f f e r e n c e sb e t w e e nt r a d i t i o n a ld i s t r i b u t e dd a t a b a s em a n a g e m e n ts y s t e m ( d b m s ) a n dd a t a b a s eg i r ds y s t e m ( d b g s ) w h i c hs t e i n sf r o ma u t o n o m ya n d h e t e r o g e n e i t yo ft h ed a t a b a s en o d e sp a r t i c i p a t i n gi nd b g s q u e r yo p t i m i z a t i o n t e c h n i q u e si nd i s t r i b u t e dd b m s c a nn o tt r i v i a l l ya n dd i r e c t l yb ea p p l i e dt od b g s s i n c ed b g ss u p p o r t st h ed a t a b a s en o d e sd y n a m i c a l l yp a r t i c i p a t ei no rq u i tt h e s y s t e r na n ds e t st a r g e tf o rf a c i n gm o r e ”o p e n ”s e t t i n g so fw 曲e n v i r o n m e n t t h eq u e r y p r o c e s s i n gp r o b l e mi sm u c hm o r ed i f f i c u l ti nd a t a b a s eg r i de n v i r o n m e n tt h a ni n c e n t r a l i z e d , d i s t r i b u t e d , a n dm u l t i d a t a b a s e b u ti ti sv e r yi m p o r t a n tf o rt h es u c c e s so f s y s t e m s p a r o l - b a s e da l g o r i t h mf o rq u e r yo p t i m i z a t i o ni ns e m a n t i cd a t a b a s eg r i di s p r o p o s e db ye x t e n d i n g t h eb e s tk n o w ns e m i j o i n t e c h n i q u e n 托d e s i g na n d i m p l e m e n t a t i o no fs o m es p a r q ls y n t a xt h a ta l en e w l yi n t r o d u c e df o rd a r t g r i d v 3 a l s oh a v eb e e nd i s e u a s e di nd e t a i l t h e 嘶g i n a lm o t i v a t i o no fd e s i g n i n ga n dd e v e l o p i n gd a r t 舒d v 3i st op r o v i d ea p l a t f o r mf o rt r a d i t i o nc h i n e s em e d i c i n ef r c m ) g r i dt h a ts u p p o r t st c ml a n g u a g e k n o w l e d g es t o r a g e ，c o n c e p t - b a s e di n f o r m a t i o nr e t r i e v a la n di n f o r m a t i o ni n t e g r a t i o n w jd e v e l o p e dt h ef i l l lt e x ts e a r c he n g i n ef o rs e m a n t i cd a t a b a s eg r i da n dn o r m a lu s e r s 啪e n t e rt h es y s t e mb yt h ew 曲s i t eo f d a r t s e a m h 1 r t 坞s y s t e r nh a sb e e ns u c c e s s f u l l y d e p l o y e da tc h i n aa c a d e m yo ft 谢i t i o n a lc 1 1 i n e s em e d i c i n ea n dc u r r e n t l yp r o v i d e s a c c e s st oo v e r7 0d a t a b a s e s i n c l u d i n gt c mh e r b a lm e d i c i n ed a t a b a s e s t c m c o m p o u n df o r m u l ad a t a b a s e s ，e l i n i e a ls y m p t o md a t a b a s e s ，t r a d i t i o n a lc h i n e s ed r u g d a t a b a s e s t r a d i t i o n a lt i b e t a nd r u gd a t a b a s e s a n ds oo n k e y w o r d s d i s t r i b u t e dc o m p u t i n g , s e m a n t i ct e c h n o l o g y , s p a r q l ，d a r t g r i d , d a t ai n t e g r a t i o n 新江大学硕士学位论文图目录 图1 1r d f 数据 图目录 图1 2 语义网格的层次9 图2 1 关系r 1 ，r 2 的数据实例 图2 2 半联结操作结果1 4 图2 3d a r t g r i d 语义数据网格架构示意图 图2 4 分布式数据库系统架构示意图1 7 图3 1 基于语义的数据库网格体系架构图1 9 图3 2 语义查询算法流程2 0 图3 3 本体模型 图3 4 语义注册的实例空问 图4 1 跨库查询优化算法的执行流程 图4 3 跨库查询的结果集 图5 1s p a r o l 查询示意图 图5 2 单数据源s p a r q l 支持5 2 图6 1 中医药领域本体论5 9 图6 2 本体论语义注册。5 9 图6 3d a r t q u e r y v 2 0 系统框架6 1 图6 4 关联查询示意图。6 2 图6 5 由结果记录构造关联查询6 3 图6 6 语义浏览6 3 图6 7 标准词提示。6 4 图6 8c n k i 全文关联 图6 9 繁体页面 图6 1 0d a r t s e a r c h v 2 0 系统框架6 6 图6 1 l 专题搜索6 8 图6 1 2 中医药数据加工平台界面 i l l 7 0 浙江大学硕士学位论文表目录 表3 1 实例空间1 的数据表 表目录 表3 1 实例空间2 的数据表 i v 浙江大学硕上学位论文第l 章绪论 第1 章绪论 1 1 应用背景 海量数据是互联网发展的必然结果，而大规模数据的开放式共享则是网络时 代的必然需求。特别的，对于科学数据，如医药、气象、生物等，这种需求已经 出现。基于语义的数掘库网格正是针对这样的需求背景，尤其针对中医药科学研 究领域而进行研制和开发的。 1 1 1 大规模科学数据共享 随着信息和知识经济时代的飞速发展，各科学研究领域都已积累了大量的科 学数据，如医药科技基础数据库群、国家气象基础数据、生物信息学数据库群等。 这些仍在呈指数级不断增长的科学数据，作为不断增值的巨大社会财富，是科技 创新、经济发展和国家安全的重要战略资源；也是政府部门制定政策、进行科学 决策的重要依据；其共享与应用对于增强我国科技创新能力，提高科技整体水平， 减少重复建设，节约人力物力资源，以及促进社会和经济发展都具有十分重要的 意义。 但是目前这些科学数据都存在如下问题： 1 、封闭性：大部分科学数据都以封闭的状态存在，不论从管理层面还是技 术层面都缺乏有效的机制支持其对社会提供开放的数据服务； 2 、数据孤岛；由于大部分科学数据都由不同部门、研究组织或大学独立开 发，完全缺乏统一的整合与集成方式，因而形成一个个彼此分离的“信 息孤岛” 3 、缺乏规范和标准：大部分科学数据的建设都没有相应的国际或国家标准 做指导，从而造成科学数据的深度异质异构性； 4 ，海量大规模；科学数据不断增长，现有的数据管理平台无法支持大数据 量的有效管理，如多备份、动态镜像、实时控制等。 5 、安全与隐私：数据库网格中跨信任域，管理域的数据交换，灵活广泛的共 享，产生新的安全与隐私问题。 这些问题严重阻碍了科学数据的有效共享，如何应用现代信息技术，动态整 合与集成跨区域、跨学科的各部门、各单位的科学数据资源，充分利用国际科学 浙江大学硬七学位论文第1 章绪论 数据，把分散的孤立的封闭的科学数据资源在开放的动态的松耦合的信息共享平 台下实现多层次、全方位、分布式的数据、信息与知识共享是亟待解决的课题。 1 2 技术背景 1 2 1 互联网技术 互联网正日益成为一个庞大的共享信息空间和人们信息交流的基础平台。概 言之，互联网及其相关技术具有如下几点本质特征： 1 开放性( o p e n ) ：任何人在任何地方可以自由的发布、查找和获取他所感 兴趣的信息； 2 普遍性( u n i v e r s a l i t y ) ：互联网基于一些基本的协议族和共同遵循的丌发 和使用模式； 3 松耦合性( l o o s ec o u p l i n g ) ：互联网中的信息实体可以独立存在而互不影 响，它们通过共同协议来实现互操作； 4 动态性( d y n a m i c ) ：互联网不存在一个持久稳定的状态，每一时刻都有新 的信息实体加入和退出，但他们又互不影响；不同时刻的相同查询的结果 可能有很大不同； 5 无界性( u n b o u n d e d ) ：互联网从时空两个角度都具备无界的特点：互联网 信息实体所组成的拓扑结构是无法确定其边界的；同时互联网信息实体的 增长也不会有时效上的边界；这两点直接导致了互联网中的信息搜索与查 询是一种无边界查询。 互联网的上述本质特点直接导致其对人类社会生活的与日俱增的影响力，但 是也正是因为这些特点造成了以下几点新的问题： i 信息海洋；互联网的信息大爆炸使得w e b 拥有海量的、异质的、多型态 的信息资源，如超文本、图片、多媒体、数据库、应用程序( 组件) 等， 大量信息淹没在互联网中，无法有效识别和发现，而成为信息海洋； 2 信息孤岛；互联网中的数据载体或应用程序都具有自主自治特点，由于缺 乏更高层次的协议和标准，而使得现有数据载体之间和互联网程序之问无 法进行无缝的衔接、随意的数据交换和高效的系统集成，从而产生了大量 的信息孤岛； 此外，不断产生的新需求对互联网要求越来越高，如：高精度的信息查询、 动态的协同共享、个性化的智能服务以及广域范围的资源有效管理等。造成当前 互联网现状的本质原因有两个： 2 浙江大学硕士学位论文第1 章绪论 1 当前互联网技术缺乏规范化的信息表达模型和语义支持：互联网上信息资 源深度异质异构，因而迫切需要解决信息资源语义的不一致性问题，实现 在语义上的互联互通，支持无缝的信息集成； 2 缺乏一个统一的体系架构以支持全域范围内的动态虚拟组织的建立：互联 网上信息资源具有无统一控制的“真”分布性，因而，需要研究一个高度 可扩展的体系架构对虚拟的、动态的、层次化的组织进行动态的、有序的 管理： 当前围绕这两个问题，互联网技术有两个主要的研究热点一个是以w 3 c ( w 3 c o r g ) 组织为代表的语义w e b ( s e m a n t i cw e b ) 【l 】；另外一个是以全球网格 论坛( g # o r g ) 为代表的网格计算( g r i dc o m p u t i n g ) 1 2 j 。 语义w e b 为传统的网页添加语义，让机器“理解”网页信息的含意，从而有 助于实现知识共享，并使w e b 能够提供动态的和主动的服务。传统的网页是为了 适应人的阅读需要而设计的，机器仅仅是负责单调的显示，并不能。理解”和处 理网页信息，链接没有明确指定的语义，因而随着互联网的规模的不断扩大，大 规模智能的信息共享与搜索就变得非常困难。在语义w e b 中，我们可以基于语义 对信息进行分类、检索和查询；语义还帮助我们解决了数据交换和系统集成中的 信息不一致问题；此外通过语义链接明确描述的概念以及概念之间的关系可以辅 助用户对信息进行概念层次的浏览。 网格计算是近年来刚刚兴起的分布式计算模型，被称为下一代的i t 架构。网 格计算所解决的核心问题是：“动态虚拟组织( v m u a lo r g a n i z a t i o n ) 中的资源协 同共享( c o o r d i n a t e ds h a r i n g ) 与问题求解( p r o b l e ms o l v i n g ) ”目前，对网格体 系结构的研究正在全球范围内蓬勃地展开，科学家们已经为网格设计了数种体系 模型；其中，o g s a ( o p o ng r i ds e r v i c e a r c h i t e c t u r e ) 3 1 是一种在沙漏( h o u r g l a s s ) 模型的基础上提出的最新模型。o g s a 以“服务”概念为中心，靠近于现有的成 熟w e bs e r v i c e 技术，并侧重于商业方面的实际应用。 综上所述，当今的互联网技术要能支持如前所述的大规模数据共享的应用需 求，需要从如下几个方面入手： 1 以本体论为基础的信息资源的表达和组织 深度共享首先需要解决资源的描述和表达问题，比如传统的元数据研究和元 计算都试图从提升资源的描述能力来支持高层次的计算。但是简单的元计算是不 够的，基于本体论的信息表达能实现各种信息资源在高层次的语义表达和规范化 组织，从而能为实现一个语义上互通、逻辑上一致的数据库网格提供信息的描述 浙江大学硕士学位论文第1 章绪论 基础。 2 大规模虚拟组织的协同共享与动态有序管理 互联网是一个超大规模的分布式系统，它既不能采用简单的c s 架构也不能 完全依赖复杂度很难控制的p 2 p 模式。所以需要研究规模可扩展的数据库网格架 构和可动态组合的流程服务机制，以支持虚拟组织的动态分组和有序管理，支持 虚拟组织问的海量级大规模信息共享与虚拟服务之间的分布式动态流程协同。 3 多层次的个性化服务 数据库网格应该提供层次化的服务，如资源级服务、协同级服务、功能级服 务，以满足不同级别的用户需求，比如系统级、程序员级和普遥用户级所需要的 服务就完全不同。 1 2 2 分布式数据库技术 分布式数据库系统的各种模型基于两个基本假设： l 、数据库的位置透明性：用户事先不知道数据源的位置和内容信息，需要 选择信息源； 2 、数据库的自治性：各数据库在模式设计上独立，造成语义冲突，要实现语 义上的互操作必须解决不同模式问的语义冲突。 比如，传统的m u l t i d a t a b a s e 通过建立全局模式解决这两个问题。全局模式集 成了各本地模式，展示给用户语义一致的全局视图，并通过人工介入进行语义冲 突识别，相关性判断。尽管通过全局模式的定义及与本地模式的映射，用户能够 获得位置透明、语义统一的数据访问服务，但模式集成的方法不适应大规模的数 据库群，因为要从大量自治数据库的语义贫乏的模式结构表示中寻找它们之间的 相关性而形成逻辑统一的模式是很困难的。此外全局模式必须随任何一个成员数 据库局部模式的更新，加入或退出而更新，从而影响全局模式的可扩展性和可用 性。 而传统的f e d e r a t e dd a t a b a s e ，即联邦数据库系统同样也是采用模式集成的方 法解决不同本地模式之间的语义互操作问题，不同点在于不是采用一个集中的控 制单元维护统一全局模式，模式的集成是由各对等成员数据库根据需要自行决 定：每个数据库存在一个导出模式，划定了该数据库能够提供给联邦的本地数据； 还存在一个导入模式，选择性地集成了从其他若干联邦成员的导出模式中获得的 模式信息。这样做的好处在于同样实现了数据访问的位置透明性；此外模式集成 具有选择性，从而省略了与用户需求无关的数据源，提高了效率；同时某一数据 4 浙江人学硕士学位论文第1 章绪论 库模式上的变动只会影响与之有导入关系的联邦成员，而不至于影响整个联邦的 可用性缺点同样是不适应于大规模的数据库群，因为每个数据库管理者要遍历 所有的联邦伙伴的模式结构，从中寻找符合本地用户兴趣的数据源面临着与 m u l t i - d a t a b a s e 全局模式的维护同样棘手的问题。 通过以上分析，并结合互联网的特点，可以得出三个结论： 1 、共享必须解决语义问题，并需要支持在语义层直接对数据库进行各种操作 要通过模式集成的方法解决模式语义互操作问题，必须想方设法增强各 模式的语义自描述能力，为模式集成算法提供必要的前提条件。借助本体论 描述数据库关系模型语义是目前流行的一种方法，这种方法认为具有语义互 操作需求的数据之间必然都与某个领域相关，而本体论描述的是领域的概念 模型，定义了领域存在的一系列概念同时定义了这些概念之间的联系，如果 各数据库能够各自模式中的属性映射到各个领域概念，那么可以将本体论作 为桥梁将沟通各数据库，解决它们之问的语义冲突。 借用本体论表达数据库语义的好处在于，将原有一部分模式集成器承担 的语义冲突分析的工作下放到各数据库完成，不仅减轻了负担而且对于语义 的定位更加准确，语义集成器可以相对容易地判断各待集成数据库的相关关 系，进行模式重构 2 、必须提供一种有效的机制支持数据库在互联网中的发布与发现 在m u l f l - a t a b a s e 下用户通过浏览全局模式代表的信息空间来实现，在 f e d e r a t e d - d a t a b a s e 中数据库必须代替用户寻找与用户兴趣相关的联邦伙伴， 无论何种方式都没有提供十分有效的机制帮助用户准确快速地定位数据源。 本体论的引入可以缓解这一问题，用户可以针对本体论描述的领域模型 事先制定需求模式，可以同步地检索可获得的( 联邦内部的或者是 m u l t i d a t a b a s e 的管辖范围内的) 局部模式，或者通过征订的方式当一个新的 满足用户需求的模式产生时，异步地返回。 3 ，必须要定义一组基于互联网基本协议的数据库协议 互联网必须要在协议层解决问题，在互联网环境下实现数据库资源的共 享也必须在协议层解决问题。不仅如此，由于本体论的引入，这些协议的定 义也需要考虑本体论的因素，在这种情况下，协议的定义更加复杂。因而， 如何基于已有的网格协议定义和实旖适合于数据库的协议是一个需要解决的 难题。 总之，w 曲本体论的引入既增强了数据库模式的语义表达，又简化了语义冲 5 浙江大学硕上学位论文第l 章绪论 突的化解过程，也为建立快速准确的数据源索引提供了便利。尽管如此，这种方 法仍然有很多棘手的问题需要解决，如要求所有成员数据库遵循某一标准的本体 论违背了数据库成员的表达自治性( 这不符合互联网的本质要求) ；此外建立一 个完整的，能够确保每个与该领域相关的数据库模式都能正确的映射的本体论也 相当困难。一种改良的方法是允许不同数据源映射不同的本体论，通过本体论之 间的交互协议达到数据库模式之间的一致化，目前代表性的方法有多本体论方法 合混合本体论方法，这些研究仍停留在理论阶段，许多实际问题无法解决。 基于语义的数据库搜索引擎基于对传统分布式数据库系统的认识，并基于两 大新的互联网技术：网格计算和语义万维网，建立了一种新的数据库资源的共享 与集成模式，在一定程度上解决了上述问题。 1 2 3 语义技术 1 2 1 1 本体论 本体论( o n t o l o g y ) 是一个哲学上的概念，是客观存在的一个系统的解释或 说明，关心的是客观现实的抽象本质。在计算机人工智能界，最早给出o n t o l o g y 定义的是n e c h e s ，f i k e s 等人( 1 9 9 1 年) ，他们将o n t o l o g y 定义为“给出构成 相关领域词汇的基本术语和关系，及利用这些术语和关系构成的规定这些词汇外 延的规则的定义”【4 】 1 9 9 3 年，g r u b e r 给出了o n t o l o g y 的一个最为流行的定义，也是比较简单的 定义“as p e c i f i c a t i o no fac o n c e p t u a l i z a t i o n ”，可以理解为“对某种 概念化体系的规范说明”。其中有两层意义：一是先要对某个领域进行抽象、归 纳，即把这一领域概念化；二是再对这一概念化的结果用一种人、计算机、代理 都可以理解的通用规范表达出来，表达出来后就形成了一个o n t o l o g y g r u b e r 提出的另一种比较详细的表达：。e x p l i c i tf o r m a ls p e c i f i c a t i o n so ft h et e r m s i nt h ed o m a i na n dr e l a t i o n sa m o n gt h e m ”，即o n t o l o g y 是对某一领域中术语 及术语之间关系的规范而明确的说明f 5 】。 本体的本质是关于目标领域的概念模型，它以清晰、一致、无歧义的方式表 达领域中概念与概念之间的关系。目前，本体被越来越广泛地应用于信息检索， 知识共享和机器推理等计算机领域。 1 2 1 2 资源描述框架 资源描述框架( 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 ) 6 1 川是一个用于 6 浙江大学硕上学位论文第1 章绪论 表达关于万维网( w o f l dw i d cw e b ) 上的资源的信息的语言它专门用于表达关于 w e b 资源的元数据，比如w e b 页面的标题、作者和修改时问。w e b 文档的版权和 许可信息，某个被共享资源的可用计划表等。然而，将“w e b 资源( w e br e s o u r c e ) ” 这一概念一般化后，r d f 可被用于表达关于任何可在w e b 上被标识的事物的信 息，即使有时它们不能被直接从w 曲上获取。比如关于一个在线购物机构的某项 产品的信息( 例如关于规格、价格和可用性信息) ，或者是关于一个w e b 用户在 信息递送方面的偏好的描述。 r d f 基于这样的思想：用w e b 标识符( 称作统一资源标识符，u n i f o r m r e s o u r c ei d e n t i f i e r s 或u r i s ) 来标识事物，用简单的属性( p r o p e r t y ) 及属性值来 描述资源。这使得r d f 可以将一个或多个关于资源的简单陈述表示为一个由结点 和弧组成的图( g r a p h ) ，其中的结点和弧代表资源、属性或属性值。为了让讨论 显得尽量具体一些，下面给出一个r d f 的实例，它表达的意思是。有一个人由 h t t p ：w w w w 3 o r g p e o p l e e m c o n t a c t # m e 标识。他的名字是e r i cm i l l e r , 他的电子 邮件地址是e m w 3 o r g , 他的头衔是阢” 图1 1r d f 数据 7 浙江大学硕上学位论文 第1 章绪论 r d f 提供了一种基于x m l 的语法( 称为r d f x m l ) 用于保存和交换r d f 图。图1 1 所示的r d f 用r d f x m l 来书写的话就像下面的例l 这样： 例l ：一段描述e r i cm i l l e r 的r d f ，) 洲l e r i cm i l l e r c o n t a c t ：m a i l b o xr d f ：r e s o u r c e = ”m a i l t o ：e m w 3 o r g ”胁 d r 就其本质而言，一个r d f 图包含多个资源描述，而一个资源描述是由多个语 句构成，一个语句是由资源、属性类型、属性值构成的三元组，表示资源具有的 一个属性。资源描述中的语句可以对应于自然语言的语句，资源对应于自然语言 中的主语，属性类型对应于谓语，属性值对应于宾语。 1 2 1 3 语义w e b 语义w e b 是w e b 的扩展，它通过规范化的定义信息所包含的语义，来更好的 帮助计算机与人之间进行交互 w e b 的发明者t i mb e r n e r s - l e e 描述了互联网的两个基本功能，一是人与人 之间的信息交流每个人都可以自由的发布和浏览信息：二是作为一个可供机 器自动处理的信息空间。现在的w e b 只提供给人发布和浏览信息的基础平台，而 在机器自动处理方面做的工作微乎其微。语义w e b 最早的目标就是要让w e b 上面 发布的信息可以自动被智能代理处理 语义w e b 的研究最早可以追溯到t a r y l a n d 大学的s h o e 项目。在1 9 9 6 年s h o e 项目通过在h t m l 嵌入代表本体论的扩展标签，演示了如何通过向w e b 文档添加 语义信息来增强其被处理的能力。与此同时w 3 c 也建立了一个专门的元数据工作 组来研究如何通过向w e b 文档中添加扩展的元数据信息来提高其可管理性和可发 现性。w 3 c 的这个工作组最终演变成现在的s e m a n t i cw e bt 作组，并将定义了 r d f 为标准的w e b 语义表达模型并与2 0 0 0 年举办了第一界国际语义w e b 学术会 议，从此，关于语义w e b 的研究在全球范围来如火如荼的展开。随后，由于r d f 的表达能力很弱，d a r p a 定义了基于r d f 的d a i i l 语言，e u 定义了相类似的o i l 浙江大学顿 学位论文第1 章绪论 语言。这两门语言最后合并成d a m l + 0 i l ，并最终演变成了w 3 c 本体论工作组的标 准本体论定义语言o w l 。事实上，o w l 是传统知识表达系统描述逻辑的w e b 版本。 语义网结合了r d f 和o n t o l o g y 两种技术手段，是用计算机语言表述客观世界 模型的有力工具，图1 2 展示了语义网各个层次的语义表达能力【科。 一x m l 层( e x t e n s i b l em a r k u pl a n g u a g e 可扩展标记语言1 作为语法层 r d f 层( 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 资源描述框架) 作为数据层 本体层( o n t o l o g y ) 作为语义层 一逻辑层( l o g i c ) 提供了基于本体层上的智能推理规则 一证据层( p r o o f ) 支持代理间通讯的证据交换。 图1 2 语义网格的层次 1 2 1 4s p a r q l 查询语言 s p a r q l 是一种r d f 查询语言。它由w o r l dw i d ew e bc o n s o r t i u m 的d a t a a c c e s st 作组设计，目的是为r d f 数据提供一种自然的查询语言。s p a r q l 主 要用于查询r d f 格式的数据【9 1 。 1 3 论文结构 本文的第二章介绍了分布式数据库系统中的查询优化方法，着重分析了半联 结算法，同时介绍了基于语义的分布式查询优化策略。 第三章分析d a r t g r i d v 3 语义网格在进行分布式查询时的性能瓶颈，并提出了 9 浙江大学磺士学位论文第l 章绪论 分布式查询的优化方案。 第四章提出跨库查询优化算法，主要解决涉及多个数据源的分布式查询的性 能优化问题。 第五章介绍d a r t g r i d v 3 对于s p a r q l 查询语法的支持和实现。 第六章介绍d a r t g r i d v 3 语义网格内核在中医药领域的相关应用，包括中医药 搜索和中医药本体查询，以及中医药数据加工平台。 第七章介绍d a n g r i d v 3 语义网格内核未来的发展方向。 1 0 浙江大学顾上学位论文第2 章分布式查询技术分析 第2 章分布式查询技术分析 2 1 传统分布式数据库查询 数据库系统研究的一个主要目标是尽可能地对用户隐藏数据结构的细节，使 数据库系统的应用更加面向领域。分布式数据库系统的主要目标之一是隐藏分布 式环境的细节，是系统使用起来更加简单、有效由于数据在物理上分布地存储， 当一个查询涉及到多个物理站点时，有可能存在多种查询方案，这时就需要根据 某种策略选择查询代价最小( 或者尽可能小) 的查询方案。所谓查询优化，就是 要保证查询总开销和总响应时白j 最小。 2 1 1 查询代价分析和基本优化策略 在分布式查询处理技术中，查询的优化基本包括两种类型：针对查询响应时 间的优化和针对查询资源开销的优化。查询的响应时间有两种计算标准：种标 准是指查询开始到获得第一个结果之间的时间，另一种标准是指指查询开始到获 得全部结果之间的时间数据库查询的响应时间对于整个软件系统可用性和用户 友好性具有举足轻重的影响，特别是一些需要处理大数据量的实时的商业应用软 件。针对查询响应时阃的优化的目标是尽量减少查询的响应时间，而不计较系统 资源的消耗。在集中式数据库中，查询的响应时间主要取决于以下几个因素【l o j ： ( 1 ) c p u ，包括查询计划解析的时间和针对数据进行运算处理的时间， 比如排序和字符串处理。 ( 2 ) 加l 通道，数据二级存储设备( 磁盘，磁带) 读入到主存中的时间 在分布式数据库系统中，查询的响应时间还取决于第三个因素：网络通信， 即查询的中间数据在网络中的传输时间。特别是在互联网环境下，由于t c p i p 路由的不确定性以及数据报丢失，网络拥塞等因素，分布式查询的时间很大一部 分被消耗在网络通信上面。 响应时间方面的优化主要是利用分布式数据库系统的并行性，网络环境中的 多处理机提供了并行处理能力。同时，关键路径上的局部查询，即对全局响应时 间起决定作用的那部分查询，尤其应该重视。 针对查询资源开销的优化的目标是，使查询执行所使用的系统资源( 总和) 尽可能的少，从而降低系统开销，整个系统的开销可以从单个系统资源的开销表 浙江大学硕士学位论文第2 章分布式查询技术分析 达式中推算出来。在集中式数据库中，查询执行所消耗的系统资源包括：c p u ， 系统主存，f o 通道。在分布式数据库中，查询所消耗的系统资源则包括；c p u ， 系统主存，i o 通道，通信网络带宽。其中，通信网络带宽往往是系统的瓶颈资 源，因为在互联网环境下，网络带宽是被众多用户分享的，而且网络流量波动剧 烈。另一方面，分布式环境下的多处理机资源则大大降低了分布式查询的对单机 c p u 和内存资源的依赖，当然这需要一个足够好的调度算法以平衡各个处理机的 负载。尽管两种优化类型拥有相同的优化对象，比如：c p u ，i o 和网络通信， 但两者侧重的方面是不同的：针对查询响应时问优化的目标是“最快”，而针对查 询资源开销优化的目标是“最便宜” 在分布式数据库系统中，同一查询会有多种执行方式( 即具有不同的查询计 划) 。查询执行的方式不同，其系统的资源消耗及响应时间也不相同，因此需要 查询优化器选择最好的查询执行方式查询优化尽量使冗余的不必要的操作减为 最少，选择最便宜或最快的方法执行数据库操作，最好的调度执行顺序，并尽可 能的采用标准的可共享的子方法。查询优化有两种基本方法：第一是查询转化， 即以不同的顺序执行关系操作，如联结和投影操作。第二是查询映射，即使用一 系列高效的算法来存取各种设备( 如采用索引) 和实现关系操作。在分布式系统 中，查询优化还必须充分利用并行性和尽量减少网络数据的传输。 2 1 2 分布式查询优化方法 2 1 2 1 等价转换 s q l 查询同关系代数表达式序列是等价的。一个s q l 查询可以转化为等价 的关系代数表达式序列，而一个关系代数表达式序列也可以转化为等价的s q l 查询。如果在两个关系代数表达式中，对于每一个命名关系采用与其相同的外延 ( 数据类型相同的值集) 进行替换，其计算结果相同，则称这两个关系代数表达 式是等价的。等价转换的基本思想是：利用关系代数中的等价转换关系，把原始 s q l 查询转化为一个等价的新的s q l 查询，在这个转化的过程中改变数据库系 统操作的执行顺序，从而达到节省系统资源或者减小响应时间的目的。在关系代 数中，主要可以运用以下几个等价定型1 1 1 ： 1 交换律 当条件f 只涉及到关系a 中的属性时，有 6f ( a ( r ) ) = 兀a ( 6f ( r ) ) ( 2 - 1 ) 1 2 浙江大学硕上学位论文第2 章分布式查询技术分析 2 结合律 ( r s ) 一t = r 一( s t ) 3 分配律 6f ( r s ) = 6 f ( r ) 6f ( s ) 6f ( r v s ) = 6f ( r ) v6f ( s ) 6f ( r o o s ) = 8 f ( r ) 一s f ( r a o s ) = f ( r ) s ( 2 - 2 ) ( 2 - 3 ) ( 2 - 4 ) ( 2 - 5 ) ( 2 - 6 ) 在分布式操作系统中，查询优化使用的一条重要规则是：先执行投影和选择 操作，而联结等二元操作在其后执行。这条规则能够最大程度地避免大块的连接 数据在分布节点之间传送。 2 1 2 2s d d - 1 半联结算法 在所有基本的关系运算( s e l e c t , j o i n 和p r o j e c t ) 中，j o i n 运算无论是 在执行时间上还是在系统资源开销上都是最大的。当j o i n 的列上没有建立索引 时，数据库系统需要对参与j o i n 操作的两个关系表的所有存储页面的所有组合 都进行匹配和搜索。因此与其它的关系运算相比较，j o i n 运算引起的页交换更多， 而也交换对于响应时间和执行代价都是重要的影响因素。但是在许多情况下，有 些页面之间的匹配和搜索是没有必要的，例如当一个参与j o i n 运算的关系中有 一个受到p r o j e c t 或者s e l e c t 运算的约束时，就会出现这种情况。如果采用 2 1 2 1 节中提到的优化方法：即先执行p r o j e c t 和s e l e c t 操作，而后执行二 元的j o i n 操作。这样可以最大程度地减少需要匹配的页面数。 j o i n 操作的执行代价是如此之大，人们很早就开始研究j o i n 操作的优化方 法，其中s d d - 1 半联结算法( s d d - 1s e m i j o i n ) 就是其中很有效的方法之一 s d d - 1 是美国计算机公司( c o m p u t e rc o r p o r a t i o no fa m e r i c a ) 研制的第一个分 布式数据库管理系统的原型，它是在1 9 7 6 年到1 9 7 8 年间设计的，并于1 9 7 9 年 在d e c - o i 和d e c - 0 2 两个型号的计算机上实现，而s d d - 1 半联结算法也是在这个 系统中设计和实现的【1 2 1 1 1 3 】【1 4 1 。 半连接( s 酬i j o i n ) 操作 半连接操作的基本思想是：将两个关系进行联结以后，再将其结果在其中一 个关系的属