Containment of XPath Expressions

Description

We have considered the simplest case, when the XPath expressions consists only of tags, *, /, //, and [...]. It is easy to check containment (and, hence, equivalence) if one removes one of the following three constructs: *, //, [...]. But when all three of them are allowed, then both problems are coNP-complete.

This example illustrates why it's a hard problem. The following XPath expression:

/a[.//b[c/*//d]/b[c//d]/b[c/d]]

/a[.//b[c/*//d]/b[c/d]]

Given the hardness of the problem we have developed some practical approximation algorithms for checking containment and equivalence. As an application we have developed an XPath vizualization tool, XViz. The code is available here (no guarantees or support are provided).

Supported by:

Members

Publications