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

Minimization of XML tree pattern queries under DTD constraints

作　　者：王梅娟[1] 庞引明[2] 谈子敬[2] 

机构地区：[1]中国人民解放军理工大学理学院基础电子学系,南京211101 [2]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机工程与应用》2009年第23期144-148,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.60603043~~

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

关 键 词：可扩展标记语言 树模式查询 文档类型定义(DTD)约束 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]