NVDL — a Breath of Fresh Air for Compound Document Validation (XTech2007)

Jirka Kosek

University of Economics, Prague LISp (Laboratory for Intelligent Systems Prague)

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
jirka@kosek.cz

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
petr@nalevka.com

Abstract

Compound document is a document that consist of elements and attributes from different mark-up vocabularies (namespaces). This approach to document engineering is very effective because it allows reusing existing markup technologies in a novel ways. However validation of such documents is a big challenge. It is very hard to create complex combined schemas in RELAX NG or W3C XML Schema for validation of compound documents. Instead advantages of using NVDL as a validation language are explained in this article. Further, our own implementation called JNVDL is introduced. The second part of the article deals with problems of recognizing different versions of a single XML vocabulary. Finally, an extension of the NVDL language able to solve this problem is introduced.

---

Table of Contents

Introduction

Compound documents

The Web environment

Examples of application

Validation of compound documents

XML Schema or RELAX NG is insufficient

NVDL is the right solution

JNVDL

Implementation issues

Impact on a Web architecture

Namespace is not a document type

Versioning namespaces

Extending NVDL to support versioning

Related work

Future work

Conclusions

Bibliography

Introduction

This article deals with compound document validation. In the the section called “Compound documents” advantages and the current usage of compound documents is described. The next part (the section called “Validation of compound documents”) shows insufficiency of classical schema languages for validation of compound documents. NVDL language is proposed as a solution to this problem in the section called “NVDL is the right solution”. The second part of this article introduces our implementation of NVDL called JNVDL (the section called “JNVDL”) and problems which were solved during implementation of the NVDL standard. The last part of this article (the section called “Impact on a Web architecture”) deals with the problem of versioning document types and proposes some NVDL extensions which can be used to solve problem of several different document types residing in one namespace.
Open-source implementation of NVDL validator and proposed NVDL extensions could be considered as the main contribution of our work described in this paper.

Compound documents

Compound document is a modern name for XML documents that consist of elements and attributes from different mark-up vocabularies. In other words, by combining two or more different XML languages in a single document we create a compound document. This was made technically possible thanks to XML Namespaces. In general, the Namespaces in XML recommendation[NS] solves problems of collision and recognition of elements and attributes from different mark-up vocabularies within one XML document. This is achieved through qualified names, that make different vocabulary elements or attributes distinguishable even they use the same local names.
At first, some people considered namespaces to be a hostile element polluting XML with additional complexity without any reasonable need for it. At this time, the world of mark-up vocabularies has been dominated by over-grown monolithic languages, but soon they faced serious extensibility issues. The set of problems a language addresses is growing and evolving over time. To keep-up with the changing requirements, the monolithic approach constantly pollutes the vocabulary with new closely specific mark-up. As a result, we see extensive, difficult to learn and difficult to maintain languages, which are intended to solve all sort of problems, but not solving any of them in a satisfactory manner.
Recently, it is more and more obvious that some extensibility problems may be solved smarter using composition of more different single-purpose languages rather than further extending the monolithic language. If there already exists a widely adopted and understood vocabulary, which solves part of our problem, it makes a good sense to reuse it rather than introducing something new. With this approach, we gain an immense flexibility, as for every specific problem, we can adopt a specific combination of vocabularies.
Isolated single-purpose languages are easier to maintain and what is even more important, they can be easily reused in distinct applications. The domain of such languages is narrow and their aim is well defined, which helps to keep the language free of indiscreet extensions.

The Web environment

HTML is a good example of a shift from a standalone language to the use of compound documents. At first, HTML was a simple format for publishing mostly scientific articles and for linking them together. Soon the Web became incredibly popular and widely adopted. It didn't serve just as a standard for publishing electronic documents, but it also become a standard way to create distributed user interfaces for various information systems.
The tendency to use or misuse HTML to solve all sorts of distinct problems slowly polluted the language with various indiscreet proprietary extensions. Browser and other software vendors were promptly introducing new user-oriented features to gain a competitive advantage, without having a long term vision of the language development in mind. All those issues slowly caused the Web was loosing one of its main advantage; cross-platform interoperability.
The situation has significantly improved after standardization of the language (under W3C). The language has been purified from most of the presentational aspects and HTML has been made fully XML based (XHTML). But the major improvement was modularization of XHTML (see [XHTMLMOD]). The language became more flexible and adaptable in various environments for various tasks. Modularization allows to use a subset of HTML features that most reflects our particular needs. Logically related aspects of the language are decomposed into modules such as e. g. structure module with the main HTML structure, table module for expressing tabular data, text module for organizing texts into headings and paragraphs, forms module to define user interfaces, meta-information module to attach meta-data to documents, image module for images, link module to hyperlink our documents etc.
For addressing different problems, we can use different XHTML modules. For example, it doesn't make sense to use the forms module when publishing a simple electronic document. Moreover, we may look at modules as default vocabulary fragments with limited expressiveness. They can be left out completely (if not needed), but they can also be replaced by a whole different specialized and feature-rich language. This can be clearly spotted as the current trend in Web standards. Instead of the forms module, we can use XForms, RDF can replace the meta-information module, link module can be overridden by XLink, instead of images we can directly embed SVG vector graphics and so on.
To conclude, compound documents make Web more flexible and powerful. It makes it suitable for all sort of very different applications. Every specific problem can be addressed by a custom combination of highly specialized languages. If we follow this line of thinking, at some point we realize, there is no need for HTML anymore. The only think needed is a parent language to embed all the vocabularies which best suit our intentions. The XHTML structure module is a good candidate, but a completely different language can serve this purpose as well. As an example, imagine a Web application, where SVG takes the role of the parent language and embedded XForms is used to define the user interface. As SVG is a powerful presentational language and XForms is the latest declarative and feature-rich user interface standard, such combination of languages may be considered as the best solution to a particular problem.

Examples of application

There are many different applications of compound documents in many different areas. When once adopted, composition of different vocabularies seems as a natural and convenient approach to many problems. One of the first application of compound documents ever were templating languages. The W3C XSL Transformations recommendation has been published just few months after Namespaces in XML. XSLT is a popular templating language, which can express rules for transforming a source XML tree into a result tree. The particular rules are expressed using the XSLT vocabulary and they contain embedded fragments of the result tree vocabularies. This means XSLT stylesheets are basically compound documents.
In addition, XML is widely used as a data exchange format. In non-trivial cases, there is a protocol such as for example SOAP to exchange structured XML messages. SOAP messages are again compound documents as they consist of an envelope (SOAP vocabulary) which encapsulates the actual message payload (arbitrary vocabulary).
Compound documents are perfectly applicable also for office document formats. In this case, various differently structured data as structured text, tables, graphs, diagrams, spreadsheets need to be incorporated into one document. This is the right task for XML, as it features the right combining mechanisms and there are many specialized and mature XML vocabularies ready to be reused within the office documents. Lets mention the Open Document Format (ODF) as an example of XML being successfully used in various office bundles as the native document format.
As mentioned previously, the Web offers huge opportunities for compound documents and those haven't been really exploited yet. One of the problems is the lacking client support for the new standards. The situation is far better among the mobile device clients than on the desktop. Despite those issues, there are already some interesting compound document solutions, which may be used with some compromises in most today's mainstream browsers. Among of all, a good example of a Web compound document concept is the xH language, presented at the WWW2006 conference[XH]. It is basically a synthesis of XHTML and several other well-know standard XML languages; mainly XForms, SVG and MathML. Interaction of the different language blocks is achieved through JavaScript.
All the languages recommended by xH are widely used and well-known. But the value added and the major intention of xH is to encourage people to use those languages in combination to build a new generation of rich and flexible Web application with enhanced user experience.

Validation of compound documents

