S. Yoo, J.H. Son, and M.H. Kim (Korea)
XPath patterns, containment, homomorphism, partially or dered set.
XPath patterns are mainly used as a query language for XML documents. There may be a containment relation ship between two XPath patterns. The containment prob lem between two XPath patterns is a problem that deter mines whether one XPath pattern contains another XPath pattern. While there are many XML applications that may need the containment relationship, the containment prob lem is known as a co-NP complete. The homomorphismre lationship between two XPath patterns, which is a PTIME problem, is a sufficient condition for the containment rela tionship. We first discuss that the homomorphism can be utilized for many applications in place of the containment, and maintaining homomorphisminformation among XPath patterns will benefit those applications. Then, we propose a lattice structure for maintaining homomorphism relation ships 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 algo rithm can efficiently maintain POX in a polynomial time.
Important Links:
Go Back
