Containment Algorithm for XPath Fragment in Cache Replacement Strategy
Jian Li · 2004
In the environment of query-based XML cache,the query containment algorithm is important to the performance of cache replacement strategy. XML queries are usually expressed by means of XPath expressions,which are equivalent to tree patterns. This paper studies the containment problems for a fragment of the XPath query language. In particular, we study a special case of tree patterns, and provide a sound and complete PTIME algorithm for pattern containment. We also analyze its time complexity,and experimental results verify our analysis.