1.一种XML流数据的快速查询方法,其特征在于,包括以下步骤:
步骤1、XML Schema定义预处理:构建查询导航PAT树
步骤101、搜索根元素并根据其元素信息创建查询树的根节点;
步骤102、判断是否为Schema定义文档中的最末元素,如果是结束此预处理,否则跳转到步骤103;
步骤103、通过当前元素寻找所有子元素,构建相对应的子标签节点并放入查询树中,在该子标签节点中放入此子元素标签特定的详细信息,同时在父-子标签节点中放入导航信息;
步骤104、根据节点及其所有直属孩子节点构建Patricia tries辅助快速搜索结构,中间PAT节点记录“共同”部分的长度,叶子PAT节点指向对应的直属孩子标签节点;
步骤2、查询参数预处理:构建谓词表达式语法计算树、查询导航PAT树
步骤201、如果谓词表达式不存在的话,跳转到步骤204,如果存在,顺序执行下一步骤
202;
步骤202、按照表达式EBNF范式,语法分析谓词条件表达式,并把操作数作为叶子节点,相关的操作符作为其父节点,依次类推构造谓词语法计算树;
步骤203、把每个条件表达式子项中的标签路径追加到查询标签路径表中;
步骤204、判断是否查询标签路径列表末尾,如果不是执行步骤205,否则结束查询参数预处理;
步骤205、针对每一查询标签路径,首先分拆成一个标签序列,按照顺序处理每一个标签,在查询导航PAT树结构中的对应标签节点标注为需要查询聚焦:此标签节点状态为“通过”,同时把父标签节点通向该标签节点的每一个PAT节点标注状态为“通过”,其它的PAT节点的状态为“拒绝”;然后顺序检查下一个标签,直到此标签序列结束,跳转执行步骤204;
步骤3、查询处理并提供二维结果集
步骤301、解析目标XML流数据文档,解析过程中根据产生的事件回调不同方法,其中事件“StartElement”执行步骤302、事件“Characters”执行步骤303、事件“EndElement”执行步骤304;
步骤302、输入标签匹配搜索查询导航PAT树中从当前标签节点也就是父标签节点开始通过PAT辅助结构和其对应的快速搜索算法,能够快速检查确定是否定位到正确的孩子节点标签上,根据匹配结果更新上下文状态,包括:“接受”和“拒绝”状态;
步骤303、收集本次事件对应的标签值并放入缓存中;
步骤304、如果到达标注谓词计算位置的标签节点,则提取表达式中的各标签路径对应值,然后开始按照谓词表达式语法计算树结构来计算表达式,结果为真则执行步骤305,结果为假则拒绝收集以此标签节点为根节点的分支的所有标签值集;
步骤305、如果计算结果为真并且本标签节点为“接受”状态,则收集本次标签对应值并放入缓存中;
步骤306、收集所有缓存中的标签对应结果集,合并组成二维标签结果集,结束查询处理,并返回二维结果集。
2.如权利要求1所述的XML流数据的快速查询方法,其特征在于,步骤3中查询处理过程以XML流数据为主导,查询导航PAT树为辅助指导作用,同时记录系统的状态变化或者上下文变化;假定当前流数据节点元素Nd下的某个孩子节点Ndc,其标签为Tdc,需要搜索匹配的对象是查询树中对应节点Nq下的所有孩子标签节点标签列表TLqc,找到标签Tdc对应查询树中孩子标签节点后同时检测其是否为查询聚焦的标签节点。因为该标签列表是当前节点下所有孩子节点的全集,对应需要的查询聚焦的孩子节点标签列表为TLqfc,二者的关系为TLqc包含TLqfc;采用Patricia trie匹配搜索算法进行匹配,分为如下几种情况:A)查询聚焦标签列表TLqfc为空,意味着以Ndc为根节点的数据分支无须继续查询处理,可以剪掉此数据分支;
B)TLqc等于TLqfc,意味着Ndc数据节点无需匹配必然是是用户查询聚焦的标签,可以继续后续查询处理;
C)TLqfc不为空同时TLqc真包含TLqfc,采用Patricia搜索算法,其中PAT节点记录标签跳过的共同部分长度,分支对应不同的目标匹配标签,搜索从PAT根节点依次向下,直到到达“接受”或“拒绝”PAT节点;如果是“拒绝”PAT节点,意味着以Ndc为根节点的数据分支无须继续查询处理,可以剪掉此数据分支;如果是“接受”PAT节点,意味着此Ndc为查询聚焦的标签。