XML查询中具有位置谓词的树模式匹配方法  

Twig Pattern Matching with Positional Predicatesin XML Queries

作　　者：李发金[1] 廖湖声[1] 高红雨[1] 

机构地区：[1]北京工业大学计算机学院,北京100124

出　　处：《计算机研究与发展》2013年第S1期1-11,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金青年科学基金项目(61202074);北京市自然科学基金项目(4122011)

摘　　要：XML树模式匹配是XPath查询等XML数据处理中的核心操作.采用整体匹配方式的XML树模式查询算法已经得到了深入研究,然而这些算法均未考虑到XPath表达式中位置谓词的实现需求.由于无法从整体匹配的结果中筛选出符合位置谓词的查询结果,使得这些算法无法用于实现具有位置谓词的XPath查询.为了支持具有位置谓词的XML树模式查询的实现,为XML树模式扩展了位置谓词和兄弟轴,提出了一种基于嵌套栈的整体模式匹配算法TwigPos,所实现的XPath查询能够同时支持存在谓词、位置谓词和兄弟轴.在不同数据集上的实验说明该算法能够有效地处理此类XML查询请求,增强了XML树模式查询技术的实用性.Twig pattern matching is acore operation in XML query processing(such asXPath). Although holistic twig pattern matching algorithms have been studied intensively nowadays,little attention is paid on positional predicates defined on navigation axis in XPath expressions.Since query results fail to be selected from the holistic pattern matching results,those algorithms cannot be used to implement XPath queries with positional predicates.For implementation of XPath query with the positional predicates,in this paper,we extend the traditional twig pattern to a new one to deal with both positional predicates and following-sibling axis.We also propose the corresponding holistic twig pattern matching algorithm TwigPos to process XPath query withlabel test predicates,positional predicates and following-sibling axis.Comparison experiments on large benchmarksshow that our algorithm is efficient and practical.

关 键 词：XML XPATH 树模式查询 位置谓词 兄弟轴 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]