Active XML Schema Containment Checking Based on Tree Automata Theory

An active XML (AXMLfor short) document is an XML document where some of the data is given explicitly while other parts are defined only intentionally by means of embedded calls to Web services. When one of these calls is invoked, its results will be returned to enrich the original document. AXML schema defines the specification that AXML documents should conform. Containment checking for AXML schemas has many applications, and is thus important. In this paper, we focus on the problem of AXML schema containment and propose an efficient algorithm for this purpose based on tree automata theory. More precisely, we extend regular tree automata to represent AXML schemas and reduce schema containment to the corresponding problem of tree automata. Though the latter has high complexity in general cases, we describe the tractable case by introducing un-ambiguous restricts to AXML schema. Finally, we discuss that our methods for checking schema containment also can be used to solve the problem of AXML schema rewriting.