Tree Match算法是一种有效的Twig查询匹配算法,但其存在反复分析Twig模式的缺点。针对该问题,引入编译中的部分求值技术,提出一种Twig查询优化方案。通过部分求值提前完成对Twig模式的分析,生成查询专用的指令序列代替原查询程序,并给...Tree Match算法是一种有效的Twig查询匹配算法,但其存在反复分析Twig模式的缺点。针对该问题,引入编译中的部分求值技术,提出一种Twig查询优化方案。通过部分求值提前完成对Twig模式的分析,生成查询专用的指令序列代替原查询程序,并给出查询机执行引擎,从而消除重复计算,优化XML树模式查询过程。实验结果表明,在不同Twig模式下,该优化方案能够有效提高XML查询的执行效率。展开更多
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 b...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.展开更多
基金This work is in part.supported by the National Natural Science Foundation of China under Grant No.60573094National Grand Fundamental Research 973 Program of China under Grant No.2006CB303103+1 种基金National High Technology Development 863 Program of China under Grant No.2006AA01A101Tsinghua Basic Research Foundation under Grant No.JCqn2005022.
文摘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.
