（计算机软件与理论专业论文）对等网络环境下基于语义的异构数据管理模型.pdf

摘要 随着对等网络技术的广泛应用，对等网络环境下的数据管理成为研究热点 它包括三个关键问题： ( 1 ) 如何在大规模网络环境下，基于语义，统一、规范、有效地组织和管理分布 的数据资源和服务资源。 ( 2 ) 如何在大规模网络环境下，基于语义，准确、有效地把查询请求传递给相关 节点，避免产生过大的网络负载 ( 3 ) 如何在大规模网络环境下，动态地集成各节点返回的异构数据，为用户和应 用提供统一视图。 本论文针对以上三个关键问题，提出对等网络环境下基于语义的异构数据管 理模型。 主要创新点包括： ( 1 ) 提出资源空间模型和结构化对等网络c h o r d 模型相结合的新资源组织模型， 统一、规范、有效地组织和管理分布的数据资源。经实验验证：与传统的结 构化对等网络c h o r d 模型相比较，本论文所提出的模型支持分类语义查询、 灵活性好、系统开销小 ( 2 ) 提出基于对等语义链网络的资源组织模型和路由方法，通过数据和服务两个 层次的语义链来建立各节点数据模式问和服务间的语义关系，提高路由效率。 经实验验证：与泛洪和随机选择等非结构化对等网络路由方法相比，基于对 等语义链的路由方法的查询效果( 召回率) 接近泛洪方法，但系统响应查询 所产生的消息数目最小。 ( 3 ) 提出基于语义的异构数据集成模型，通过建立各节点数据模式间的映射和查 询变换，解决各数据源的语义异构和结构异构问题，动态地集成对等网络中 分布的异构数据，为用户和应用需求提供统一视图。 关键词：对等网络；资源空间模型；对等语义链网络模型；语义；异构数据管理 s e m a n t i c 。b a s e dp 2 pm o d e lf o rh e t e r o g e n e o u sd a t am a n a g e m e n t j i el i u ( c o m p u t e rs o f t w a r ea n d t h e o r y ) d i r e c t e db yp r o f e s s o rh a i z h u g e w i t ht h ep o p u l a r i t yo fp e e r - t o - p e e r ( p 2 p ) s y s t e m s ，p e e rd a t am a n a g e m e n ts y s t e m ( p d m s ) h a sb e c o m eap r o m i s i n ga r e ai nt h e 如t u r ei n t e r c o n n e e t i o ne n v i r o n m e n t t h r e ek e yi s s u e sr e l a t e dt op d m s sa r e ： ( 1 ) e f f i c i e n t l yo r g a n i z i n ga n dm a n a g i n gd i s t r i b u t e dr e s o u r c e si np 2 pn e t w o r k s ( 2 ) a c c u r a t e l ya n de f f i c i e n t l yr o u t i n gq u e r i e sf r o mt h ep e e ri n i t i a t i n gt h eq u e r yt o t h er e l e v a n tp e e r st oa v o i dn e t w o r k f l o o d i n g ( 3 ) i n t e g r a t i n gh e t e r o g e n e o u sd a t ar e t u r n e df r o md i f f e r e n tp e e r st op r o v i d eu s e r s a n do t h e rp e e r sw i t hau n i f o r md a t au s a g em o d e t or e s o l v et h ea b o v et h r e ek e yi s s u e s t h i sd i s s e r t a t i o np r o p o s e sas e m a n t i c - b a s e d p 2 pm o d e l t h es i g n i f i c a n tc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r e ： ( 1 ) t h er - c h o r dm o d e lb yd e p l o y i n gt h er e s o u r c es p a c em o d e la b o v et h ec h o r d o v e r l a y f o ru n i f o r m l y , n o r m a l l ya n d e f f e c t i v e l yo r g a n i z i n ga n dm a n a g i n g r e s o u r c e sd i s t r i b u t e di np 2 pn e t w o r k s e x p e r i m e n t ss h o wt h a tt h e p r o p o s e d m o d e li sm o r ef l e x i b l et os u p p o r ts e m a n t i c - b a s e dq u e r i e sa n dt h ea v e r a g en u m b e r o fn o d e si n v o l v e dt oa n s w e rq u e r i e si sq u i t ef e w e rt h a nt h a to ft h ec h o r d a p p r o a c h ( 2 ) t h ep e e r - t o p e e rs e m a n t i cl i n kn e t w o r km o d e lb yu s i n gs e m a n t i cd a t al i n k sa n d s e m a n t i cs e r v i c el i n k st oe s t a b l i s ht h es e m a n t i c r e l a t i o n s h i p b e t w e e np e e r s c h e m a sa n db e t w e e np e e rs e r v i c e s e x p e r i m e n t ss h o wt h a tc o m p a r e dw i t ht h e f l o o d i n ga n dt h er a n d o mw a l kr o u t i n ga p p r o a c h e s ，t h er e c a l lr a t eo ft h ep r o p o s e d a p p r o a c hi sc l o s et ot h a to ft h ef l o o d i n ga p p r o a c h ，b u tt h ea v e r a g en u m b e ro f m e s s a g e sg e n e r a t e db yt h ep r o p o s e da p p r o a c ht oa n s w e rq u e r i e si st h ef e w e s to f t h et h r e e ( 3 ) t h es e m a n t i c - b a s e dh e t e r o g e n e o u sd a t ai n t e g r a t i o nm o d e l 。w h i c hs o l v e st h e p r o b l e mo fs e m a n t i ch e t e r o g e n e i t ya n ds t r u c t u r a lh e t e r o g e n e i t yb ys c h e m a m a p p i n g a n dq u e r yr e f o r m u l a t i o nt oi n t e g r a t et h eh e t e r o g e n e o u sd a t aa n dp r o v i d e u s e r sa n da p p l i c a t i o n sw i t hau n i f o r i l lv i e w k e y w o r d s ：h e t e r o g e n e o u sd a t am a n a g e m e n t , p e e r - t o p e e rn e t w o r k s ，p e e r - t o p e e r s e m a n t i cl i n kn e t w o r km o d e l ，r e s o u r c es p a c em o d e l ，s e m a n t i c s i i l 对等嘲络环境下基丁语义的斤构数据管理模犁；图h 录 图目录 图1 i 对等网络数据管理面i 陶构挑战。4 图2 1 资源空问模型构成1 5 图2 2 三维资源空间模型示例1 5 图2 3 知识空间和知识使用机制2 3 图3 1 资源组织模型r - c h o r d 2 7 图3 2 基于对等语义链网络的资源组织模型2 8 图3 3 单一语义映像资源组织模型s s e l 图3 4 非结构化和结构化资源空间视图3 3 图3 5 资源空间字典和资源空问视图的数据模式3 3 图3 6 对等语义链网络数据管理模块3 5 图3 7 对等语义链网络服务管理模块3 6 图3 8 对等语义链网络定义工具3 9 图3 9 后缀t i l e 和后缀树举例4 6 图3 1 0 “s e m a n t i cw e bs e m a n t i cg r i dk n o w l e d g eg r i d x f f 应的后缀树4 7 图3 1 lc h o r d 协议扩展4 8 图4 1 在c h o r d 、资源空间和对等语义链网络三个层次上的相邻节点。5 2 图4 2 基于语义的路由方法总体结构图。5 3 图4 3 节点结构相似度算法5 6 图4 4 数据语义链路由规则 图4 5 对等语义链网络模糊评价系统结构图 图4 6 对等语义链网络评价标准生成 图4 7 对等语义链网络客观评价标准 图4 8 模糊隶属度函数 图4 9 公式( 4 2 1 ) q ，参数 图4 1 0 节点存贮的x m l 数据 6 1 。6 2 6 3 6 5 图4 1l 结构化对等网络c h o r d 层支持的查询类型 图5 i 定义语义块和映射语义块的用户界面 图5 2 数据源a c ms i g m o d 和v l d b 的数据模式 图5 3 资源空间和资源空间视图更新过程 6 8 6 8 7 8 7 8 8 4 图6 1 资源空问中的论文分布情况8 7 图6 2 响应查询所涉及的目标数据节点个数比较8 8 图6 3 响应查询对所涉及的目标数据节点的访问总次数比较8 9 图6 4 响应查询对所涉及的所有节点的访问总次数比较9 0 图6 5 对等语义链网络实验环境 9 1 图6 6 泛洪，对等语义链和随机选抒路由方法召回率比较( t t l 产5 ) 9 2 图6 7 泛洪、对等语义链和随机选择路由方法响应查询的消息数比较f r r l = 5 ) 9 3 图6 8 对等语义链网络动态性能( t t l = 5 ) 9 4 1 0 1 图7 1 基于语义的对等网络数据管理模型s s e l 对等1 4 络t 4 , 境下基丁语义的斤构数据管理模刭：表目录 表目录 表2 1 结构化对等网络c a n ，c h o r d 、p a s t r y 和t a p e s t r y 的性能比较1 0 表3 i 资源空间层操作列表3 0 表3 2 对等语义链网络操作列表3 7 表3 3 数据语义链自动发现规则3 8 表3 4 数据语义链推理规则4 3 表3 5 服务语义链推理规则“ 表3 6 基于后缀树的c h o r d 协议操作接口4 9 表5 1 数据源s i g m o d 和v l d b 数据模式的结点映射7 5 表5 2 数据源s i g m o d 和v l d b 数据模式的语义块映射7 6 表5 3 数据源s i g m o d 和v l d b 数据模式的路径映射8 0 表6 1 对等网络环境下基于语义的异构数据管理模型s s e l 和相关工作比较 表6 2 资源空间模型、对等语义链网络模型和c h o r d 模型相结合的优点 x i 9 4 9 8 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名： 锄丧 日期：2 0 0 5 - 0 4 - 0 1 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者繇刭l 老新躲躐泐吼2 0 0 5 - 0 4 - 0 1 1 1 研究背景及意义 第一章引言 随着互联网的广泛应用，分布式计算在网格计算( g r i dc o m p u t i n g ) 和对等计 算( p e e r - t o - p e e rc o m p u t i n g ) 两个领域得到迅速发展。 网格技术通过高性能计算环境实现全球分布资源的共享、管理、协同和控制。 网格已从计算网格发展成为面向服务的网格【3 4 ，3 5 1 。 对等计算为用户提供了一种新的分布式计算模型，用户可以通过点对点的方 式直接连接到其它用户的计算机，进行文件共享与交换其最显著的特点是网络 采用自组织的方式，不需要中央服务器管理各节点，各节点既可以作为服务器为 其它节点提供服务，又可以作为客户端使用其它节点提供的服务 一个对等网络系统( p e e r - t o - p e e rs y s t e m ) 由大量节点组成，它们以完全分布 的方式交换数据和服务网络节点具有自治、动态和异构等特点【8 8 】。 早期的对等网络系统的设计目标是用于文件共享。在对等网络系统中，资源 分布于多个自治的节点上。通常一个对等网络系统具有如下特性：节点动态加入 和退出，数据和模式的局部性、自组织和自优化等。 随着p 2 p 系统的广泛应用。对等网络环境下的数据管理系统( p e e rd a t a m a n a g e m e n ts y s t e m p d m s ) 成为研究热点通常一个对等网络数据管理系统 由一组节点组成，每个节点有自己的x m l 数据模式或关系数据模式。虽然传统 的分布式数据管理已经有很好的解决方案 1 0 9 ，但现有的对等网络系统缺乏传 统数据库所能提供的数据管理能力，大规模数据共享仍然是有待解决的重要问题 2 4 ，4 0 ，4 1 ，4 6 ，5 5 ，8 6 。 对等网络环境下的数据管理具有以下新的特点： ( 1 ) 大规模为了实现资源共享，网络中往往存在大量节点，各节点共享大 量数据。 ( 2 ) 分布性和分散性数据分散在不同节点，查询请求需要多个节点共同响 应 ( 3 ) 自治性无需中央服务器的集中控制。 ( 4 ) 异构性各数据源节点之间存在数据模型、语义和结构差异。 ( 5 ) 动态性各节点频繁加入和退出网络 对等嘲络环境下基丁语义的畀构数据管理模犁 语义互联网是对当前w e b 的一种扩展，其目标是通过使用本体和标记语言 等，如：x m l 、r d f 和d a m l ，使w e b 资源的内容能被机器理解，为用户提供 智能索引、基于语义的内容检索和知识管理等智能服务【4 7 。为了解决目前w e b 缺乏语义信息的问题。2 0 0 1 年5 月啊mb e m e r s l e e 等学者在s c i e n t i f i c a m e r i c a n 上发表了叮h es e m a n t i cw e b ”一文【8 】，系统地描绘了语义互联网，成为语义互联 网领域发展史上的重要文献。 虽然目前p 2 p 系统已在文件共享、科学计算、协同工作等方面有广泛应用， 成为国际上学术界和工业界普遍关注的热点，但是从数据有效管理的角度来看， 现有的对等网络环境下的数据管理方法较难全面反映网络中各节点数据间和服 务问的语义关系。为了对数据和服务进行有效管理。首先必须建立基于语义的对 等网络模型，语义将成为提供有效数据管理的主要依据。在对等网络环境下研究 如何基于语义实现资源的有效组织和管理，如何基于语义支持高层复杂应用，具 有重要的理论意义和应用价值 从国家和社会信息化发展需要来看，建立对等网络环境下基于语义的异构数 据管理模型将有助于充分利用现有的网络资源，建立一个统一、有效的信息共享 和管理的模型，方法和平台，消除信息孤岛，实现动态网络环境下异构数据集成 和信息有效利用，相关研究成果将在分布式知识共享、协同工作、电子科学 ( e - s c i e n c e ) 、电子商务( e b u s i n e s s ) 、电子政务( e - g o v e r n m e n t ) 等领域具有广泛的应 用前景。 1 2 对等网络环境下数据管理的研究进展 根据网络拓扑结构，现有的对等网络系统主要包括三大类4 ，1 0 0 ： ( 1 ) 非结构化对等网络系统，如g n u t e l l a ，节点可以任意地加入和离开网络，同 时可以与任何一个节点相连接。 ( 2 ) 结构化对等网络系统，如c a n ( c o n t e n t a d d r e s s a b l en e t w o r k ) 【9 5 、c h o r d 【i 0 8 、p a s t r y 【9 9 1 和t a p e s t r y 1 2 9 ，节点以固定的结构组织起来，节点之间 的连接按某种协议确定，数据的存放由节点的连接决定 ( 3 ) 混合对等网络系统，如n a p s t e r ，提供一个集中式的目录服务，但节点间的文 件传送采用分散式管理。 文献 5 8 1 从分散程度、网络拓扑结构、信息在节点的分布情况和各节点存贮 数掘的类型这四个角度对现有的对等网络数据管理系统进行了分类。 根据对等网络拓扑结构，现有的数据管理方法主要包括非结构化和结构化两 大类。其中，非结构化对等网络数据管理方法主要包括： ( 1 ) 资源管理模型 采用关系数据模型【9 ，4 2 、e c a ( e v e n tc o n d i t i o n a c t i o n ) 规, 1 j 5 4 】管理 第一节引二 对等网络中各数据源节点的方式 基于超节点的p 2 p 资源管理模型，即网络中的每个节点连接到一个相关 的超节点，超节点负责聚集相关节点，维护路由索引，将用户查询请求 发送给相应的节点或超节点，集成相关信息 7 0 ，8 2 1 ( 2 ) 查询路由方法 根据查询结果判断节点语义相关性的路由方法【1 1 。 基于语义的层次化文档索引方法 1 0 4 。 基于b l o o m 算法的数据源索引方法 1 4 ，5 7 。 ( 3 ) 查询变换算法 g a v ( g l o b a la sv i e w ) 和l a v c l o c a la sv i e w ) 相结合的查询变换算法 【4 3 】 查询优化策略 1 1 2 。 采用局部关系模型l r m ( 1 0 c a lr e l a t i o n a lm o d e l ) 把用户查询请求根据局 部节点的模式变换成局部查询的方法【9 】。 基于一阶逻辑和认知逻辑的p 2 p 数据源节点映射方法【6 0 】。 ( 4 ) 原型系统 基于对等网络的分布式数据共享和管理系统1 8 5 。 基于本体的对等网络环境下生物数据交换系统b i b s t e r 【 3 1 。 基于对等网络的知识管理平台【1 1 4 。 基于语义的数据管理框架p i a z z a 【4 4 。 基于对等网络的数据管理系统p e e r d b 【8 4 。 结构化对等网络数据管理方法主要包括： ( 1 ) 基于结构化对等网络d h t 的数据管理系统p i e r 4 8 ，4 9 。 ( 2 ) 采用h i l b e r t 曲线和d h t 算法相结合的p 2 p 信息检索系统s q u i d 1 0 2 。 ( 3 ) 基于a d - h o e 对等网络的数据管理原型系统a m b i e n t d b 【1 0 。 1 3 对等网络环境下数据管理的关键问题 从基于语义的资源组织的角度来看，基于非结构化对等网络的数据管理系统 通过建立索引来反映各节点数掘间和服务间的语义关系，而基于结构化对等网络 的数据管理系统则根据特定节点连接所决定的网络拓扑结构来确定数据的组织 方式及数据在网络中的存贮位置，难以全面反映各节点数据和服务的语义。 从查询灵活性的角度来看，基于非结构化对等网络的数据管理系统能根据节 点数据模式和节点内容，建立多粒度、多层次的索引，提供灵活的查询方式而 基于结构化对等网络的数据管理系统采用基于关键字的哈希方法查找满足查询 请求的数据，查询灵活性较差。 对等嘲络环境下基丁：语义的丹构数据管理模犁 从查询可扩展性的角度来看，基于非结构化对等网络的数掘管理系统通过建 立索引反映邻居节点的内容，节点动态加入、离刀= 网络或在各节点内容更新时， 索引维护代价较高。因而系统可扩展性较差，较难适应大规模动态网络环境而 基于结构化对等网络的数据管理系统能够适应大规模动态网络环境，具有较好的 查询可扩展性 图1 1 显示了对等网络数据管理面临的一些挑战。这些挑战包括：如何将基 于语义的资源组织方式、查询灵活性和查询可扩展性相结合? 如何有机结合结构 化和非结构化对等网络，充分利用它们的优点? 图1 1 对等网络数据管理面临的挑战 对等网络环境下的异构数据管理主要包括以下三个关键问题： ( 1 ) 如何在大规模网络环境下，基于语义，统一、规范、有效地组织和管理分布 的数据资源和服务资源； ( 2 ) 准确、有效地把查询请求传递给相关节点。避免网络泛洪，减少网络负载； ( 3 ) 动态地集成各节点返回的异构数据，为用户和应用提供统一视图 4 第一节引二 1 4 论文的主要贡献 ( 1 ) 针对第一个关键问题，本论文提出了基于语义的资源组织模型s s e l ( s i n g l e s e m a n t i ci m a g e ) ，有效地根据分类语义和关系语义组织、管理分布在大规模 对等网络中的数据和服务，具体包括： r - c h o r d 模型，它把资源空间模型( r e s o u r c es p a c em o d e l r s m ) 和结构 化对等网络c h o r d 模型相结合 对等语义链网络模型( p 2 ps e m a n t i cl i n kn e t w o r km o d e l p 2 p s l n ) ，用 数据语义链描述各节点数据模式之间的语义关系，用服务语义链描述各 节点服务名称、功能、输入参数和输出参数之间的语义关系。 ( 2 ) 针对第二个关键问题，本论文提出了分层路由的策略，即分别在资源空间层、 对等语义链网络层和结构化对等网络c h o r d 层根据分类语义和关系语义，检 索满足查询请求的资源本论文还提出一个模糊协作评价方法来评价对等语 义链网络的性能，帮助开发人员发现对等语义链网络中的瓶颈、进行性能优 化。 ( 3 ) 针对第三个关键问题，本论文提出三种数据模式映射方法：通过建立结点映 射、语义块映射和路径映射，以此来解决各数据源语义异构和结构异构的问 题、实现源节点和目的节点数据模式的变换。通过集成各数据源节点的异构 数据，为用户和对等网络中的其它节点提供统一视图。 本论文所提出的对等网络环境下基于语义的异构数据管理模型通过资源空 间模型、语义链网络模型和对等网络模型来组织和管理分布的数据资源和服务资 源，构建单一语义映像( s i n g l es e m a n t i ci m a g e s s e l ) 。该模型为未来互联环境 提供资源有效管理和利用的基础，相关关键问题的解决具有重要的理论意义和应 用价值。 论文的主要贡献体现在三个方面： ( 1 ) 提出资源空间模型和结构化对等网络模型相结合的新资源组织模型，统一、 规范、有效地组织和管理分布的数据资源。经实验验证：与传统的结构化对 等网络c h o r d 模型相比较，本论文所提出的模型支持分类语义查询、灵活性 好、系统开销小 ( 2 ) 提出基于对等语义链网络的资源组织模型和路由方法，通过数据和服务两个 层次的语义链来建立各节点数据模式问和服务问的语义关系，提高路由效率 经实验验证：与泛洪和随机选择等非结构化对等网络路由方法相比，基于对 等语义链的路由方法的查询效果( 召回率) 接近泛洪方法，但系统响应查询 所产生的消息数目最小 ( 3 ) 提出基于语义的异构数据集成模型，通过建立各节点数据模式间的映射和查 询变换，解决各数据源的语义异构和结构异构问题，动态地集成对等网络中 对等纠络环境下基丁语义的斤构数据管理横犁 分布的异构数据，为用户和应用需求提供统一视图。 i 5 论文的组织结构 本论文的组织结构如下： 第一章介绍了论文的研究背景和意义，对等网络环境下数掘管理的研究进 展、关键问题和本论文的主要贡献。 第二章综述了非结构化、结构化和基于拓扑结构的对等网络搜索机制；异构 数据集成方法；资源空间模型的基本概念、相关操作和范式；语义链网络模型的 基本概念、范式、推理规则、构造工具及相关应用；w e b 服务的基本概念、集中 式和对等网络环境下w e b 服务发现机制以及知识网格领域的相关工作。 第三章针对对等网络环境下数据管理的第一个关键问题，即有效的资源组织 问题，提出基于分类语义和关系语义的资源组织方法，包括：( 1 ) 资源空间模型 和结构化对等网络c h o r d 模型相结合的r - c h o r d 模型；( 2 ) 对等语义链网络模型 p 2 p s l n ：( 3 ) 结构化对等网络层基于后缀树的资源组织模型。 第四章针对对等网络环境下数据管理的第二个关键问题，即有效的查询路由 问题，提出基于语义的路由方法，包括在资源空问模型层、对等语义链网络层和 结构化对等网络这三个层次的路由。在资源空间层，通过建立资源空间语义链和 资源空间视图，进行资源定位在对等语义链网络层，通过建立数据语义链和服 务语义链来描述各节点数据模式问以及节点所提供的服务间的关系，进行资源定 位 6 9 ，1 4 5 。在结构化对等网络层通过基于后缀树的哈希算法扩展了c h o r d 路 由协议，支持：基于关键字的查询( k e y w o r d b a s e dq u e r y ) 、组合查询 ( c o m b i n a t i o n a lm a t c h i n g ) 、范围查询( r a n g eq u e 啪、涉及j o i n 操作的查询( q u e r y i n v o l v i n gj o i no p e r a t o r s ) 以及涉及u n i o n 操作的查询( q u e r yi n v o l v i n gu n i o n o p e r a t o r s ) 。 第五章针对对等网络环境下数掘管理的第三个关键问题，即异构数据集成问 题，提出通过建立数据模式映射，包括：结点映射、语义块映射和路径映射，解 决各数据源的语义异构和结构异构的问题，实现异构数据集成。扩展了单一语义 映像操作语言( s i n g l es e m a n t i ci m a g eq u e r yl a n g u a g e s s e l q l ) 用于管理资源空 间层、对等语义链网络层和结构化对等网络c h o r d 层上的资源。提出了资源空间、 资源空间视图、对等语义链网络和c h o r d 层的索引更新过程以确保在节点加入、 退出网络以及节点内容更新时，仍然能够在对等网络中准确、有效地找到所需的 资源。 第六章通过仿真实验验证所提出的r - c h o r d 模型和对等语义链网络模型的 性能，并就本论文所提出的对等网络环境下基于语义的数据管理模型s s e i 与已 有的对等网络数据管理系统在资源组织、查询路由和异构数据集成这三个方面加 芤一章引二 以比较，从而总结出所提出模型的优点 第七章对整个论文进行总结 2 1 对等网络搜索机铷 第二章相关工作 s a k a r y a n 等人指出对等网络结构和搜索算法对对等网络应用有重要的影响 【1 0 0 。p 2 p 系统的基本操作是资源定位，主要包括三种搜索机制，即非结构化对 等网络搜索机制、结构化对等网络搜索机制和基于物理层拓扑结构的搜索机制。 2 1 1 非结构化对等网络搜索机制 非结构化对等网络主要采用泛洪( f l o o d i n g ) 和随机选择( r a n d o mw a l k ) 路由 方法进行资源定位泛洪方法把查询请求发送给当前节点的所有邻居节点进行查 找，这种路由方法将产生大量消息，查询可扩展性较差随机选择方法将在所有 邻居节点中随机选择一个或者多个节点发送查询请求，但不能保证能够查到网络 中已有的符合查询要求的资源 为了提高泛洪和随机选择路由方法的查找效率，人们提出节点聚类和索引的 方法。节点聚类的方法通过建立超节点来提高路由的效率。文献 6 2 】提出根据节 点数据间的语义关系动态聚集各节点，形成小世界语义层( s m a l lw o r l do v e r l a y ) 的方法 索引的方法通过建立索引，有选择地把查询请求发送给可能响应查询请求的 节点。相关的工作包括：基于内容的路由方法，通过维护文档的结构信息有选择 地把查询请求发送给相关的邻居节点【5 6 】，基于文档分类的路由索7 1 1 2 1 1 ，根据 关键字之间的语义关系建立查询扩展的方法【8 0 】，以及基于非结构化对等网络的 智能搜索机制i n t e l l i g e n ts e a r c hm e c h a n i s mf i s m ) 【1 2 7 1 等。 2 1 2 结构化对等网络搜索机制 为了提高非结构化对等网络的搜索效率，人们提出基于分布式哈希表 ( d i s t r i b u t e d h a s h t a b l e d h t ) 的路由方法。文献 8 7 】提出评价d h t 系统性能的 基准( b e n c h m a r k ) ，包括对d h ta p i 进行调用而引起网络中数据分布的变化 ( w o r k l o a d ) ，节点加入、退出网络和更新时引起的负载变化( p e r t u r b a t i o nl o a d ) 以 及节点失败时的网络性能和数据质量等。 结构化p 2 p 系统主要包括：数据查找系统和关键字搜索系统。基于分布式哈 希表的数据查找系统不支持复杂查询，但能够保证在有限步内找到系统中存在的 和用户查询相匹配的信息。结构化对等网络中的每个节点都支持根据输入关键字 定位保留该关键字的节点的操作。 9 对等叫络环境下基丁语义的异构数据管理模犁 结构化关键字搜索系统，例如：c a n 【9 5 、c h o r d 【1 0 8 1 、p a s t r y 9 9 1 和t a p e s t r y 1 2 9 ，扩展了数据查找系统，增强了搜索能力表2 1 比较了结构化对等网络 c a n 、c h o r d 、p a s t r y 和t a p e s t r y 的性能，其中 n o d es t a t e 是每个节点维护的 邻居节点的数目 l o o k u p 是定位所要查找的节点的步数； j o i n ”是节点加入时 所要更新的节点个数，是网络中的节点个数，d 是空间维数 表2 1 结构化对等网络c a n 、c h o r d 、p a s t r y 和t a p e s t r y 的性能比较 c h o r d 系统和其它p 2 p 定位系统相比，其优点在于【1 0 8 】： ( 1 ) 简单性( s i m p l i c i t y ) ； ( 2 ) 可证明的路由正确性( p r o v a b l ec o r r e c t n e s s ) ； ( 3 ) 可证明的性能( p r o v a b l ep e r f o r m a n c e ) 。 文献【4 5 ，9 6 ，1 1 5 介绍了基于d h t 的p 2 p 系统的复杂查询问题，包括： 范围查询、多属性查询、涉及j o i n 操作的查询等。p s e a r c h 是最早的基于语义 检索信息的p 2 p 系统，它根据文档的向量表示在对等网络中组织相关文档t 支持 基于语义的全文检索 t l o l 。文献【3 7 1 提出了一种根据不完全信息，在基于d h t 的p 2 p 系统中定位资源的方法，该方法通过建立多个层次的索引帮助用户在输入 信息不完全的情况下找到所需要的资源。 文献【5 1 】介绍了一种简单的h a s h 函数红( p ) ：i s 。三( p - l o _ w o , ) ，来解决d h t n i g h d 一w w v , 系统的范围查询问题，该方法的主要问题在于不能很好地支持随机性 文献【9 7 】提出前缀哈希树( p r e f i x h a s h t r e e p h t ) 的分布式数据结构，支持 基于d h t 的范围查询。文献【2 】介绍了通过空间填充曲线( s p a c e f i l l i n g c u r v e s ) 解决c a nd h t 系统复杂查询的相关技术。文献【5 】介绍了c a n d y ( c o n t e n t a d d r e s s a b l en e t w o r kd i r e c t o r yn 框架，支持包括范围查询、前缀匹配等复杂查 询。 r e y n o l d s 和v a h d a t 提出分布式倒排索引，采用b l o o m f i l t e r 、高速缓冲存储 器( c a c h i n 蓟和结果增量( i n c r e m e n t a lr e s u l t s ) 的方法使得在多关键字搜索过程 1 0 第：节相关1 作 中系统的带宽消耗最4 、【9 8 】。 文献【3 0 】介绍了通过建立多级索引解决基于d h t 的p 2 p 系统的复杂查询问 题，但是所提出的建立查询描述符和通用查询的方法非常费时，而且所提出的方 法基于查询描述符和预先设计查询的精确匹配，未涉及错拼、同义词以及其它和 语义相关的问题 2 1 3 基于物理层拓扑结构的搜索机制 前面介绍的非结构化和结构化对等网络的资源定位机制并没有考虑到物理 层的网络结构。例如：c h o r d 层的单跳( as i n g l e “h o p ”) 可能涉及到物理层跨越 半个地球的两个节点。w a n g 等人根据物理层网络和结构化、非结构化对等网络 协议的特点，在文献【1 2 3 】提出一种基于物理层网络拓扑结构的搜索机制。 2 2 异构数据集成 2 2 1 基本概念 由于对等网络各节点的数据由不同的开发者提供和维护，数据之间可能存在 语义异构、结构异构、数据模型冲突和数据值冲突等问题【9 3 。数据集成主要 解决如何把分布在各数据源的异构数据集成起来为用户提供一个统一视图的问 题。 本体( o n t o l o g y ) 主要用来定义统一的术语和概念，而数据模式主要用于对 数据建模和描述。本体和数据模式都在解决异构数据集成问题中扮演重要角色。 通常，通过x m l 或者其它方法定义的数据模式需要关联相应的本体，以使资源 的语义更加清晰【2 2 ，8 9 】。 文献【5 9 】介绍了数据集成需要解决的一些关键问题，例如：完整性约束、 数据不一致性和查询优化。文献 1 8 1 介绍了基于约束的异构数据集成方法。文献 【2 0 】介绍了采用数据挖掘技术实现数据集成的方法。文献 3 6 1 介绍了w e b 数据集 成方法 数据集成主要通过两种方式实现，即实视图( m a t e r i a l i z e dv i e w ) 和虚视图 ( v i r n l a lv i e w ) 的方法。实视图方法保存了各数据源的数据以响应查询，虚视图 方法保存访问各数据源的视图实视图方法通过搜索本地的数据存贮响应查询， 而虚视图方法把查询请求分解成一系列子查询，把各子查询发送到相应的数据 源。并集成返回的结果。如果各数据源的数据更新不是很频繁，多采用实视图方 法，否则就采用虚视图方法【3 8 ，1 2 0 】。 现有的数据集成系统主要包括m o m i s ( m e d i a t o re n v i r o n m e n tf o rm u l t i p l e 对等州络蚪境下基丁语义的芹构数据管理模犁 i n f o r m a t i o ns o u r c e s ) 【6 】、x y l e m e 【2 5 1 、g 三晒【2 8 】和m a r s l 2 6 1 等 2 2 2 异构数掘集成方法 数据集成系统可以表示为一个三元组，- ( g ，& 力，其中g 表示全局数据 模式，s 表示各数据源数据模式，肘是各数据源数据模式到全局数据模式的映射 【5 9 。 根据如何建立全局数据模式和各数据源数据模式之间的映射，文献【5 9 】把现 有的异构数据集成方法分为四个类别： ( 1 ) g l o b a la sh e w ( g a v ) 方法根据各数据源的数据模式定义全局数据模 式，中介器( m e d i a t o o 负责建立并维护各数据源的异构数据视图，定义如何 解决语义异构、结构异构等问题，如何集成各数据源的数据为用户提供统一 视图在g a v 方法中，如果各数据源的数据发生改变，全局数据模式和映射 也要做相应调整，因此该方法不适合大规模数据集成的应用 ( 2 ) l o c a la sh e w ( l a y ) 方法预先设计全局数据模式，各数据源数据模式 根据应用需求变换到全局数据模式对全局数据模式的查询需要通过推理变 换到对各数据源的查询。由于各数据源数据模式的改变不会影响全局数据模 式，因此，l a v 方法具有较好的可扩展性 ( 3 ) g l a v 方法同时采用g a v 和l a v 方法来表示各数据源数据模式和全 局数据模式之间的关系 ( 4 ) p 2 p 方法不存在全局数据模式，网络中每个节点保存到其它节点数据 模式的映射。 2 2 3 数据模式匹配 数据模式匹配的问题最早在1 9 8 0 年提出，它要解决的主要问题是如何基于独 立的数据模式集合，构造一个全局数据视图，实现数据集成文献【9 4 】把现有 的模式匹配方法分为以下几种类别； ( 1 ) 实例或模式( i n s t a n c ev s s c h e m a ) , 数据模式匹配方法是否考虑各数据源的实 例数据( i n s t a n c e ) 还是只考虑数据模式信息( s c h e m a ) 。 ( 2 ) 元素或结构( e l e m e n tv s s t r u c t u r e ) ：数据模式匹配方法是通过元素级 ( e l e m e n o 映射还是通过结构( s t r u c t u r e ) 变换实现。 ( 3 ) 语言或约束( l a n g u a g ev s c o n s t r a i n t ) ：数据模式匹配方法是通过语言 ( l a n g u a g e )