论文部分内容阅读
近十来年,互联网技术得到了快速发展,互联网用户不断增加,网络应用得到迅速普及,网络数据的增长速度超乎想象。XML语言(可扩展标记语言)作为互联网上数据交换和共享事实上的标准,已经广泛应用于各种互联网平台。XML也成为当前一种十分常用的数据存储格式。众多领域都使用XML格式存储其网络数据信息。很多情况下,单个XML文档的体积已经远远超出有限的计算机内存的大小。如何从大量的XML数据中获得用户需要的信息成为人们必须解决的问题。传统的将整个XML文档加载到内存中,然后再对数据进行查询的办法显然已经无法对这种大小远超过内存容量的XML数据进行处理。因此,另一种形式的XML数据—XML流数据逐渐获得了研究者的普遍关注,同时流数据方面的特点也对查询处理提出了新的挑战。XML流数据具有以下特征:数据以标签(tag/token)为单位实时到达;数据进入处理系统的顺序无法控制;数据可能是持续到来的,并且有可能不会结束。处理XML流数据的系统一般使用XML解析器对数据进行解析,使用XPath或XQuery来表示用户的查询需求。XML流数据处理系统会在处理完某个数据元素之后便将其转发或者丢弃,以减少数据对内存的占用。在如今的数据研究领域,找到一种高效地查询和处理XML流数据的方法具有重要意义。对XML流数据进行处理的要求是在计算机内存有限的情况下,对持续的查询给出高效实时的响应。目前,已经有不少处理XML流数据的方法。然而现有的XML流数据处理方法尚不能满足人们对数据的处理需求。它们或无法支持丰富多样的查询需求,或无法对查询给出实时高效的响应。本文针对现有的XML流数据处理方法的缺陷,提出了一种新的XML流处理方法。该方法以下推自动机为基础,主要针对XPath语言表示的用户查询。该方法为XPath语言提供了强有力的支持,不仅能够处理查询中的祖先后代关系和双亲子女关系,也能够支持多层嵌套的谓词和多重并列谓词,覆盖了XPath语言的核心功能。该方法以XPath中的查询步为基本设计单元,不会出现自动机状态数暴增的情况。同时该方法在一次遍历数据的前提下,能够找到所有查询结果,具有较高查询效率。该方法弥补了前人处理方法的不足,它具有高效、实时的特点,能够更好的满足人们对海量XML数据的处理需求。