基于模式P2P系统复杂查询处理研究摘要：通过以关系名的同义关键字作为模式信息的索引键以及垂直分区关系元组，设计了用结构化重叠网络索引模式和数据的方法。基于这两级索引，提出了支持多属性复杂查询的算法。定性分析和比较表明，该方法比相关工作更接近P2P数据管理的理想目标。关键词：对等计算机模型;基于模式的;复杂查询处理：TP311．13文献标志码：A：1001－3695(2007)07－0081－050引言??Peer－to－Peer模型（又称P2P模型或对等计算模型）是一种新型的体系结构模型。与传统的客户服务器模型不同，P2P系统中没有集中控制点，从而避免了单点故障。P2P网络是可扩展的、容错的、动态的，节点可以容易地加入和离开网络。因此P2P计算吸引了学术界和工业界越来越多的关注。??支持复杂查询处理是对现有P2P系统中基于键(Key)和关键字搜索的自然扩展。要在P2P系统中实现复杂查询回答功能需要解决若干个挑战[1]：①P2P系统中Peer可以在任何时刻、任何地点，以任何方式离开网络，因此产生了完全动态和即兴的网络环境。这样底层协议必须足够健壮以处理Peer和网络故障。②查询处理必须用完全分布式的过程。在动态P2P环境中，由于缺乏全局知识，查询执行和优化都非常困难。③为了有效利用系统中的资源，自治Peer之间必须协作。这通常涉及更多的优化问题，如协调、位置感知Peer聚簇和负载平衡等。总而言之，P2P查询处理必须能够有效且高效地处理自治Peer组成的大规模动态分布式网络[1]。??本文关注于P2P系统中的关系查询处理问题。这是一个重要的研究领域，在电子学习、P2P数据库、监视和流处理等领域具有广泛应用前景。一般认为大规模P2P网络中信息以关系元组的形式存在，这些元组可以用SQL查询检索。每个节点保存全部数据元组的一部分。属于一个关系的元组的各部分可以分布在多个节点上。??P2P系统依赖于重叠网络以便独立于底层的物理网络拓扑。重叠网络有非结构化和结构化之分。在非结构化重叠网络中对数据放置方式没有严格要求，求值复杂查询简单；但是必须使用洪泛算法在网络中分布查询，开销大却不能保证在有限的跳步内找到存在的数据，阻碍了低带宽用户的加入，限制了P2P技术的应用。结构化重叠网络通过对数据放置的严格限制，提供对查询效率和系统健壮性的强大理论保证。但是，结构化重叠网络本身只能支持确切匹配和范围查询，不能直接支持共享关系数据所需的连接、聚集等复杂查询。因此，PIER[2]通过水平分区关系表，利用结构化重叠网络索引关系的某个属性来支持复杂查询。但是它必须假定系统中所有节点服从同一个模式，不适合P2P语义异构网络中共享信息；并且它仅能索引一个模式元素，而不能有效地支持多属性复杂查询。因此，本文研究基于结构化重叠网络共享模式异构关系数据的方法。定性分析表明，该算法是可取的。??1框架概况??1．1Peer??Peer采用各自的模式来描述自己共享的数据，所关心的Peer模式是Peer节点的外模式。在节点内部，内模式和外模式之间的映射采用传统数据库中的视图机制实现，在此不再赘述。Peer模式中为关系和关系的各属性均维护一些关键字充当同义辞典[3]，进一步描述其语义。这样，可以不必人工预先指定模式映射。每个节点由本地数据库LDB、垂直分区器VP、索引分区缓冲区IPB、元数据抽取器ME、本地模式缓冲区LSB、索引模式缓冲区ISB组成。首先，ME从LDB中抽取外模式以及相应的同义辞典放入LSB中，它是本节点提供的共享数据模式。同时ME使用下面介绍的模式索引该模式。ISB存放按照模式索引发布到此节点上存储的模式信息，然后VP按照共享模式从LDB中提取共享数据，将这些数据垂直分区成(tid，关系名：属性名，属性值)三元组[4]后发布到结构化实例索引中。IPB用来存放按照实例级索引分配给本地节点进行维护的三元组。笔者借鉴PIER[5]中软状态的方法来确保数据源故障的情况下，它所发布的数据和模式均会最终被丢弃。??1．2P2P网络??图1从宏观角度粗略地描述了本文方法的核心思想：用户通过用户界面可以看到用户当前登录的节点p的ISB和LSB中的模式，用户可以据此提出查询q。p收到查询后一方面直接用该查询中使用的关系名和属性名检索实例级索引，获得q的结果；另...