Applications of Brzozowski derivatives to XML Schema processing

Notation

Brzozowski worked with a regular-expression notation which differs interestingly both from standard regular expressions and from XSD content model notation. So to apply the notion of derivatives to XSD content models, we need to extend Brzozowski's rules. This is easily done.

For concision, I will use the following notation as a shorthand instead of writing content models in the transfer syntax defined by the XML Schema specification [W3C 2001b]. A content model expression is one of the following:

• ε (in the XML Schema transfer syntax, this can be written <xsd:sequence/>)
• ∅ (in the transfer syntax: <xsd:choice/>)
• an expanded name, in the sense of the XML Namespaces specification [W3C 2004] (in the transfer syntax, <xsd:element ref = "QName"/> or <xsd:element name = "NCName"> ... </xsd:element>). For convenience, we will allow ourselves to write expanded names as qualified names (QNames) whenever the bindings of namespace prefixes are clear. The symbol e will sometimes be used as a dummy name.
• wc(KW, NS), where KW is in {strict, lax, skip} and NS is either the keyword ##any or a list of namespace names or ε (in the transfer syntax, <xsd:any namespace = "NS" processContents = "KW"/>); I'll use ε to denote the absence of a namespace name; since the empty string can never be used as a namespace name, this leads to no ambiguities; the transfer syntax uses the keyword ##local.
• wc(KW, not(NS)), with KW as above and NS either a namespace name or ε (in the transfer syntax, <xsd:any namespace = "##other" processContents = "KW"/>).
• F | G, where F and G are each content-model expressions (in the transfer syntax, <xsd:choice> F G </xsd:choice>).
• F, G, where F and G are each content-model expressions (in the transfer syntax, <xsd:sequence> F G </xsd:sequence>).
• F{n, m}, where F is a content-model expression (in the content model, this is minOccurs = "n" maxOccurs = "m" on the element representing F).

These expressions denote regular sets of sequences of XML elements as follows:

• ε denotes the set consisting solely of the empty sequence.²
• ∅ denotes the empty set.
• An expanded name e denotes an element (or, strictly speaking, a sequence of length one whose sole member is an element) whose generic identifier (written as a QName) maps to e.³
• wc(KW, NS) (wc for ‘wildcard’) denotes a sequence whose sole member is an element in namespace NS.
• wc(KW, not(NS)) denotes a sequence whose sole member is an element not in namespace NS.
• F | G denotes the union of the set denoted by F and that denoted by G.
• F, G denotes the set of sequences fg where f ∈ F and g ∈ G.
• F{n, m} denotes the set of sequences formed by concatenating at least n and at most m occurrences of members of the set denoted by F, where F is a content-model expression, n is a non-negative integer, and m is either a positive integer or the symbol unbounded.

In examples, the notations familiar from SGML and XML content models will occasionally be used: for some expression E, E* ≡ E{0, unbounded}, E+ ≡ E{1, unbounded}, E? ≡ E{0, 1}.

Content models are either content-model expressions or “all”-expressions. An “all”-expression is:

• F&G, where F and G are each either simple content-model expressions or are themselves “all”-expressions.

• F&G, denotes the set of sequences formed by concatenating, in any order, exactly one member of each set denoted by the simple content-model expressions in F and G.

Some examples may help make things clear.

• The content model expression “a, b, c{1, unbounded}” matches any of the following sequences of elements:
  • a b c
  • a b c c
  • a b c c c
  etc.
• The content model expression “a, b, (c{1, unbounded} | (d){2, 4})” matches any of the sequences above, as well as any of:
  • a b d d
  • a b d d d
  • a b d d d d
• The content model expression “a & b{0, 1} & c” matches any of the sequences
  • a c
  • c a
  • a b c
  • a c b
  • b a c
  • b c a
  • c a b
  • c b a
• The content model expression “ε” matches the empty sequence.
• The content model expression “∅” matches no sequences at all.

Note that while in XSD all of the operators | and , and & are n-ary (i.e. they take an arbitrary number of arguments), we can treat them without loss of generality as binary operators, all of which obey the associative law. That is, for any content model expressions E, F, and G, we have

and

and

The last set of equations requires some discussion. They will seem foreign to those used to the SGML & operator, which is not associative, but natural to those accustomed to working with the interleave operator of Relax NG and some recent discussions of content models by computer scientists. In SGML, the expression (a & (b & c)) is not at all the same as ((a & b) & c): the former requires an a to appear at the beginning or end of the sequence, while the latter requires c to appear at the beginning or end, so that a c b is accepted by the first expression, but not the second. In RelaxNG, the two expressions are equivalent. In XSD, the issue does not arise, since XSD does not allow all-expressions to nest within all-expressions and so does not need to specify either the associative or the non-associative interpretation.

