Typechecking for XML transformers

✍ Scribed by Tova Milo; Dan Suciu; Victor Vianu

• Book ID: 104147645
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 316 KB
• Volume: 66
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(02)00030-2

✦ Synopsis

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.