一种基于区间预留编码的XML关键字查询算法

doi:10.3969/j.issn.1006-2475.2019.10.004

摘要/Abstract

摘要： 近年来，随着XML数据的爆炸式增长，对XML关键字查询技术的研究日益受到关注。数据编码是关键字查询的基础，目前主要有2种方式——基于路径的编码及区间编码。区间编码可更好地适应对查询中的XML数据进行动态的更新，因而具有更多的优势。本文研究基于区间编码的关键字查询问题，提出一种新的查询算法。该算法首先根据预留的区间值建立索引，再根据最小范围值对索引进行选择遍历，减少了不必要的比较，达到了提高查询效率的目的。研究发现，预留空间的选择对查询效率有一定的影响。为此，本文设计一种基于节点自身进行区间预留的编码方式（Interval Reservation Based on Node， IRBN），为节点设置权值，并根据权值进行区间值的设定，形成根据节点自身分配区间的较为均衡的编码。实验表明，IRBN编码是合理的，有较高的查询效率。

关键词: XML, 关键字查询, 区间预留, IRBN

Abstract: In recent years, with the explosive growth of XML data, research on XML keyword query technology has received increasing attention. Data coding is the basis of keyword query. There are two main ways at present: path-based coding and interval coding. Interval coding can better adapt to the dynamic updating of XML data in queries, and thus has more advantages. This paper studies the keyword query problem based on interval coding and puts forward a new query algorithm. The algorithm firstly establishes an index according to the reserved interval value, and then selects and traverses the index according to the minimum range value, thereby reducing unnecessary comparison and achieving the purpose of improving query efficiency. The study found that the choice of reserved space has a certain impact on query efficiency. This paper designs an Interval Reservation Based on Node (IRBN) based on the node itself, sets the weight for the node, and sets the interval value according to the weight, forming an interval more balanced coding method according to the node’s own allocation. Experiments show that IRBN coding is reasonable and has high query efficiency.

Key words: XML, keyword query, interval reservation, IRBN

中图分类号:

TP311

魏东平，罗丹. 一种基于区间预留编码的XML关键字查询算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.10.004.