XML namespaces technically allow presence of multiple vocabularies inside one XML document, but there are many other issues, which need to be addressed, before we can adopt a compound document solution. Having descriptions of syntax and semantics of the particular vocabularies is insufficient for the client application to handle compound documents correctly. In addition, we need to have also syntax and semantics defined for the compound language.^[1]
Different vocabulary fragments can be combined in many different ways and even the isolated fragments are meaningful (in respect to their language semantics) and they are syntactically correct, the combination of such fragments can be difficult to interpret or it can be even semantically empty.
As an example, imagine we have an XHTML document which consists of a head section, used to place document related meta-data, and a body section, intended to be rendered. Placing an RDF meta-data fragment into the body section would cause interpretation difficulties, as meta-data are not intended to be rendered. The correct place to put the fragment is of course the head section.
This implies, there are two major issues concerning compound documents. First, we need to create semantics for different compound languages to make them correctly interpretable by different applications. Second, we need to constrain the way different languages are combined together by allowing just meaningful combinations. This requires some kind of a “meta-schema” to express such constraints.
Today, automated validation is absolutely essential for standalone XML languages to ensure their syntactical correctness and thus interoperability. But this is even more important for compound documents, as they bring additional interpretation complexity. To make compound documents applicable in a heterogeneous environment (as the Web environment for example), it is absolutely essential to provide powerful compound document validation tools and techniques. This requires schema languages able to cope with multiple namespaces and validation engines able to check document instances against such schemas. In the following sections we will discuss two distinct approaches to compound document validation.

XML Schema or RELAX NG is insufficient

One approach to face the compound document validation problem is to use namespace support included in today's mainstream schema languages; e. g. in RELAX NG or XML Schema. Those namespace-aware schema languages use qualified names to define elements and attributes, thus compound document schemas can be created easily just by specifying the appropriate namespace for elements from different vocabularies.

Example 1. Allowing RDF inside the XHTML head section (RELAX NG)

<element name="head" 
         ns="http://www.w3.org/1999/xhtml">          
  <element name="title" 
           ns="http://www.w3.org/1999/xhtml">
    <text/>
  </element>
  <interleave>
    ... other XHTML head elements ...
    <optional>
      <element name="RDF" 
               ns="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
        ...
      </element>
    </optional>  
  </interleave>
</element>