The & operators of SGML and RelaxNG also differ in another way: as suggested by the term interleave, RelaxNG allows sub-parts of the left- and right-hand expressions to be interleaved. In RelaxNG, for example, the expression (a, b) & (d, e) accepts the sequence a d b e, as well as any other in which both a occurs before b and c occurs before d, and nothing else occurs. In SGML, the expression accepts only the two sequences “a b d e” and “d e a b”. Here, too, XSD restricts the operator in such a way that the XSD operator can be interpreted either way: in XSD, all arguments of the & operator must be simple content-model expressions, so that the question of interleaving sub-parts of the matching strings does not arise.

Let it suffice for now to observe that the validation semantics assigned to all-expressions below have been formulated in such a way that the binary &-operator to which we translate XSD all-expressions does obey the associative law.

Nullability

It is useful to know, for an expression E, whether ε is in L(E) (i.e. whether the language accepted by E includes the empty string). Following Brüggeman-Klein [Brüggemann-Klein 1993a], I will say that if ε is in L(E), then E is nullable, and define the predicate ν(E) which is true if and only if E is nullable.

The definition of nullable for content-model expressions is:

• ν(ε) = true
• ν(∅) = false
• ν(e) = false for any expanded name e
• ν(wc(KW, NS)) = false for any value of KW and NS
• ν(F | G) = ν(F) ∨ ν(G)
• ν(F, G) = ν(F) ∧ ν(G)
• ν(F{n, m}) = (n = 0) ∨ ν(F)
• ν(F & G) = ν(F) ∧ ν(G)

Some algebraic manipulations will become simpler if we define a related function, which following Brzozowski I call δ. For all regular expressions E,

• δ(E) = ε if and only if L(E) includes ε.
• Otherwise, δ(E) = ∅

Construction of derivatives

First we define the derivative of an expression E with respect to a single expanded name x. This we specify to be identical by definition to the derivative with respect to a sequence consisting just of one element whose expanded name is x.

• D_x ε = ∅
• D_x ∅ = ∅
• D_x e = ε if x = e
• D_x e = ∅ if e is an expanded name, and (x ≠ e)
• D_x wc(KW, NS) = ε if x is in namespace NS, else ∅
• D_x wc(KW, not(NS)) = ∅ if x is in namespace NS, else ε
• D_x (F | G) = (D_x F) | (D_x G)
• D_x (F, G) = ((D_x F), G) | (D_x G) if F is nullable, else (D_x F), G⁴
• D_x F{n,m} = (D_x F), F{--n, --m} if F is not nullable or if n = 0 and m = unbounded, else (D_x F), F{--n, --m} | (D_x F{--n, --m}). (See definition of -- operator below.)
• D_x (F & G) = ((D_x F) & G) | (F & (D_x G))

For positive integers, the -- operator decrements, but it respects special cases: --k = k - 1 for integer k > 0, but --0 = 0, and --unbounded = unbounded.⁵

To calculate the derivative of E with respect to a sequence x₁, x₂, x₃, ..., x_n, we first take the derivative with respect to x₁, then the derivative of that expression with respect to x₂, and so on until we are at the end of the sequence. Algebraically,

Simplification of expressions

The following identities are useful. For any expressions E, F, and G,

• E | E = E
• E | F = F | E
• (E | F) | G = E | (F | G)
• ε, E = E, ε = E
• ε & E = E & ε = E
• ∅ | E = E | ∅ = E
• ∅, E = E, ∅ = ∅
• ∅ & E = E & ∅ = ∅

In what follows, we'll (silently) make use of these identities to simplify expressions generated by taking derivatives.

Characteristic derivatives

Brzozowski proves that every regular expression is guaranteed to have a finite number of distinct (i.e. non-equivalent) derivatives. The set of distinct derivatives of E with respect to the strings in Σ* (for some input alphabet Σ) is called the characteristic derivatives of E.

Brzozowski also defines a test of similarity for regular expressions: expressions are similar if they can be transformed into each other using only the first three identities listed in section 3-4. Since in practice the detection of equivalence may be expensive, it is encouraging to note that Brzozowski also proves that every regular expression is guaranteed to have a finite number of dissimilar derivatives. The consequence is that even if we fail to detect all equivalences among the derivatives of an expression, we can still avoid having the number of characteristic derivatives grow without bound.

