Containment and Equivalence of Active XML Documents

An active XML (AXML for short) document is an XML document where some of the data is given explicitly and other parts are defined only intensionally by means of embedded calls to Web services. By introducing intensional data, it brings much more flexibility but also many new problems to XML documents. In this paper, we study the complexities of containment and equivalence of AXML documents. We describe these problems in an uniform framework based on tree automata theory and reduce these problems to the corresponding ones of tree automata. More precisely, we define a new tree automaton, AXML tree automaton, which can efficiently describe the set of all documents that can be produced from an AXML document by invoking the Web services embedded in it. Based on AXML tree automata, we show the complexities of containment and equivalence problems to be exponential time in general case. By restricting AXML document specifications, we also identify a tractable case of these problems and propose an algorithm performing in polynomial time to solve it. and propose an algorithm performing in polynomial time to solve it.