Abstract: Focused on the characteristics of processing semi-structure eXtensible Markup Language (XML) streaming data such as the stream real-time arriving continuously, requiring to be read sequentially and only once into memory, the query must be processed on the fly and usable buffer size is very little, and concerned the current status for limitation of query expression and inefficiency in practical applications of processing large scale data, QXList method was proposed for massive data processing based on SAX parsing XML. Data model and algorithm integrated framework were defined firstly. The integrated methods to process predicate and wildcard were discussed in detail. Layer value was used to determine the relationship of two elements and relational pointer was constructed to link multiple candidate nodes' lists to get query results in this method. Two optimal points were analyzed for decreasing buffer size. The experimental results show that the proposed approach is effective and efficient to this problem, and outperforms the state-of-the-art algorithms about 30 percent such as QStream++ and query engines MonetDB and SAXSON especially for large processed data. At the same time, memory usage is nearly constant.

Key words: streaming data, query processing, XPath query, relational pointer, buffer management

摘要： 针对半结构化可扩展标记语言(XML)流数据实时在线到达,顺序性一次访问及处理时效性高、缓存量小的需求,以及目前算法在大规模数据处理中查询表达式的能力有限、效率尚不能满足实际应用的现状,基于SAX解析,提出以列表及关系指针组合处理XPath查询的QXSList方法。首先定义数据模型,给出算法实现的整体框架,然后分别针对两个不同的XPath查询片段重点考虑了谓词判断条件和通配符的处理方法;该方法通过层次值计算判断节点的结构关系,利用关系指针链接多个候选节点列表,获取查询查询结果;最后分析给出优化算法,进一步减少缓存管理。通过实验对该方法与QStream++方法及MonetDB和SAXON查询引擎的运行时间和内存占比进行分析,得出与同类算法相比,随着数据量级的增加,效率提升在30%以上,且运行过程中内存占比接近于常量。

关键词: 流数据, 查询处理, XPath查询, 关系指针, 缓存管理