One complication should be addressed here: like all standard work on regular languages, Brzozowski assumes that the input alphabet Σ is finite. Content models, however, are regular expressions over an infinite set, namely XML element types (or element type names). The following discussion silently makes the usual adjustment: for content models without wildcards, it suffices to assume an alphabet including all the names used in the content model, plus one name which matches nothing in the content model. Since in the absence of wildcards all non-matching names behave the same way, the single non-matching name successfully represents the infinite set of possible inputs which match nothing in the content model. When wildcards are present, it suffices to include one otherwise unknown name in each namespace mentioned in any wildcard, plus one name in a namespace unmentioned in any wildcard. In this way we can work with finite input alphabets which correctly stand in for the infinite input alphabet provided by XML.

Validation

We can use derivatives to validate without ever constructing anything recognizable as an automaton: for content model E and sequence s, E accepts s if and only if ν(D_s E).⁶

For strongly deterministic expressions, the time it takes to calculate the derivative of E with respect to a single input symbol is at most linear in the size of E, and the derivative is never larger than E.⁷ This means that overall, validation of a sequence will be at worst linear in the size of the sequence. (Note that formal proofs of these claims remain a task for future work.)

For example, let us consider the strongly deterministic content model E =

( (script | style | meta)*,
  ( (title, (script | style | meta)*, (base, (script | style | meta)*)?)
    |
    (base, (script | style | meta)*, (title, (script | style | meta)*))
  )
)

1. Find D_meta E.
   This proves to be E again (which is intuitively plausible: any number of meta elements are allowed at the beginning of the sequence).⁸
2. Now find D_title E.
   This proves to be ((script | style | meta)*, (base, (script | style | meta)*)?).⁹
3. Now find D_style ((script | style | meta)*, (base, (script | style | meta)*)?).
   This is (base, (script | style | meta)*)?¹⁰
   Since ν((base, (script | style | meta)*)?) is true, the sequence is valid against the content model.

For non-strongly-deterministic expressions, the derivative may be larger than the original expression and will take the form of a disjunction. If the expression is weakly deterministic, then the number of disjuncts will correspond to the number of states the (non-strongly-deterministic) Glushkov automaton could be in at the given state in the parse.

For example, consider the content model E = (e{1,5}, b{0,2}){1,5}. A straightforward calculation of the derivatives shows how the second and later occurrences of “e” in an input string cause more and more growth in the size of the derivative:

E =

(e{1,5}, b{0,1}){1,5}

D_e E =

e{0,4}, b?, (e{1,5}, b?){0,4}

D_ee E =

  e{0,3}, b?, (e{1,5}, b?){0,4} 
| e{0,4}, b?, (e{1,5}, b?){0,3}

D_eee E =

  e{0,2}, b?, (e{1,5}, b?){0,4}
| e{0,4}, b?, (e{1,5}, b?){0,3}
| e{0,3}, b?, (e{1,5}, b?){0,3} 
| e{0,4}, b?, (e{1,5}, b?){0,2}

D_eeeb E =

  (e{1,5}, b?){0,4} 
| (e{1,5}, b?){0,3} 
| (e{1,5}, b?){0,3} 
| (e{1,5}, b?){0,2}'

D_eeee E =

  e?, b?, (e{1,5}, b?){0,4} 
| e{0,4}, b?, (e{1,5}, b?){0,3} 
| e{0,3}, b?, (e{1,5}, b?){0,3} 
| e{0,4}, b?, (e{1,5}, b?){0,2} 
| e{0,2}, b?, (e{1,5}, b?){0,3} 
| e{0,4}, b?, (e{1,5}, b?){0,2} 
| e{0,3}, b?, (e{1,5}, b?){0,2} 
| e{0,4}, b?, (e{1,5}, b?)?

Unique Particle Attribution

SGML DTDs, XML 1.0 DTDs, and XSD 1.0 all share a rule which restricts the forms of regular expressions legal in content models, in order to ensure that they do not require unbounded lookahead. ISO 8879 requires that content models be “unambiguous”. The sense assigned to ambiguity is somewhat broader than the sense usual in formal language study: the expression a?, a is ambiguous in the SGML sense, because when a parser is confronted with a sequence beginning with an a, lookahead is required to know whether it matches the first a in the expression, or the second. It is not ambiguous in the usual formal sense: for any word in the language, there is only one parse tree. In part to avoid the confusion caused by this unusual usage of the term ambiguity, the XML 1.0 spec requires instead that content models be deterministic. Determinism, however, may be defined in either of two ways, weak or strong. To avoid the confusion caused by the two flavors of determinism, XSD 1.0, in turn, imposes what it calls the Unique Particle Attribution constraint. All three of these names denote essentially the same requirement: that it be possible, without lookahead in the document instance, to know which token (or particle) in a content model is matched by a token in the document instance, and that there be at most one such token. This is what Brüggemann-Klein calls weak determinism, as opposed to strong determinism, which additionally requires that every repetition of a token be licensed by at most one occurrence indicator in the expression.¹¹

