On the complexity of typechecking top-down XML transformations |
| |
Affiliation: | Limburgs Universitair Centrum, Universitaire Campus, B-3590 Diepenbeek, Belgium |
| |
Abstract: | We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as input and output schemas. The complexity of the typechecking problems in this scenario ranges from to . |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|