摘要: 为利用Dewey前缀编码索引方案实现对XML/GML文档的编码并消除其缺点,提出一种扩展的Dewey编码方案——Ex-Dewey。在保留Dewey前缀编码优点的同时提出节点插入及删除对已有节点编码值串无影响的更新策略。针对Ex-Dewey编码方案提出一种在XML/GML非空间数据查询时快速确定候选节点间先辈-子孙、父-子关系的结构化连接算法——ED-XQ-SJ。给出算法思想、描述与验证。该算法无须访问实际存储的节点,算法复杂度较低且I/O开销减少。
关键词:
可扩展标记语言,
地理标记语言,
编码索引,
扩展Dewey编码,
非空间数据查询,
结构化连接
Abstract: In order to take advantage of Dewey prefix encoding scheme to encode eXtensible Markup Language(XML)/Geography Markup Language(GML) documents and eliminate Dewey encoding scheme’s shortcoming, a kind of extended Dewey encoding scheme, Ex-Dewey, is proposed. Ex-Dewey achieves updating strategy of node’s inserting and deleting no affecting others’ encoding value, and also keeps the advantages of Dewey encoding scheme. And corresponding structural join algorithms, ED-XQ-SJ for XML or GML non-spatial data querying are proposed. The algorithms’ idea, description and verification are given. The algorithms can directly determine the ancestors-descendants or parents-children relationship between potential ancestor node set and descendant node set, and do not access the real storage nodes. Their complexity is much reduced, and the I/O overhead is decreased obviously as well.
Key words:
eXtensible Markup Language(XML),
Geography Markup Language(GML),
encoding index,
extended Dewey encoding,
non-spatial data querying,
structural join
中图分类号:
陈建华;王华军;苗 放;王卫红. XML/GML非空间数据查询的结构连接算法[J]. 计算机工程, 2010, 36(3): 69-71,7.
CHEN Jian-hua; WANG Hua-jun; MIAO Fang; WANG Wei-hong. Structural Join Algorithm for XML/GML Non-spatial Data Querying[J]. Computer Engineering, 2010, 36(3): 69-71,7.