Previous formulations of this constraint have either provided an algorithm translating expressions into automata, required that this translation be performed, and appealed to properties of the resulting automata (so Brüggemann-Klein and Wood in [Brüggemann-Klein 1993a] and [Brüggemann-Klein/Wood 1998]), or else they have refrained from requiring such a translation, but then found themselves unable to specify precisely what the constraint is, relying instead on nudges and winks and hopes that the reader understands what is meant (so ISO 8879 [ISO 1986] and the XML specification [W3C 2004]).¹² Using Brzozowski derivatives, however, the UPA constraint of XSD 1.0 can be specified constructively and precisely, without reference to the corresponding automata.¹³ Two approaches offer themselves.

Weakened wildcards

In discussions of XSD and the Unique Particle Attribution constraint, various alternative validation behaviors have occasionally been proposed; one of the most popular ideas is ‘weakened wildcards’. This is a weakened form of the Unique Particle Attribution constraint, which allows content models in which both an extended name and a wildcard can match an input element, with the proviso that in cases of such competition, it is the extended name, not the wildcard, which is used to match the input element. Competition between element tokens or between wildcards is still prohibited.

Either of the two approaches to the UPA constraint described above can be extended to handle weakened wildcards.

The idet predicate can be specialized in the obvious way into two predicates, edet (which is true just in case there is at most one element particle in the content model which can match the input symbol) and wdet (true if there is at most one matching wildcard). The weakened form of the constraint is then:

• For all symbols x in the input alphabet, and for all characteristic derivatives F of the original content model, edet(x,F) and wdet(x,F) must both be true.

The c function can similarly be specialized to make functions that count just element tokens (ecount) or just wildcard tokens (wcount) which can match an initial x. The weak wildcard rule then says that for every member F of the characteristic derivatives of E and every symbol x in the input alphabet, it must be the case both that ecount(x,F) ≤ 1 and that wcount(x,F) ≤ 1.

Checking subsumption of content models

This topic has already been treated, using different formalisms, by Henry Thompson and Matthew Fuchs [Thompson/Tobin 2003], [Fuchs/Brown 2003]. Brzozowski derivatives provide a different way of considering the problem, which seems in some respects more convenient and concise.

Section 4-4-1 below extends the notation described above in section 3-1, adding (as Brzozowski does) the operators 'and' and 'not' to the expression language and showing how to take their derivatives. They are redundant and do not extend the expressive power of the language, but they are convenient to have when considering subsumption.

Section 4-4-2 expresses the subsumption test in several ways using derivatives, notably:

(N.B. this definition of subsumption corresponds to shallow local validation, not to deep validation.)

Section 4-4-3 describes a relatively simple way to test subsumption: find the set of characteristic derivatives of (R and ~B) and test each one for nullability. Some speculations about complexity are also included.

Section 4-4-4 works in detail through some examples.

Section 4-4-5 is a series of proofs showing that the various formulations of subsumption offered in section 4-4-2 are in fact equivalent.

(c, d, e, f) 
        and 
        ~( ( (c, d, ((b, c, d)?), (e?), 
             ((((b, c, d){0,5}), (e?)){0,3}))
           | (c, d, ((b, c, d){0,4}), (e?), 
             ((((b, c, d){0,5}), (e?)){0,2}))
           | (c, d, ((b, c, d){0,4}), (e?), 
             ((((b, c, d){0,5}), (e?))?))
           | (c, d, ((b, c, d){0,4}), (e?))
           | (c, d, ((b, c, d){0,3}), (e?), 
             ((((b, c, d){0,5}), (e?)){0,2}))
           | (c, d, ((b, c, d){0,3}), (e?), 
             ((((b, c, d){0,5}), (e?))?))
           | (c, d, ((b, c, d){0,3}), (e?))
           | (c, d, ((b, c, d){0,2}), (e?), 
             ((((b, c, d){0,5}), (e?)){0,2}))
           | (c, d, ((b, c, d){0,2}), (e?), 
             ((((b, c, d){0,5}), (e?))?))
           | (c, d, ((b, c, d){0,2}), (e?))
           | (c, d, ((b, c, d)?), (e?), 
             ((((b, c, d){0,5}), (e?)){0,2}))
           | (c, d, ((b, c, d)?), (e?), 
             ((((b, c, d){0,5}), (e?))?))
           | (c, d, ((b, c, d)?), (e?))
         ), f)