The previous example is quite straightforward, but it is not really flexible indeed. Reusing the definition for a different combination of vocabularies would be very painful as it would require us to use the copy and paste technique. The definition can be significantly improved by modularizing the schema. Having modules for each vocabulary would allow us to create schemas for various compound languages simply by including the right subset of modules.
Despite the namespace-aware schema language approach is very simple, it has several drawbacks. Imagine we like to allow a foreign vocabulary in some contexts of XHTML. This is a simple task for someone who is familiar with the implementation details of the XHTML schema (knowing the structure of the schema's definition and modules). But it is not as straightforward for someone who doesn't have the right insight.
Moreover, in most cases we cannot simply reuse the existing schemas for vocabularies we like to combine. Standalone language schemas aren't often well prepared to be combined with other schemas. Usually they don't have the right level of modularity and abstraction which is needed for their seamless integration. In addition, they are frequently written in different schema languages or even in languages which aren't namespace-aware at all (for example DTD). This implies, schemas for different vocabularies first need to be converted to the same namespace-aware schema language and slightly modified before they can be used as modules of the compound definition.
Such approach would not only require deep knowledge of the particular schemas and a long implementation time, but it also leads to maintenance issues. As different languages evolve over time, we need to keep our modified or converted schemas constantly up-to-date. For complex compound languages this may be an essential problem.
To demonstrate the issues, lets consider the following example. We would like to create a compound document schema for XHTML with embedded SVG and MathML in all block level and inline elements and RDF in the head section. When we decide to use a namespace-aware schema language (for example XML Schema) to achieve that, we run into problems. First, we need to convert the official XHTML DTDs into XML Schema. This needs to be done in a specific way, as we need to have abstract classes prepared for the head section and block and inline elements to make them easily extensible through additional modules. Further we can reuse the XML Schema for MathML, but such schema cannot be used as it is. First, we need to modify it to make it a module of our parent XHTML schema. The module needs to be further tailored in a specific way to allow MathML just in the context of the block and inline elements. A similar task needs to be done also for SVG and RDF.
Basically, every time a new vocabulary needs to be incorporated into the compound definition, its official schema first needs to be converted and modified. Moreover, different vocabulary modules needs to be constantly synchronized with new versions of the languages. This is an error-prone approach, because the different definitions are being duplicated. Another problem arises, when for example SVG should displace XHTML as the parent language. In such case, different vocabulary modules cannot be simply reused. On the contrary, they may need to be again duplicated and slightly reworked.
To conclude, the namespace-aware schema language concept is applicable in simple cases, but it is not a solution which can be considered for complex scenarios. Reusability of existing schemas is an important requirement which is not satisfied at all within today's namespace-aware schema languages. Different approach to compound document validation is needed to allow schema reusability. Such approach has to be independent of the particular schema's implementation details and the schema languages used.

NVDL is the right solution

NVDL, which means Namespace-based Validation Dispatching Language, is “Part 4 of ISO/IEC 19757 DSDL” (Document Schema Definition Languages) international standard. NVDL is a simple “meta-schema” language which allows to control processing and validation of compound documents. Figure 1, “NVDL validation process at a glance” demonstrates a particular validation dispatching process decomposed into several phases. An NVDL schema and a compound document instance shown in Example 2, “NVDL validation process” are potential participants of such process.
The essence of NVDL is dividing XML document instances into sections each of which contains elements or attributes from a single namespace. A section tree is first constructed for every instance (see Example 3, “Decomposing sections”). Sections are further combined or manipulated in various ways to create so called validation candidates.
Manipulation of sections is achieved through rules and their corresponding actions defined in an NVDL script. Actions are executed on a particular section whenever they match a certain rule; usually in case the sections namespace matches the rule's namespace wildcard.
There are several actions defined in NVDL; e. g. attach for attaching sections back to their parent, unwrap to handle wrapped sections and validate to send a particular validation fragment to a particular validator.
After executing actions, we usually obtain single namespace validation candidates which are further filtered for redundancy into validation fragments. Such fragments are finally independently send for validation against different subschemas^[2] (see Example 4, “Dispatching validation fragments to validators”).
The ability to create single namespace fragments allows us not to care about namespaces in our subschemas at all. Single namespace schemas are easier to write and what is important also easy to reuse for various different compound languages, where the same vocabulary may be used in a different context or in combination with different vocabularies. Moreover, NVDL is schema language transparent, thus subschemas may be written in any preferable schema language e. g. RELAX NG, XML Schema, Schematron or DTD. For detailed information about the NVDL validation dispatching process, refer to [NVDL].

Figure 1. NVDL validation process at a glance

Example 2. NVDL validation process

The following example shows an NVDL schema and a compound document instance which relates to Figure 1, “NVDL validation process at a glance”. In this case, NS1 represents the XHTML namespace and NS2 stands for the XForms namespace. The following instance is an XHTML document with a simple form for retrieving stock quote information.

<html xmlns="http://www.w3.org/1999/xhtml" xmlns:xf="http://www.w3.org/2002/xforms">
<head>
<xf:model>
  <xf:instance><stockquote><symbol/></stockquote></xf:instance>
  <xf:submission xml:id="form" method="post"  action="getStockQuote.do"/>
</xf:model>
</head>

<body>
<xf:group ref="stockquote">
<xf:input ref="symbol"><xf:label>Symbol</xf:label></xf:input>
<br />
<xf:submit submission="form"><xf:label>Get Quote</xf:label></xf:submit>
</xf:group>
</body></html>

To achieve behavior consistent with Figure 1, “NVDL validation process at a glance”, the following schema is applied to the previous compound document instance. Using such schema, the NVDL dispatcher first sends the root XHTML fragment for validation after filtering any descendant XForms fragments and attaching any descendant XHTML fragments. XForms sections are handled in a similar way by filtering any descendant XHTML. For any XHTML document instance with embedded XForms, the following NVDL schema causes one pure XHTML fragment to be send for validation against xhtml.xsd and one or more pure XForms fragments to be validated using xforms.rng.

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0">
<namespace ns="http://www.w3.org/1999/xhtml">
  <validate schema="xhtml.xsd">
    <mode><namespace ns="http://www.w3.org/2002/xforms">
      <validate schema="xforms.rng">
        <mode><namespace ns="http://www.w3.org/2002/xforms"><attach/></namespace>
          <namespace ns="http://www.w3.org/2002/06/xhtml2"><unwrap/></namespace>
        </mode>
      </validate>
      <unwrap>
      <mode><namespace ns="http://www.w3.org/2002/xforms"><unwrap/></namespace>
        <namespace ns="http://www.w3.org/2002/06/xhtml2"><attach/></namespace>
      </mode>
      </unwrap>
    </namespace></mode>
  </validate>
</namespace>
</rules>

Example 3. Decomposing sections

The instance shown in Example 2, “NVDL validation process” is decomposed into the following section tree after applying the NVDL schema from the same example.

ES1 <html><head>ref to ES2</head>
<body>ref to ES4</body>
</html>

ES2 <xf:model>...</xf:model>

ES3 <br />

ES4 <xf:group ref="stockquote"><xf:input ref="symbol">...</xf:input>
ref to ES3
<xf:submit submission="form">...</xf:submit></xf:group>

Example 4. Dispatching validation fragments to validators

After executing attach and unwrap actions on the section tree shown in Example 3, “Decomposing sections”, the following resulting fragments are created and send independently for validation.

<html><head></head>
<body><br /></body>
</html> -> xhtml.xsd

<xf:model>...</xf:model> -> xforms.rng

<xf:group ref="stockquote"><xf:input ref="symbol">...</xf:input>
<xf:submit submission="form">...</xf:submit></xf:group> -> xforms.rng

Namespace-aware schema languages force us to convert all our schemas to the same schema language. In contrast, when using NVDL, we are free to choose any languages we prefer and we may also combine different schema languages during a single validation process. NVDL does not force XML language designers to use mainstream schema languages. On the contrary, they are encouraged to choose the schema language which best suits their vocabulary needs. NVDL is also completely isolated from the implementation details of the particular subschemas. The vocabulary designers can fully focus on the schema implementation without even thinking about how can their vocabulary possibly be combined with a different one. NVDL schema designers do not need any knowledge of the particular subschema implementation details. Moreover, they don't even need to understand the different subschema languages when designing their NVDL scripts.
In the previous section we have seen how difficult it is to create a compound definition using a namespace-aware schema language. Lets use NVDL to create the same compound schema: XHTML with embedded SVG, MathML and RDF. In this case, there is no need for several experts to work on that for days. One person can create such NVDL script in a matter of minutes (see Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF”). The reason is, existing schemas can be fully reused without making any changes to them.

Example 5. NVDL schema for XHTML with embedded SVG, MathML and RDF

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0" startMode="root">
  <mode name="root">       
    <namespace ns="http://www.w3.org/1999/xhtml">
      <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
        <context path="head" useMode="head"/>
        <context path="div|li|p...all block level elements" useMode="block_inline"/>
        <context path="a|em|span|...all inline elements" useMode="block_inline"/>
      </validate>
    </namespace>
  </mode>  
  <mode name="block_inline">
    <namespace ns="http://www.w3.org/2000/svg">
      <validate schema="http://www.w3.org/TR/2002/WD-SVG11-20020108/SVG.xsd"/>
    </namespace>
    <namespace ns="http://www.w3.org/1998/Math/MathML">
      <validate schema="http://www.w3.org/Math/XMLSchema/mathml2/mathml2.xsd"/>
    </namespace>
  </mode>
  <mode namne="head">
    <namespace ns="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
      <validate schema="http://www.w3.org/2000/07/rdf.xsd">
        <mode><anyNamespace><attach/></anyNamespace></mode>  
      </validate>
    </namespace>
  </mode>
</rules>

In the NVDL script in Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF”, subschemas are referenced directly at their original locations using URLs. The script tells the NVDL engine that the only acceptable parent language is XHTML and other vocabularies are forbidden in that context. Plain XHTML is extracted from the validated document and send for validation against the official DTDs. RDF sections may only occur in the context of the head element. Any foreign vocabulary contained inside the RDF fragment is attached to it before being send for validation. SVG and MathML fragments are allowed only in block and inline elements. Any other vocabulary in any other context of the document is rejected.
This simple example demonstrates the power of NVDL. Modifying the NVDL script to allow any other vocabulary in some context is a simple and straightforward task. In addition, the script contains only the required information about the compound language. Anything related to the grammar of the particular vocabularies is encapsulated in the subschemas where it really belongs. This makes NVDL schemas not only easy to design, but also easy to read and understand.
Note that Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF” demonstrates the use of an NVDL context construct which allows to apply a specific handling to sections in a given path within their parent section. Several paths separated by | may be used within one context condition. Paths used in the example are relative, but absolute paths may be used as well. For example an HTML head context can be addressed also using the /html/head path.

JNVDL

JNVDL is a Java-based implementation of the [NVDL] specification and it was developed by our team. JNVDL uses the new JAXP validation API, which has been introduced in Java 5. This is a standard way to invoke validation processes and it makes JNVDL easy to use for the end user as well as simply reusable in other applications.

Example 6. Invoking NVDL validation using the JAXP validation API

Schema schema = 
  SchemaFactory.newInstance(
    "http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0")
      .newSchema(new File("schema.nvdl"));

schema.newValidator().validate("instance.xml");

The validation API is also used by JNVDL to invoke further validation processes for particular subschemas. This makes JNVDL transparent to different schema language validator implementations. Enabling JNVDL to validate against a new schema language is just the matter of adding the appropriate validator's jar library on the Java classpath. No changes to the JNVDL code are required.

Implementation issues

One of the issues the JNVDL implementation faced is related to the fact that validators tend to report error locations using line and column numbers. When parsing the validated instance and turning it into validation fragments, the original position of elements and attributes is inevitably lost. There are two reasons for that. First, today parsers are lacking round-tripping support, thus some whitespaces which are considered to be irrelevant aren't reported and preserved. Second, different validation fragments are taken from different places within the original document. As they are send to validators separately, the original position is lost.
Such behavior may confuse users as the error line numbers reported by the particular validators aren't related to the original document but to the particular fragment context. To interpret the information correctly, users would need to deduce the line numbers from the original position of the validation fragments created by JNVDL.
To overcome those difficulties, JNVDL provides a proprietary round-tripping extension. Such extension preserves whitespaces from the original document and before validation fragments are being send to the particular validators, they are modified so that elements and attributes occur on the same lines as in the original document. Further, if an XML fragment is extracted from the middle of the document, JNVDL adds the appropriate number of empty lines before it to keep the fragment at the same location.
The problem of irrelevance of some whitespaces within XML documents makes the use of line numbers to locate elements and attribute problematic or even error-prone. Validation API designers should consider using a different mechanism to locate errors. For example XPath is a good candidate, as it is whitespace independent and precise.

Impact on a Web architecture

It is evident that compound documents are used more and more often. At this time NVDL is the best available technology for validation of compound documents. Still NVDL has some limitations which make it not very usable for some document types that are widely used on the Web. On the other hand the most popular container format for compound documents—XHTML—is not designed with this usage scenario in mind and breaks many principles of a Web architecture.

Namespace is not a document type

It is a quite common misconception that for each namespace there is a single schema defined somewhere. This assumption might hold for some simpler specialized XML based languages, but for many languages used on the Web, namespace works just as a basic semantic identification.
Very often, there are multiple different variants of vocabulary in one particular namespace. These vocabularies could be subsets of the “base” language—for example, this is a case of XHTML 1.0 Transitional and its derivates like XHTML 1.0 Strict, XHTML Basic or XHTML Print. The second case is newer version of vocabulary which does not change meaning of original elements so there is no need to change namespace. Both XSLT 1.0 and XSLT 2.0 share the same namespace, but XSLT 2.0 defines dozen of new elements and attributes, it even changes content model of some elements. Similar situation is true also for XHTML—XHTML 1.1 defines several new elements for Ruby annotations.

Versioning namespaces

Several different approaches for recognizing document types in a single namespace are in a common use. One of the easiest is usage of dedicated attribute for holding version information; for example in case of XSLT.

Example 7. Version information inside XSLT 2.0 stylesheet

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  version="2.0">
  ...
</xsl:stylesheet>

This is almost ideal way of conveying version information. Attribute value can be easily accessed in almost all processing tools. What is even more important, you can embed XSLT into other XML vocabulary and you are still able to identify a version of XSLT used by using the version attribute.
The only problem is that XSLT allows versioning attribute to occur only on a top element of a stylesheet. So you are unable to extract for example one template from stylesheet and add versioning information to this template.
XHTML uses legacy way of specifying versioning information which is depending on presence of a document type declaration (!DOCTYPE) at the start of the document.

Example 8. Version information in XHTML document

<!DOCTYPE html 
  PUBLIC "-//W3C//DTD XHTML-Print 1.0//EN"
  "http://www.w3.org/MarkUp/DTD/xhtml-print10.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  ...
</html>

Strictly speaking, document type declaration is not version indication, it is just reference to DTD which can be used for validation and definition of entities used. But public or system identifier could be used as a version identifier albeit quite long and verbose.
Unfortunately document type declaration can occur only at the beginning of an XML document. It can not be embedded in the middle of the document—this disqualifies it from being used in the Web of compound documents. This for example means that you can not embedded an XHTML page into SOAP message and identify version of XHTML used.
Moreover, current specifications of several XHTML flavors (for example XHTML Basic and XHTML Print) make public identifier optional and allows specification of a private system identifier as long as it points to a copy of original DTD. This means that in order to reliably detect version of XHTML used, you have to download DTD, normalize line-end characters inside it and then compare it to one of original DTDs provided by W3C as a part of respective specification. It is evident that such process is overkill. Moreover, requests for download of private copy of DTD could be misused as attack against the Web agent—this DTD could be very long or it could use a big amount of entity declarations to congest the XML parser.
There is also not very well known feature of XHTML that could be used for specifying version information instead of document type declaration. It is possible to use the profile attribute on the head element. Profile identifies particular profile (version, subset) of the language used and it has form of URI.

Example 9. More robust way of labeling document as XHTML Print

<html xmlns="http://www.w3.org/1999/xhtml">
  <head 
    profile="http://www.w3.org/Markup/Profile/Print">
  ...
  </head>
  ...
</html>

Again, profile attribute is not a perfect solution—it can be specified only on the head element and thus can not be used for specifying flavor of XHTML used for just a small fragment of XHTML code.
Previous examples show a very sad conclusion that the current state of XML vocabularies and their specifications were not designed in order to make it possible to fully exploit possibilities of compound documents. We think that W3C should extend current Web architecture [WEBARCH] and update older specifications to support robust and flexible way of attaching version information to arbitrary fragments of XML vocabularies. It seems that allowing version or similar attribute on all elements which can be used as root elements of XML fragments is a simple and sufficient solution. At the same time, a document type declaration should be made an optional part of a conforming document.

Extending NVDL to support versioning

In the previous text we explained why we think that namespace itself is not sufficient for a document type identification. As NVDL validation dispatching is based solely on namespaces, we have a problem here—the current version of NVDL is not able to recognize different flavors of XHTML or XSLT and route validation to appropriate versions of the schema. To overcome this limitation, we designed few extensions to the NVDL language. Their utility is being evaluated using JNVDL (our implementation of the NVDL standard).
Our extensions allow better control over the dispatching process. Validations candidate (usually XML fragment from a single namespace) is being validated only if corresponding rule in NVDL script matches both namespace and additional condition. This condition can be expressed in XPath language. Example 10, “Validation dispatching based on XPath expression” shows NVDL script which can differentiate between XSLT 1.0 and XSLT 2.0 and use the correct schema for validation.

Example 10. Validation dispatching based on XPath expression

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0"
       xmlns:jnvdl="http://jnvdl.sf.net">
  <namespace ns="http://www.w3.org/1999/XSL/Transform" 
             jnvdl:useWhen="@version = '1.0'">
    <validate schema="xslt1.xsd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/XSL/Transform" 
             jnvdl:useWhen="@version = '2.0'">
    <validate schema="xslt2.rng"/>
  </namespace>
</rules>

The appropriate rule in an NVDL script is used for dispatching only when expression in the useWhen attribute is true. Context for XPath evaluation corresponds to the element section to be dispatched. For attribute sections, dummy element with attached attributes is expected.
Although we previously stated that document type declaration is not a robust way for specifying version information, it is worth to support this way for legacy documents. The past practice was to differentiate document types using system and public identifier. JNVDL thus supports also additional parameters useWhenPublicId, useWhenSystemId, useWhenPublicIdRegex and useWhenSystemIdRegex to control when a particular rule will be used for dispatching based on content of system or public identifiers. If there is more then one “useWhen…” parameter on a single rule, it is sufficient if just one of them matches. Example 11, “Extended NVDL script which handles various flavors of XHTML” shows how to use these JNVDL extensions for handling various kinds of XHTML in a single NVDL script.

Example 11. Extended NVDL script which handles various flavors of XHTML

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0"
       xmlns:jnvdl="http://jnvdl.sf.net"
       xmlns:html="http://www.w3.org/1999/xhtml">
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML 1.0 Strict//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML 1.0 Transitional//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML-Print 1.0//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/MarkUp/DTD/xhtml-print10.dtd"
             jnvdl:useWhen="contains(concat(' ', normalize-space(html:html/html:head/@profile), ' '), 
                                      ' http://www.w3.org/Markup/Profile/Print ')">
    <validate schema="xhtml-print-1.rng"/>
  </namespace>
  <!-- Unrecognized flavors of XHTML are validated as XHTML 1.0 Transitional -->
  <namespace ns="http://www.w3.org/1999/xhtml">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"/>
  </namespace>
</rules>

We think that without extensions similar to what we propose, usage of NVDL is somehow limited when considering the real Web compound documents in use. On the other hand, only XPath enabled matching (useWhen) could be potentially added into a future revision of NVDL. Matching done on system and public identifiers needs information, which is not available in the NVDL data model. JNVDL is thus using an augmented data model to support those extensions.

Related work

NVDL could be used not only for validation, but also as a generic mechanism for associating schemas to XML documents. This feature is necessary in many scenarios, including XML editors or loosely coupled interfaces for accepting incoming XML messages.
NVDL is an international standard and builds on many preceding technologies. Some XML editors, for example nXML mode for Emacs and oXygen, use similar approach for association of schemas for document being edited. But as far as we know, none of those systems supports usage of full XPath to manage associations. In this regard our NVDL implementation offers unique functionality which we believe will be incorporated directly into NVDL standard in a future.
Currently there are two other NVDL implementations—oNVDL and enovdl. Advantages of our implementation include seamless integration with Java XML APIs and extensions for working with multiple different schemas for the same namespace.
Our implementation holds all validation candidates in memory in a tree representation. This allows us to do fancy things like evaluating full XPath before dispatching takes place. oNVDL uses streaming approach which is more memory efficient and can be used for processing of a very large datasets. But it is impossible to support full XPath in a streaming mode.

Future work

One of the future plans for JNVDL is to incorporate it into the Relaxed Web document validation project, see [RLX]. Relaxed consists of comprehensive HTML 4.01/XHTML 1.0 schemas and a validation framework. The schemas were created using RELAX NG with embedded Schematron rules. This combination of languages is very powerful. It allows to express more constrains than the official W3C DTD-based schemas. Relaxed validates also some of the WCAG 1.0 constrains and it has a compound documents validation support. Users may choose to allow foreign namespaces inside their documents or to ban them completely. They may also validate against a set of predefined compound schemas e. g. XHTML+SVG, XHTML+MathML etc.
In terms of compound documents, the Relaxed project is limited to RELAX NG namespace support. As described previously, this makes it difficult or even time consuming to create compound document schemas. To overcome those difficulties, the new version of Relaxed, which is currently being developed, will use JNVDL as the core validation engine. Such step will make NVDL validation publicly accessible through a Web based interface.
Moreover, JNVDL will help to create and maintain new compound document schemas easily. Part of the future work is to enrich the current Relaxed schema repository with NVDL scripts for different combinations of the standard and widely used vocabularies, especially those intended to be used in the Web environment.

Conclusions

