可扩展标记语言(eXtensible Markup Language,XML)是W3C提出的一种半结构化的数据描述语言,由于具有高可读性、可扩展性、自描述性以及跨平台等特性,在互联网上得到了广泛的应用。随着互联网技术的发展,互联网用户持续增加,网络应用的普及,互联网上数据规模正在不断的扩大。XML作为目前互联网数据的存储格式、数据共享和数据交换的主导标准,在许多应用中都有广泛的使用。近年来大数据和云计算的飞速发展,XML已经不再局限于单个文档,更多的情况是数据以流的形式出现,不能完全存放于一个文档之内。很多现有的应用中,XML的文档已经不能够一次性都放入内存中了。传统的XML处理方法依赖于将XML放入计算机的内存中,将XML构建成一棵树的结构,对XML进行查询。很明显,这样的查询方法已经不再适用于当前的XML查询。而使用XML流数据的方式,将海量的数据以流的形式出现,单边扫描进行查询处理的方式受到了研究人员的普遍关注,XML流数据查询也成为了数据领域的热点。XML流数据由于数据实时到达,需要实时处理,数据进入的顺讯不可控,而且是持续到来,没有结束,一旦数据处理完毕,除非特意保存,再次处理需要花费昂贵的代价这些特性,使得如何从海量XML流数据中查找到有用的数据成为一个富有挑战的问题。处理XML流数据的过程一般会使用例如SAX等的XML解析器对XML进行解析,使用例如XPath、XQuery等的XML查询语言对XML进行查询。为了保持占用较少的内存,处理完成后的XML元素会被丢弃。目前,虽然已经存在很多XML流数据查询的方法,但是这些方法在描述能力上稍显不足,有些不支持谓词筛选,有些的查询效率不高等。因此,研究一种高性能的功能丰富的针对XML流数据的查询方法就变得尤为重要。传统的查询方法不能够应用到流数据中,现有的流数据查询方法又有一些缺陷,根据这些问题,本文提出了一种基于图归约的XML查询自动机(GRAT),采用一种图结构来表示针对不同XML流元素的子查询任务之间的关系,通过图的归约变化来实现XPath查询。该方法提供了XPath查询的主要功能,并且能够在XML流数据一次遍历的过程中有良好的表现。由于图结构可以有多个前驱和后继节点,在处理上非常灵活,也便于扩展。另外,图结构的每个节点保存了查询中所必要的节点,每个节点的移动没有其他不必要的操作,因此效率上也很高。对于嵌套的XML流数据,普通的查询方法需要花费高额的代价进行处理,而对GRAT来说只需要添加一些节点即可。不同于树型结构的自动机和层次栈,使用图归约的查询算法使用很少的缓存,而每次查询不是扫描图结构的所有节点,而是指定的入口节点,也节省了很多时间。GRAT还将查询应用到了多个XML流嵌套的分布式环境中。实验表明,基于GRAT的查询算法能够高效地完成复杂的XML查询,具有高效,可扩展和实时等特点,能够更好地处理多源XML流数据处理的需求,并且流数据处理的吞吐量达到了较高水平。