DTD约束下的XML树模式查询最小化

doi:10.3778/j.issn.1002-8331.2009.23.040

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (23): 144-148.DOI: 10.3778/j.issn.1002-8331.2009.23.040

DTD约束下的XML树模式查询最小化

王梅娟¹，庞引明²，谈子敬²

.中国人民解放军理工大学理学院基础电子学系，南京 211101
2.复旦大学计算机与信息技术系，上海 200433

收稿日期:2008-05-05 修回日期:2008-12-29 出版日期:2009-08-11 发布日期:2009-08-11
通讯作者: 王梅娟

Minimization of XML tree pattern queries under DTD constraints

WANG Mei-juan¹，PANG Yin-ming²，TAN Zi-jing ²

1.Department of Fundamental Electronics，PLA University of Science and Technology，Nanjing 211101，China
2.Department of Computing and Information Technology，Fudan University，Shanghai 200433，China

Received:2008-05-05 Revised:2008-12-29 Online:2009-08-11 Published:2009-08-11
Contact: WANG Mei-juan

摘要/Abstract

摘要： 目前大部分XML查询语言都使用树模式来匹配待查询的XML文档树以得到所需要的、与模式树相吻合的查询结果，此效率在很大程度上取决于XML模式树的大小，那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要。重点讨论DTD约束下树模式的最小化问题，将DTD兄弟约束SC拓展成扩展兄弟约束ESC，使其能够表达DTD约束中的祖先-后代关系；并指出只包含{ESC，/，//，[]，*}的查询树模式的最小化问题的复杂度是指数级的，且当模式树是分支受限的时候，其最小化问题的复杂度是多项式时间的；最后给出了一个多项式时间的受限分支的模式树最小化算法。

Abstract: Many XML query languages use tree patterns to navigate an XML document and select a set of element nodes.Since the efficiency of tree pattern matching against an XML tree-structured database depends on the size of the pattern，it is essential to identify and eliminate redundant nodes in the pattern and do so as quickly as possible.This paper studies tree pattern minimization in the presence of DTD.The SC to ESC that can express descendant relationships under DTD constraints is extend.This paper shows that minimization of tree pattern queries contain {ESC，/，//，[]，*} is EXPTIME，and，in particular，when tree pattern branches are limited，queries are PTIME.At last provide an algorithm for minimization of limited branched tree patterns and analyze its complexity.

中图分类号:

TP311

王梅娟¹，庞引明²，谈子敬². DTD约束下的XML树模式查询最小化[J]. 计算机工程与应用, 2009, 45(23): 144-148.

WANG Mei-juan¹，PANG Yin-ming²，TAN Zi-jing ²
. Minimization of XML tree pattern queries under DTD constraints[J]. Computer Engineering and Applications, 2009, 45(23): 144-148.

[1]	史恒亮^1，2，3，任崇广^1，3，白光一^1，3，普杰信². 自适应蚁群优化的云数据库动态路径查询[J]. 计算机工程与应用, 2010, 46(9): 10-12.
[2]	赵倩，尚学群. 从基因芯片数据快速有效地挖掘共调控基因[J]. 计算机工程与应用, 2010, 46(9): 33-37.
[3]	戎玫. 一种基于场景的嵌入式软件设计方法[J]. 计算机工程与应用, 2010, 46(9): 62-64.
[4]	刘顺江，刘国华，李颖. 基于数据源信息语境的复杂模式匹配方法[J]. 计算机工程与应用, 2010, 46(9): 120-122.
[5]	鲁小云，杨勇，王凌云. S-粗Vague集合及应用[J]. 计算机工程与应用, 2010, 46(8): 34-36.
[6]	袁本刚¹，陈莉¹，金燕². 挖掘数据库中的负频繁模式[J]. 计算机工程与应用, 2010, 46(8): 117-119.
[7]	陈红^1，2，郭躬德^1，2. 基于空间覆盖的半监督特征选择方法[J]. 计算机工程与应用, 2010, 46(8): 130-132.
[8]	赵倩，尚学群，王淼. 基于seeds集和频繁项集挖掘的半监督聚类算法[J]. 计算机工程与应用, 2010, 46(8): 123-126.
[9]	张黎¹，逄涣利¹，王小虎¹，王佳². 一种共调控基因C均值模糊聚类算法[J]. 计算机工程与应用, 2010, 46(7): 32-33.
[10]	唐爱国¹，王如龙²，胡春华¹. 贝叶斯网络在软件项目风险评估中的应用[J]. 计算机工程与应用, 2010, 46(7): 62-65.
[11]	汪琳，庄卫华. 一种Web日志序列模式挖掘的改进方法[J]. 计算机工程与应用, 2010, 46(7): 136-138.
[12]	胡明晓¹，DING Leon X². 一种用于抄袭识别的文档距离度量[J]. 计算机工程与应用, 2010, 46(7): 148-152.
[13]	朱峰，陈莉. 一种改进的蚁群聚类算法[J]. 计算机工程与应用, 2010, 46(6): 133-135.
[14]	陈小冬^1，2，尹学松²，林焕祥³. 基于判别分析的半监督聚类方法[J]. 计算机工程与应用, 2010, 46(6): 139-143.
[15]	吴庆曦，陶先平. ARDF：一种用于应用迁移的资源描述框架[J]. 计算机工程与应用, 2010, 46(6): 67-70.

DTD约束下的XML树模式查询最小化

Minimization of XML tree pattern queries under DTD constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics