The difficulty of schema conformance problems

Abstract

This paper examines the difficulty of the schema conformance problem for the following XML schema languages:

• DTD
• RELAX NG with W3C XML Schema Datatypes
• Schematron
• W3C XML Schema
• Namespace Routing Language

The schema conformance problem is defined as follows: Given a schema, is there an XML document that conforms to the schema?

For these five XML schema languages, the schema conformance problem is intractable (ranging from NP-hard to undecidable).