XPath patterns are mainly used as a query language for XML documents. There may be a containment relationship between two XPath patterns. The containment problem between two XPath patterns is a problem that determines whether one XPath pattern contains another XPath pattern. While there are many XML applications that may need the containment relationship, the containment problem is known as a co-NP complete. The homomorphism relationship between two XPath patterns, which is a PTIME problem, is a sufficient condition for the containment relationship. We first discuss that the homomorphism can be utilized for many applications in place of the containment, and maintaining homomorphism information among XPath patterns will benefit those applications. Then, we propose a lattice structure for maintaining homomorphism relationships among XPath patterns, called the partially ordered set of XPath patterns(POX), and develop an algorithm for maintaining it. Our analyses show that our proposed algorithm can efficiently maintain POX in a polynomial time.
