Balisage Paper: Refining the Taxonomy of XML Schema Languages. A new Approach for Categorizing XML Schema Languages in Terms of Processing Complexity

Introduction to the Formal Concepts

In this paper, we will mainly use tree grammars. Since the use of tree grammars is well established in the XML community, we will just shortly provide the necessary definitions; for a more explicit treatment and motivation, we defer the reader to Gécseg and Steinby, 1997 or Murata et al., 2005.

Definition 1 A regular tree grammar (RTG) is a 4-tuple (N,T,S,P), where N is a finite set of nonterminals, T is a finite set of terminals, S is a set of start symbols, which form a subset of N, P is a set of production rules, which have the form: A → a(r), where A ∈ N, a ∈ T, and r is a regular expression over elements of N. We call A the left hand side of a rule, a the terminal or label which is introduced by the rule, and r its content model.

We generally use uppercase letters for nonterminals, and lower-case letters for terminals. Note that this grammar generates trees, not strings, and that the nonterminals do not remain the labels of the (non-leaf) nodes they introduce, but are substituted by the terminal labels. The class of languages generated by RTGs is called the regular tree languages (RTLs). This is the most general class of languages we will consider here; and we now introduce various restrictions on this class of grammars, as they are defined by Murata et al., 2005.

Definition 2 We call two rules of a RTG competing, if they introduce the same terminal nodes, but have different left hand sides. Thus, A → a(r) and B → a(r') are competing.

In general, in an RTG we can merge any two rules which have the same left-hand side and introduce the same terminal, by merging their content models, because for any two regular expressions we can easily form a single expression which denotes is the union of both. Therefore, we will generally assume that in our grammars any two rules with same left-hand side and same terminal do not exist. As a consequence, the concept of competing rules is the crucial point if we deal with determinism and ambiguity. For the same reason, we can speak of competing nonterminals almost in the same way as of competing rules: competing nonterminals are the left-hand sides of competing rules; a grammar has competing nonterminals exactly if it has competing rules, and exactly as many as.

Definition 3 A local tree grammar (LTG) is an RTG with no competing rules.

In an LTG, we have thus a one-to-one correspondence of nonterminals and terminals, which makes them very similar to context-free grammars (though not identical, since regular content models allow for non-finitary branching).

Definition 4 A single type tree grammar (STG) is an RTG, where competing nonterminals must not occur in the same content model.

As Murata et al., 2005 point out, LTGs roughly correspond to DTDs, STGs correspond to XML Schema, and RTGs correspond to Relax NG. Note that this correspondence is established by only regarding the "core" syntactic features of the schema languages, that is XML's inherent reference mechanism is not taken into account. These are thus the most important grammar types for XML. Murata et al., 2005 still add another type:

Definition 5 A restrained competition grammar (RCG) is an RTG, where competing nonterminals must not occur in the same content model and with the same prefix of nonterminals; we thus disallow rules with identical left-hand side, terminals, and content models of the form (Γ A Δ) and (Γ B Δ'), where A and B are competing nonterminals, and where uppercase Greek letters refer to possibly empty sequences of nonterminals.

Notably, the restriction concerns only the left context of the competing nonterminals. Of course, there exists a parallel definition for the right context. The problem is that both definitions lack some generalization, as they both generate different classes of languages, and there is no inclusion in either direction. If we, however, generalize the restriction of competition to both the left and the right context (which weakens the overall restriction on the grammar), some problems arise. We will discuss possible generalizations later on.

It is easily seen that there is a hierarchy of proper inclusion of the grammar types presented: LTGs are always STGs, which are always RCGs, which are always RTGs, whereas the converse does not hold.

We furthermore define an interpretation of a given tree against a given grammar as follows:

Definition 6 An interpretation I of a tree t against a grammar G is a mapping from each node label of t, denoted by e, to a nonterminal N of the grammar, such that

As is easily seen, with this definition, the ease of interpretation directly interacts with the Murata hierarchy. We will continue in this vein. To keep things clear, it is crucial to distinguish between the label of a node and its interpretation: the label of a node corresponds to its terminal in the production rule (recall that tree grammars directly generate trees, not strings via trees as CFGs), and it is immediately visible in the tree. By the interpretation of a node in turn we denote the nonterminal by which the node label has been produced. This nonterminal is not visible and has to be inferred. In addition, we have to distinguish between rule and rule instantiation: since content models are regular expressions over nonterminals, they denote sets of sequences of nonterminals, and one member of this set is an instantiation. An additional problem arises in interaction with the fact that there is no necessary one-to-one correspondence of nonterminals and terminals (i.e., labels); a possible consequence is that the same sequence of labels can be produced by different instantiations of a content model (we will exhaustively discuss this source of ambiguity later on).

So far, we have introduced the main concepts which are well-known in the literature, and which we are going to use and elaborate in this paper.

An Example Grammar

We will use the following example to demonstrate some of our findings. We want to define a document grammar for a text. The text may contain an optional title, followed by either at least a single section or a single paragraph. An optional author entity (possibly decoded using an attribute) may contain information about the text's author. Inside a section an optional title followed by other (sub-)sections or paragraphs are allowed. The title consists of raw text while a paragraph may contain raw text or a reference to other paragraphs, since these may have an optional identifier (using XML's ID type).

If we try to express these constraints more formally we might end up with a grammar similar to the one shown in Figure 1. Again, nonterminals are printed in capital letters, while node labels or terminals are printed in small letters. Note, that in this formulation elements, attributes and raw text are defined as terminals.

S → text(author,Title? (Section|Para))
Section → section(Title? (Section|Para))
Title → title(#pcdata)
Para → para(id, #pcdata|Xref)
Xref → xref(href,ε) 

<!ELEMENT text (title?, (section | para)+)>
<!ATTLIST text author CDATA #IMPLIED>
<!ELEMENT title (#PCDATA)>
<!ELEMENT section (title?, (section | para)+)>
<!ELEMENT para (#PCDATA | xref)*>
<!ATTLIST para id ID #IMPLIED>
<!ELEMENT xref EMPTY>
<!ATTLIST xref href IDREF #REQUIRED>

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xs:element name="text">
    <xs:complexType>
      <xs:complexContent>
        <xs:extension base="textType">
          <xs:attribute name="author" type="xs:string" use="optional"/>
        </xs:extension>
      </xs:complexContent>
    </xs:complexType>
  </xs:element>
  <xs:element name="title" type="xs:string"/>
  <xs:element name="section" type="textType"/>
  <xs:element name="para">
    <xs:complexType mixed="true">
      <xs:sequence>
        <xs:element name="xref" minOccurs="0">
          <xs:complexType>
            <xs:attribute name="href" type="xs:IDREF" use="required"/>
          </xs:complexType>
        </xs:element>
      </xs:sequence>
      <xs:attribute ref="id" use="optional"/>
    </xs:complexType>
  </xs:element>
  <xs:attribute name="id" type="xs:ID"/>
  <xs:complexType name="textType">
    <xs:sequence>
      <xs:element ref="title" minOccurs="0"/>
      <xs:group ref="sectOrPara" maxOccurs="unbounded"/>
    </xs:sequence>
  </xs:complexType>
  <xs:group name="sectOrPara">
    <xs:choice>
      <xs:element ref="section"/>
      <xs:element ref="para"/>
    </xs:choice>
  </xs:group>
</xs:schema>

<?xml version="1.0" encoding="UTF-8"?>
<grammar xmlns="http://relaxng.org/ns/structure/1.0"
  datatypeLibrary="http://www.w3.org/2001/XMLSchema-datatypes">
  <start>
    <element name="text">
      <optional>
        <attribute name="author"/>
      </optional>
      <choice>
        <optional>
          <group>
            <ref name="element.title"/>
            <ref name="element.section"/>
          </group>
        </optional>
        <optional>
          <group>
            <ref name="element.title"/>
            <ref name="element.para"/>
          </group>
        </optional>
      </choice>
    </element>
  </start>
  <define name="element.title">
    <element name="title">
      <text/>
    </element>
  </define>
  <define name="element.section">
    <element name="section">
      <optional>
        <ref name="element.title"/>
      </optional>
      <ref name="sectOrPara"/>
    </element>
  </define>
  <define name="element.para">
    <element name="para">
      <optional>
        <attribute name="id">
          <data type="ID"/>
        </attribute>
      </optional>
      <zeroOrMore>
        <choice>
          <text/>
          <element name="xref">
            <attribute name="href">
              <data type="IDREF"/>
            </attribute>
            <empty/>
          </element>
        </choice>
      </zeroOrMore>
    </element>
  </define>
  <define name="sectOrPara">
    <group>
      <oneOrMore>
        <choice>
          <ref name="element.section"/>
          <ref name="element.para"/>
        </choice>
      </oneOrMore>
    </group>
  </define>
</grammar>

<?xml version="1.0" encoding="UTF-8"?>
<text xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:noNamespaceSchemaLocation="text.xsd" author="maik">
  <title>A simple title</title>
  <section>
    <title>A section title</title>
    <para id="p1">Introductory para</para>
    <section>
      <title>A subsection title</title>
      <para>Some text with a reference: <xref href="p1"/>.</para>
    </section>
  </section>
</text>

Determinism, Algorithms and Local Ambiguities

In this section we will review the concept of determinism, as opposed to local ambiguity of a grammar. As introductory issue, we show that determinism does not only depend on the grammar we use, but also on the algorithm. In regular tree languages, there can be no one-dimensional concept of determinism, as there is for regular string languages. Note that this is more than a metaphor, since we can perceive of regular string languages as one-dimensional structures; in order to talk about trees or the strings formed by their leaves, we need at least two dimensions (see Rogers, 2003). In the remainder, we will show how different grammar types provide determinism for all, some particular class of, or no algorithms.

Deterministic Content Models

Firstly, we consider the concept of deterministic content models. This draws on the notion of deterministic (or 1-unambiguous) regular expressions (DREs), thoroughly surveyed by Brüggemann-Klein and Wood, 1997^[5]. Assume we have a string s which is denoted by some regular expression E. Assume furthermore we build our expressions with letters from an alphabet Π, which is identical to the alphabet Σ, except for the fact that we have additional indices for the letters (taken here from the set of natural numbers). If we build an expression from Π, we have to make sure that every index must occur at most once in it. Constructors for regular expressions are as usual, and indices are passed on to the letters of the strings the expression denotes. We say that a letter in s instantiates a letter in E, if the following holds:

Definition 7 A letter a_i in s instantiates a letter a_j from E, if i = j.

The index ensures that for every string an expression denotes, there is a unique surjective mapping from letters in s to letters in E. We now define a mapping ♮ on strings over Π to strings over Σ, such that ♮(x_i):= x, ♮(xs):=♮(x)♮(s), where s is a string and x a letter (the first of the string). This homomorphism simply deletes the indices and leaves anything else untouched. Note that for a unique string ♮s, and a given expression E, there might be several s ∈ E, such that their mapping under ♮ is identical. In this case we say that a letter in s might instantiate several letters in E. A deterministic regular expression over Π is then defined as follows:

Definition 8 E is deterministic or one-unambiguous, if for all strings u, v, w over Π, and all letters x, y in Π, the following holds: if uxv and uyw ∈ L(E), and x ≠ y, then also ♮ x ≠ ♮ y.

This means that we can skip the indices, and we still know which letter in E is instantiated by any letter in s, simply from knowing its left context. Formally, this means that the mapping ♮ is reversible. A regular language is deterministic if it is denoted by a deterministic regular expression. A simple example of a non-deterministic expression is the expression a*b*a*, as we can easily check for the string a, which might be the instantiation of either of the two as.

As a consequence for processing, quite informally, we can state that reading s ∈ L(E) from the left to the right, where E is a DRE, at any point in s, we know at which point in E we find ourselves. In automata theory, DREs correspond to deterministic Glushkov automata.

There is however a problem if we apply this concept to content models in regular tree grammars: in regular expressions, we can see from a letter in the string which type of letter in the expression it instantiates (thus, we have a unique letter in Σ, though not in Π). We can thus deduce from a letter in the string a letter in the expression, though not a letter instantiation, if the expression is not deterministic. We cannot, however, deduce from a given tree node label a unique type of nonterminal: if we have competing rules, different nonterminals introduce identical labels; and we still have to keep them apart. Thus, if the content model of nonterminals itself is deterministic, this is of little use if we cannot infer from a given label the unique nonterminal it belongs to.

By way of example, consider the following grammar rule:

A → a(ABC|CBA)

Its content model is surely deterministic. However, if A and C are competing rules (have identical labels), this is of little use. We have to check each subtree until we have its unique interpretation. This means, in the worst case, we have to check both subtrees (as we will see, this is the case in which the trees generated by A (C) form a subset of the trees generated by C (A)).

The obvious reason for the fact that this concept of determinism comes short is that it originates in one-dimensional strings. As our trees are two dimensional, we can define determinism only with respect to directions in which our analysis proceeds. The main difference is, of course, the one between top-down and bottom-up processing. In this paper we will not consider the difference between depth-first and breadth-first parsing, though this is surely worthwhile.

In the next subsection, we will reformulate and complete the Murata hierarchy in a way, that makes clear which kind of determinism is facilitated by which kind of grammar. In the sequel, we will disregard the one-dimensional problem of non-deterministic content models, since they have been thoroughly analyzed, and we have nothing to add (see Brüggemann-Klein and Wood, 1997). At this point, our interest is the second dimension: importantly, this means that talking about determinism, we implicitly always add: provided that content models are deterministic in the above sense. We thus exclude all problems which may arise from regular expressions.

The Murata Hierarchy as Hierarchy of Locality Conditions

As our main concern will be the formal properties of the grammar types, as they affect processing, we will firstly reformulate the hierarchy. This reformulation aims at making clear which information we need in order to uniquely interpret a local node or subtree.

Restrained Competition Grammars and Variants

In this section we will scrutinize formal properties of the different types of restrained competition grammars. We will show which kind of languages cannot be generated by RCGs; we will prove that there are GRCGs which are ambiguous, and that for every language which can be generated by an RTG, there is a GRCG which generates the same language. Finally, we will show that URCGs do not have these properties, are properly included within GRCGs and properly include RCGs.

The type of languages we cannot generate with RCGs is quickly described as follows: all grammars, where a single content model contains competing nonterminals, which can be uniquely distinguished only from their left (right, respectively) context, are not RCGs. Consequently, we cannot generate sets of trees, where a certain node has different subtrees depending on its right siblings. If we want to get rid if this asymmetry, and allow for GRCGs, where competing nonterminals in a single content model are uniquely determined by their left or right context, we run into problems:

Theorem 6 There are GRCGs which are ambiguous.

For proof, consider the following rule: S → a(AB|BA). Suppose, A and B are competing nonterminals; suppose furthermore, that there is some overlapping between A and B; i.e., the nonterminals generate overlapping sets of trees. In particular, we may assume that the trees generated by A form a subset of the trees generated by B. For example, A and B generate identical trees up to depth n; B in addition generates a tree of depth n+1. In this case, the trees of the language have the root a, with two symmetrical sets of subtrees up to depth n, and possibly one subtree with depth n+1. It is easily seen that now it is impossible to merge A and B, for then we would be incapable of expressing the condition that at most one subtree has depth n+1. However, for the trees, where the subtrees introduced by A and B have depth at most n, there is necessarily more than one analysis. The grammar we have described so far is, however, a GRCG, because neither A nor B occur in identical contexts (though in similar contexts, remember the preceding section).

Theorem 7 For every language which can be generated by an RTG, there is a GRCG which generates the same language.

To proof this theorem, we describe a simple procedure to convert any RTG into a GRCG, which generates the same language. We define competing sequences of length n of nonterminals as follows: two sequences of nonterminals compete, if for all n, the nth nonterminal of one sequence competes with the nth nonterminal of the other sequence. We have to assume a content model r which is not GRCG conform. Therefore, there have to be two competing nonterminals or competing sequences of nonterminals A and B in r, such that for possibly empty sequences of nonterminals Γ and Δ, (Γ A Δ) and (Γ B Δ) match with r.

Given this, we can be sure, that in the instantiations of r, which violate the GRCG condition, A and B occur in exactly the same global tree contexts. By global tree context we here mean that a tree with a governing the subtrees generated by A is part of the language iff a also governs the set of subtrees generated by B. Since this is the case, we can simply merge the two nonterminals to a new one, C, which is the union of the former two. This new nonterminal substitutes all instantiations of A and B, which occur in the same global tree context. This, by definition, are the instantiations which violate the GRCG condition. This we can apply to all nonterminals which violate the GRCG condition. The only thing we have to take care of is that we apply this only to those instantiations of the content models where two competing nonterminals match equally (this might force us to change some regular expressions). We do not show an exact algorithm at this point, since it is clear that an equivalent GRCG exist, and the details of the construction are of no practical interest at this point.

We now show that there is a hierarchy of proper inclusion RCG ⊂ URCG ⊂ GRCG. To show that RCG ⊂ URCG, consider the following: every rule which is admitted by an RCG is also admitted by a URCG, because if competing nonterminals in the same content model have a unique prefix, a fortiori they also have a unique context (we have already shown that a unique prefix of nonterminals is paramount to a unique prefix of labels/siblings, by induction). Above, we have already shown that for an RCG it is impossible to generate languages as the following, which is a URCG.

S → a(AC|BD)
A → b(C)
B → b(D)
C → c(ε)
D → d(ε)

This concludes the first part; the second part will be a corollary of the next section: We will show that some languages are inherently ambiguous, that is, there is no unambiguous grammar for them. By Theorem 7 we know that we can generate these languages with GRCGs, but URCGs cannot:

Proposition 1 A URCG cannot be ambiguous.

This is easy to see: an ambiguous grammar assigns two different sequences of nonterminals to the daughters of one node (since root nodes are unambiguous): Then however, there must be at least two competing nonterminals which occur in the same content model in similar contexts, which, by definition, is impossible.

Inherently Ambiguous Languages

As a corollary, we can show that there are regular tree languages, for which there is no unambiguous grammar. There are sets of trees, which are generated by an ambiguous GRCG, but by no URCG. We will call these languages inherently ambiguous.

Theorem 8 Some regular tree languages are inherently ambiguous.

This can be seen easily, if we spell out a grammar which we described in the above subsection. We will then show that there is now way to write an unambiguous grammar which generates the same language.

S → r(AB|BA)
A → a(C)
B → a(D)
C → b(ε)
D → b(ε|E)
E → c(ε)

There is no way to merge A and B, since they generate different sets of subtrees (we can write L(A)≠L(B)); but since they overlap (L(A)∩ L(B)≠ ∅), there is no way to have a unique interpretation in the cases where the subtrees generated by the nonterminals are identical. There will always be two ways to generate trees in this case.

We can, furthermore, precisely state the conditions, under which a regular tree language is ambiguous. To this end, however, we need to introduce some notation. We now for simplicity write trees as terms: a tree with root a and daughters b and c is denoted as a(b,c), etc. As a next step, we define a context as the position, where certain subtrees occur within trees of a language.

Definition 9 A context C is a tree-term with exactly one variable. We say that a set of subtrees α occurs in a context C in a language L, if the following holds: We can instantiate the variable of C with any tree from α, and the resulting tree is in L.

Note that sets of subtrees correspond to nonterminals, when we speak of languages rather than grammars. In the sequel, for simplicity we will use lower case Greek variables equally for sets of subtrees as for ordered sequences of sets of subtrees. The definition of a context is easily accommodated to sequences. A set of sequences of trees of length n consists of ordered tuples of trees of length n, of the form (t₀,...,t_n-1). Sets of subtrees are then simply sets of one-tuples. Importantly, we will not provide a proof for the following proposition, and leave it open as a conjecture. However, we will sketch the argument. We now make the following conjecture:

Conjecture 1 A tree-language is inherently ambiguous iff at least one node fulfills all of the following conditions:

We need to have one node with an arbitrary label a, with at least two (sequences of) sets of subtrees α and β, such that

Due to space restrictions, we leave the prove for this conjecture open here; this reminds however of a theorem in Odgen, 1968 for string languages. But we will give some rather informal discussion of the points in the next section. It is not hard to see that this is merely a generalization of the cases we have been described above. As we will see, we can derive some useful facts from these properties of ambiguous languages, even without a general proof: we can show that we can construe grammars for languages which do not fulfill one of the conditions, and, moreover, which type of grammars we can construe.

Unambiguous Languages

Theorem 9 From the grammar types sketched so far, there is no type which generates all and only the RTLs that are not inherently ambiguous.

We will demonstrate this going through the three conditions mentioned in the preceding section, and look which unambiguous grammar we can construe if one condition is not met. This is to be read as follows: if one condition is not met, then it means, that from all nodes of the tree language, there might be any one which meets the ones not in question, but none which meets the one currently under consideration.

This shows that we still have not solved the problem to define a canonical grammar type which generates all and only the unambiguous languages, since there are languages which are generated by USGs, but no other canonical class which does not allow any ambiguity type, and languages which are generated by URCGs and no other such type. So far, we are still lacking a characterization of the unambiguous languages in terms of grammar rules.