一种支持通配符查询的XML模式匹配算法

doi:10.3969/j.issn.1006-2475.2016.04.014

计算机与现代化

一种支持通配符查询的XML模式匹配算法

(南京航空航天大学计算机科学与技术学院,江苏南京211106)

收稿日期:2015-11-20 出版日期:2016-04-14 发布日期:2018-09-30
作者简介:陈冲(1990-),男,山东菏泽人,南京航空航天大学计算机科学与技术学院硕士研究生,研究方向：XML数据库; 蒋夏军(1973-),男,江苏南京人,讲师,博士,研究方向:时空数据库,计算机仿真。
基金资助:
江苏省自然科学基金资助项目(BK20140826)

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query

(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China)

Received:2015-11-20 Online:2016-04-14 Published:2018-09-30

摘要/Abstract

摘要：

XML查询语言当中，包含通配符*的查询能够方便有效地满足一些特殊查询要求，但在大数据时代下XML文件容量与结构复杂性不断增加，现有支持通配符查询的算法需消耗巨量内存来解析XML，并且在对嵌套通配符处理时需要大量的单路径匹配操作和局部结果的缓存。针对此现状，结合现有经典算法，提出一种新的、能够高效解决小枝模式当中含有通配符*的查询算法—WTwigList。该算法首先对查询模式进行通配符的层次关系处理，减少不必要的通配符匹配，以数据流形式解析XML文件并执行局部的扩展Dewey编码，经过滤操作后得到有序的叶子节点编码列表，在列表中执行匹配操作得到结果；其次在真实和合成数据集上做大量实验，结果表明WTwigList算法与现有算法相比，能够有效提高查询效率，在空间效率上具有一定优势，且能够快速准确地处理查询模式中PC关系。

关键词: 通配符查询, 流数据处理, 扩展Dewey编码, XML模式匹配

Abstract:

In XML query language, the wildcard query which includes “*” can effectively meet some special query requirements. But in the big data era, with the increasing of the XML file size and structural complexity, the existing algorithms which support wildcard query need huge amounts of memory to parse XML file and also need many single path matching operations and local result caching. Aiming at this situation, we propose a new XML pattern matching algorithm named WTwigList to solve the twig pattern containing the wildcard effectively. First, the hierarchical relationship of wildcard in the query pattern is processed to reduce unnecessary wildcard matching. Then the XML file is parsed as data stream pattern and the local Extended Dewey encoding is executed. After filtering operation, the ordered list of leaf node encoding is gotten, and the matching results can get from the list matching operations. A set of experimental result on both reallife and synthetic dataset demonstrates that WTwigList improves query efficiency andis of advantages in space efficiency, and it can deal with the P-C relationship quickly and accurately.

Key words: wildcard query, stream data processing, Extended Dewey Encoding, XML pattern matching

中图分类号:

TP311

陈冲,蒋夏军. 一种支持通配符查询的XML模式匹配算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.04.014.

CHEN Chong, JIANG Xia-jun.

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.04.014.

参考文献

［1］ Al-Khalifa S, Jagadish H V, Koudas Nick, et al. Structural joins: A primitive for efficient XML query pattern matching［C］// Proceedings of the 18th International Conference on Data Engineering. 2002:141-152.

［2］ Bruno N, Koudas N, Srivastava D.Holistic twig joins: Optimal XML pattern matching［C］// Proceedings of 2002 ACM SIGMOD International Conference on Management of Data. 2002:310-321.

［3］ Jiang Haifeng, Wang Wei, Lu Hongjun, et al. Holistictwig joins on indexed XML documents［C］// Proceedings of the 29th International Conference on Very Large Databases(VLDB). 2003:273-284.

［4］ Lu Jiaheng, Chen Ting, Ling Tokwang.Efficient processing of XML twig patterns with parent child edges: A look-ahead approach［C］// Proceedings of the 13th ACM International Conference on Information and Knowledge Management(CIKM). 2004:533-542.

［5］ Che Dunren, Ling T W, Hou Wenchi. Holistic Booleantwig pattern matching for efficient XML query processing［J］. IEEE Transaction on Knowledge and Data Engineering, 2012,24(11):2008-2024.

［6］李国良，冯建华，塔娜，等. TwigStar——快速处理XML twig查询中含通配符*的算法［J］. 计算机研究与发展， 2006,43(z3):430-437.

［7］ Lu Jiaheng, Ling Tokwang, Chan Chee-Yong, et al. From region encoding to extended dewey: On efficient processing of XML twig pattern matching［C］// Proceedings of the 31st VLDB Conference. 2005.

［8］ Lu Jiaheng, Ling Tokwang, Bao Zhifeng, et al. Extended XML treepattern matching: Theories and algorithms［J］. IEEE Transactions on Knowledge and Data Engineering, 2011,23(3):402-416.

［9］孟小峰. XML数据管理: 概念与技术［M］. 北京:清华大学出版社, 2009:126140.

［10］毕鑫,王国仁,赵相国,等. XML数据中Twig查询处理与优化技术研究综述［J］. 计算机科学与探索, 2013,7(9):769-782.

［11］Knorad C, Magnize F, Validating XML document in the streaming model with external memory［J］. ACM Transactions on Database Systems(TODS), 2013,38(4):84-87.

［12］张红. 基于ASP.NET与XML的异构数据库数据交互解析与实现［J］. 计算机与现代化, 2011(1):18-19.

［13］Hachicha M, Darmont J. A survey of XML tree pattern［J］. IEEE Transactions on Knowledge and Data Engineering, 2013,25(1):29-46.

［14］David Hunter, Jeff Rafter, Joe Fawcett,等. XML入门经典［M］. 吴文国译. 4版. 北京:清华大学出版社, 2009.

［15］University of Washington.XMLDataRepository［EB/OL］. http://www.cs.washington.edu/research/xmldatasets/, 2015-11-15.

［16］Xu Xiaoshuang,FengYucai,Wang Feng. Efficient processing of XML twig queries with all predicates［C］//Proceedings of the 8th International Conference on Computer and Information Science Conference. 2009:457-462.

[1]	杨贵福1，胡佑蓉1，刘淑霞1，刘振邦2,3，包宇2. 基于命名管道和异构通信机制的多应用场景下驱动升级策略[J]. 计算机与现代化, 2020, 0(05): 44-.
[2]	李华莹,刘丽,刘怡静. 面向软件生态的资源定位技术[J]. 计算机与现代化, 2020, 0(03): 24-.
[3]	吕坦悦1,2，陆小敏1,2，王健1,2. 基于决策树和层次分析的地铁车辆健康评估[J]. 计算机与现代化, 2020, 0(03): 29-.
[4]	张紫璇,陆佳民,姜笑,冯钧. 面向水利信息资源的智能问答系统构建与应用[J]. 计算机与现代化, 2020, 0(03): 65-.
[5]	魏庆征，杨云，李凌燕，魏海洲 . 基于灰色马尔科夫的外汇预测模型[J]. 计算机与现代化, 2020, 0(02): 12-.
[6]	苏林萍，安然，李为，崔文超，张晓良. 基于Hadoop的电力运维审计系统的设计[J]. 计算机与现代化, 2020, 0(01): 49-.
[7]	梁晓琦1，戴永辉2，藏鸿雁1. 基于双重定位技术的智能考勤系统[J]. 计算机与现代化, 2020, 0(01): 58-.
[8]	姜书浩1，2，张立毅1，2，周娜1. 基于用户偏好动态变化的协同过滤推荐[J]. 计算机与现代化, 2020, 0(01): 75-.
[9]	阿不都克里木·玉素甫1,2，王亮亮1. 基于自主可控平台的FFMPEG在线视频转换系统[J]. 计算机与现代化, 2020, 0(01): 81-.
[10]	戴文博，徐珞，卫津逸. 面向军事信息系统的自动化软件部署算法[J]. 计算机与现代化, 2020, 0(01): 90-.
[11]	戴延军1，吴志强2，刘杰1，刘朝晖1，陈智2，肖安红2. 一种安全关键软件系统符号执行优化方法[J]. 计算机与现代化, 2020, 0(01): 96-.
[12]	王云，李丛. 基于改进关联规则算法的警情数据分析[J]. 计算机与现代化, 2019, 0(12): 1-.
[13]	卫津逸，徐珞，戴文博. 基于脆弱点分析的故障注入技术[J]. 计算机与现代化, 2019, 0(12): 39-.
[14]	魏东平，罗丹. 一种基于区间预留编码的XML关键字查询算法[J]. 计算机与现代化, 2019, 0(10): 17-.
[15]	欧阳宏基１，杨铎2. 基于微服务架构的学位论文写作辅助平台[J]. 计算机与现代化, 2019, 0(10): 34-.

一种支持通配符查询的XML模式匹配算法

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价