WEI Dong-ping, LUO Dan. An XML Keyword Query Algorithm Based on Interval Reserved Coding[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.10.004.

参考文献

［1］牛大伟,苏龙超,韩雨童,等. 基于扩展倒排索引的不确定XML关键字查询算法［J］. 计算机应用与软件, 2015,32(4):247-251.
［2］周军锋,孟小峰. XML关键字查询处理研究［J］. 计算机学报, 2012,35(12):2459-2478.
［3］ ZHOU J F, BAO Z F, WANG W, et al. Efficient query processings for XML keyword queries based on the IDList index［J］. The VLDB Journal, 2014,23(1):25-50.
［4］高海康,魏祥丽,李华昱. 基于区间编码的XML数据压缩方法［J］. 中国科技论文, 2015,10(8):905-911.
［5］王邦军. 一种新的XML文档节点编码方案［J］. 武汉理工大学学报(信息与管理工程版), 2007,29(4):28-30.
［6］韩旭东. 一种基于非等概率更新的XML区间编码方法［J］. 电大理工, 2008(2):55-57.
［7］韩萌,陈群,王鹏. 基于LCA的高效XML关键字检索算法［J］. 计算机工程, 2010,36(23):59-62.
［8］ ZHOU R, LIU C F, LI J X. Fast ELCA computation for keyword queries on XML data［C］// Proceedings of the 13th International Conference on Extending Databases Technology. 2010:549-560.
［9］ ZHOU R, LIU C F, LI J X, et al. ELCA evaluation for keyword search on probabilistic XML data［J］. Word Wide Web, 2013,16(2):171-193.
［10］LIN R R, CHANG Y H, CHAO K M. Locating valid SLCAs for XML keyword search with not semantics［J］. ACM Sigmod Record, 2014,43(2):29-34.
［11］WANG W Y, WANG X L, ZHOU A Y. Hash-search: An efficient SLCA-based keyword search algorithm on XML documents［C］// Proceedings of International Conference on Database Systems for Advanced Applications. 2009:496-510.
［12］LI Y Y, YU C, JAGADISH H V. Schema-free XQuery［C］// Proceedings of the 30th International Conference on Very Large Data Bases. 2004:72-83.
［13］LIU Z Y, CHER Y. Reasoning and identifying relevant matches for XML keyword search［J］. Proceedings of the VLDB Endowment, 2008,1(1):921-932.
［14］郑弘晖,郭红. 基于有效最低公共祖先的XML关键字查询算法［J］. 计算机应用, 2010,30(3):825-830.
［15］MA Z M, LI T, YAN L. An approach of top-k keyword querying for fuzzy XML［J］. Computing, 2017,100(3):303-330.
［16］魏东平,苑志朋. 基于关键词权重的XML查询结果排序方法［J］. 计算机系统应用, 2017,26(4):198-202.
［17］姚全珠,王丹,蒋鹏飞. 基于路径内容索引相关关键节点的XML关键字查询算法［J］. 计算机应用, 2016,36(Z1):210-212.
［18］王大伟,崔婉秋,覃飙. 基于XML搜索的相关技术及发展［J］. 小型微型计算机系统, 2018,39(7):1390-1397.
［19］KUN H, ZHANG X L, LIU L X, et al. An efficient algorithm for XML keyword search based on interval encoding［C］// 2016 13th Web Information Systems and Applications Conference. 2016.
［20］覃遵跃,黄云,梁平元. 一种支持更新的XML编码方法［J］. 计算机工程与应用, 2013,49(3):20-24.
［21］陈子阳,王璿,汤显. 面向XML关键字查询的高效RKN求解策略［J］. 通信学报, 2014,35(7):46-55.
［22］NASERIPARSA M, ISLAM M S, LIU C F, et al. No-but-semantic-match: Computing semantically matched XML keyword search results［J］. World Wide Web, 2017(2):1-35.
［23］YUE D J, YU G, LIU J S, et al. Efficient keyword search for SLCA in parallel XML databases［C］// 2011 8th Web Information Systems and Applications Conference. 2011:29-34. T, YAN L. An approach of top-k keyword querying for fuzzy XML［J］. Computing, 2017,100(3):303-330.

[1]	王亮亮1,2，闫威3，张佳伟1. 新疆昆仑卫星数字专用频道的汉维哈XML解析器[J]. 计算机与现代化, 2017, 0(8): 42-.
[2]	钱哨，陈丹. 基于JSON数据格式的飞机协同设计应用适配器[J]. 计算机与现代化, 2016, 0(8): 123-126.
[3]	陈冲,蒋夏军. 一种支持通配符查询的XML模式匹配算法[J]. 计算机与现代化, 2016, 0(4): 65-73.
[4]	王成勇，杜庆伟，孙静，孙振. 用带权重的pq-gram算法计算XML文档相似度[J]. 计算机与现代化, 2015, 0(3): 20-25.
[5]	李宗花,张磊. 基于XML Schema的轻量级异构数据集成方法[J]. 计算机与现代化, 2015, 0(11): 93-98.
[6]	林郁峰，陈中育，骆正平，吴星同. 一种基于目标转换的用例建模方法[J]. 计算机与现代化, 2014, 0(7): 40-44.
[7]	杨运平，吴智俊. Apache Shiro安全框架在技术转移服务系统中的应用[J]. 计算机与现代化, 2014, 0(3): 158-160.
[8]	朱兴动;刘啸;李其申. IETM馈线数据模块的设计与应用[J]. 计算机与现代化, 2013, 1(7): 212-216.
[9]	杨帆. 基于XML和MQ的异构数据库数据交换技术[J]. 计算机与现代化, 2013, 1(6): 147-150.
[10]	周安漪;仇润鹤;王嘉伟. 树形XML结构在销售报价系统中的应用 [J]. 计算机与现代化, 2013, 1(6): 189-190.
[11]	魏伟. 基于REST的个性化数据重用方法[J]. 计算机与现代化, 2013, 1(5): 215-218.
[12]	徐辉;王芳;梁晓琦. 基于XML的数据交换和同步更新的平台研究 ——以上海电视大学松江分校为例[J]. 计算机与现代化, 2013, 1(3): 102-105.
[13]	汤世凤;杨国强. 基于VTD-XML的流程定义文件解析方法研究[J]. 计算机与现代化, 2013, 1(2): 113-116.
[14]	楚威,孙丰鑫,刘力力 . C4ISR系统仿真试验环境构建与配置方法[J]. 计算机与现代化, 2013, 12(12): 77-80.
[15]	刘琼;邓明中;张宁. 基于特征语义描述的协同造型[J]. 计算机与现代化, 2013, 218(10): 149-152,.