This article has shown that validation of compound documents is best handled using the NVDL validation language, which has many advantages over other similar approaches (e. g. namespace support in Relax NG or XML Schema). We disclosed a problem of having different versions of document type in a single namespace and we have shown how to fix this problem by extending NVDL in our implementation called JNVDL. We will use the acquired knowledge from developing JNVDL and using NVDL when building new version of the Relaxed validator.

Bibliography

[NVDL] Document Schema Definition Languages (DSDL) — Part 4: Namespace-based Validation Dispatching Language — NVDL. ISO/IEC 19757-4. 2006. Available at: http://standards.iso.org/ittf/PubliclyAvailableStandards/c038615_ISO_IEC_19757-4_2006(E).zip

[XH] Birkbeck, M: xH: The new language you already know. Presented at WWW 2006 conference, Edinburgh.

[XML] Bray, T., Paoli, J., Sperberg-McQueen, C., Maler, E., Yergeau, F.: Extensible Markup Language (XML) 1.0 (Fourth Edition). W3C, 2006. Available at: http://www.w3.org/TR/2006/REC-xml-20060816

[NS] Bray, T., Hollander, D., Layman, A., Tobin, R.: Namespaces in XML 1.0 (Second Edition). W3C, 2006. Available at: http://www.w3.org/TR/REC-xml-names

[WEBARCH] Walsh, N., Jacobs. I: Architecture of the World Wide Web, Volume One. W3C, 2004. Available at: http://www.w3.org/TR/webarch/

[RLX] Kosek, J., Nálevka, P.: Relaxed—on the Way Towards True Validation of Compound Documents. In: WWW 2006 Proceedings. WWW 2006. May 23–26, 2006. Edinburgh, Scotland. Available at: http://www2006.org/programme/files/pdf/4508.pdf

[HTML4] Ragget, D., Le Hors, A., Jacobs, I.: HTML 4.01 Specification. W3C, 1999. Available at: http://www.w3.org/TR/1999/REC-html401-19991224/

[XHTML1] XHTML™ 1.0 The Extensible HyperText Markup Language (Second Edition). W3C, 2002. Available at: http://www.w3.org/TR/2002/REC-xhtml1-20020801/

[XMLSCH-ST] Thompson, H.S., Beech, D., Maloney, M., Mendelsohn, N.: XML Schema Part 1: Structures Second Edition. W3C, 2004. Available at: http://www.w3.org/TR/2004/REC-xmlschema-1-20041028/

[XMLSCH-DT] Biron, P., Malhotra, A.: XML Schema Part 2: Datatypes Second Edition. W3C, 2004. Available at: http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/

[RNG] Clark, J., Murata, M.: RELAX NG Specification. OASIS Committee Specification, 2001. Available at: http://www.relaxng.org/spec-20011203.html

[XHTMLMOD] Altheim, M., McCarron, S., Boumphrey, F., Dooley, S., Schnitzenbaumer, S., Wugofski, T.: Modularization of XHTML™. W3C, 2001. Available at: http://www.w3.org/TR/2001/REC-xhtml-modularization-20010410/

[RDF] Beckett, D.: RDF/XML Syntax Specification (Revised). W3C, 2004. Available at: http://www.w3.org/TR/rdf-syntax-grammar

[SVG] Ferraiolo, J., Fujisawa, S., Jackson, J.: Scalable Vector Graphics (SVG) 1.1 Specification. W3C, 2003. Available at: http://www.w3.org/TR/SVG11

[MTHML] Carlisle, D., Ion, P., Miner, R., Poppelier, N.: Mathematical Markup Language (MathML) Version 2.0 (Second Edition). W3C, 2003. Available at: http://www.w3.org/TR/MathML2

---

^[1] Compound language is a term used within this text to describe a language composed of two or more different XML vocabularies. Such a composition is considered to be a language itself, as it has its own syntax and semantics in addition to the syntax and semantics of the particular vocabularies.

^[2] Subschema is defined in the NVDL specification as a schema referenced by the NVDL script.

New version of NVDL available

---

JNVDL 20071112 ..download latest version here.

I have created a new version of the JNVDL suite for compound document validation. The new version reflects the latest Murata Makoto's chnages in the NVDL specification including big changes in attribute section handling.
A major usability enhancement was validation debug outputs. Now the outputs correspond to how examples are shown in the specification. You will find in he output only what you are really interested in. Using the -d for validation the XFroms example from the specification shows the following output. You see exactly what JNVDL did, all the element and attribute sections it has created, interpretations it assigned to each section and finally fragments and what schema has been used to validate them. This may significatly help with debugging of your validation but also of JNVDL.

Example 1. Example JNVDL debug output

