（计算机应用技术专业论文）p2p系统一致性及查询问题研究.pdf

摘要 摘要 对等计算( p e e r - t o p e e r ，p 2 p ) 系统是一种i n t e m e t 应用，可以充分利 用大量的自治参与者的资源。受到早期诸如n a p s t e r 、g n u t e l l a 等p 2 p 系统 成功的影响，越来越多的研究团体致力于发现对等计算的本质特征、实现 技术并设计形式多样的应用系统。本文以提出p 2 p 系统中映射表的自动推 导，检测工具和实现p 2 p 系统中局部查询的全局化为目的。在对国内外研 究现状进行了深入分析的基础上，对p 2 p 系统自治数据源之间数据共享中 的若干关键问题进行了研究。 首先，本文从映射表和映射约束的定义开始，介绍了映射表推导和一 致性问题在p 2 p 系统中的重要意义。在此基础上提出了在特定条件下解决 映射一致性问题的划分算法，并对算法的执行条件和复杂度等特性进行了 分析。 其次，本文关注了p 2 p 系统中的查询翻译问题。通过在对等点模型中 加入查询分析模块，将外部查询转换为表形式的内部信息，并将其加入由 划分算法得到的导出映射表中。基于这种映射表定义的扩充，提出了一个 计算局部查询的完全翻译的算法，并对翻译算法的执行特性进行了分析。 最后，对划分算法和翻译算法从执行效率，对结构特性的适应情况以 及一些重要参数的选取等方面，设计了详尽的实验方案。利用欧洲生物学 数据库的真实数据对算法进行了测试，对测试结果进行了分析和总结，并 对未来的研究工作进行了展望。 关键词对等系统；映射表；推导；一致性；划分；查询翻译 燕山大学工学硕士学位论文 a b s t r a c t p e e v t o p e e rs y s t e mi sa l li n t e m e ta p p h c a t i o nt h a tc a i lt a k ef u l la d v a n t a g e o fr e s o u r c e so fa u t o n o m o u sp a r t i c i p a n t s w i t he a r l ys u c c e s s f u lp a r a d i g m sl i k e n a p s t e ra n dg n u t e l l a ，r e s e a r c hc o m m u n i t i e sh a v ed e d i c a t e dt h e m s e l v e st o d i s c o v e rt h es u b s t a n t i a lc h a r a c t e r sa n da c t u a l i z e dt e c h n i q u e s f o rt h eg o a l so f p r e s e n t i n gat o o lf o rm a p p i n gt a b l e sc o n s i s t e n c ya n das o l u t i o nf o rt r a n s l a t i o n al o c a lq u e r y t h ep a p e rd o e st h ei n - d e p t hr e s e a r c ho ns o m ep i v o t a li s s u e s a b o u td a t as h a r i n g f i r s t l y ，t h ep a p e ri n t r o d u c e st h ei m p o r t a n c eo fi n f e r e n c ea n dc o n s i s t e n c y a n dp r e s e n t sap a r t i t i o na l g o r i t h mt os o l v et h ei n f e r e n c ea n dc o n s i s t e n c y p r o b l e m se f f e c t i v e l y , a n dl a t e rd i s c u s s e st h ep r o b l e m so fe x e c u t e dc o n d i t i o n s a n dc o m p l e x i t y s e c o n d l y t h ep a p e rf o c u s e so nt h ei s s u eo f t h eq u e r yt r a n s l a t i o n b ym e a n s o fa d d i n gt h em o d u l eo fs q lp a r s e ri n t ot h eo r i g i n a la r c h i t e c t u r e ，t h eo u t e r q u e r i e sa r ec o n v e r t e d t ot h ei n n e rt a b l e a ui n f o r m a t i o nt ob es t o r e dl a t e ri nt h e c o m p u t e dm a p p i n gt a b l e sa st h eo u t p u t so fp a r t i t i o na l g o r i t h m t h ep a p e r p r e s e n t sa na l g o r i t h mo fc o m p l e t et r a n s l a t i o nf o rl o c a lq u e r ya n da n a l y z e si t s c h a r a c t e rt h e o r e t i c a l l y f i n a l l y ，e x h a u s t i v ee x p e r i m e n t sa l ed e s i g n e dt oe v a l u a t et h ee x e c u t i v e c h a r a c t e r , p e r f o r m a n c e s 、丽mr e s p e c t t os e v e r a lp a r a m e t e r s a n dt h et e s t i n gd a t a a r er e t r i e v e df r o mt h ee u r o p e a nb i o l o g i c a ld a t a b a s e s a tt h ee n do ft h ep a p e r , i t a n a l y z e st h ee x p e r i m e n t a lr e s u l t sa n dd r a w sac o n c l u s i o n ，a l lo f w h i c hp r o v i d e t h ef u t u r ew o r kw i t ht h ea b u n d a n te x p e r i e n c e sa n daf o u n d a t i o n k e y w o r d sp e e v t o p e e rs y s t e m ；m a p p i n gt a b l e ；i n f e r e n c e ；c o n s i s t e n c y ； p a r t i t i o n ；q u e r yt r a n s l a t i o n 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 p 2 p 系统一致性及查询问 题研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己 发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字龟扣 日期：珈e e 年 月汀日 燕山大学硕士学位论文使用授权书 p 2 p 系统一致性及查询问题研究系本人在燕山大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全 了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山 大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全 部或部分内容。 保密口，在 年解密后适用本授权书。 本学位论文属于， 不保密醑。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 日期：弼气月谬日 日期溺年 月妒 第1 章绪论 1 1p 2 p 系统简介 第1 章绪论 p e e r - t o p e e r ( 以下简称p 2 p ) 系统由分布式计算对等节点的开放终端网络 组成，可以充分利用大量自治参与者的资源。大多数情况下，这些p 2 p 网络 节点会形成一个自组织网络，该网络位于传统i r l t e m e t 协议的上层，而且没 有中心化的结构特征。因此，这种系统成本不高，易于使用，也不需要中 心管理i l j 。每个对等节点都可以在任何时间加入或者离开网络，并且在加入 时与其它的一组被称作近邻的对等节点交换数据和服务。每个对等节点在 选择自身的近邻时是高度自治的。而且，这里既没有全局注册，全局服务， 全局资源管理，也没有全局模式和数据仓库形式的全局控制【2 】0 如今，像 n a p s t e r 和g n u t e l l a 这样成功的p 2 p 范例已经作为存在于传统的分布式系统 和w e b 服务器之间的分布式计算系统被广泛推广。相对而言，p 2 p 系统为 传统的分布式用户提供了一个进化了的网络应用结构，在这里节点可以随 意加入和离开，可以自主选择通信对象，并以很小的成本享受一些传统的 分布式服务p j 。 1 1 1p 2 p 系统与网格系统 与当今蓬勃发展的网格计算技术相比，p 2 p 系统同样强调为分布在不同 地点的人们提供资源共享服务。但是，由于这两种技术有着不同的前提假 设，导致了它们有着截然不同的需求背景和技术发展方向【4 l 。p 2 p 系统所关 注的资源共享主要用于那些包含数以百万计的用户的大型环境，并且这些 用户大多通过家庭桌面系统以及低带宽设备连接到i n t e m e t 。因此，其重点 在于容错技术和大规模扩展技术，而网格系统主要用于规模相对较小的用 户组织的协作，并且提供更加丰富多彩的可共享资源。 尽管具有这些不同之处，但是p 2 p 与网格的长远目标似乎在某些方面是 l 燕山大学工学硕士学位论文 一致的，因为网格系统需要扩展规模，并把短期服务与资源结合起来对外 发布；而p 2 p 的研究者们则考虑提供一些稍微宽泛的服务。目前，国外的一 些研究机构已经开始尝试调和对等计算与网格计算的工作。 1 1 2p 2 p 系统的发展历史 p 2 p 系统的发展经历了几个周期。传统分布式计算的研究者认为这些新 兴技术是“目无尊长、数典忘祖的暴发户”。实际中确实存在一些现象支持 这一论断。而有些人则认为它带来了一个绝佳的机会，能够提供一个重新 审视过去研究成果的机会，并获得设计大规模分布式一算法的实践经验。“对 等计算”这个名词的早期使用可以追溯到m m 公司l u 6 2t r a n s a c t i o n 上的 系统网络体系结构文档。如今，这个名词随着n a p s t e r 系统的起起落落，走 到了舆论的前台。尽管在分布式系统的演化过程之中出现过许多优秀的原 型设计，但是限于篇幅这里只简单回顾自n a p s t e r 出现以来这段时期的研究 进展。 p 2 p 系统可以与不对称的客户服务器模型相对比。在客户服务器模型 中，服务器通常是具有较强计算能力和较好网络连接的计算机，它能够长 时间运行，并把大量存储数据和计算资源分发给广大客户。因此，服务器 很容易遇到性能、可靠性瓶颈。为解决这些问题，服务器节点可以使用诸 如副本放置、负载平衡及请求路由等技术，并将一组不同的机器对外显示 为一个抽象服务器。这种想法的自然延伸就是将大量客户机的资源也纳入 到系统中来，应用这种方法，将大大缩小桌面计算机与服务器的性能差别， 并且显著提高客户端的网络可连接性。 因此，p 2 p 系统其实就是去掉了客户服务器的不对称因素并对其进行 改进的系统。其中，客户机也可以充当服务器，接受其它节点对其资源访 问的请求。而客户机，现在称为“节点”，可以贡献自己的资源，以换取所 需要的服务。以前服务器方所需要完成的工作现在可以分散到大量节点之 间完成，以便于一个节点( 相当于服务器) 可以代表其它节点( 如客户机) 来消 耗自己的资源。这些工作包括消息转发、计算、存储和搜索等。但是，在 现实世界中如果节点没有足够的合作动机，这种合作模式就会破裂。目前 2 第1 苹绪论 的研究期望通过信任、信誉和经济的方法来维护这种合作动机。 p 2 p 系统宣称没有不可或缺的特殊节点。因此，人们认为它具有高度的 容错能力，并具有良好的性能和扩展能力。尽管有些情况确实如上所言， 但是，大多数情况下p 2 p 网络中还是会存在超级节点，也会出现瓶颈。事实 上，在早期的p 2 p 系统中很难说有容错特性，只要看看这些系统，如n a p s t e r ， g n u t e l l a 5 1 和f r e e n e t “，就可以发现它们的可用性还不如最普通的w e b 站点。 但是，第二代乃至后面的几种p 2 p 系统确实拥有了上述的容错特性与性能。 从p a s t r y ”，c h o r d 8 】和c a n 9 】身上研究者们可以看到美好的未来。当前在这 些系统上所构建的应用和服务器也显示出了许多潜在的优点1 1 2 p 2 p 系统国内外研究现状 p 2 p 系统当今仍然是一个热门的研究领域，其发展进程一直非常稳健。 虽然目前的研究工作仍面l l 缶许多的技术问题，但随着新一代p 2 p 路由基的诞 生和分布式哈希表技术的使用以及众多p 2 p 软件的开发，p 2 p 计算已经给主 流计算带来了巨大的影响。 1 2 1p 2 p 系统的研究前景 p 2 p 系统的规模意味着参与者是无外带( o u t - o f - b a n d ) 信任关系的个体或 组织【l o l 。这一关键特性当前并没有被网络系统所共享，但由于网络系统规 模的不断扩大，这一特征带来了更加重要的现实意义，同时也激发了人们 很多的研究兴趣，包括在信任域的建立、信誉系统、经济动机和恶意参与 者检测等方面的研究。 实际上，从部署第二代系统那里得到的许多经验都与人类的行为相关。 绝大多数应用都依赖于节点之间的协作模型。参与者加入网络并使用服务。 相应地，他们也希望为他人贡献自身的资源。即使协作者之间的公共利益 也不能阻止人们相互背叛1 1 1 】。因而来自经济模型【1 2 】以及信任模型的动机 形成了当前研究领域的重要组成部分。 在安全、攻击防卫等方面的研究【1 4 】已经获得了大量的进展，这些成果 燕山大学工学硕士学位论文 还包括一个结论，如果虚拟身份与真实世界的身份没有可信任的关系，就 不能有效地防止伪装欺骗( 拥有不止一个虚拟身份) 的发生【”j 。 随着p 2 p 技术的不断成熟，研究人员也发现了其应用领域的多样性。随 着网络系统的不断扩大和p 2 p 技术开始注重特定资源的共享利用，用户也能 够更好地定义位置、性能限制、可用性以及一致性的需求。 1 2 2p 2 p 系统中的数据管理 当今，p 2 p 计算系统被吹捧为一种支持直接和动态的点对点通信模式的 i n t e m e t 网络体系结构。每个对等节点使用单独的命名空间，同时扮演客户 和服务器的角色。在网络的控制和组织结构上每个对等节点都是高度自治 的。新的节点可以在任何时刻加入或离开网络。一旦节点加入网络，就可 以与其它的对等节点建立近邻关系。成为近邻的对等节点就可以进行实际 的数据集成和共享。当然，这种近邻关系也是暂时的。尽管已经有一些成 功的p 2 p 应用范例，如c r a u t e l l 和k a z z a 。但p 2 p 应用目前主要还是针对共 享项的。例如，将文件作为一个处理单元却不对它的内容进行管理。更确 切地说，已有的p 2 p 应用仍然没有给予数据管理问题足够的重视。 在传统上，异构数据源间的数据集成和交换都是通过视图实现的【1 6 , 1 7 。 这种情况下，各个资源站必须自愿分享各自的模式并且在创建和管理查询 等方面合作。然而在某些环境中，由于资源限制以及数据结构的动态特性 等原因【l3 ，1 9 】，无法实现这种紧密的协作方式。在p 2 p 数据共享系统中，各个 对等节点依照自身的模式输出数据，依靠各个对等模式中的映射表来集成 不同资源站上的数据 2 0 l 。 1 3 主要的研究内容 本文的工作主要关注p 2 p 系统中的数据管理问题，尤其是如何在p 2 p 环 境中数据共享的问题。 目前，由加拿大1 砷l t o 大学计算机科学系主持的h 1 ，p e r i o n 项目口1 ，捌代 表了当今世界上晟前沿和最重要的p 2 p 技术的研究成果。此外，s i n g a p o r e 4 第1 章绪论 大学的研究人员也针对p 2 p 系统的数据管理问题进行了一些开创性的研究。 2 0 0 3 年，k e m e n t s i e t s i d i s ，a r e n a s ，m i l l e r 等人在s i g m o d 上发表了介绍p 2 p 系统数据管理问题和映射表管理的重要论文，其中特别强调了映射表自动 推导和一致性检测机剑对日常数据管理的重要性，同时也指出直到当时还 没有出现一套可以实际使用的自动工具来帮助p 2 p 系统管理者。在2 0 0 4 年， k e m e n t s i e t s i d i s ，a r e n a s 再次发表了一篇关于p 2 p 系统中的查询问题的文章。 文中通过对映射表定义的扩展将基于特定对等节点上提出的查询转化为表 的形式以便于存储在映射表中，从而为实现在p 2 p 系统中的全局检索提供了 条件和基础。 1 3 1 映射表的推导和一致性问题 p 2 p 系统使用映射表来定义各个资源节点上数据间的相关性，从而支持 数据间的交换和集成。本课题的目标之是在各个资源使用不同数据模式 的情况下，从动态的网络环境中搜集映射表信息并对这些信息进行整合和 处理，使之成为日后在对等节点上进行数据查询和交换时的依据。 在映射表的创建和维护过程中，有两种能力是用户和管理员都十分需 要的。 ( 1 1 推导新的影射表目前，p 2 p 系统的一项日常工作就是在特定的属性 集上寻找所有合法的映射表。这项工作需要对网络上获得的映射表信息进 行整合。这时要使用一组被看作约束条件的映射表来推导那些没有出现过 的新映射。 ( 2 ) 确定映射约束的一致性管理者在管理来自不同资源的映射表时， 需要一种自动工具来帮助他们检查映射约束的一致性，并帮助他们正确理 解语义问题】。因此，他们希望有一套自动的推理和一致性检测机制来确 定适用于特定领域的语义。 h y p e r i o n 项目中的研究人员针对具体应用领域的语义在系统中动态地 创建和修改映射表，并且提出了映射约束的概念，在实际处理过程中把表 处理成为约束条件，这样就可以在信息交换时对已有的映射表进行进一步 的推导并对推导出的新的映射进行一致性检测。但目前的问题是，在对推 燕山大学工学硕士学位论文 导和一致性问题进行抽象后，实际网络环境中的串行计算执行效率极低， 并且完全不适应p 2 p 环境的结构特征。显然，p 2 p 系统中每一个节点都是一 个服务器，并且都拥有自己的计算资源，各种应用所需要的处理和运算应 该尽量分配到各个节点上。另外，为了尽可能利用一切可用资源，防止个 别资源节点处于空闲或忙等状态，还要保证服务器之间的数据交换和传输 以“流”的形式进行。为此，本文将提出所谓的“划分”算法，该算法的 设计思想是在实际计算之前对映射信息进行预处理，对映射约束分组，使 得在各组内的计算可以相互独立和并行地执行。此外，在第2 章中还将对该 算法的执行条件，复杂性等问题进行理论分析。并通过具体的实验测试对 提出的算法进行评估，实验方案包含两方面的内容。首先，需要设计一个 实验来考察算法是否能为那些已经使用并且广泛交换映射表的用户提供附 加的信息。测试使用来自公共可用资源( 如g d b 、m i m 等生物学数据库) 的 真实映射数据。第二项研究是设计用来评估本文所采取的方法本身是否适 合p 2 p 环境的结构特性，并了解在路径长度和映射表规模不同的情况下算 法的执行情况。 1 3 2 通过查询翻译的数据共享 在通过“划分”算法得到新的映射表之后，第3 章继续关注在自治资 源之间的数据共享问题，并把研究重点放在p 2 p 环境下的查询和全局检索 上。这里所提出的解决方法仍然依赖于上一章中介绍的那些定义数据之间 相关性的映射表的使用。利用无错翻译( s o u n dt r a n s l a t i o n ) 和完全翻译 f c o m p l e t e 订a 璐l a t i o n 、概念l 以及y , s a g i v 等人于1 9 8 0 年提出的可溶性测试 算法【2 卯，本文将一个s q l 解析器加入p 2 p 服务器模型中。由此，将在一个 对等节点上提出的s q l 查询转换为t - 查询【2 6 】，并将其以列表项的形式存储 于映射表中。这样做使映射表不仅能存储自治资源间数据的相关信息，还 可以存储基于不同模式的查询问的相关信息。 这部分工作的目标是在使用多重映射表的条件下将基于一个对等节点 上提出的本地查询自动转化为可以在相关资源节点上执行的一组相关子查 询，即实现计算一个本地查询的翻译并检验翻译是否合法的算法。 6 第1 章绪论 在对所提出方法进行必要的理论分析和论证之后，后面的实验验证部 分将参照三个主要指标对翻译算法的性能进行评估，三个指标参数分别是 输入查询的规模，输出查询的规模以及在翻译过程中所用的映射表的规模。 实验中的参数和数据主要来自m e d l i n e ，p u b m e d 和s w i s s p o r t 三个公共生物 学数据库1 2 ”。 1 4 本文组织结构 本论文总体上分为四章，从第2 章开始具体布局如下。 第2 章首先对p 2 p 系统中映射表的相关概念和基础知识进行了介绍，然 后具体阐述t p 2 p 系统中一致性问题和推导问题的定义和数学模型，并且讨 论了其中的一些关键的技术问题。最后，本章提出在一定条件下解决一致 性问题的算法并对算法的实际运行情况进行了分析。 第3 章在第2 章的基础上将映射表的应用重点放在p 2 p 系统的查询问题 上。本章首先介绍了映射表在p 2 p 系统查询服务中的应用基础和相关的语义 特性，进而引入了查询翻译的概念。最后，在t - 查询表示法的模式下提出 了有关查询翻译的关键算法，并对查询翻译的组成和多重映射表环境下的 解决方案进行了分析。 第4 章是实验验证部分。本章首先针对第2 章提出的推导算法和一致 性算法在执行效率、映射推导能力方面进行了测试，在此基础上进一步测 试了路径长度和映射表规模等参数对算法的影响。接下来，本章对第3 章提 出查询翻译算法，针对其翻译执行时间以及输入查询规模对算法执行效率 的影响等进行了详尽的实验并对实验结果进行了细致的分析。 最后一部分是本文的结论以及对下一步的研究工作进行了展望。 7 燕山大学工学硕士学位论文 第2 章p 2 p 系统映射一致性问题的研究 映射表是对等节点之间进行信息交换的基础工具。在p 2 p 环境中，通常 不存在特定的命名标准，不同的对等节点必须开发属于自己的命名规范。 当各个资源建立了自己的命名规范之后，就不可能有统一标准存在。然而 实际中，有很多应用依赖于内部规范的使用，此时向外部规范的移植是一 项极其费时和昂贵的工作。因此，在这样的环境中检索数据，就必须使用 储存着不同数据值之间的相关信息的映射表。本章首先介绍有关p 2 p 系统 映射管理的相关概念。在最简单的情况下，这些表就是一些包含来自两个 不同资源的相关标识符的二进制表。使用这种表仍然可以使用简单值查询。 在一般情况下，可能需要一条映射含有多个属性的值。例如，在个对等 节点上，地理位置可能是由邮编的形式指示的，而在另一个节点上是以由 地区码和城市名的序偶来标识的。目前仍然使用映射表来交换这些与特定 值相关的数据，在一个对等节点上形如“r e t r i e v ea l li n f o r m a t i o nr e l a t e dt o p o s t a lc o d ex ”的查询在另一个节点上可能变成“r e t r i e v ea l li n f o r m a t i o n r e l a t e dt ot h ea r e ac o d e ，t o w np 姐y z ) ”的形式。如果映射不是一对一而是一 对多，那么，翻译的结果就是一组值。在更加结构化的数据管理环境( 如文 件共享系统) 中，数据交换是通过使用自描述数据模型【8 】实现的，对于查询 结果的结构不存在预先的协议，因此，数据一旦建立后就以自身的描述性 模式进行交换。但如果在映射表中存储了数据的关联信息后，就可以高效 地执行单值查询，并且使数据管理系统问的检索和信息交换更加方便。 映射表的内容蕴涵专业知识，通常是由领域专家创建。目前。创建映 射表是一项极其耗时的工作，并且大部分创建过程都由管理员手工完成。 虽然映射表被广泛应用，尤其是在生物学领域，但当前却没有一种使映射 表的创建、维护和管理更加便利的工具。本章将重点阐述，如何通过在对 等节点问进行信息交换时把映射表处理为约束条件( 本章中称之为跌射约束) 而对映射表进行推导和一致性( 合法性) 检查。在a n a s t a s i o sk e m e n t s i e t s i d i s 第2 章p 2 p 系统映射一致性问题的研究 和m a r c e l o a r e n a s 所提出的数学描述的基础上，本章将提出一个解决映射表 推导和一致性问题的算法，并且针对解决方案的复杂性、限制条件等性能 指标进行分析。 2 1p 2 p 系统中的映射数据 为了更好的理解p 2 p 系统中的映射数据，先看一个来自生物学数据库领 域的实例。在这里，染色体数据可以在大量的权威机构数据资源中得到， 这些资源可能是公开的公共资源或取自私人实验室，例如g d b ( 有关基因数 据库) 、s w i s s p r o t ( 有关蛋白质数据库) 以及m i m ( 一个关于基因和与这些基因 相关的无序对的数据库) 。显然，现实中急需为广大科学工作者提供一个统 一接口来对这些资源进行集成。但是，由于政治、资金和技术上的原因， 这一方案暂时还无法实现。在技术方面，资源所固有的异构性是一个重要 的因素，这些资源的结构可能是关系数据库，格式化文件或电子数据表等 等。此外，资源的模式和格式随着新的生物学技术的提出也在不断改进和 演化。为了得到某种程度的集成，生物学家通常在实际中使用前面所述的 映射表。例如，映射表可以用来把一个资源上的基因数据与另一个资源上 其相关的蛋白质数据联系在一起。但映射表并不是一个函数，因为可能存 在很多蛋白质对应一个基因的情况，甚至在一个与基因标识符对应的映射 表中可能会出现多对一的情况。这些情况的频繁出现是因为在生物学资源 中，同一个标识符经常会有几个不同的别名，当标识符被更新后，旧的标 识符还会被保留。也就是说，这些标识符可能指示一些包含实体的旧的名 字和标识符不可更新的静态资源。 接下来，将介绍一些映射表的主要应用和特性。首先，本章关注于映 射表如何被用于表示域内和域间的数据关联的问题。其次，本文将说明， 由于映射表充分尊重对等节点的自治，它可以作为一种适当的工具在p 2 p 系统中被有效地使用。最后，将解释映射表中的可选择性语义以及为什么 在使用映射表的环境中对映射表的推导能力是必要的。 注意到，通过使用映射表可以把那些看起来没有关系的数据库联系在 9 燕山大学工学硕士学位论文 一起，这类似于多级世界( m u l t i p l ew o r l d ) f 司的中间件1 2 引。在典型的集成环 境中，通常只处理一个世界，例如，一组包含全部基因信息的资源。然而， 现实中也存在另外一些情况。这种情况下，来自于彼此孤立的世界的资源 由于其对应的世界在语义上彼此接近而发生关联。例如，g d b 生物学数据 库拥有一个映射表，在其中存储了其自身的基因标识与来自s w i s s p r o t 的蛋 白质表示之间的关联，表2 1 中列举出了这样的映射表中的部分内容。 表2 - 1g d b 数据库中的映射表 t a b l e2 - 1m a p p i n gt a b l ei ng d b g d bi ds w i s s p o r ti d g d b ：1 2 0 2 3 1p 2 1 3 5 9 g d b ：1 2 0 2 3 l0 0 0 6 6 2 g d b ：1 2 0 2 3 l q g u m k 3 g d b ：1 2 0 2 3 2p 3 5 2 4 0 g d b ：1 2 0 2 3 2p 0 1 1 3 8 利用映射表g d b 数据库的用户可以为每个基因检索来自于s w i s s p r o t 的 相关的蛋白质。为了明显起见，这里对表2 1 中的数据进行了简化，在本文 后面的实验部分中，将使用真实的从g d b 到s w i s s p r o t 的映射表。 2 1 1映射表 在映射表的实际应用中，相关的领域专家拥有不同层次的专门知识。 因此，映射表应该不仅能记录领域专家提出的关联，还应该记录这些联合 的置信度刚。下面，首先介绍一下映射表的可选择性语义以及如何使用这 些语义表示一个感兴趣领域的部分和全部信息。 设一个映射表包含两个互不相交的属性集x 、y 。映射表中的一个元组 ( x ，y ) 被称作一条映射，它表示值x 与值y 相关联。如果x ，值可以与任何y - 值关联，那么称它遵守o p e n - w o r l d 语义。在这一语义规则下，映射表只对 其中出现的部分有关x 值的信息进行编码。如果映射表中出现的x 值只与 那些事先指定的y - 值关联，则称其遵守c l o s e d w o r l d 语义。在此种语义下， 映射表必须对其中出现的全部x - 值信息进行编码。类似地，对于一个没有 1 0 第2 章p 2 p 系统映射一致性问题的研究 在映射表中出现的值，如果它可以与任何的y - 值关联，则称它遵守 o p e n - w o r l d 语义；如果它不与任何y 二值关联，则称它遵守c l o s e d w o r l d 语义。 表2 - 2 直观地总结了上述结论。 表2 - 2 可选择o p e n c l o s e dw o r l d 语义 t a b l e2 - 2a l t e r n a t i v eo p e n c l o s e dw o r l ds e m a n t i c o p e n - w o r d c l o s e - w o r l d p r e s e n tx v a l u 0 a n yy v a l u ei n d i c a t e dy - v a l u e m i s s i n gx - v a l u e a n y1 y v a l u cn oy v a l u c 这种情况下，将两组语义组合起来就得到四种映射表的可选语义。特 别地，在o p e n o p e n w o r l d ( o o w o r l d ) 语义下，无论是表中出现的x 一值还是 那些没有出现的x 值均遵守o p e n - w o r l d 语义。这种语义允许任意的x 值与 任意的y - 值相互关联。因此，该语义在实际应用中没有任何实际意义。在 o p e n - c l o s e d - w o r l d ( o c - w o r l d ) 语义下，在映射表中出现的所有x 一值均遵守 o p e n - w o r l d 语义，而那些没有在表中出现的值遵守相应的c l o s e d w o r l d 语义。 对于这样的语义，映射表实际上指定了一组可以与任何y - 值关联的x 值， 同时映射表中显示的y ：值却没有被考虑。对于一个旨在记录特定x 值与y _ 值之间详细映射的领域专家来说，这种语义也没有任何实际意义。而在 c l o s e d o p e n - w o r l d ( c o w o r l d ) 语义条件下，一个映射可以真正描述局部信 息，这样的情况才更具有实用价值。当一个领域专家只熟悉该领域的某个 子集时，c o w o r l d 语义显得更加实用。此时，他可以通过约束那些与特定 x 一值相关联的y - 值来记录自己的专业知识。同时，既然用户和领域专家对 其余的x - 值都一无所知，那么就可以允许其与任意的y - 值关联。 c l o s e d - c l o s e d - w o r l d ( c c w o r l d ) 语义对于表达全部领域知识是有效的。在这 种语义下，专家可以指定全部的正确的映射集合。综上所述，下面把主要 精力放在后两种语义的研究上。 在理解了语义的概念之后，接下来给出映射表的正式定义及其它相关 的概念。由于映射表可以很方便地与关系模型相适应，因此下面的定义由 关系模型提出。但要注意，这里不需要现实中的任何p 2 p 系统使用这种模 型。实际上，本章所提出的算法是设计用来与那些作为信息查询系统、d b m s 燕山大学工学硕士学位论文 系统或文件共享系统的对等网络节点协n t 作的。并且，在p 2 p 网络中， 映射表并不限制各个对等节点上数据库的内容，它所限制的只是信息在各 个资源站之间交换的方式【j 。 本文中将统一用字母a 、b 、c 、d 来表示单一的属性，对于一个属性 a ，d o m ( a ) 表示a 的域。这里域的概念与大多数关系数据库中的域概念相 一致。u 、x 、y 用来表示属性集，r 用来表示一个关系模型，r 表示一个 关系实例。t 表示一个元组。另外，在文中用t x 】来表示元组t 在x 属性集 上的值，并且统一使用标准关系代数操作符如投影( 呶) 和选择( 呶) 等。 在映射表和映射中出现的一般都是常量，但为了表示出不同的语义 f c o w o r l d 或c c - w o r l d 语义) 就必须引入变量的概念。令v 为一个变量集，其 中对于其中任何一个属性a ，都有v n d o m ( a ) = m 。这里定义映射为一个包 含常量和变量的元组。其正式的定义如下。 定义1 ：给定一个属性集u 。如果对于任一属性a u ，t 【a 】或者是d o m ( a ) 中的一个常量，或者是v 中的一个变量，或者是一个如v _ s 形式的表达式， 则称t 是u 上的一个映射。( 这里v e u ，s 为d o m ( a ) 中的一个有限子集) 。 这里将映射定义为一个包含着常量或变量的元组。这样的元组在文字 上通常被称作自由元组【3 ”。并且用术语“表”来表示含有变量的关系，为 了与之在文字上保持一致，本文中也用术语“映射表”来代替“映射关系”。 另外，此处还附加了一项限制，即每个变量最多在一条映射中出现。这一 限制与映射表中不同映射应完全独立的假设相一致。 定义2 ：设x ，y 是两个非空且不相交的属性集。映射表m 是x u y 上的一组有限映射集，它规定每一个变量最多只能在一个映射中出现。 由此可以看出，变量的引入为表示属性值之间的一般关联提供了一条 简洁而方便的渠道。下面是一个有关属性之间关联的例子。 设想燕山大学有一个生物学数据库，它使用与g d b 数据库相同的标识 符。这时可将映射表表示成一个形如( i d ，i d ) 的表，或者构建一个只包含一条 映射的映射表( v ，v ) ，其中v 是变量。显然，如果没有变量，用户就必须在查 询中自己确定是否使用一个标识符映射。这种情况将会大大增加用户的使 用复杂度。此外，变量还为选择性的映射语义提供了一种简单的表示法。 第2 章p 2 p 系统映射一致性问题的研究 下面再看另外一个例子。假设有两个映射表，其中的内容分别如下面 表2 3 和2 4 所示。前者使用c o w o r l d 语义，任何没有显式说明的基因可以与 任何的蛋白质相关。表2 4 所表示的映射表使用c c w o r l d 语义，该表中的前 两个映射与表2 3 中出现的映射相同。而表中最后一条映射表示除了 g d b ：1 2 0 2 3 1 和g d b ：1 2 0 2 3 2 以外，所有的g d b 标识符均可能与任何的蛋白 质相关，两个表中的映射表分别使用不同的语义，但却表达了相同的关联 信息。 表2 3c c w o r l d 语义实例 t a b l e2 - 3a ne x a m p l eo f c c w o r l ds e m a n t i c s g d bi dy s ui d g d b ：1 2 0 2 3 1p 2 1 3 5 9 g d b ：1 2 0 2 3 lp 3 5 2 4 0 表2 - 4c o w o r l d 语义实例 t a b l e2 - 4a ne x a m p l eo f c o - w o r l ds e m a n t i c s g d bi dy s ui d g d b ：1 2 0 2 3 1p 2 1 3 5 9 g d b ：1 2 0 2 3 1p 3 5 2 4 0 n g d b ：1 2 0 2 3 1 ，g d b ：1 2 0 2 3 1 ) v 最后，介绍一个在本文中非常重要的概念，即赋值式的概念【3 2 1 。 定义3 ：映射表m 上的赋值式p 是一个函数，它将m 中的每一个常量 映射到自身，将m 中的每一个变量v 映射到v 在其中出现过的那些属性值 域交集中的某一个值。特别地，如果v 出现在形如v - s 的表达式中，那么有 p ( v ) gs 。 2 ，1 2 映射约束与映射推导 接下来，映射表将被看作是不同资源间进行信息交换的约束条件【2 5 l 。 这种处理的目的是为了推导出新的映射约束并对其一致性进行检验。 通过把映射表处理成约束，可以鉴别不同资源上数据目标间的合法或 非法映射。也就是说，给定一组被约束的目标，能够辨别它们是否满足一 燕山大学工学硕士学位论文 个映射表m 。下面是对于新的约束的可满足性( s a t i s f i a b i l i t y ) 【3 剐的定义。 令m 是一个从属性集x 到属性集y 的映射表，则y 。( x ) ( 其中x e d o m ( x ) ) 的定义如下。 y 。( x ) = y 1 3 t m 并且存在一个映射表m 上的赋值式p 使得o f f x ) ：x 且 阿功= y ) 注意到，y m ( x ) 包含d o m ( y ) 中那些值x d o r a ( x ) 依据映射表m 能够映射 到的所有属性。 定义4 ：令u = x u y 。表达式x 里寸y 是u 上的一个映射约束。如果 有t y 】y m ( t ( x ) ) ，则u 中必有一个的元组t 满足x 竺叶y 。而且，对于 每一个t r 都满足x 里一y ，则称关系r 满足x 生y 。 设r 、r 1 分别是r 【u 】和r u 】上的两个关系。设m 为x 到y 的映射表。 这里x _ c u ，y _ c u 。令r ”为关系r 和r 的笛卡儿积，r 中的元组t 与f ，中的元 组t 一一对应。 此时，可以利用1 1 1 作为约束条件对上面得到的笛卡儿积r ”进行过滤。 令t ”为笛卡儿积r ”中的元组，如果m 上不存在赋值式p 使得t ”i x 】p ( m ”， 且t ”【叼7 【y ( o 鞠”。( p ) ) 。那么这个元组，就必须从关系r ”中删除。举例 说，设从x 到y 的映射表m ，m 上的赋值式p ，以及一个值x 取( p ( m ) ) 。 那么，值x 将与y 的域中的一组特定值相关，或者说与集合y ( 啾。( p ( m ) ) ) 相关。因而，参照于映射表m 和赋值式p ，满足t x 】- x 的一个元组t e r 可 能仅仅被映到一个元组t r 上，这里川e l t v ( a x ：x ( p ( m ) ”。 可以看到，上面的方法将两个关系实例做了笛卡儿积，这样做的目的 是保证不遗漏任何的隐含的映射关联。毫无疑问，在实际应用中会占用大 量的存储空间和计算时间。针对此种情况，可以在实际应用中，借鉴分布 式数据库中的半连接方法进行优化。也就是说，在实际进行数据的传输和 做笛卡儿积之前先对当前感兴趣的属性进行投影，借此减少运算和传输的 代价。然而，这种优化并不是对于每种具体情况都有效。但这种方法确实 可以保证得到较完备的附加信息，在第4 章的实验验证部分，将对映射表的 推导能力进行实际验证和分析。 接下来用一个运行实例分析上述推导的执行过程，其结果如表2 - 5 到表 1 4 第2 章p 2 p 系统映射一致性问题的研究 2 _ 8 所示，前两个表分别与g d b 和s w i s s p o r t 中的数据库关系相对应。表2 7 是g d b 年t l s w i s s p o r t 间遵守c c - w o d d 语义的映射表。依照上述步骤，将前两 个表做笛卡儿积，并使用映射表作为约束条件对结果进行过滤。最后，得 到表2 8 中所示的关系，其中的映射均为合法的，例如，对于该关系中的第 一条元组存在赋值式p ( v ) = g d b ：1 2 0 2 3 1 以及赋值式p ( v ) = p 2 1 3 5 9 。 表2 - 5g d b 中的关系 t a b l e2 5r e l a t i