Garbage* in, garbage out.

(Click in the rectangle to start this animation.) N.B. what we are producing are strings, not structures. No memory.

(Click in the rectangle to start this animation.) Now we have some memory, but it's not very tractable.

Origin: pragmatic, not theoretical; partial post hoc alignment with formal language theory.

Formal specification of validity conditions → automated validation.

Er, ah, partial formal specification of validity conditions → partial automated validation.

Distinction between

• document type definition (DTD) and
• “set of effective formal declarations”

→ division of labor.

Document grammars may have several uses:

• in the struggle against dirty data
• as documentation of a contract between data provider and data consumer
• as documentation of the content of data flows
• as specification of client/server protocols

Limericks and canzone:

<!ELEMENT poem (haiku | limerick | canzone) >

<!ELEMENT haiku    (l, l, l) >
<!ELEMENT limerick (trimeter, trimeter, 
                    dimeter, dimeter, 
                    trimeter)>
<!ELEMENT trimeter (#PCDATA)>
<!ELEMENT dimeter  (#PCDATA)>

<!ELEMENT canzone   (stanza+) >
<!ELEMENT stanza    (aufgesang, abgesang) >
<!ELEMENT aufgesang (stollen, stollen) >
<!ELEMENT stollen   (l+) >
<!ELEMENT abgesang  (l+) >
<!ELEMENT l         (#PCDATA) >

A W3C* Recommendation*.

Design space:

In version 1 of this schema, we imitate the DTD slavishly.

At the outer level is a schema element:

<xsd:schema 
 xmlns:xsd="http://www.w3.org/2001/XMLSchema">
 <!--* element declarations go here *-->
</xsd:schema>

N.B. the schema does not identify a document-root element / start symbol.

 <xsd:element name="l">
  <xsd:complexType mixed="true">
   <xsd:sequence>
   </xsd:sequence>
  </xsd:complexType>
 </xsd:element>

or

 <xsd:element name="l" type="xsd:string"/>

Let's generalize from

 <xsd:element name="l" type="xsd:string"/>

Can we do that for every element type?

N.B. four usages for the term type

• element type (vs. element, element instance)
• data type
  • simple type (lexical form has no markup)
  • complex type (can have element children)

In the example, l may be thought of as an accessor.

Named types can be used to capture commonalities:

 <xsd:complexType name="lines">
  <xsd:sequence minOccurs="1" 
                maxOccurs="unbounded">
   <xsd:element ref="l"/>
  </xsd:sequence>
 </xsd:complexType>

 <xsd:element name="abgesang" type="lines">
 <xsd:element name="stollen" type="lines">

... or just to provide a name for a type:

 <xsd:complexType name="canzoneform">
  <xsd:sequence>
   <xsd:element ref="aufgesang"/>
   <xsd:element ref="abgesang"/>
  </xsd:sequence>
 </xsd:complexType>
 <xsd:complexType name="aufgesang">
  <xsd:sequence>
   <xsd:element ref="stollen"/>
   <xsd:element ref="stollen"/>
  </xsd:sequence>
 </xsd:complexType>

 <xsd:element name="stanza" type="canzoneform"/>
 <xsd:element name="aufgesang" type="aufgesang"/>

We can hide things using anonymous local types:

 <xsd:element name="canzone">
  <xsd:complexType>
   <xsd:sequence maxOccurs="unbounded">
    <xsd:element name="stanza">
     <xsd:complexType>
      <xsd:sequence>
       <xsd:element name="aufgesang">
        <xsd:complexType>
         <xsd:sequence>
          <xsd:element name="stollen" type="lines"/>
          <xsd:element name="stollen" type="lines"/>
         </xsd:sequence>
        </xsd:complexType>
       </xsd:element>
       <xsd:element name="abgesang" type="lines"/>
      </xsd:sequence>
     </xsd:complexType>
    </xsd:element>
   </xsd:sequence>
  </xsd:complexType>
 </xsd:element>

Note nested declarations and definitions.

Extensional:

• a set of values V
• a set of lexical forms L
• a mapping from L to V

Intensional:

• a base mapping L → V
• a set of fundamental facets:
  • equality (identity)
  • order (partial, total, none)
  • boundedness
  • cardinality
  • numeric
• a set of constraining facets:
  • length, minLength, maxLength
  • pattern (constrains lexical space)
  • enumeration
  • whiteSpace
  • maxInclusive, maxExclusive, minInclusive, minExclusive
  • totalDigits, fractionDigits

It turns out to be hard to model stepwise refinement of types:

• restriction (preserves subset semantics)
• extension (preserves prefix semantics)

Existing document systems turn out to have a very different model of class systems and inheritance.

• inheritance of attributes
• inheritance of locations

XML Schema models these with

• inheritance (by extension or restriction)
• substitution groups

Some (unpleasant) facts of life:

• Namespaces are not incompatible with document grammars
• — but they don't play well with DTDs.
• Namespaces allow us to distinguish mine from not-mine.
• Namespaces do not provide universal names.
• The namespace : language relation is 1:n.
• The language : grammar relation is 1:n.
• Therefore, the namespace : schema relation is 1:n.

Live with it.

We distinguish:

• schema documents (with single target namespace)
• schemas (sets of abstract components)

Schema composition operations:

• import
• include
• include with override / redefine

XML Schema makes it possible to write modular document type definitions:

• late collection of schema components
• namespace-aware name matching, validation
• white-box wildcards (lax / opportunistic)
• black-box wildcards (skip)

Consider the HTML input element:

• legal only in p and similar elements
• legal only within form elements

SGML DTDs have partial solutions:

• inclusion exceptions
• content models

Fundamentally, we trade verbosity for context-sensitivity:

 <xsd:element name="div" type="div-type"/>
 <xsd:element name="div" type="div-in-form-type"/>

 <xsd:element name="p" type="p-type"/>
 <xsd:element name="p" type="p-in-form-type"/>

 <xsd:element name="ul" type="ul-type"/>
 <xsd:element name="ul" type="ul-in-form-type"/>

 <xsd:element name="li" type="li-type"/>
 <xsd:element name="li" type="li-in-form-type"/>

One bit of context information = double the size of grammar.

Cf. van Wijngaarden grammars (infinite size, unlimited of context sensitivity).

The determinism rule remains controversial:

• LL(1) guarantees may help implementors
• All regular languages have a deterministic FSA;
• ... but not necessarily a deterministic regular expression!
• Implications for closure under union, intersection.
• Implications for subsumption tests.
• Implications for interoperability, single-pass processing.

• XML notation*
• Linking document and schema
  • namespace name
  • schemaLocation hint
• Hooks for schema annotation: the annotation element

XML-Schema validation: infoset → infoset.

• additions, no changes
• type assignment information
• validation-attempted information (strict, lax, skip)
• validation-outcome information

For more information: http://www.w3.org/XML