petr@alfa-pn-3:~/dev/project/nvdl/impl/dist$ ./jnvdl.sh -s ./example/primary/spec-xf-html.nvdl.xml -d ./example/primary/spec-xf-html.instance.xml
Round tripping: false
Keep line numbers: false
Stage 1 - Decomposing Sections -
        <{http://www.w3.org/2002/06/xhtml2} ES1(table)>
                <{http://www.w3.org/2002/xforms} ES2(repeat)>
                  AS{}(id nodeset )
                        <{http://www.w3.org/2002/06/xhtml2} ES3(tr)>
                                <{http://www.w3.org/2002/xforms} ES4(input)>
                                  AS{}(ref )
                                        <{http://www.w3.org/2002/06/xhtml2} ES5(p)>
                                                <{http://www.w3.org/2002/xforms} ES6(label)>
                                                </ES6(label)>
                                        </ES5(p)>
                                </ES4(input)>
                        </ES3(tr)>
                </ES2(repeat)>
        </ES1(table)>

Stage 2 - Building Interpretations -

Interpretation 1

                AS{}(ref )
                                 [ATTACH]
                ES1(table)
                                 [VALIDATE against '../secondary/xhtml2/xhtml2.rng']
                ES4(input)
                                 [ATTACH]
                AS{}(id nodeset )
                                 [ATTACH]
                ES2(repeat)
                                 [VALIDATE against '../secondary/xforms/xforms.rng']
                ES5(p)
                                 [UNWRAP]
                ES6(label)
                                 [ATTACH]
                ES3(tr)
                                 [UNWRAP]

Interpretation 2

                AS{}(ref )
                                 [ATTACH]
                ES1(table)
                                 [VALIDATE against '../secondary/xhtml2/xhtml2.rng']
                ES4(input)
                                 [UNWRAP]
                AS{}(id nodeset )
                                 [ATTACH]
                ES2(repeat)
                                 [UNWRAP]
                ES5(p)
                                 [ATTACH]
                ES6(label)
                                 [UNWRAP]
                ES3(tr)
                                 [ATTACH]

Stage 3 and 4 - Combining Sections and Filtering -
        Validation candidate overwritten by a larger fragment:
 [1 < 4]<table xmlns="http://www.w3.org/2002/06/xhtml2" xmlns:xforms="http://www.w3.org/2002/xforms">  <tr>  <td>  <p>    </p>  </td>  </tr>  </table>

Stage 5 - Validation -

        Schema 'file:/home/petr/dev/project/nvdl/impl/dist/./example/primary/../secondary/xhtml2/xhtml2.rng'
        Namespace 'http://relaxng.org/ns/structure/1.0'
        Fragment: '<table xmlns="http://www.w3.org/2002/06/xhtml2" xmlns:xforms="http://www.w3.org/2002/xforms">  <tr>  <td>  <p>    </p>  </td>  </tr>  </table>'
ERROR: line 1 column 94, tag name "table" is not allowed. Possible tag names are: <html>

        Schema 'file:/home/petr/dev/project/nvdl/impl/dist/./example/primary/../secondary/xforms/xforms.rng'
        Namespace 'http://relaxng.org/ns/structure/1.0'
        Fragment: '<xforms:repeat xmlns:xforms="http://www.w3.org/2002/xforms" id="lineset" nodeset="/my:lines/my:line">  <xforms:input ref="my:price">  <xforms:label>Line Item</xforms:label>  </xforms:input>  </xforms:repeat>'

Grammar vs. Rules

Diagnostics in XML document validation

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
petr@nalevka.com

Abstract

Regular grammars has been used over decades for different formal language validation tasks because of their relative easiness of expression but more important because of their low computing expenses. Validation using regular grammars is commonly used also for XML document validation. In this case human understandable grammar definitions are converted into regular expressions which are evaluated against the input document. This approach is fast, straightforward but it lacks good diagnostics. It is hard for the validator engine to track grammar errors back to the information domain and provide some useful error messages understandable for the author.
An alternative approach tends to be rule-based validation which is closely related to the modelled information domain. Rule-based approach gives very good diagnostics but it is more complicated to express simple parent-child relationships as in grammar-based languages. An interesting way how to gain advantages of both approaches is to support conversion from grammar-based schemes into rule-based schemes.

---

Table of Contents

Introduction

Validation with Grammar

Grammar-based XML Validation

Hedge

Regular Hedge Grammar

Automata-based Validation

Grammar and Diagnostics

Using Rules

Schematron

Expressiveness

From Grammar to Rules

Conclusions

Bibliography

Introduction

Regular grammar is a formal grammar which is defined by a set of terminal symbols, a set of non-terminals, and a set of production rules.
Production rules need to have the following form.

Regular grammar production rules

1. 
   X →x; where X is a non-terminal and x is a terminal symbol
   
2. 
   X →xY; where X and Y is a non-terminal and x is a terminal symbol.
   
3. 
   X →ε; where X is a non-terminal and ε is an empty word.
   

The previous is also known as right regular grammar. For a left regular grammar the second production rule takes the form of X →Yx.
Regular grammar describes all regular languages. They are in a sense equivalent to the finite state automaton. Form every regular grammar a FSA may be constructed. For each regular language a FSA can be constructed which accepts all words from this language but rejects all other words. A FSA is an algorithmic approach how to decide whether a particular language is generated by a particular regular grammar.
Regular languages may also be described by regular expressions. This task is information common practice in information technologies. There is an algorithmic way to create a FSA from a regular expression and thus a way how to automatically decide whether a word belongs into a regular language or not.

Validation with Grammar

Regular language theory is often used for validation of whether a string (a program or a document) matches a regular grammar. This is a typical task which is done during compilation of a computer program where the compiler checks whether the program has correct syntax and can be compiled. Another example is validation of an XML document against a schema. An XML schema may be converted into a regular grammar and then decided whether a document is generated by that particular grammar or not.
Keeping validation algorithm regular grammar-based is convenient in terms of computational complexity. For example regular expressions may be evaluated in a linear time by converting them into deterministic finite state automaton (DFSA). For any input word N of length n and a regular expression R of the lengthm; N may be matched against R in the time O(n+2^m) .

Grammar-based XML Validation

One of the concepts for XML document validation based on regular grammars is regular hedge grammar. In general, hedge is a sequence of trees. In the XML terminology, we would call them elements. Basically an XML document is an example of a hedge.

Hedge

Hedge over a finite set of symbols S and variables V is either:

• 
  an null hedge (ε),
  
• 
  a variable fromV,
  
• 
  s<h> where s is a symbol from S and h is again a hedge,
  
• 
  or a concatenation of two hedges i.j.
  

This text uses same hedge notation as used by Murata Makoto in [HEDGE].

Figure 1. Example hedge notation

a<b c<f g<χ>> d<ψ> e>

Alternatively we can depict hedges also using diagrams. The same hedge again in a different notation.

Note that symbols occur in hedges only in non-leaf nodes and variables in leafs.

Any XML document can simply be converted into the hedge notation. Tags are represented through symbols and their textual content as variables (In this case we abstract from XML attributes). Such conversion is demonstrated within the next example.

Figure 2. XML document as a hedge

Here is an simple HTML document.

<html>
  <head>
    <title>Example</title>
  </head>
  <body>
    <p>Foo</p>
  </body>
</html>

The following hedge is equivalent to the previous document.

html<head<title<'Example'> body<p<'Foo'>>

In this case the set of symbols S = { html, head, title, body, p } and V = { 'Foo', 'Example' }

Regular Hedge Grammar

Now it is the right time to introduce the Regular Hedge Grammar (RHG) which is a mechanism for generation of different hedges. For a grammar there is an algorithmic way how to decide whether a particular word belongs to a language generated by that grammar.
This process in called validation in the XML terminology and any particular RHG which generates a set of hedges may be understood as a schema which defines all valid XML documents.
Validation of an XML document against a schema is a task of converting a RHG into a hedge automaton and try whether it accepts the input document or not.
Formal definition of RHG is very similar to the regular grammar definition described in the section called “Introduction”.
Regular hedge grammar is a formal grammar which is defined in [HEDGE] as a finite set of terminal symbols S, a finite set of non-terminals N, a finite set of variables V a set of production rules P and r which is a regular expression composed of non-terminals.

RHG production rules

Production rules in P are only of the following form.

1. 
   n →v; where n is a non-terminal and v is a variable. Applying this production rules means a non-terminal is replaced by a variable.
   
2. 
   n →s<r>; where n is a non-terminal, s is a symbol and r is a regular expression composed of non-terminal symbols. If this production rule gets applied a non-terminal is replaced by a terminal symbol which contains a sequence of non-terminals matching the regular expression r.
   

The language generated by the RHG is a set of hedges generated by applying the production rules to a set non-terminals which match the regular expression r.
The use of RHGs as a schema can be demonstrated on a simple example. Imagine, we like to define an simplification of the HTML language, where the root element is html which must contain one head and one body element in a sequence. Further, there is one title element in head and an unlimited amount of p or img in the body in any order.

Figure 3. Schema in RHG

The verbal definition may be expressed formally in DTD as follows.

<!ELEMENT  html (head, body)>
<!ELEMENT  body (p|img)*>
<!ELEMENT  head  (title)>
<!ELEMENT  title   (#PCDATA)>
<!ELEMENT  p   (#PCDATA)>
<!ELEMENT  img  EMPTY>

The same definition in the RHG notation.

S = {html, head, body, title, p, img }
V = { "#PCDATA" }
N = { N(html), N(head), N(body), N(title), N(p), N(img), N(pcdata) }
P = { N(html)  →  html<N(head), N(body)>
      N(head)  →  head<N(title)>
      N(body)  →  body<(N(p) | N(img))*>
      N(title) →  title<N(pcdata)>
      N(p)     →  p<N(pcdata)>
      N(img)   →  img<ε>
      N(pcdata)→  #PCDATA }

Automata-based Validation

The validation task for a particular schema (RHG) and a particular XML document (input word) is equivalent to a task to construct a Deterministic Hedge Automaton (DHA) and find out whether it accepts the input.
DHA is a finite state automaton (FSA) and as such it is defined with a finite set of symbols, states and transitional function which transit the automaton from one state to another, depending on the input symbol.
DHA have just few slight modifications; there are two transition functions, one for symbols ( Fs) and other for variables (Fv) and the result of Fs depends not only on the current state and the input symbol, but it depends on a set of states which are the target states for the child symbols or values in the hedge.

Here is the formal definition of a DHA taken from [HEDGE]. DHA is a sextuple (S, V, Q, F, Fs, Fv), where:

1. 
   S is a finite set of symbols,
   
2. 
   V is a finite set of values,
   
3. 
   Q is a finite set of states,
   
4. 
   F is a set of terminal states, a regular set over Q,
   
5. 
   Fs is a function from S × Q* → Q such that for every q in Q and s in S, {q1 q2 ... qk | k >= 0, α(x, q1 q2 ... qk ) = q } is a regular set,
   
6. 
   Fv is a function from V → Q
   

Figure 4. Example of the DHA process

Here is the very same HTML document which we created grammar for in Figure 3, “Schema in RHG”.

<html>
  <head><title>Test</title></head>
  <body>
    <img/>
  </body>
</html>

And this is how a DHA evaluates the transition functions.

Fs(html, Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)))

Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(head, Fs(title,Fv('Test')))
Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(body, Fs(img, ε))

Fs(head, Fs(title,Fv('Test'))) → Fs(title,Fv('Test'))

Fs(body, Fs(img, ε)) → Fs(img, ε)

Fs(title,Fv('Test')) → Fv('Test')

Fs(img, ε) → ε

Note that validation using RHG is used withing one of the current mainstream validation languages Relax NG, see [RNG].
The Fs function which accepts multiple states as parameters makes it difficult to depict a finite hedge automaton in a diagram, thus in the later text we will use a classical finite state automaton to demonstrate regular grammar-based XML validation process. The expressive power is the same and we may depict such automata more easily and make the diagrams more understandable.

Figure 5. XML Validating FSA

In the diagram you can see a FSA which validates XML documents against the schema described in Figure 3, “Schema in RHG”. For any symbol which has no explicit transition in the diagram the target state is ERROR. ERROR is not part of the final state set and thus any input document which leads the DHA to ERROR is considered to be invalid. Only FIN belongs to F; the set of terminal states.

Note, there are tree different arrows pointing from the B1 state, because body may contain p | img | ε.
The final state for an invalid document doesn't need to be ERROR. For example a document which would be missing the html end tag but otherwise it is correct will finish in the B3 state and thus the automaton won't accept it.
Using FSA we can express many common restrictions within XML trees, thus it is a suitable model for us at this stage. For example a sequence of head and body elements which has a strict order is expressed with the transition from H5 → H6 → B1.
In case we like to express an arbitrary order of child elements withing a parent we can use multiple transitions from one state as demonstrated in the B1 state pointing to P1 and I1.

Grammar and Diagnostics

Regular grammar-based validation is fast and straight forward, but does it really give suitable validation outputs? Experiences from the SGML/XML world shows that not always. With grammars it is easy to find out that something is wrong in the document, but it is more difficult to explain where exactly the problem occurred and extremely difficult to guide the author to resolve the issue or to explain the issue in a human understandable form.
One sort of problems with diagnostics can be explained with a example grammar for a simple Member of Parliament evidence. MPs are identified by name which is required and also each MP must have one assistant. The only exception is the Speaker of the Parliament who has two assistants. The door number of the MPs office is optional.

Figure 6. Schema for MPs evidence

<!ELEMENT  MP (name, (speaker, assistant)?, assistant, office?)
<!ELEMENT  office    (#PCDATA)>
<!ELEMENT  assistant (#PCDATA)>
<!ELEMENT  speaker  EMPTY>

Next we construct a FSA automaton to validate such grammar. Such automaton is depicted in the next diagram.

Figure 7. Validator for the MPs evidence grammar

Next consider several example of instances, their validation flow and the validation results.

Instances and validation

Nr	Document	Flow	Error	Explanation	Result
1	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> <office>56</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ Q4 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
2	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> <office>121</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
3	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ FIN			VALID
4	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ ERROR	Expected <assistant> but was </MP>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID
5	<MP> <name>Miloslav Vlcek</name> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ ERROR	Expected </MP> or <office> but was <assistant>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID

In the table above, the diagnostics for instance number 4 is appropriate. The validation engine expected a assistant tag but in the instance the MP tag has already been closed. The fix is quite obvious and clearly explained in the diagnostics. The author shall provide a second sibling assistant element.
A real problem occurs in the instance number 5 validation example. In this case somebody did obviously forgotten to mark the MP as the Speaker of the Parliament as nobody else may have two assistants assigned. The regular grammar-based diagnostics does not help to resolve such issue.
The location of the error is the second assistant element, but in reality the error is the missing speaker element after name. The error message claims we have a redundant assistant element, but in this case we are talking about the Speaker's document and we just forgot to add the speaker element indicator. In this case the validation result gives us no clue how to resolve the issue, as it does not mention the missing speaker element at all.
Moreover, the validation result guides us to delete the second assistant element which is completely wrong and in addition we would loose important information in order to make the document pass the validation.
There are many more examples where regular grammar-based validation diagnostics leads to misleading error messages, but this is not the only problem. As grammar-based validation is completely unaware of the semantics of the validated language there is no way how to attach reasonable domain specific diagnostics which would help the authors resolve issues more easily.

Quality of diagnostics

Compare the following two validation diagnostics

1. 
   “Expected MP end tag or office but was assistant”.
   
2. 
   “Missing speaker element. 'Miloslav Vlcek' has 2 assistants defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.”.
   

It is obvious that the second error massage gives a reasonable resolution to the user but the first message is completely useless, misleading and wrongly positioned. In the rest of the text we will learn possible approaches to get to the quality of diagnostics demonstrated in the second sentence in Quality of diagnostics.

Using Rules

Fortunately grammar-based validation is not the only validation approach which exists today. Rule-based validation languages are becoming more and more popular.
In principle, rule-based validation matches an input document against a set of patterns which are called rules. The result of such matching is a set of assertions and diagnostics. [RJ] stresses the distinction between the assertion text, which is a positive statement of what should be true in the document, and the diagnostics, which contains specific messages for describing, locating and correcting the problem.
To illustrate the difference, in Quality of diagnostics the Missing speaker element. message is the assertion and the rest of the message is diagnostics.
The rule-based approach is quite double-edged. At one side, when designing the schema we have a more low level control over the validation process and that is the reason we are able to attach domain specific diagnostics, but on the other hand, some definitions which are implicitly expressed by declaring an element in a grammar-based language need to be expressed in the rule-based approach explicitly, sometimes with more rules.
This is definitely error-prone, because forgetting one of the rules means we have an incomplete schema and there is no easy way how to detect it.
Another problem of the rule-based approach is performance. Where grammar-based validation can be performed in a linear time, in rule-based validation the execution time depends on the expressions we use within our rule assertions. We can easily get into the world of context-sensitive tasks and in case, performance is a important factor in a certain application, it is necessary to judge each individual rule in terms of performance. In contrast, schema designers who are using the regular grammar-based approach are free of expression. They may use any language constructs they like and keep their validation tasks in linear time.
Even there are downsides of the rule-based approach, it is worth studying it. Grammar-based validation did already reach its limits in terms of diagnostics and there are many real life validation problems were diagnostics is far more important than performance. For example validation of complex XML languages with hundreds of pages of specification like for example HTML, SVG, DocBook and others. In this case authors validate relatively small documents, but correct diagnostics is very important for them as they did not read the whole specification.
Moreover, there is a huge area of possibilities for future performance optimisation for rule-based languages. In the time when they are used as long as grammar based languages are used now, I sure there will be effective optimisation techniques which will minimize the performance handicap.

Schematron

To demonstrate the rule-based approach on a few examples, in this section we will have closer look into Schematron; the major standardized rule-based validation language.
Schematron is a simple XML-based schema language composed just of a few elements and attribute. There are only six main elements in Schematron which makes it very easy to learn. In this short introduction to Schematron we will mention just the six most important elements and their semantics which will allow us to understand how are rules being constructed.

Four most important Schematron elements

schema

the root container for patterns.

pattern

a named container for a set of rules

rule

a particular rule with a defined context within the validated document. Rules contain mixed assert and report elements.

assert

Assertion contains a statement about the document in a formal language which may be automatically evaluated against the document from within the rules context. In case the assertion is not satisfied, an attached plain text explanation of the problem is displayed to the end-user.

report

Report is equivalent to assertion, but the attached plain text is invoked in case the report's test expression is evaluated as TRUE (opposite to the assertion).

value-of

This element allows to enrich the diagnostics with values from withing the current rule context of the document to enhance the diagnostics with additional guidance for the author to resolve the reported issue.

Although Schematron uses XPath as the preferred formal language to evaluate assertions and reports against XML document, it is possible to use also other languages able to address nodes and values within the XML DOM tree; for example JavaScript is a good candidate.

Figure 8. Schematron rule example

Now we can return to our MP evidence problem and try to reach the level of diagnostics shown in the second message in Quality of diagnostics.

<sch:pattern name="MP Evidence">
    <sch:rule context="MP">
        <sch:assert report="count(assistant) > 0 and not(speaker)">
                Missing speaker element.
                '<sch:value-of select="name"/>' has <sch:value-of select="count(assistant)"/> assistant(s) defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.
        </sch:assert>
    </sch:rule>
</sch:pattern>

Note that in Schematron there is a way how to logically split assertion texts and diagnostics. To simplify the example, those two distinct parts of the error message has been put together as the report text.
In terms of performance optimisation, Schematron features the phases construct. Patterns may be organized into phases and during validation only a certain phase may be evaluated. Just in case there are no errors the next phase gets processed.

Expressiveness

It is difficult to say which approach (rules or grammar) is more expressive. The set of documents able to be described by a rule-based approach (Schematron) and a regular grammar-based approach are two distinct sets with a significant intersection. But there are documents which may be described with one approach but cannot be described with the other.
On the other hand there are many real life use-cases where Schematron can be used to model some restrictions which are really useful but they can't be expressed using regular grammar-based validation. This is caused by the fact that Schematron can operate with multiple contexts across the documents where grammar-based languages usually model just simple parent-child relationships withing the context of the current parent element. With Schematron we may for example condition the occurrence of an element by the values of an attribute in a completely different branch of the document. This is very powerful and has many real life use-cases. For example, using Schematron I was able to formalize additional restrictions expressed in the HTML specification only verbally; thus improving validation results and diagnostics for HTML document validation, see [PN1].

Figure 9. Schematron rule not expressible using a regular grammar-based approach

This example was taken from [PN1] and is based in my Schematron schema for W3C WCAG 1.0 specification.

<sch:rule context="html:abbr">
  <sch:report test="not(@title) and not(preceding::html:abbr[. = string(current())][@title])">
   WCAG 1.0 Checkpoint 4.2 (Priority 3) First occurrence of abbreviation in a document needs to have an title defined.
  </sch:report>
</sch:rule>

When thinking about suitability of grammar or rules for different validation tasks, we can easily come to a conclusion that a mixture of both approaches would bring the best of both worlds. This is the approach proposed in [PN1]. Such approach encourages to use a grammar-based language to enumerate elements and attributes and define their content model easily and to use rules to define advanced multi-context assertions with enhanced diagnostics. This approach was used to model extended HTML schemas in [PN1].

From Grammar to Rules

Another approach to combine rules and grammar is a to convert grammar-based schemas to Schematron rules. Such conversion may slightly enhance diagnostics by keeping simplicity of expression. Also such generated schemas become really platform/programming language independent as we don't need any validation engine for our specific schema language, but validation becomes a simple XSLT transformation and today an XSLT processor is present in vast majority of environments (even a web browser can be used as an XSLT processor).
Converting grammar to rules makes also integration of grammar-based language with Schematron easy as the generated rules may be simply merged with some additional rules defined.
There are clearly advantages to convert grammar-based schemas to rules, but how to achieve that? As we stated, those two approaches are not equally expressive, we already know that this conversion cannot be exhaustive. But in real life this may not be a big problem, because most of the reasonable constructs defined in regular grammar-based schema languages can be expressed using rules. But there is no simple algorithmic way how to convert a FSA into a set of XPath rules. So the task here is to go through different constructs of a particular grammar-based language and invent templates to convert them into Schematron patterns.

Figure 10. Grammar validation using pure rules

The following diagram show the validation process including conversion. A grammar-based schema is first converted to rules, rules are merged with other restrictions already defined using rules, rules are grouped into phases to optimise performance and enhance diagnostics. Finally, an input document is validated against the generated and merged rules.
The conversion as well as the validation process may be nothing else than a standard XSLT transformation.

The most tricky part of the diagram above is of course conversion to Schematron. There is currently no such converter and implementation of such conversion is under research. In the simplest case, [RJ] mentions a straightforward way how to get grammars into XSLT using the XSLT 2 build-in regular expression engine. With regular expressions we can express cardinality, sequence, choice and other constructs common in grammar-based schemas. The advantage is, with such conversion we can do validation tasks using a standard XSLT 2 transformer, but on the other hand, there is no improvement in diagnostics. Again we are just doing a regular grammar-based validation with a FSA.
Another approach is to break individual grammar-based restrictions into different kind or rule types. For example the grammar-based schema enumerates all allowed element and attributes. This may be converted into Schematron rule which checks that for every element and attribute in the input document the element or attribute names belong into a set of allowed names, otherwise an unknown element error is reported.
Also it is easy to extract content models for each element (what different children it is allowed to contain) and for each element create a rule that checks that all children belong to a particular set of allowed child elements for that particular parent.
Having such rules does not really bring domain related explanations, but on the other hand, grammar-based validators are usually not able to show all violated rules in a sub-tree as they already die on the first error occurrence as they move to a ERROR state and there is no way out. In contrast Schematron rules will show all diagnostics of all violated assertions in one validation run which is a diagnostic improvement. Also it is possible to group certain type of checks into phases and systematically point our validation effort at some sort of issues.
As result, we can have phases for validation of mistakes in element or attribute names, for broken content models, for required elements or attribute if whether they are present and for all sort of different groups of problems.
Moreover, one part of our rule-based schema may be auto-generated from a grammar schema, not forcing us doing a lot of implicit rules manually, but another part of the rules may be defined explicitly with domain specific diagnostics. Another big challenge of the converting method is to find effective ways how to merge the generated implicit rules with the explicit one and thus enriching the validation results with highly specific and domain related diagnostics.

Conclusions

This article explains principles of XML document validation. Regular grammar-based validation is explained in detail using examples and diagrams. One of the examples demonstrates limits of regular grammar-based validation diagnostics.
The aim of this article is to show that despite its efficiency, regular grammar-based validation diagnostics is inappropriate for some applications. Error messages may be located wrongly and their explanation may be confusing for the XML document author.
One of the options to overcome such limitations is to use rule-based systems instead. Rule-based languages are more expressive for some sort of restrictions and they have much better diagnostics as they allow to control the error message form by the schema author. On the other hand it is more difficult to model some sort of simple relationships and a big issue is optimization. It is difficult to judge the computing price of different rules. But although there are drawbacks it is necessary to investigate new ways in validation because classical grammar-based approach did reach its limit already long time ago in terms of diagnostics and currently it is insufficient for some sort of tasks.
Very promising seems a hybrid approach exploiting the best of grammars and the best of rules in one validation process. Rules may be directly embedded into grammar-based schemas.
Another way is to get simplicity of expression using the grammar approach but enhance diagnostics through converting grammar definitions to rules before validation.
All approaches have their pros and cons and they are more or less suitable for different purposes. But the lack of good diagnostics in grammar-based validation is an outstanding issue which needs to be coped with. That's why exploring novel ways in XML document validation is important.

Bibliography

[HEDGE] Murata, M.:Hedge automata: a formal model for XML schemata. Fuji Xerox Information Systems. 2000. Available at: http://www.xml.gr.jp/relax/hedge_nice.html

[PN1] Kosek, J., Nálevka, P.: Relaxed — on the Way Towards True Validation of Compound Documents. WWW2006, Edinburg, 2006. Available at: http://www2006.org/programme/files/pdf/4508.pdf

[PN2] Nálevka, P.: Doplňková validate HTML a XHTML dokumentů. University of Economics, Prague, 2003. Available at: http://nalevka.com/resources/thesis.pdf

[PN3] Nálevka, P., Kosek, J.: Advanced approaches to XML document validation. Extreme Mark-up Languages Conference, Montreal, 2007. Available at: http://www.idealliance.org/papers/extreme/proceedings/xslfo-pdf/2007/Nalevka01/EML2007Nalevka01.pdf

[RNG] Clark, J., Murata, M.: RELAX NG Specification. OASIS Committee Specification, 2001. Available at: http://www.relaxng.org/spec-20011203.html

[SCH] Jelliffe, R.: The Schematron Assertion Language 1.5. Academia Sinica Computing Centre, 2002. Available at: http://xml.ascc.net/resource/schematron/Schematron2000.html

[RJ] Jelliffe, R.: Converting XML Schemas to Schematron. O'Reilly XML Blog, 2007. Available at: http://www.oreillynet.com/xml/blog/2007/09/converting_xml_schemas_to_sche.html

[MI] Ivánek, J.: Základy matematické informatiky I: Informace a automaty. Státní pedagogické nakladatelství, 1991, Praha, ISBN: 80-7079-673-1.