HCH for Checking Containment of XPath Fragment

作     者：冯建华 廖雨果 张勇 

作者机构：Department of Computer Science and Technology Tsinghua UniversityBeijing 100084China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2007年第22卷第5期

页      面：736-748页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：This work is in part.supported by the National Natural Science Foundation of China under Grant No.60573094 National Grand Fundamental Research 973 Program of China under Grant No.2006CB303103 National High Technology Development 863 Program of China under Grant No.2006AA01A101 Tsinghua Basic Research Foundation under Grant No.JCqn2005022 

主　　题：computer software query containment conditioned homomorphism tree pattern XML XPath 

摘      要：XPath is ubiquitous in XML applications for navigating XML trees and selecting a set of element nodes. In XPath query processing, one of the most important issues is how to efficiently check containment relationship between two XPath expressions. To get out of the intricacy and complexity caused by numerous XPath features, we investigate this issue on a frequently used fragment of XPath expressions that consists of node tests, the child axis （/）, the descendant axis （//）, branches （[]） and label wildcards （＊）. Prior work has shown that homomorphism technology can be used for containment checking. However, homomorphism is the sufficient but not necessary condition for containment. For special classes of this fragment, the homomorphism algorithm returns false negatives. To address this problem, this paper proposes two containment techniques, conditioned homomorphism and hidden conditioned homomorphism, and then presents sound algorithms for checking containment. Experimental results confirm the practicability and efficiency of the proposed algorithms.