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

• 数据库、信息处理 • 上一篇    下一篇

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

王梅娟1,庞引明2,谈子敬2   

  1. .中国人民解放军理工大学 理学院 基础电子学系,南京 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-juan1,PANG Yin-ming2,TAN Zi-jing 2
  

  1. 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

摘要: 目前大部分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.

中图分类号: