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

doi:10.3969/j.issn.1006-2475.2016.04.014

计算机与现代化 ›› 2016, Vol. 0 ›› Issue (4): 65-73.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]. 计算机与现代化, 2016, 0(4): 65-73.

CHEN Chong, JIANG Xia-jun.

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query[J]. Computer and Modernization, 2016, 0(4): 65-73.

参考文献

［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, 2, 余劲松弟1, 2, 魏丹丹1, 2, 罗源1, 2, 佟瑞菊3. 面向格网化立方体元数据的抽象树模型[J]. 计算机与现代化, 2024, 0(11): 1-6.
[2]	邱玲1, 2, 宋智1, 2, 吕爽1, 2, 杨雪1, 2. 数据同步技术在气象大数据云平台对外服务中的应用[J]. 计算机与现代化, 2024, 0(07): 76-81.
[3]	杨柯1, 潘大志1, 2, 池莹1. 改进蜉蝣算法求解工艺规划与调度集成问题[J]. 计算机与现代化, 2024, 0(04): 92-98.
[4]	范良俊1, 彭振皖1, 王晨2, 于泓涛2, 梁振1. 基于YAML的iOS应用开发框架[J]. 计算机与现代化, 2024, 0(04): 115-120.
[5]	王子琛, 瞿有利. 基于CRF的分区倒排索引压缩算法[J]. 计算机与现代化, 2024, 0(02): 36-42.
[6]	王晓霞, 孟佳娜, 江烽, 丁梓晴. 基于多视图的知识感知推荐系统#br#[J]. 计算机与现代化, 2024, 0(02): 100-107.
[7]	林威. 基于自监督学习和数据回放的新闻推荐模型增量学习方法[J]. 计算机与现代化, 2023, 0(12): 1-6.
[8]	柴荔, 王萧, 龚嘉豪, 汪洋, 吉顺慧, 张鹏程. 面向供应链的共识算法研究综述[J]. 计算机与现代化, 2023, 0(11): 22-27.
[9]	王重阳, 庄毅. 基于SDN和改进CSA算法的多作业集群的负载均衡算法[J]. 计算机与现代化, 2023, 0(11): 28-35.
[10]	王光辉, 程功旭, 李青. 基于区块链技术的电力物资共享云仓设计[J]. 计算机与现代化, 2023, 0(10): 99-106.
[11]	沈加炜, 陆一鸣, 陈晓艺, 钱美玲, 陆卫忠, . 基于深度学习的人体行为检测方法研究综述[J]. 计算机与现代化, 2023, 0(09): 1-9.
[12]	顾成伟, 丁勇, 李登华. 基于计算机视觉的工业厂区人员安全警戒系统[J]. 计算机与现代化, 2023, 0(09): 20-26.
[13]	刘瑞雪, 李文, 刘芳, 杜守国. 用于具有缺失值的时间序列预测的张量自回归补全算法[J]. 计算机与现代化, 2023, 0(09): 51-58.
[14]	毛明扬, 徐胜超. 面向粒子群优化BP神经网络的粗糙集连续属性离散化算法[J]. 计算机与现代化, 2023, 0(09): 115-119.
[15]	陈嘉敏, 张伯泉, 麦海鹏. 基于特征融合的海马体分割[J]. 计算机与现代化, 2023, 0(08): 1-6.

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

An Efficient XML Pattern Matching Algorithm for Supporting Wildcard Query

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价