web数据管理的分布式图数据存储和查询.pdf

捅 要 Wide 随着万维网(WorldWeb，WEB或WWW)规模和应用的飞速发展， Web数据爆炸式增长，Web数据已经形成了世界上最庞大的数据库。此外， Web数据的相关数据如有哪些信誉好的足球投注网站记录、各种Web服务使用记录数据等都在迅速增 长。与传统的数据相比，Web数据具有非结构化，增长速度快以及数据类型多 样的特点，这使得Web数据的处理方式和现有的数据处理方式存在着较大的区 别。在现实的各个领域中，Web数据处理技术有着广泛的需求和应用，因此对 于Web数据的研究已经成为当今计算机科学的一个重点。 为此，我们介绍了cwl[]1，一种新的海量数据查询和存储工具。在CWI 的实际应用中，需要对大量的Web数据进行存储和索引，并且在此基础上实现 关键字和结构信息的查询。TLGM[2]和TLGM·QL【3】作为CWl的一部分，满足 了上述要求。本文主要着重于在分布式的环境下实现TLGM数据模型的存储， 并且实现了TLGM-QL的四个基本算子。在设计和实现过程中，我们发现真实环 境数据的不均衡性会导致存储和查询算法的退化，从而降低效率。针对这些问题，‘． 本文提出了一系列均衡措施，保证各节点的运算和存储负载差异保持在一个合理 的范围之内。在此基础上，本文提出了新的子图重构的算法，以支持对于图结构 的查询，并通过均衡措施保证算法的效率。本文通过对虚拟数据和真实环境数据 的实验验证了系统的有效性。 本文的贡献和创新之处总结如下： 1．本文分析了Web数据的特性，并引入了TLGM模型来说明图数据在存 储、索引和查询方面和传统数据的区别。本文首先在集中式的环境下分 析了使用关系数据库存储图数据的可能性，收集整理了若干图数据，并 且设计了一系列的查询，通过实验来验证该条件下图数据存储和查询的 效率，由此说明集中式存储的不足和局限性。 2．分析了TLGM的特性，从而阐述在分布式环境下实现该数据模型存储和 查询的实现方法。在此基础上，我们概括了TLGM图数据模型可以满足 的各类查询条件，并在此基础上提出了四个基本的算子，并举例说明这 些算子具有良好的扩展性。同时我们给出在分布式环境下这些算子的实 现方法以及具体算法。 3．提出了新的图重构的算法，介绍了如何使用该算法来实现对于图结构的 查询。本文通过MapReduce【4】框架来实现该算法，该算法具有良好的 3 可扩展性，并允许我们缓存重构的结果从而提高效率。在实现过程中， 我们发现不同数据节点负载差异较大，从而通过对原算法进行若干修改 从而达到负载均衡。同时我们生成并收集了若干图数据，并且通过一系 列的实验来验证该方法的有效性。 综上所述，我们整理并分析了Web数据存储、索引和查询中的问题，并且 通过TLGM模型将此转化为图数据存储、索引和查询的问题。并根据实验结果 我们确定了以MapReduce的分布式框架作为基础，在此之上设计并实现了图 数据的四个基本算子和图重构算法，通过实验证明了我们的研究成果具有良好的 效率和扩展性。 关键字：TLGM数据模型，分布式存储，Web数据管理 中图分类号：TP31 4 ABSTRACT W计hfhedramatic of Wide WWW(WorldWeb)，web development datawitnessa boominboth andscale，which up quantity explosive makeswebdata the databaseintheworld．Moreover， hugest