On the evaluation of tree pattern queries

The evaluation of Xpath expressions can be handled as a tree embedding problem. In this paper, we propose two strategies on this issue. One is ordered-tree embedding based and the other is unordered-tree embedding based. For the ordered-tree embedding, our algorithm needs only O(vertical bar T vertical bar(.)vertical bar P vertical bar) time and O(vertical bar T vertical bar(.)vertical bar P vertical bar) space, where vertical bar T vertical bar and vertical bar P vertical bar stands for the numbers of the nodes in the target tree T and the pattern tree P, respectively. For the unordered-tree embedding, we give an algorithm that needs O(vertical bar T vertical bar(.)vertical bar P vertical bar(.2k)) time, where k is the largest out-degree of any node in P.