段克松，施化吉，李星毅

（江苏大学 计算机科学与通信工程学院，江苏 镇江212013）

0 引 言

在XML查询中，如何对大量的XML数据流进行查询匹配是一个关键问题。目前，人们已经取得了一定的成果，如XFilter，YFilter，XPush技术等。但是面对海量XML数据流进行查询处理时依然很难满足实际应用的需求。最近有学者提出利用能够自然处理树状数据结构的树自动机来实现XML查询匹配的方法XEBT［1］，提供了一个很好的思路。但该方法存在以下两个问题：①如果系统中有n条XPath查询语句，则转换后系统会存在n个非确定的树自动机；②在XPath表达式与树自动机的转换过程中，把谓词直接转换为树自动机的状态，造成系统运行时对于每个查询都要进行谓词匹配，相对于只在结构匹配成功时才进行谓词匹配效率明显比较低。本文针对上述认识，提出了一种高效的XML过滤技术XTAFilter。该技术具有以下特点：通过构建hash表来存储谓词信息来替代把谓词作为树自动机状态的方法，使得该技术只有在结构匹配成功时，才进行谓词匹配，而不是每次查询都进行谓词匹配，提高了匹配效率；同时利用共享路径构建树自动机，减少了匹配消耗的时间，提高了查询匹配的效率。

1 相关概念

XML（extensible markup language）已成为互联网上数据存储、交换和表示的事实性标准。在具体的XML应用中，查询通常使用XPath（XML path language）语言，通过结构 （路径表达式）和内容 （谓词）来进行信息的查询匹配。XPath是XML数据流查询匹配的基本机制，支持丰富的路径查询特性。它由一系列位置步骤组成，每个位置步骤包括轴、节点测试和零个或多个谓词。……