论文部分内容阅读
随着信息技术的不断发展，特别是Internet技术的发展，各行业的信息量呈爆炸性增长趋势，一些应用中的数据量已经从几十个Terabyte发展到Petabyte，并且在不断扩大。地理上广泛分布的用户都希望能够访问、分析和使用这些海量的分布式数据，而用户的任务往往计算复杂且计算量庞大。这些应用就促使了数据网格技术的发展。 数据网格是一种分布式数据管理体系结构，能够为分布在网格中远端的数据资源提供协同的管理机制，可以通过集成网络上分布的多个数据集等资源，形成单一虚拟的数据访问、管理和处理环境，建立分布海量数据的一体化数据访问、存储、传输、管理与服务架构。 数据网格下的非平凡任务通常是把数据访问和数据分析结合在一起的，它们能够被有效地封装为数据库查询的形式来表示对网格资源的请求。因此查询处理在数据网格中具有非常重要的作用，并且能够应用于全球气候模拟、高能物理、生物计算等数据密集型应用中。 数据网格为不同资源的协同使用以及广域范围的查询处理提供很多便利，但是网格资源的异构性、不可预测性以及可变性使得网格中的查询处理非常复杂。本文对数据网格分布式查询处理的若干关键问题进行了研究，主要包括两路连接查询处理算法、多路连接查询处理算法以及分布式聚集查询处理算法等，主要研究成果包括以下几个方面： (1)本文提出了基于网络带宽差异的数据网格两路连接查询处理算法。算法中首先提出了两路关系缩减算法，通过对操作关系的缩减来有效地减少网络的数据传输量；然后提出了行分块的数据传输方式，该传输方式可以减少数据的传输时间，同时减小网络延迟对数据传输的影响，具有较强的可靠性；接着提出了块归并连接操作算法，该算法能够在往内存中读入数据的同时，尽快地把连接结果输出，为后续到达的数据块腾出空间，避免数据在内存和磁盘之间来回移动。 (2)本文提出了基于多个完全副本的数据网格两路连接查询处理算法。算法中首次提出了最小-最大边匹配的理论及其生成算法，可以用于操作关系的选择以及计算结点的选择。该理论确保操作关系始终在高效的结点上并行执行连接操作。操作关系多个完全副本的存在增加了查询处理的并行性，有效地减小了查询的响应时间。 (3)本文提出了数据网格多路连接查询处理算法。算法中首先提出了n路关系缩减算法，用于减小 n个操作关系的大小，仅使得操作关系中满足连接条件的元组参加连接操作，从而减少网络的数据传输量；然后对多路连接查询处理中计算结点的调度问题进行了形式化描述，并证明该问题是NP-完全的，给出了一个近似算法用于解决该问题，近似算法的应用使得多路连接查询以部分并行的方式进行处理；最后提出了一个创新的方法用于控制计算结点上中间连接结果的传输，使得计算结点在进行连接操作的同时往其后续结点传送连接结果，这样就可以使多路连接查询以流水线的方式并行执行。 (4)本文提出了当操作关系具有多个部分副本时的分布式聚集查询处理算法。首先在最短路径树的基础上提出了分布式聚集树的概念，并且给出了分布式聚集树的生成算法。然后，让多个部分副本所在的结点形成一个分布式聚集树，并且按照该分布式聚集树表明的结点顺序，在每一个结点进行散列去重操作的同时往其父结点传送数据，这样就可以使分布式聚集操作以流水线方式并行执行。当系统性能发生变化时，可以对分布式聚集查询处理进行自适应调整，以确保用尽可能短的时间完成分布式聚集查询处理。 (5)本文提出了当操作关系具有多个部分副本时的分布式聚集-连接查询处理算法。首先，给出了基于部分副本的n路关系缩减算法，该算法可以保证最小化网络的数据传输量；然后提出了副本最大覆盖的概念，为操作关系选择合适的副本，这样就可以最大化查询处理的并行性；接着在最小-最大边匹配理论的基础上选择计算结点，确保聚集-连接操作始终在高效结点上执行；最后给出了系统性能发生变化时查询处理的自适应调整算法，通过计算结点的重新选择，就可以使得系统负载保持平衡的同时，最小化查询的响应时间。