张剑妹,陶世群,梁吉业.XML结构完整性约束下的路径表达式的最小化.软件学报,2009,20(11):2977-2987 |
XML结构完整性约束下的路径表达式的最小化 |
Minimization of Path Expression Under Structural Integrity Constraints for XML |
投稿时间:2007-11-06 修订日期:2008-07-09 |
DOI: |
中文关键词: 路径表达式 XML结构完整性约束 路径蕴涵闭包 子路径 最小化 |
英文关键词:path expression structural integrity constraint for XML path implication closure sub-path minimization |
基金项目:Supported by the National Natural Science Foundation of China under Grant No.70471003 (国家自然科学基金); the Research Foundation for the Doctoral Program of the Ministry of Education of China under Grant No.20050108004 (国家教育部高等学校博士学科点专项科研基金) |
|
摘要点击次数: 3930 |
全文下载次数: 3772 |
中文摘要: |
引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性. |
英文摘要: |
A system of structural integrity constraints for XML (XSICs) is introduced, which specifies five structural relationships between different paths or nodes in XML documents, including path implication, path cooccurrence, path mutual-exclusion, obligatory inclusion and exclusive inclusion. This paper defines the syntax and semantics of these XSICs, and studies their core role in XML query optimization. Based on the concept of sub-path, this paper proposes an algorithm for minimizing path expression in the presence of XSICs. By using the path implication closure as a tool, the algorithm cannot only effectively eliminate redundant nodes or predicates, but also identify invalid path expressions. Experimental results show the effectiveness and efficiency of the proposed minimization algorithm. |
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |