reactos/lib/libxml2/test/relaxng/spec_0.xml

   1 <?xml version="1.0" encoding="iso-8859-1"?>
   2 <!DOCTYPE article [
   3 <!-- ELEMENT declarations work around MSXML bug. -->
   4 <!ELEMENT section ANY>
   5 <!ATTLIST section id ID #IMPLIED>
   6 <!ELEMENT appendix ANY>
   7 <!ATTLIST appendix id ID #IMPLIED>
   8 <!ELEMENT bibliomixed ANY>
   9 <!ATTLIST bibliomixed id ID #IMPLIED>
  10 ]>
  11 <article status="Committee Specification" xmlns:p="http://relaxng.org/ns/proofsystem">
  12
  13 <articleinfo>
  14 <releaseinfo>$Id: spec.xml,v 1.159 2001/12/02 12:12:12 jjc Exp $</releaseinfo>
  15 <title>RELAX NG Specification</title>
  16 <authorgroup>
  17 <editor>
  18   <firstname>James</firstname><surname>Clark</surname>
  19   <affiliation>
  20     <address><email>jjc@jclark.com</email></address>
  21   </affiliation>
  22 </editor>
  23 <editor>
  24   <surname>MURATA</surname><firstname>Makoto</firstname>
  25   <affiliation>
  26     <address><email>EB2M-MRT@asahi-net.or.jp</email></address>
  27   </affiliation>
  28 </editor>
  29 </authorgroup>
  30 <pubdate>3 December 2001</pubdate>
  31 <releaseinfo role="meta">
  32 $Id: spec.xml,v 1.159 2001/12/02 12:12:12 jjc Exp $
  33 </releaseinfo>
  34
  35 <copyright><year>2001</year><holder>OASIS</holder></copyright>
  36
  37 <legalnotice>
  38
  39 <para>Copyright &#169; The Organization for the Advancement of
  40 Structured Information Standards [OASIS] 2001. All Rights
  41 Reserved.</para>
  42
  43 <para>This document and translations of it may be copied and furnished
  44 to others, and derivative works that comment on or otherwise explain
  45 it or assist in its implementation may be prepared, copied, published
  46 and distributed, in whole or in part, without restriction of any kind,
  47 provided that the above copyright notice and this paragraph are
  48 included on all such copies and derivative works. However, this
  49 document itself may not be modified in any way, such as by removing
  50 the copyright notice or references to OASIS, except as needed for the
  51 purpose of developing OASIS specifications, in which case the
  52 procedures for copyrights defined in the OASIS Intellectual Property
  53 Rights document must be followed, or as required to translate it into
  54 languages other than English.</para>
  55
  56 <para>The limited permissions granted above are perpetual and will not
  57 be revoked by OASIS or its successors or assigns.</para>
  58
  59 <para>This document and the information contained herein is provided
  60 on an <quote>AS IS</quote> basis and OASIS DISCLAIMS ALL WARRANTIES,
  61 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE
  62 USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY
  63 IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR
  64 PURPOSE.</para>
  65
  66 </legalnotice>
  67
  68 <legalnotice role="status"><title>Status of this Document</title>
  69
  70 <para>This Committee Specification was approved for publication by the
  71 OASIS RELAX NG technical committee. It is a stable document which
  72 represents the consensus of the committee. Comments on this document
  73 may be sent to <ulink
  74 url="mailto:relax-ng-comment@lists.oasis-open.org"
  75 >relax-ng-comment@lists.oasis-open.org</ulink>.</para>
  76
  77 <para>A list of known errors in this document is available at <ulink
  78 url="http://www.oasis-open.org/committees/relax-ng/spec-20011203-errata.html"
  79 >http://www.oasis-open.org/committees/relax-ng/spec-20011203-errata.html</ulink
  80 >.</para>
  81
  82 </legalnotice>
  83
  84 <abstract>
  85 <para>This is the definitive specification of RELAX NG, a simple
  86 schema language for XML, based on <xref linkend="relax"/> and <xref
  87 linkend="trex"/>. A RELAX NG schema specifies a pattern for the
  88 structure and content of an XML document. A RELAX NG schema is itself
  89 an XML document.</para>
  90 </abstract>
  91
  92 <revhistory>
  93 <revision>
  94   <revnumber>Committee Specification</revnumber>
  95   <date>3 December 2001</date>
  96 </revision>
  97 <revision>
  98   <revnumber>Committee Specification</revnumber>
  99   <date>11 August 2001</date>
 100 </revision>
 101 </revhistory>
 102 </articleinfo>
 103
 104
 105 <section>
 106 <title>Introduction</title>
 107
 108 <para>This document specifies</para>
 109
 110 <itemizedlist>
 111
 112 <listitem><para>when an XML document is a correct RELAX NG
 113 schema</para></listitem>
 114
 115 <listitem><para>when an XML document is valid with respect to a
 116 correct RELAX NG schema</para></listitem>
 117
 118 </itemizedlist>
 119
 120 <para>An XML document that is being validated with respect to a RELAX NG
 121 schema is referred to as an instance.</para>
 122
 123 <para>The structure of this document is as follows.  <xref
 124 linkend="data-model"/> describes the data model, which is the
 125 abstraction of an XML document used throughout the rest of the
 126 document.  <xref linkend="full-syntax"/> describes the syntax of a
 127 RELAX NG schema; any correct RELAX NG schema must conform to this
 128 syntax.  <xref linkend="simplification"/> describes a sequence of
 129 transformations that are applied to simplify a RELAX NG schema;
 130 applying the transformations also involves checking certain
 131 restrictions that must be satisfied by a correct RELAX NG
 132 schema. <xref linkend="simple-syntax"/> describes the syntax that
 133 results from applying the transformations; this simple syntax is a
 134 subset of the full syntax.  <xref linkend="semantics"/> describes the
 135 semantics of a correct RELAX NG schema that uses the simple syntax;
 136 the semantics specify when an element is valid with respect to a RELAX
 137 NG schema.  <xref linkend="restriction"/> describes restrictions in
 138 terms of the simple syntax; a correct RELAX NG schema must be such
 139 that, after transformation into the simple form, it satisfies these
 140 restrictions. Finally, <xref linkend="conformance"/> describes
 141 conformance requirements for RELAX NG validators.</para>
 142
 143 <para>A tutorial is available separately (see <xref
 144 linkend="tutorial"/>).</para>
 145
 146 </section>
 147
 148 <section id="data-model">
 149 <title>Data model</title>
 150
 151 <para>RELAX NG deals with XML documents representing both schemas and
 152 instances through an abstract data model.  XML documents representing
 153 schemas and instances must be well-formed in conformance with <xref
 154 linkend="xml-rec"/> and must conform to the constraints of <xref
 155 linkend="xml-names"/>.</para>
 156
 157 <para>An XML document is represented by an element.  An element consists
 158 of</para>
 159
 160 <itemizedlist>
 161
 162 <listitem><para>a name</para></listitem>
 163
 164 <listitem><para>a context</para></listitem>
 165
 166 <listitem><para>a set of attributes</para></listitem>
 167
 168 <listitem><para>an ordered sequence of zero or more children; each
 169 child is either an element or a non-empty string; the sequence never contains
 170 two consecutive strings</para></listitem>
 171
 172 </itemizedlist>
 173
 174 <para>A name consists of</para>
 175
 176 <itemizedlist>
 177 <listitem><para>a string representing the namespace URI; the empty
 178 string has special significance, representing the absence of any
 179 namespace</para></listitem>
 180
 181 <listitem><para>a string representing the local name; this string matches the NCName
 182 production of <xref linkend="xml-names"/></para></listitem>
 183 </itemizedlist>
 184
 185 <para>A context consists of</para>
 186
 187 <itemizedlist>
 188 <listitem><para>a base URI</para></listitem>
 189 <listitem><para>a namespace map; this maps prefixes to namespace URIs,
 190 and also may specify a default namespace URI (as declared
 191 by the <literal>xmlns</literal> attribute)</para></listitem>
 192 </itemizedlist>
 193
 194 <para>An attribute consists of</para>
 195
 196 <itemizedlist>
 197 <listitem><para>a name</para></listitem>
 198 <listitem><para>a string representing the value</para></listitem>
 199 </itemizedlist>
 200
 201 <para>A string consists of a sequence of zero or more characters,
 202 where a character is as defined in <xref linkend="xml-rec"/>.</para>
 203
 204 <para>The element for an XML document is constructed from an instance
 205 of the <xref linkend="infoset"/> as follows.  We use the notation
 206 [<replaceable>x</replaceable>] to refer to the value of the
 207 <replaceable>x</replaceable> property of an information item. An
 208 element is constructed from a document information item by
 209 constructing an element from the [document element].  An element is
 210 constructed from an element information item by constructing the name
 211 from the [namespace name] and [local name], the context from the [base
 212 URI] and [in-scope namespaces], the attributes from the [attributes],
 213 and the children from the [children].  The attributes of an element
 214 are constructed from the unordered set of attribute information items
 215 by constructing an attribute for each attribute information item.  The
 216 children of an element are constructed from the list of child
 217 information items first by removing information items other than
 218 element information items and character information items, and then by
 219 constructing an element for each element information item in the list
 220 and a string for each maximal sequence of character information items.
 221 An attribute is constructed from an attribute information item by
 222 constructing the name from the [namespace name] and [local name], and
 223 the value from the [normalized value].  When constructing the name of
 224 an element or attribute from the [namespace name] and [local name], if
 225 the [namespace name] property is not present, then the name is
 226 constructed from an empty string and the [local name]. A string is
 227 constructed from a sequence of character information items by
 228 constructing a character from the [character code] of each character
 229 information item.</para>
 230
 231 <para>It is possible for there to be multiple distinct infosets for a
 232 single XML document.  This is because XML parsers are not required to
 233 process all DTD declarations or expand all external parsed general
 234 entities.  Amongst these multiple infosets, there is exactly one
 235 infoset for which [all declarations processed] is true and which does
 236 not contain any unexpanded entity reference information items.  This
 237 is the infoset that is the basis for defining the RELAX NG data
 238 model.</para>
 239
 240 <section id="data-model-example">
 241 <title>Example</title>
 242
 243 <para>Suppose the document
 244 <literal>http://www.example.com/doc.xml</literal> is as
 245 follows:</para>
 246
 247 <programlisting><![CDATA[<?xml version="1.0"?>
 248 <foo><pre1:bar1 xmlns:pre1="http://www.example.com/n1"/><pre2:bar2
 249   xmlns:pre2="http://www.example.com/n2"/></foo>
 250 ]]></programlisting>
 251
 252 <para>The element representing this document has</para>
 253
 254 <itemizedlist>
 255 <listitem><para>a name which has</para>
 256 <itemizedlist>
 257
 258 <listitem><para>the empty string as the namespace URI, representing
 259 the absence of any namespace</para></listitem>
 260
 261 <listitem><para><literal>foo</literal> as the local
 262 name</para></listitem>
 263
 264 </itemizedlist>
 265
 266 </listitem>
 267
 268 <listitem><para>a context which has</para>
 269
 270 <itemizedlist>
 271 <listitem><para><literal>http://www.example.com/doc.xml</literal> as the base
 272 URI</para></listitem>
 273
 274 <listitem><para>a namespace map which</para>
 275
 276 <itemizedlist>
 277
 278 <listitem><para>maps the prefix <literal>xml</literal> to the
 279 namespace URI
 280 <literal>http://www.w3.org/XML/1998/namespace</literal>
 281 (the <literal>xml</literal> prefix is implicitly declared
 282 by every XML document)</para></listitem>
 283
 284 <listitem><para>specifies the empty string as the default namespace
 285 URI</para></listitem>
 286
 287 </itemizedlist>
 288
 289 </listitem>
 290
 291 </itemizedlist>
 292
 293 </listitem>
 294
 295 <listitem><para>an empty set of attributes</para></listitem>
 296
 297 <listitem><para>a sequence of children consisting
 298 of an element which has</para>
 299
 300 <itemizedlist>
 301 <listitem><para>a name which has</para>
 302 <itemizedlist>
 303
 304 <listitem><para><literal>http://www.example.com/n1</literal> as the
 305 namespace URI</para></listitem>
 306
 307 <listitem><para><literal>bar1</literal> as the local
 308 name</para></listitem>
 309
 310 </itemizedlist>
 311
 312 </listitem>
 313
 314 <listitem><para>a context which has</para>
 315
 316 <itemizedlist>
 317 <listitem><para><literal>http://www.example.com/doc.xml</literal> as the base
 318 URI</para></listitem>
 319
 320 <listitem><para>a namespace map which</para>
 321
 322 <itemizedlist>
 323
 324 <listitem><para>maps the prefix <literal>pre1</literal> to the
 325 namespace URI
 326 <literal>http://www.example.com/n1</literal></para></listitem>
 327
 328 <listitem><para>maps the prefix <literal>xml</literal> to the
 329 namespace URI
 330 <literal>http://www.w3.org/XML/1998/namespace</literal></para></listitem>
 331
 332 <listitem><para>specifies the empty string as the default namespace
 333 URI</para></listitem>
 334
 335 </itemizedlist>
 336
 337 </listitem>
 338
 339 </itemizedlist>
 340
 341 </listitem>
 342
 343 <listitem><para>an empty set of attributes</para></listitem>
 344
 345 <listitem><para>an empty sequence of children</para></listitem>
 346
 347 </itemizedlist>
 348
 349 <para>followed by an element which has</para>
 350
 351 <itemizedlist>
 352 <listitem><para>a name which has</para>
 353 <itemizedlist>
 354
 355 <listitem><para><literal>http://www.example.com/n2</literal> as the
 356 namespace URI</para></listitem>
 357
 358 <listitem><para><literal>bar2</literal> as the local
 359 name</para></listitem>
 360
 361 </itemizedlist>
 362
 363 </listitem>
 364
 365 <listitem><para>a context which has</para>
 366
 367 <itemizedlist>
 368 <listitem><para><literal>http://www.example.com/doc.xml</literal> as the base
 369 URI</para></listitem>
 370
 371 <listitem><para>a namespace map which</para>
 372
 373 <itemizedlist>
 374
 375 <listitem><para>maps the prefix <literal>pre2</literal> to the
 376 namespace URI
 377 <literal>http://www.example.com/n2</literal></para></listitem>
 378
 379 <listitem><para>maps the prefix <literal>xml</literal> to the
 380 namespace URI
 381 <literal>http://www.w3.org/XML/1998/namespace</literal></para></listitem>
 382
 383 <listitem><para>specifies the empty string as the default namespace
 384 URI</para></listitem>
 385
 386 </itemizedlist>
 387
 388 </listitem>
 389
 390 </itemizedlist>
 391
 392 </listitem>
 393
 394 <listitem><para>an empty set of attributes</para></listitem>
 395
 396 <listitem><para>an empty sequence of children</para></listitem>
 397
 398 </itemizedlist>
 399
 400 </listitem>
 401 </itemizedlist>
 402
 403 </section>
 404
 405 </section>
 406
 407 <section id="full-syntax">
 408 <title>Full syntax</title>
 409
 410 <para>The following grammar summarizes the syntax of RELAX NG.
 411 Although we use a notation based on the XML representation of an RELAX
 412 NG schema as a sequence of characters, the grammar must be understood
 413 as operating at the data model level.  For example, although the
 414 syntax uses <literal><![CDATA[<text/>]]></literal>, an instance or
 415 schema can use <literal><![CDATA[<text></text>]]></literal> instead,
 416 because they both represent the same element at the data model level.
 417 All elements shown in the grammar are qualified with the namespace
 418 URI:</para>
 419
 420 <programlisting>http://relaxng.org/ns/structure/1.0</programlisting>
 421
 422 <para>The symbols QName and NCName are defined in <xref
 423 linkend="xml-names"/>.  The anyURI symbol has the same meaning as the
 424 anyURI datatype of <xref linkend="xmlschema-2"/>: it indicates a
 425 string that, after escaping of disallowed values as described in
 426 Section 5.4 of <xref linkend="xlink"/>, is a URI reference as defined
 427 in <xref linkend="rfc2396"/> (as modified by <xref
 428 linkend="rfc2732"/>).  The symbol string matches any string.</para>
 429
 430 <para>In addition to the attributes shown explicitly, any element can
 431 have an <literal>ns</literal> attribute and any element can have a
 432 <literal>datatypeLibrary</literal> attribute. The
 433 <literal>ns</literal> attribute can have any value.  The value of the
 434 <literal>datatypeLibrary</literal> attribute must match the anyURI
 435 symbol as described in the previous paragraph; in addition, it must
 436 not use the relative form of URI reference and must not have a
 437 fragment identifier; as an exception to this, the value may be the
 438 empty string.</para>
 439
 440 <para>Any element can also have foreign attributes in addition to the
 441 attributes shown in the grammar. A foreign attribute is an attribute
 442 with a name whose namespace URI is neither the empty string nor the
 443 RELAX NG namespace URI.  Any element that cannot have string children
 444 (that is, any element other than <literal>value</literal>, <literal>param</literal>
 445 and <literal>name</literal>) may have foreign child elements in addition
 446 to the child elements shown in the grammar. A foreign element is an
 447 element with a name whose namespace URI is not the RELAX NG namespace
 448 URI.  There are no constraints on the relative position of foreign
 449 child elements with respect to other child elements.</para>
 450
 451 <para>Any element can also have as children strings that consist
 452 entirely of whitespace characters, where a whitespace character is one
 453 of #x20, #x9, #xD or #xA. There are no constraints on the relative
 454 position of whitespace string children with respect to child
 455 elements.</para>
 456
 457 <para>Leading and trailing whitespace is allowed for value of each
 458 <literal>name</literal>, <literal>type</literal> and
 459 <literal>combine</literal> attribute and for the content of each
 460 <literal>name</literal> element.</para>
 461
 462 <grammarref src="full.rng"/>
 463
 464 <section id="full-syntax-example">
 465 <title>Example</title>
 466
 467 <para>Here is an example of a schema in the full syntax for the
 468 document in <xref linkend="data-model-example"/>.</para>
 469
 470 <programlisting><![CDATA[<?xml version="1.0"?>
 471 <element name="foo"
 472          xmlns="http://relaxng.org/ns/structure/1.0"
 473          xmlns:a="http://relaxng.org/ns/annotation/1.0"
 474          xmlns:ex1="http://www.example.com/n1"
 475          xmlns:ex2="http://www.example.com/n2">
 476   <a:documentation>A foo element.</a:document>
 477   <element name="ex1:bar1">
 478     <empty/>
 479   </element>
 480   <element name="ex2:bar2">
 481     <empty/>
 482   </element>
 483 </element>]]></programlisting>
 484
 485 </section>
 486
 487 </section>
 488
 489 <section id="simplification">
 490 <title>Simplification</title>
 491
 492 <para>The full syntax given in the previous section is transformed
 493 into a simpler syntax by applying the following transformation rules
 494 in order. The effect must be as if each rule was applied to all
 495 elements in the schema before the next rule is applied.  A
 496 transformation rule may also specify constraints that must be
 497 satisfied by a correct schema. The transformation rules are applied
 498 at the data model level.  Before the transformations are applied, the
 499 schema is parsed into an instance of the data model.</para>
 500
 501 <section>
 502 <title>Annotations</title>
 503
 504 <para>Foreign attributes and elements are removed.</para>
 505
 506 <note><para>It is safe to remove <literal>xml:base</literal>
 507 attributes at this stage because <literal>xml:base</literal>
 508 attributes are used in determining the [base URI] of an element
 509 information item, which is in turn used to construct the base URI of
 510 the context of an element.  Thus, after a document has been parsed
 511 into an instance of the data model, <literal>xml:base</literal>
 512 attributes can be discarded.</para></note>
 513
 514 </section>
 515
 516 <section>
 517 <title>Whitespace</title>
 518
 519 <para>For each element other than <literal>value</literal> and
 520 <literal>param</literal>, each child that is a string containing only
 521 whitespace characters is removed.</para>
 522
 523 <para>Leading and trailing whitespace characters are removed from the
 524 value of each <literal>name</literal>, <literal>type</literal> and
 525 <literal>combine</literal> attribute and from the content of each
 526 <literal>name</literal> element.</para>
 527
 528 </section>
 529
 530 <section>
 531 <title><literal>datatypeLibrary</literal> attribute</title>
 532
 533 <para>The value of each <literal>datatypeLibary</literal> attribute is
 534 transformed by escaping disallowed characters as specified in Section
 535 5.4 of <xref linkend="xlink"/>.</para>
 536
 537 <para>For any <literal>data</literal> or <literal>value</literal>
 538 element that does not have a <literal>datatypeLibrary</literal>
 539 attribute, a <literal>datatypeLibrary</literal> attribute is
 540 added. The value of the added <literal>datatypeLibrary</literal>
 541 attribute is the value of the <literal>datatypeLibrary</literal>
 542 attribute of the nearest ancestor element that has a
 543 <literal>datatypeLibrary</literal> attribute, or the empty string if
 544 there is no such ancestor. Then, any <literal>datatypeLibrary</literal>
 545 attribute that is on an element other than <literal>data</literal> or
 546 <literal>value</literal> is removed.</para>
 547
 548 </section>
 549
 550 <section>
 551 <title><literal>type</literal> attribute of <literal>value</literal> element</title>
 552
 553 <para>For any <literal>value</literal> element that does not have a
 554 <literal>type</literal> attribute, a <literal>type</literal> attribute
 555 is added with value <literal>token</literal> and the value of the
 556 <literal>datatypeLibrary</literal> attribute is changed to the empty
 557 string.</para>
 558
 559 </section>
 560
 561 <section id="href">
 562 <title><literal>href</literal> attribute</title>
 563
 564 <para>The value of the <literal>href</literal> attribute on an
 565 <literal>externalRef</literal> or <literal>include</literal> element
 566 is first transformed by escaping disallowed characters as specified in
 567 Section 5.4 of <xref linkend="xlink"/>.  The URI reference is then
 568 resolved into an absolute form as described in section 5.2 of <xref
 569 linkend="rfc2396"/> using the base URI from the context of the element
 570 that bears the <literal>href</literal> attribute.</para>
 571
 572 <para>The value of the <literal>href</literal> attribute will be used
 573 to construct an element (as specified in <xref
 574 linkend="data-model"/>). This must be done as follows.  The URI
 575 reference consists of the URI itself and an optional fragment
 576 identifier. The resource identified by the URI is retrieved.  The
 577 result is a MIME entity: a sequence of bytes labeled with a MIME
 578 media type.  The media type determines how an element is constructed
 579 from the MIME entity and optional fragment identifier.  When the media
 580 type is <literal>application/xml</literal> or
 581 <literal>text/xml</literal>, the MIME entity must be parsed as an XML
 582 document in accordance with the applicable RFC (at the term of writing
 583 <xref linkend="rfc3023"/>) and an element constructed from the result
 584 of the parse as specified in <xref linkend="data-model"/>.  In
 585 particular, the <literal>charset</literal> parameter must be handled
 586 as specified by the RFC. This specification does not define the
 587 handling of media types other than <literal>application/xml</literal>
 588 and <literal>text/xml</literal>. The <literal>href</literal> attribute
 589 must not include a fragment identifier unless the registration of the
 590 media type of the resource identified by the attribute defines the
 591 interpretation of fragment identifiers for that media type.</para>
 592
 593 <note><para><xref linkend="rfc3023"/> does not define the
 594 interpretation of fragment identifiers for
 595 <literal>application/xml</literal> or
 596 <literal>text/xml</literal>.</para></note>
 597
 598 </section>
 599
 600 <section>
 601 <title><literal>externalRef</literal> element</title>
 602
 603 <para>An <literal>externalRef</literal> element is transformed as
 604 follows.  An element is constructed using the URI reference that is
 605 the value of <literal>href</literal> attribute as specified in <xref
 606 linkend="href"/>. This element must match the syntax for pattern.  The
 607 element is transformed by recursively applying the rules from this
 608 subsection and from previous subsections of this section. This must
 609 not result in a loop. In other words, the transformation of the
 610 referenced element must not require the dereferencing of an
 611 <literal>externalRef</literal> attribute with an
 612 <literal>href</literal> attribute with the same value.</para>
 613
 614 <para>Any <literal>ns</literal> attribute on the
 615 <literal>externalRef</literal> element is transferred to the
 616 referenced element if the referenced element does not already have an
 617 <literal>ns</literal> attribute.  The <literal>externalRef</literal>
 618 element is then replaced by the referenced element.</para>
 619
 620 </section>
 621
 622 <section>
 623 <title><literal>include</literal> element</title>
 624
 625 <para>An <literal>include</literal> element is transformed as follows.
 626 An element is constructed using the URI reference that is the value of
 627 <literal>href</literal> attribute as specified in <xref
 628 linkend="href"/>.  This element must be a <literal>grammar</literal>
 629 element, matching the syntax for grammar.</para>
 630
 631 <para>This <literal>grammar</literal> element is transformed by
 632 recursively applying the rules from this subsection and from previous
 633 subsections of this section.  This must not result in a loop. In other
 634 words, the transformation of the <literal>grammar</literal> element
 635 must not require the dereferencing of an <literal>include</literal>
 636 attribute with an <literal>href</literal> attribute with the same
 637 value.</para>
 638
 639 <para>Define the <firstterm>components</firstterm> of an element to
 640 be the children of the element together with the components of any
 641 <literal>div</literal> child elements.  If the
 642 <literal>include</literal> element has a <literal>start</literal>
 643 component, then the <literal>grammar</literal> element must have a
 644 <literal>start</literal> component.  If the <literal>include</literal>
 645 element has a <literal>start</literal> component, then all
 646 <literal>start</literal> components are removed from the
 647 <literal>grammar</literal> element.  If the <literal>include</literal>
 648 element has a <literal>define</literal> component, then the
 649 <literal>grammar</literal> element must have a
 650 <literal>define</literal> component with the same name.  For every
 651 <literal>define</literal> component of the <literal>include</literal>
 652 element, all <literal>define</literal> components with the same name
 653 are removed from the <literal>grammar</literal> element.</para>
 654
 655 <para>The <literal>include</literal> element is transformed into a
 656 <literal>div</literal> element.  The attributes of the
 657 <literal>div</literal> element are the attributes of the
 658 <literal>include</literal> element other than the
 659 <literal>href</literal> attribute.  The children of the
 660 <literal>div</literal> element are the <literal>grammar</literal>
 661 element (after the removal of the <literal>start</literal> and
 662 <literal>define</literal> components described by the preceding
 663 paragraph) followed by the children of the <literal>include</literal>
 664 element.  The <literal>grammar</literal> element is then renamed to
 665 <literal>div</literal>.</para>
 666
 667 </section>
 668
 669 <section>
 670 <title><literal>name</literal> attribute of <literal>element</literal>
 671 and <literal>attribute</literal> elements</title>
 672
 673 <para>The <literal>name</literal> attribute on an
 674 <literal>element</literal> or <literal>attribute</literal> element is
 675 transformed into a <literal>name</literal> child element.</para>
 676
 677 <para>If an <literal>attribute</literal> element has a
 678 <literal>name</literal> attribute but no <literal>ns</literal>
 679 attribute, then an <literal>ns=""</literal> attribute is added to the
 680 <literal>name</literal> child element.</para>
 681
 682 </section>
 683
 684 <section>
 685 <title><literal>ns</literal> attribute</title>
 686
 687 <para>For any <literal>name</literal>, <literal>nsName</literal> or
 688 <literal>value</literal> element that does not have an
 689 <literal>ns</literal> attribute, an <literal>ns</literal> attribute is
 690 added. The value of the added <literal>ns</literal> attribute is the
 691 value of the <literal>ns</literal> attribute of the nearest ancestor
 692 element that has an <literal>ns</literal> attribute, or the empty
 693 string if there is no such ancestor. Then, any <literal>ns</literal>
 694 attribute that is on an element other than <literal>name</literal>,
 695 <literal>nsName</literal> or <literal>value</literal> is
 696 removed.</para>
 697
 698 <note><para>The value of the <literal>ns</literal> attribute is
 699 <emphasis role="strong">not</emphasis> transformed either by escaping
 700 disallowed characters, or in any other way, because the value of the
 701 <literal>ns</literal> attribute is compared against namespace URIs in
 702 the instance, which are not subject to any
 703 transformation.</para></note>
 704
 705 <note><para>Since <literal>include</literal> and
 706 <literal>externalRef</literal> elements are resolved after
 707 <literal>datatypeLibrary</literal> attributes are added but before
 708 <literal>ns</literal> attributes are added, <literal>ns</literal>
 709 attributes are inherited into external schemas but
 710 <literal>datatypeLibrary</literal> attributes are not.</para></note>
 711
 712 </section>
 713
 714 <section>
 715 <title>QNames</title>
 716
 717 <para>For any <literal>name</literal> element containing a prefix, the
 718 prefix is removed and an <literal>ns</literal> attribute is added
 719 replacing any existing <literal>ns</literal> attribute. The value of
 720 the added <literal>ns</literal> attribute is the value to which the
 721 namespace map of the context of the <literal>name</literal> element
 722 maps the prefix.  The context must have a mapping for the
 723 prefix.</para>
 724
 725 </section>
 726
 727 <section>
 728 <title><literal>div</literal> element</title>
 729
 730 <para>Each <literal>div</literal> element is replaced by its
 731 children.</para>
 732
 733 </section>
 734
 735 <section id="number-child-elements">
 736 <title>Number of child elements</title>
 737
 738 <para>A <literal>define</literal>, <literal>oneOrMore</literal>,
 739 <literal>zeroOrMore</literal>, <literal>optional</literal>, <literal>list</literal> or
 740 <literal>mixed</literal> element is transformed so that it has exactly
 741 one child element.  If it has more than one child element, then its
 742 child elements are wrapped in a <literal>group</literal>
 743 element. Similarly, an <literal>element</literal> element is transformed so
 744 that it has exactly two child elements, the first being a name class
 745 and the second being a pattern. If it has more than two child elements,
 746 then the child elements other than the first are wrapped in a
 747 <literal>group</literal> element.</para>
 748
 749 <para>A <literal>except</literal> element is transformed
 750 so that it has exactly one child element. If it has more
 751 than one child element, then its child elements are wrapped
 752 in a <literal>choice</literal> element.</para>
 753
 754 <para>If an <literal>attribute</literal> element has only one child
 755 element (a name class), then a <literal>text</literal> element is
 756 added.</para>
 757
 758 <para>A <literal>choice</literal>, <literal>group</literal> or
 759 <literal>interleave</literal> element is transformed so that it has
 760 exactly two child elements. If it has one child element, then it is
 761 replaced by its child element.  If it has more than two child
 762 elements, then the first two child elements are combined into a new
 763 element with the same name as the parent element and with the first
 764 two child elements as its children.  For example,</para>
 765
 766 <programlisting>&lt;choice&gt; <replaceable>p1</replaceable> <replaceable>p2</replaceable> <replaceable>p3</replaceable> &lt;/choice&gt;</programlisting>
 767
 768 <para>is transformed to</para>
 769
 770 <programlisting>&lt;choice&gt; &lt;choice&gt; <replaceable>p1</replaceable> <replaceable>p2</replaceable> &lt;/choice&gt; <replaceable>p3</replaceable> &lt;/choice&gt;</programlisting>
 771
 772 <para>This reduces the number of child elements by one. The
 773 transformation is applied repeatedly until there are exactly two child
 774 elements.</para>
 775
 776 </section>
 777
 778 <section>
 779 <title><literal>mixed</literal> element</title>
 780
 781 <para>A <literal>mixed</literal> element is transformed into an
 782 interleaving with a <literal>text</literal> element:</para>
 783
 784 <programlisting>&lt;mixed> <replaceable>p</replaceable> &lt;/mixed></programlisting>
 785
 786 <para>is transformed into</para>
 787
 788 <programlisting>&lt;interleave> <replaceable>p</replaceable> &lt;text/> &lt;/interleave></programlisting>
 789
 790 </section>
 791
 792 <section>
 793 <title><literal>optional</literal> element</title>
 794
 795 <para>An <literal>optional</literal> element is transformed into
 796 a choice with <literal>empty</literal>:</para>
 797
 798 <programlisting>&lt;optional> <replaceable>p</replaceable> &lt;/optional></programlisting>
 799
 800 <para>is transformed into</para>
 801
 802 <programlisting>&lt;choice> <replaceable>p</replaceable> &lt;empty/> &lt;/choice></programlisting>
 803
 804 </section>
 805
 806 <section>
 807 <title><literal>zeroOrMore</literal> element</title>
 808
 809 <para>A <literal>zeroOrMore</literal> element is transformed into a choice
 810 between <literal>oneOrMore</literal> and
 811 <literal>empty</literal>:</para>
 812
 813 <programlisting>&lt;zeroOrMore> <replaceable>p</replaceable> &lt;/zeroOrMore></programlisting>
 814
 815 <para>is transformed into</para>
 816
 817 <programlisting>&lt;choice> &lt;oneOrMore> <replaceable>p</replaceable> &lt;/oneOrMore> &lt;empty/> &lt;/choice></programlisting>
 818
 819 </section>
 820
 821 <section id="constraints">
 822 <title>Constraints</title>
 823
 824 <para>In this rule, no transformation is performed, but various
 825 constraints are checked.</para>
 826
 827 <note><para>The constraints in this section, unlike the constraints
 828 specified in <xref linkend="restriction"/>, can be checked without
 829 resolving any <literal>ref</literal> elements, and are accordingly
 830 applied even to patterns that will disappear during later stages of
 831 simplification because they are not reachable (see <xref
 832 linkend="define-ref"/>) or because of <literal>notAllowed</literal>
 833 (see <xref linkend="notAllowed"/>).</para></note>
 834
 835 <para>An <literal>except</literal> element that is a child of an
 836 <literal>anyName</literal> element must not have any
 837 <literal>anyName</literal> descendant elements. An
 838 <literal>except</literal> element that is a child of an
 839 <literal>nsName</literal> element must not have any
 840 <literal>nsName</literal> or <literal>anyName</literal> descendant
 841 elements.</para>
 842
 843 <para>A <literal>name</literal> element that occurs as the first child
 844 of an <literal>attribute</literal> element or as the descendant of the
 845 first child of an <literal>attribute</literal> element and that has an
 846 <literal>ns</literal> attribute with value equal to the empty string
 847 must not have content equal to <literal>xmlns</literal>.</para>
 848
 849 <para>A <literal>name</literal> or <literal>nsName</literal> element
 850 that occurs as the first child of an <literal>attribute</literal>
 851 element or as the descendant of the first child of an
 852 <literal>attribute</literal> element must not have an
 853 <literal>ns</literal> attribute with value
 854 <literal>http://www.w3.org/2000/xmlns</literal>.</para>
 855
 856 <note><para>The <xref linkend="infoset"/> defines the namespace URI of
 857 namespace declaration attributes to be
 858 <literal>http://www.w3.org/2000/xmlns</literal>.</para></note>
 859
 860 <para>A <literal>data</literal> or <literal>value</literal> element
 861 must be correct in its use of datatypes. Specifically, the
 862 <literal>type</literal> attribute must identify a datatype within the
 863 datatype library identified by the value of the
 864 <literal>datatypeLibrary</literal> attribute.  For a
 865 <literal>data</literal> element, the parameter list must be one that
 866 is allowed by the datatype (see <xref
 867 linkend="data-pattern"/>).</para>
 868
 869 </section>
 870
 871 <section>
 872 <title><literal>combine</literal> attribute</title>
 873
 874 <para>For each <literal>grammar</literal> element, all
 875 <literal>define</literal> elements with the same name are combined
 876 together.  For any name, there must not be more than one
 877 <literal>define</literal> element with that name that does not have a
 878 <literal>combine</literal> attribute.  For any name, if there is a
 879 <literal>define</literal> element with that name that has a
 880 <literal>combine</literal> attribute with the value
 881 <literal>choice</literal>, then there must not also be a
 882 <literal>define</literal> element with that name that has a
 883 <literal>combine</literal> attribute with the value
 884 <literal>interleave</literal>. Thus, for any name, if there is more
 885 than one <literal>define</literal> element with that name, then there
 886 is a unique value for the <literal>combine</literal> attribute for
 887 that name.  After determining this unique value, the
 888 <literal>combine</literal> attributes are removed.  A pair of
 889 definitions</para>
 890
 891 <programlisting>&lt;define name="<replaceable>n</replaceable>"&gt;
 892   <replaceable>p1</replaceable>
 893 &lt;/define>
 894 &lt;define name="<replaceable>n</replaceable>"&gt;
 895   <replaceable>p2</replaceable>
 896 &lt;/define></programlisting>
 897
 898 <para>is combined into</para>
 899
 900 <programlisting>&lt;define name="<replaceable>n</replaceable>">
 901   &lt;<replaceable>c</replaceable>&gt;
 902     <replaceable>p1</replaceable>
 903     <replaceable>p2</replaceable>
 904   &lt;/<replaceable>c</replaceable>&gt;
 905 &lt;/define></programlisting>
 906
 907 <para>where <replaceable>c</replaceable> is the value of the
 908 <literal>combine</literal> attribute. Pairs of definitions are
 909 combined until there is exactly one <literal>define</literal> element
 910 for each name.</para>
 911
 912 <para>Similarly, for each <literal>grammar</literal> element all
 913 <literal>start</literal> elements are combined together.  There must
 914 not be more than one <literal>start</literal> element that does not
 915 have a <literal>combine</literal> attribute.  If there is a
 916 <literal>start</literal> element that has a <literal>combine</literal>
 917 attribute with the value <literal>choice</literal>, there must not
 918 also be a <literal>start</literal> element that has a
 919 <literal>combine</literal> attribute with the value
 920 <literal>interleave</literal>.</para>
 921
 922 </section>
 923
 924 <section>
 925 <title><literal>grammar</literal> element</title>
 926
 927 <para>In this rule, the schema is transformed so that its top-level
 928 element is <literal>grammar</literal> and so that it has no other
 929 <literal>grammar</literal> elements.</para>
 930
 931 <para>Define the <firstterm>in-scope grammar</firstterm> for an
 932 element to be the nearest ancestor <literal>grammar</literal> element.  A
 933 <literal>ref</literal> element <firstterm>refers to</firstterm> a
 934 <literal>define</literal> element if the value of their
 935 <literal>name</literal> attributes is the same and their in-scope
 936 grammars are the same.  A <literal>parentRef</literal> element
 937 <firstterm>refers to</firstterm> a <literal>define</literal> element
 938 if the value of their <literal>name</literal> attributes is the same
 939 and the in-scope grammar of the in-scope grammar of the
 940 <literal>parentRef</literal> element is the same as the in-scope
 941 grammar of the <literal>define</literal> element. Every
 942 <literal>ref</literal> or <literal>parentRef</literal> element must
 943 refer to a <literal>define</literal> element.  A
 944 <literal>grammar</literal> must have a <literal>start</literal> child
 945 element.</para>
 946
 947 <para>First, transform the top-level pattern
 948 <replaceable>p</replaceable> into
 949 <literal>&lt;grammar>&lt;start><replaceable>p</replaceable>&lt;/start>&lt;/grammar></literal>.
 950 Next, rename <literal>define</literal> elements so that no two
 951 <literal>define</literal> elements anywhere in the schema have the
 952 same name.  To rename a <literal>define</literal> element, change the
 953 value of its <literal>name</literal> attribute and change the value of
 954 the <literal>name</literal> attribute of all <literal>ref</literal>
 955 and <literal>parentRef</literal> elements that refer to that
 956 <literal>define</literal> element. Next, move all
 957 <literal>define</literal> elements to be children of the top-level
 958 <literal>grammar</literal> element, replace each nested
 959 <literal>grammar</literal> element by the child of its
 960 <literal>start</literal> element and rename each
 961 <literal>parentRef</literal> element to <literal>ref</literal>.</para>
 962
 963 </section>
 964
 965
 966 <section id="define-ref">
 967 <title><literal>define</literal> and <literal>ref</literal> elements</title>
 968
 969 <para>In this rule, the grammar is transformed so that every
 970 <literal>element</literal> element is the child of a
 971 <literal>define</literal> element, and the child of every
 972 <literal>define</literal> element is an <literal>element</literal>
 973 element.</para>
 974
 975 <para>First, remove any <literal>define</literal> element that is not
 976 <firstterm>reachable</firstterm>.  A <literal>define</literal> element
 977 is reachable if there is reachable <literal>ref</literal> element
 978 referring to it.  A <literal>ref</literal> element is reachable if it
 979 is the descendant of the <literal>start</literal> element or of a
 980 reachable <literal>define</literal> element. Now, for
 981 each <literal>element</literal> element that is not the child of a
 982 <literal>define</literal> element, add a <literal>define</literal>
 983 element to the <literal>grammar</literal> element, and replace the
 984 <literal>element</literal> element by a <literal>ref</literal> element
 985 referring to the added <literal>define</literal> element. The value of
 986 the <literal>name</literal> attribute of the added
 987 <literal>define</literal> element must be different from value of the
 988 <literal>name</literal> attribute of all other
 989 <literal>define</literal> elements. The child of the added
 990 <literal>define</literal> element is the <literal>element</literal>
 991 element.</para>
 992
 993 <para>Define a <literal>ref</literal> element to be
 994 <firstterm>expandable</firstterm> if it refers to a
 995 <literal>define</literal> element whose child is not an
 996 <literal>element</literal> element.  For each <literal>ref</literal>
 997 element that is expandable and is a descendant of a
 998 <literal>start</literal> element or an <literal>element</literal>
 999 element, expand it by replacing the <literal>ref</literal> element by
1000 the child of the <literal>define</literal> element to which it refers and
1001 then recursively expanding any expandable <literal>ref</literal>
1002 elements in this replacement.  This must not result in a loop.
1003 In other words expanding the replacement of a
1004 <literal>ref</literal> element having a <literal>name</literal> with
1005 value <replaceable>n</replaceable> must not require the expansion of
1006 <literal>ref</literal> element also having a <literal>name</literal>
1007 with value <replaceable>n</replaceable>.  Finally, remove any
1008 <literal>define</literal> element whose child is not an
1009 <literal>element</literal> element.</para>
1010
1011 </section>
1012
1013 <section id="notAllowed">
1014 <title><literal>notAllowed</literal> element</title>
1015
1016 <para>In this rule, the grammar is transformed so that a
1017 <literal>notAllowed</literal> element occurs only as the child of
1018 a <literal>start</literal> or <literal>element</literal> element.  An
1019 <literal>attribute</literal>, <literal>list</literal>,
1020 <literal>group</literal>, <literal>interleave</literal>,
1021 or <literal>oneOrMore</literal> element that has a
1022 <literal>notAllowed</literal> child element is transformed into a
1023 <literal>notAllowed</literal> element.  A <literal>choice</literal>
1024 element that has two <literal>notAllowed</literal> child elements is
1025 transformed into a <literal>notAllowed</literal> element.  A
1026 <literal>choice</literal> element that has one
1027 <literal>notAllowed</literal> child element is transformed into its
1028 other child element. An <literal>except</literal> element that has a
1029 <literal>notAllowed</literal> child element is removed.
1030 The preceding transformations are applied
1031 repeatedly until none of them is applicable any more.
1032 Any <literal>define</literal> element that is no longer reachable
1033 is removed.</para>
1034
1035 </section>
1036
1037 <section>
1038 <title><literal>empty</literal> element</title>
1039
1040 <para>In this rule, the grammar is transformed so that an
1041 <literal>empty</literal> element does not occur as a child of a
1042 <literal>group</literal>, <literal>interleave</literal>, or
1043 <literal>oneOrMore</literal> element or as the second child of
1044 a <literal>choice</literal> element. A <literal>group</literal>,
1045 <literal>interleave</literal> or <literal>choice</literal> element
1046 that has two <literal>empty</literal> child elements is transformed
1047 into an <literal>empty</literal> element.  A <literal>group</literal>
1048 or <literal>interleave</literal> element that has one
1049 <literal>empty</literal> child element is transformed into its other
1050 child element.  A <literal>choice</literal> element whose
1051 second child element is an <literal>empty</literal> element is
1052 transformed by interchanging its two child elements.  A
1053 <literal>oneOrMore</literal> element that has an
1054 <literal>empty</literal> child element is transformed into an
1055 <literal>empty</literal> element. The preceding transformations are applied
1056 repeatedly until none of them is applicable any more.</para>
1057
1058 </section>
1059
1060 </section>
1061
1062 <section id="simple-syntax">
1063 <title>Simple syntax</title>
1064
1065 <para>After applying all the rules in <xref
1066 linkend="simplification"/>, the schema will match the following
1067 grammar:</para>
1068
1069 <grammarref src="simple.rng"/>
1070
1071 <para>With this grammar, no elements or attributes are allowed other
1072 than those explicitly shown.</para>
1073
1074 <section id="simple-syntax-example">
1075 <title>Example</title>
1076
1077 <para>The following is an example of how the schema in <xref
1078 linkend="full-syntax-example"/> can be transformed into the simple
1079 syntax:</para>
1080
1081 <programlisting><![CDATA[<?xml version="1.0"?>
1082 <grammar xmlns="http://relaxng.org/ns/structure/1.0">
1083   <start>
1084     <ref name="foo.element"/>
1085   </start>
1086
1087   <define name="foo.element">
1088     <element>
1089       <name ns="">foo</name>
1090       <group>
1091         <ref name="bar1.element"/>
1092         <ref name="bar2.element"/>
1093       </group>
1094     </element>
1095   </define>
1096
1097   <define name="bar1.element">
1098     <element>
1099       <name ns="http://www.example.com/n1">bar1</name>
1100       <empty/>
1101     </element>
1102   </define>
1103
1104   <define name="bar2.element">
1105     <element>
1106       <name ns="http://www.example.com/n2">bar2</name>
1107       <empty/>
1108     </element>
1109   </define>
1110 </grammar>]]></programlisting>
1111
1112 <note><para>Strictly speaking, the result of simplification is an
1113 instance of the data model rather than an XML document.  For
1114 convenience, we use an XML document to represent an instance of the
1115 data model.</para></note>
1116
1117 </section>
1118
1119 </section>
1120
1121 <section id="semantics">
1122 <title>Semantics</title>
1123
1124 <para>In this section, we define the semantics of a correct RELAX NG
1125 schema that has been transformed into the simple syntax.  The
1126 semantics of a RELAX NG schema consist of a specification of what XML
1127 documents are valid with respect to that schema.  The semantics are
1128 described formally.  The formalism uses axioms and inference rules.
1129 Axioms are propositions that are provable unconditionally.  An
1130 inference rule consists of one or more antecedents and exactly one
1131 consequent.  An antecedent is either positive or negative.  If all the
1132 positive antecedents of an inference rule are provable and none of the
1133 negative antecedents are provable, then the consequent of the
1134 inference rule is provable. An XML document is valid with respect to a
1135 RELAX NG schema if and only if the proposition that it is valid is
1136 provable in the formalism specified in this section.</para>
1137
1138 <note><para>This kind of formalism is similar to a proof system.
1139 However, a traditional proof system only has positive
1140 antecedents.</para></note>
1141
1142 <para>The notation for inference rules separates the antecedents from
1143 the consequent by a horizontal line: the antecedents are above the
1144 line; the consequent is below the line.  If an antecedent is of the
1145 form not(<replaceable>p</replaceable>), then it is a negative
1146 antecedent; otherwise, it is a positive antecedent.  Both axioms and
1147 inferences
1148 rules may use variables.  A variable has a name and optionally a
1149 subscript.  The name of a variable is italicized.  Each variable has a
1150 range that is determined by its name.  Axioms and inference rules are
1151 implicitly universally quantified over the variables they contain.  We
1152 explain this further below.</para>
1153
1154 <para>The possibility that an inference rule or axiom may contain more
1155 than one occurrence of a particular variable requires that an identity
1156 relation be defined on each kind of object over which a variable can
1157 range.  The identity relation for all kinds of object is value-based.
1158 Two objects of a particular kind are identical if the constituents of
1159 the objects are identical.  For example, two attributes are considered
1160 the same if they have the same name and the same value. Two characters
1161 are identical if their Unicode character codes are the same.</para>
1162
1163 <section id="name-classes">
1164 <title>Name classes</title>
1165
1166 <para>The main semantic concept for name classes is that of a name
1167 belonging to a name class. A name class is an element that matches the
1168 production nameClass. A name is as defined in <xref
1169 linkend="data-model"/>: it consists of a namespace URI and a local
1170 name.</para>
1171
1172 <para>We use the following notation:</para>
1173
1174 <variablelist>
1175
1176 <varlistentry><term><p:var range="name"/></term><listitem><para>is a variable
1177 that ranges over names</para></listitem></varlistentry>
1178
1179 <varlistentry><term><p:var range="nameClass"/></term><listitem><para>ranges over name classes</para></listitem></varlistentry>
1180
1181 <varlistentry><term><p:judgement name="belongs">
1182       <p:var range="name"/>
1183       <p:var range="nameClass"/>
1184     </p:judgement></term><listitem><para>
1185
1186 asserts that name <p:var range="name"/> is a member of name class <p:var range="nameClass"/>
1187
1188 </para></listitem></varlistentry>
1189
1190 </variablelist>
1191
1192 <para>We are now ready for our first axiom, which is called "anyName
1193 1":</para>
1194
1195 <p:proofSystem>
1196   <p:rule name="anyName 1">
1197     <p:judgement name="belongs">
1198       <p:var range="name"/>
1199       <p:element name="anyName"/>
1200     </p:judgement>
1201   </p:rule>
1202 </p:proofSystem>
1203
1204 <para>This says for any name <p:var range="name"/>, <p:var
1205 range="name"/> belongs to the name class <p:element name="anyName"/>,
1206 in other words <p:element name="anyName"/> matches any name. Note the
1207 effect of the implicit universal quantification over the variables in
1208 the axiom: this is what makes the axiom apply for any name <p:var
1209 range="name"/>.</para>
1210
1211 <para>Our first inference rule is almost as simple:</para>
1212
1213 <p:proofSystem>
1214   <p:rule name="anyName 2">
1215     <p:not>
1216       <p:judgement name="belongs">
1217         <p:var range="name"/>
1218         <p:var range="nameClass"/>
1219       </p:judgement>
1220     </p:not>
1221     <p:judgement name="belongs">
1222       <p:var range="name"/>
1223       <p:element name="anyName">
1224         <p:element name="except">
1225           <p:var range="nameClass"/>
1226         </p:element>
1227       </p:element>
1228     </p:judgement>
1229   </p:rule>
1230
1231 </p:proofSystem>
1232
1233 <para>This says that for any name <p:var range="name"/>
1234 and for any name class  <p:var range="nameClass"/>,
1235 if <p:var range="name"/> does not belong to <p:var range="nameClass"/>,
1236 then <p:var range="name"/> belongs to
1237       <p:element name="anyName">
1238         <p:element name="except">
1239           <p:var range="nameClass"/>
1240         </p:element>
1241       </p:element>. In other words,       <p:element name="anyName">
1242         <p:element name="except">
1243           <p:var range="nameClass"/>
1244         </p:element>
1245       </p:element> matches any name that does not match <p:var range="nameClass"/>.</para>
1246
1247 <para>We now need the following additional notation:</para>
1248
1249 <variablelist>
1250
1251 <varlistentry><term><p:var range="ncname"/></term>
1252
1253 <listitem><para>ranges over local names; a local name is a string that
1254 matches the NCName production of <xref linkend="xml-names"/>, that is,
1255 a name with no colons</para></listitem>
1256 </varlistentry>
1257
1258 <varlistentry><term><p:var range="uri"/></term><listitem><para>ranges over URIs</para></listitem></varlistentry>
1259
1260 <varlistentry>
1261 <term>
1262   <p:function name="name">
1263     <p:var range="uri"/>
1264     <p:var range="ncname"/>
1265   </p:function>
1266 </term>
1267 <listitem><para>constructs a name with URI <p:var range="uri"/> and local
1268 name <p:var range="ncname"/></para></listitem>
1269 </varlistentry>
1270
1271 </variablelist>
1272
1273 <para>The remaining axioms and inference rules for name classes are as
1274 follows:</para>
1275
1276 <p:proofSystem>
1277
1278   <p:rule name="nsName 1">
1279     <p:judgement name="belongs">
1280       <p:function name="name">
1281         <p:var range="uri"/>
1282         <p:var range="ncname"/>
1283       </p:function>
1284       <p:element name="nsName">
1285         <p:attribute name="ns">
1286           <p:var range="uri"/>
1287         </p:attribute>
1288       </p:element>
1289     </p:judgement>
1290   </p:rule>
1291
1292   <p:rule name="nsName 2">
1293     <p:not>
1294       <p:judgement name="belongs">
1295         <p:function name="name">
1296           <p:var range="uri"/>
1297           <p:var range="ncname"/>
1298         </p:function>
1299         <p:var range="nameClass"/>
1300       </p:judgement>
1301     </p:not>
1302     <p:judgement name="belongs">
1303       <p:function name="name">
1304         <p:var range="uri"/>
1305         <p:var range="ncname"/>
1306       </p:function>
1307       <p:element name="nsName">
1308         <p:attribute name="ns">
1309           <p:var range="uri"/>
1310         </p:attribute>
1311         <p:element name="except">
1312           <p:var range="nameClass"/>
1313         </p:element>
1314       </p:element>
1315     </p:judgement>
1316   </p:rule>
1317
1318   <p:rule name="name">
1319     <p:judgement name="belongs">
1320       <p:function name="name">
1321         <p:var range="uri"/>
1322         <p:var range="ncname"/>
1323       </p:function>
1324       <p:element name="name">
1325         <p:attribute name="ns">
1326           <p:var range="uri"/>
1327         </p:attribute>
1328         <p:var range="ncname"/>
1329       </p:element>
1330     </p:judgement>
1331   </p:rule>
1332
1333   <p:rule name="name choice 1">
1334     <p:judgement name="belongs">
1335       <p:var range="name"/>
1336       <p:var range="nameClass" sub="1"/>
1337     </p:judgement>
1338     <p:judgement name="belongs">
1339       <p:var range="name"/>
1340       <p:element name="choice">
1341         <p:var range="nameClass" sub="1"/>
1342         <p:var range="nameClass" sub="2"/>
1343       </p:element>
1344     </p:judgement>
1345   </p:rule>
1346
1347   <p:rule name="name choice 2">
1348     <p:judgement name="belongs">
1349       <p:var range="name"/>
1350       <p:var range="nameClass" sub="2"/>
1351     </p:judgement>
1352     <p:judgement name="belongs">
1353       <p:var range="name"/>
1354       <p:element name="choice">
1355         <p:var range="nameClass" sub="1"/>
1356         <p:var range="nameClass" sub="2"/>
1357       </p:element>
1358     </p:judgement>
1359   </p:rule>
1360
1361 </p:proofSystem>
1362
1363 </section>
1364
1365
1366 <section>
1367 <title>Patterns</title>
1368
1369 <para>The axioms and inference rules for patterns use the following
1370 notation:</para>
1371
1372 <variablelist>
1373
1374 <varlistentry><term><p:var range="context"/></term><listitem><para>ranges
1375 over contexts (as defined in <xref
1376 linkend="data-model"/>)</para></listitem></varlistentry>
1377
1378 <varlistentry><term><p:var range="att"/></term><listitem><para>ranges over
1379 sets of attributes; a set with a single member
1380 is considered the same as that member</para></listitem></varlistentry>
1381
1382 <varlistentry><term><p:var
1383 range="mixed"/></term><listitem><para>ranges over sequences of
1384 elements and strings; a sequence with a single member is considered
1385 the same as that member; the sequences ranged over by <p:var
1386 range="mixed"/> may contain consecutive strings and may contain strings
1387 that are empty; thus, there are sequences ranged over by <p:var
1388 range="mixed"/> that cannot occur as the children of an
1389 element</para></listitem></varlistentry>
1390
1391 <varlistentry><term><p:var range="pattern"/></term><listitem><para>ranges
1392 over patterns (elements matching the pattern
1393 production)</para></listitem></varlistentry>
1394
1395 <varlistentry><term><p:judgement name="match">
1396       <p:var range="context"/>
1397       <p:var range="att"/>
1398       <p:var range="mixed"/>
1399       <p:var range="pattern"/>
1400     </p:judgement></term><listitem><para>
1401
1402 asserts that with respect to context <p:var range="context"/>, the
1403 attributes <p:var range="att"/> and the sequence of elements and
1404 strings <p:var range="mixed"/> matches the pattern <p:var
1405 range="pattern"/></para></listitem></varlistentry>
1406
1407 </variablelist>
1408
1409 <section id="choice-pattern">
1410 <title><literal>choice</literal> pattern</title>
1411
1412 <para>The semantics of the <literal>choice</literal> pattern are as follows:</para>
1413
1414 <p:proofSystem>
1415   <p:rule name="choice 1">
1416
1417     <p:judgement name="match">
1418       <p:var range="context"/>
1419       <p:var range="att"/>
1420       <p:var range="mixed"/>
1421       <p:var range="pattern" sub="1"/>
1422     </p:judgement>
1423
1424     <p:judgement name="match">
1425       <p:var range="context"/>
1426       <p:var range="att"/>
1427       <p:var range="mixed"/>
1428       <p:element name="choice">
1429         <p:var range="pattern" sub="1"/>
1430         <p:var range="pattern" sub="2"/>
1431       </p:element>
1432     </p:judgement>
1433
1434   </p:rule>
1435
1436   <p:rule name="choice 2">
1437
1438     <p:judgement name="match">
1439       <p:var range="context"/>
1440       <p:var range="att"/>
1441       <p:var range="mixed"/>
1442       <p:var range="pattern" sub="2"/>
1443     </p:judgement>
1444
1445     <p:judgement name="match">
1446       <p:var range="context"/>
1447       <p:var range="att"/>
1448       <p:var range="mixed"/>
1449       <p:element name="choice">
1450         <p:var range="pattern" sub="1"/>
1451         <p:var range="pattern" sub="2"/>
1452       </p:element>
1453     </p:judgement>
1454
1455   </p:rule>
1456
1457
1458 </p:proofSystem>
1459
1460 </section>
1461
1462 <section>
1463 <title><literal>group</literal> pattern</title>
1464
1465 <para>We use the following additional notation:</para>
1466
1467 <variablelist>
1468
1469 <varlistentry><term><p:function name="append">
1470         <p:var range="mixed" sub="1"/>
1471         <p:var range="mixed" sub="2"/>
1472       </p:function></term><listitem>
1473 <para>represents the concatenation of the sequences <p:var range="mixed" sub="1"/> and <p:var range="mixed" sub="2"/>
1474
1475 </para></listitem></varlistentry>
1476
1477 <varlistentry><term><p:function name="union">
1478         <p:var range="att" sub="1"/>
1479         <p:var range="att" sub="2"/>
1480       </p:function></term><listitem>
1481 <para>represents the union of <p:var range="att" sub="1"/>
1482 and <p:var range="att" sub="2"/></para>
1483 </listitem>
1484 </varlistentry>
1485
1486 </variablelist>
1487
1488 <para>The semantics of the <literal>group</literal> pattern are as follows:</para>
1489
1490 <p:proofSystem>
1491   <p:rule name="group">
1492
1493     <p:judgement name="match">
1494       <p:var range="context"/>
1495       <p:var range="att" sub="1"/>
1496       <p:var range="mixed" sub="1"/>
1497       <p:var range="pattern" sub="1"/>
1498     </p:judgement>
1499
1500     <p:judgement name="match">
1501       <p:var range="context"/>
1502       <p:var range="att" sub="2"/>
1503       <p:var range="mixed" sub="2"/>
1504       <p:var range="pattern" sub="2"/>
1505     </p:judgement>
1506
1507     <p:judgement name="match">
1508       <p:var range="context"/>
1509       <p:function name="union">
1510         <p:var range="att" sub="1"/>
1511         <p:var range="att" sub="2"/>
1512       </p:function>
1513       <p:function name="append">
1514         <p:var range="mixed" sub="1"/>
1515         <p:var range="mixed" sub="2"/>
1516       </p:function>
1517       <p:element name="group">
1518         <p:var range="pattern" sub="1"/>
1519         <p:var range="pattern" sub="2"/>
1520       </p:element>
1521     </p:judgement>
1522
1523   </p:rule>
1524
1525 </p:proofSystem>
1526
1527 <note><para>The restriction in <xref linkend="attribute-restrictions"/>
1528 ensures that the set of attributes constructed in the consequent will
1529 not have multiple attributes with the same name.</para></note>
1530
1531 </section>
1532
1533
1534 <section id="empty-pattern">
1535 <title><literal>empty</literal> pattern</title>
1536
1537 <para>We use the following additional notation:</para>
1538
1539 <variablelist>
1540 <varlistentry><term><p:function name="emptySequence"/></term><listitem><para>represents an empty sequence</para></listitem></varlistentry>
1541
1542 <varlistentry><term><p:function name="emptySet"/></term><listitem><para>represents an empty set</para></listitem></varlistentry>
1543
1544 </variablelist>
1545
1546 <para>The semantics of the <literal>empty</literal> pattern are as follows:</para>
1547
1548 <p:proofSystem>
1549   <p:rule name="empty">
1550     <p:judgement name="match">
1551       <p:var range="context"/>
1552       <p:function name="emptySet"/>
1553       <p:function name="emptySequence"/>
1554       <p:element name="empty"></p:element>
1555       <p:function name="emptySet"/>
1556       <p:function name="emptySet"/>
1557     </p:judgement>
1558   </p:rule>
1559 </p:proofSystem>
1560
1561 </section>
1562
1563
1564 <section id="text-pattern">
1565 <title><literal>text</literal> pattern</title>
1566
1567 <para>We use the following additional notation:</para>
1568
1569 <variablelist>
1570 <varlistentry><term><p:var range="string"/></term><listitem><para>ranges
1571 over strings</para></listitem></varlistentry>
1572 </variablelist>
1573
1574 <para>The semantics of the <literal>text</literal> pattern are as follows:</para>
1575
1576 <p:proofSystem>
1577   <p:rule name="text 1">
1578     <p:judgement name="match">
1579       <p:var range="context"/>
1580       <p:function name="emptySet"/>
1581       <p:function name="emptySequence"/>
1582       <p:element name="text"></p:element>
1583       <p:function name="emptySet"/>
1584       <p:function name="emptySet"/>
1585     </p:judgement>
1586   </p:rule>
1587
1588   <p:rule name="text 2">
1589     <p:judgement name="match">
1590       <p:var range="context"/>
1591       <p:function name="emptySet"/>
1592       <p:var range="mixed"/>
1593       <p:element name="text"></p:element>
1594       <p:function name="emptySet"/>
1595       <p:function name="emptySet"/>
1596     </p:judgement>
1597     <p:judgement name="match">
1598       <p:var range="context"/>
1599       <p:function name="emptySet"/>
1600       <p:function name="append">
1601         <p:var range="mixed"/>
1602         <p:var range="string"/>
1603       </p:function>
1604       <p:element name="text"></p:element>
1605       <p:function name="emptySet"/>
1606       <p:function name="emptySet"/>
1607     </p:judgement>
1608   </p:rule>
1609
1610 </p:proofSystem>
1611
1612 <para>The effect of the above rule is that a <literal>text</literal>
1613 element matches zero or more strings.</para>
1614
1615 </section>
1616
1617
1618 <section>
1619 <title><literal>oneOrMore</literal> pattern</title>
1620
1621 <para>We use the following additional notation:</para>
1622
1623 <variablelist>
1624 <varlistentry><term><p:judgement name="disjoint">
1625       <p:var range="att" sub="1"/>
1626       <p:var range="att" sub="2"/>
1627     </p:judgement></term><listitem><para>
1628 asserts that there is no name that is
1629 the name of both an attribute in <p:var range="att" sub="1"/>
1630 and of an attribute in <p:var range="att" sub="2"/>
1631 </para></listitem></varlistentry>
1632 </variablelist>
1633
1634 <para>The semantics of the <literal>oneOrMore</literal> pattern are as follows:</para>
1635
1636 <p:proofSystem>
1637   <p:rule name="oneOrMore 1">
1638     <p:judgement name="match">
1639       <p:var range="context"/>
1640       <p:var range="att"/>
1641       <p:var range="mixed"/>
1642       <p:var range="pattern"/>
1643     </p:judgement>
1644
1645     <p:judgement name="match">
1646       <p:var range="context"/>
1647       <p:var range="att"/>
1648       <p:var range="mixed"/>
1649       <p:element name="oneOrMore">
1650         <p:var range="pattern"/>
1651       </p:element>
1652     </p:judgement>
1653   </p:rule>
1654
1655   <p:rule name="oneOrMore 2">
1656     <p:judgement name="match">
1657       <p:var range="context"/>
1658       <p:var range="att" sub="1"/>
1659       <p:var range="mixed" sub="1"/>
1660       <p:var range="pattern"/>
1661     </p:judgement>
1662
1663     <p:judgement name="match">
1664       <p:var range="context"/>
1665       <p:var range="att" sub="2"/>
1666       <p:var range="mixed" sub="2"/>
1667       <p:element name="oneOrMore">
1668         <p:var range="pattern"/>
1669       </p:element>
1670     </p:judgement>
1671
1672     <p:judgement name="disjoint">
1673       <p:var range="att" sub="1"/>
1674       <p:var range="att" sub="2"/>
1675     </p:judgement>
1676
1677     <p:judgement name="match">
1678       <p:var range="context"/>
1679       <p:function name="union">
1680         <p:var range="att" sub="1"/>
1681         <p:var range="att" sub="2"/>
1682       </p:function>
1683       <p:function name="append">
1684         <p:var range="mixed" sub="1"/>
1685         <p:var range="mixed" sub="2"/>
1686       </p:function>
1687       <p:element name="oneOrMore">
1688         <p:var range="pattern"/>
1689       </p:element>
1690     </p:judgement>
1691   </p:rule>
1692
1693 </p:proofSystem>
1694
1695 </section>
1696
1697
1698 <section>
1699 <title><literal>interleave</literal> pattern</title>
1700
1701 <para>We use the following additional notation:</para>
1702
1703 <variablelist>
1704 <varlistentry><term><p:judgement name="interleave">
1705       <p:var range="mixed" sub="1"/>
1706       <p:var range="mixed" sub="2"/>
1707       <p:var range="mixed" sub="3"/>
1708     </p:judgement></term><listitem><para>
1709
1710 asserts that <p:var range="mixed" sub="1"/>
1711 is an interleaving of <p:var range="mixed" sub="2"/>
1712 and <p:var range="mixed" sub="3"/>
1713 </para></listitem></varlistentry>
1714
1715 </variablelist>
1716
1717 <para>The semantics of interleaving are defined by the following rules.</para>
1718
1719
1720 <p:proofSystem>
1721   <p:rule name="interleaves 1">
1722
1723     <p:judgement name="interleave">
1724       <p:function name="emptySequence"/>
1725       <p:function name="emptySequence"/>
1726       <p:function name="emptySequence"/>
1727     </p:judgement>
1728
1729   </p:rule>
1730
1731   <p:rule name="interleaves 2">
1732
1733     <p:judgement name="interleave">
1734       <p:var range="mixed" sub="1"/>
1735       <p:var range="mixed" sub="2"/>
1736       <p:var range="mixed" sub="3"/>
1737     </p:judgement>
1738
1739     <p:judgement name="interleave">
1740       <p:function name="append">
1741         <p:var range="mixed" sub="4"/>
1742         <p:var range="mixed" sub="1"/>
1743       </p:function>
1744       <p:function name="append">
1745         <p:var range="mixed" sub="4"/>
1746         <p:var range="mixed" sub="2"/>
1747       </p:function>
1748       <p:var range="mixed" sub="3"/>
1749     </p:judgement>
1750
1751   </p:rule>
1752
1753   <p:rule name="interleaves 3">
1754
1755     <p:judgement name="interleave">
1756       <p:var range="mixed" sub="1"/>
1757       <p:var range="mixed" sub="2"/>
1758       <p:var range="mixed" sub="3"/>
1759     </p:judgement>
1760
1761     <p:judgement name="interleave">
1762       <p:function name="append">
1763         <p:var range="mixed" sub="4"/>
1764         <p:var range="mixed" sub="1"/>
1765       </p:function>
1766       <p:var range="mixed" sub="2"/>
1767       <p:function name="append">
1768         <p:var range="mixed" sub="4"/>
1769         <p:var range="mixed" sub="3"/>
1770       </p:function>
1771     </p:judgement>
1772
1773   </p:rule>
1774
1775 </p:proofSystem>
1776
1777 <para>For example, the interleavings of
1778 <literal><![CDATA[<a/><a/>]]></literal> and
1779 <literal><![CDATA[<b/>]]></literal> are
1780 <literal><![CDATA[<a/><a/><b/>]]></literal>,
1781 <literal><![CDATA[<a/><b/><a/>]]></literal>, and
1782 <literal><![CDATA[<b/><a/><a/>]]></literal>.</para>
1783
1784 <para>The semantics of the <literal>interleave</literal> pattern are
1785 as follows:</para>
1786
1787 <p:proofSystem>
1788   <p:rule name="interleave">
1789
1790     <p:judgement name="match">
1791       <p:var range="context"/>
1792       <p:var range="att" sub="1"/>
1793       <p:var range="mixed" sub="1"/>
1794       <p:var range="pattern" sub="1"/>
1795     </p:judgement>
1796
1797     <p:judgement name="match">
1798       <p:var range="context"/>
1799       <p:var range="att" sub="2"/>
1800       <p:var range="mixed" sub="2"/>
1801       <p:var range="pattern" sub="2"/>
1802     </p:judgement>
1803
1804     <p:judgement name="interleave">
1805       <p:var range="mixed" sub="3"/>
1806       <p:var range="mixed" sub="1"/>
1807       <p:var range="mixed" sub="2"/>
1808     </p:judgement>
1809
1810
1811     <p:judgement name="match">
1812       <p:var range="context"/>
1813       <p:function name="union">
1814         <p:var range="att" sub="1"/>
1815         <p:var range="att" sub="2"/>
1816       </p:function>
1817       <p:var range="mixed" sub="3"/>
1818       <p:element name="interleave">
1819         <p:var range="pattern" sub="1"/>
1820         <p:var range="pattern" sub="2"/>
1821       </p:element>
1822     </p:judgement>
1823
1824   </p:rule>
1825
1826 </p:proofSystem>
1827
1828 <note><para>The restriction in <xref linkend="attribute-restrictions"/>
1829 ensures that the set of attributes constructed in the consequent will
1830 not have multiple attributes with the same name.</para></note>
1831
1832 </section>
1833
1834 <section id="element-pattern">
1835 <title><literal>element</literal> and <literal>attribute</literal> pattern</title>
1836
1837 <para>The value of an attribute is always a single string, which may
1838 be empty.  Thus, the empty sequence is not a possible attribute value.
1839 On the hand, the children of an element can be an empty sequence and
1840 cannot consist of an empty string.  In order to ensure that validation
1841 handles attributes and elements consistently, we introduce a variant
1842 of matching called <firstterm>weak matching</firstterm>.  Weak
1843 matching is used when matching the pattern for the value of an
1844 attribute or for the attributes and children of an element.  We use
1845 the following notation to define weak matching.</para>
1846
1847 <variablelist>
1848
1849 <varlistentry><term><p:function
1850 name="emptyString"/></term><listitem><para>represents an empty
1851 string</para></listitem></varlistentry>
1852
1853 <varlistentry><term><p:var
1854 range="whiteSpace"/></term><listitem><para>ranges over the empty
1855 sequence and strings that consist entirely of
1856 whitespace</para></listitem></varlistentry>
1857
1858 <varlistentry><term><p:judgement name="weakMatch">
1859       <p:var range="context"/>
1860       <p:var range="att"/>
1861       <p:var range="mixed"/>
1862       <p:var range="pattern"/>
1863     </p:judgement></term><listitem><para>
1864
1865 asserts that with respect to context <p:var range="context"/>, the
1866 attributes <p:var range="att"/> and the sequence of elements and
1867 strings <p:var range="mixed"/> weakly matches the pattern <p:var
1868 range="pattern"/></para></listitem></varlistentry>
1869
1870 </variablelist>
1871
1872 <para>The semantics of weak matching are as follows:</para>
1873
1874 <p:proofSystem>
1875   <p:rule name="weak match 1">
1876     <p:judgement name="match">
1877       <p:var range="context"/>
1878       <p:var range="att"/>
1879       <p:var range="mixed"/>
1880       <p:var range="pattern"/>
1881     </p:judgement>
1882     <p:judgement name="weakMatch">
1883       <p:var range="context"/>
1884       <p:var range="att"/>
1885       <p:var range="mixed"/>
1886       <p:var range="pattern"/>
1887     </p:judgement>
1888   </p:rule>
1889   <p:rule name="weak match 2">
1890     <p:judgement name="match">
1891       <p:var range="context"/>
1892       <p:var range="att"/>
1893       <p:function name="emptySequence"/>
1894       <p:var range="pattern"/>
1895     </p:judgement>
1896     <p:judgement name="weakMatch">
1897       <p:var range="context"/>
1898       <p:var range="att"/>
1899       <p:var range="whiteSpace"/>
1900       <p:var range="pattern"/>
1901     </p:judgement>
1902   </p:rule>
1903   <p:rule name="weak match 3">
1904     <p:judgement name="match">
1905       <p:var range="context"/>
1906       <p:var range="att"/>
1907       <p:function name="emptyString"/>
1908       <p:var range="pattern"/>
1909     </p:judgement>
1910     <p:judgement name="weakMatch">
1911       <p:var range="context"/>
1912       <p:var range="att"/>
1913       <p:function name="emptySequence"/>
1914       <p:var range="pattern"/>
1915     </p:judgement>
1916   </p:rule>
1917 </p:proofSystem>
1918
1919 <para>We use the following additional notation:</para>
1920
1921 <variablelist>
1922
1923 <varlistentry><term><p:function name="attribute">
1924         <p:var range="name"/>
1925         <p:var range="string"/>
1926       </p:function></term><listitem><para>
1927
1928 constructs an attribute with name <p:var range="name"/>
1929 and value <p:var range="string"/>
1930 </para></listitem></varlistentry>
1931
1932 <varlistentry><term><p:function name="element">
1933         <p:var range="name"/>
1934         <p:var range="context"/>
1935         <p:var range="att"/>
1936         <p:var range="mixed"/>
1937       </p:function></term><listitem><para>
1938
1939 constructs an element with name <p:var range="name"/>,
1940 context <p:var range="context"/>,
1941 attributes <p:var range="att"/>
1942 and mixed sequence <p:var range="mixed"/> as children
1943 </para></listitem></varlistentry>
1944
1945 <varlistentry><term><p:judgement name="okAsChildren">
1946       <p:var range="mixed"/>
1947     </p:judgement></term><listitem><para>
1948
1949 asserts that the mixed sequence <p:var range="mixed"/> can occur as
1950 the children of an element: it does not contain any member that is an
1951 empty string, nor does it contain two consecutive members that are
1952 both strings</para></listitem></varlistentry>
1953
1954 <varlistentry><term><p:judgement name="bind">
1955       <p:var range="ncname"/>
1956       <p:var range="nameClass"/>
1957       <p:var range="pattern"/>
1958     </p:judgement></term><listitem><para>
1959
1960 asserts that the grammar contains
1961 <p:element name="define">
1962   <p:attribute name="name">
1963     <p:var range="ncname"/>
1964   </p:attribute>
1965   <p:element name="element">
1966      <p:var range="nameClass"/>
1967      <p:var range="pattern"/>
1968   </p:element>
1969 </p:element>
1970 </para></listitem></varlistentry>
1971
1972 </variablelist>
1973
1974 <para>The semantics of the <literal>attribute</literal> pattern are as follows:</para>
1975
1976 <p:proofSystem>
1977   <p:rule name="attribute">
1978
1979     <p:judgement name="weakMatch">
1980       <p:var range="context"/>
1981       <p:function name="emptySet"/>
1982       <p:var range="string"/>
1983       <p:var range="pattern"/>
1984     </p:judgement>
1985
1986     <p:judgement name="belongs">
1987       <p:var range="name"/>
1988       <p:var range="nameClass"/>
1989     </p:judgement>
1990
1991     <p:judgement name="match">
1992       <p:var range="context"/>
1993       <p:function name="attribute">
1994         <p:var range="name"/>
1995         <p:var range="string"/>
1996       </p:function>
1997       <p:function name="emptySequence"/>
1998       <p:element name="attribute">
1999         <p:var range="nameClass"/>
2000         <p:var range="pattern"/>
2001       </p:element>
2002     </p:judgement>
2003
2004   </p:rule>
2005
2006 </p:proofSystem>
2007
2008 <para>The semantics of the <literal>element</literal> pattern are as follows:</para>
2009
2010 <p:proofSystem>
2011   <p:rule name="element">
2012
2013     <p:judgement name="weakMatch">
2014       <p:var range="context" sub="1"/>
2015       <p:var range="att"/>
2016       <p:var range="mixed"/>
2017       <p:var range="pattern"/>
2018     </p:judgement>
2019
2020     <p:judgement name="belongs">
2021       <p:var range="name"/>
2022       <p:var range="nameClass"/>
2023     </p:judgement>
2024
2025     <p:judgement name="okAsChildren">
2026       <p:var range="mixed"/>
2027     </p:judgement>
2028
2029     <p:judgement name="bind">
2030       <p:var range="ncname"/>
2031       <p:var range="nameClass"/>
2032       <p:var range="pattern"/>
2033     </p:judgement>
2034
2035     <p:judgement name="match">
2036       <p:var range="context" sub="2"/>
2037       <p:function name="emptySet"/>
2038       <p:function name="append">
2039         <p:var range="whiteSpace" sub="1"/>
2040         <p:function name="element">
2041           <p:var range="name"/>
2042           <p:var range="context" sub="1"/>
2043           <p:var range="att"/>
2044           <p:var range="mixed"/>
2045         </p:function>
2046         <p:var range="whiteSpace" sub="2"/>
2047       </p:function>
2048       <p:element name="ref">
2049         <p:attribute name="name">
2050           <p:var range="ncname"/>
2051         </p:attribute>
2052       </p:element>
2053     </p:judgement>
2054
2055   </p:rule>
2056
2057 </p:proofSystem>
2058
2059
2060 </section>
2061
2062 <section id="data-pattern">
2063 <title><literal>data</literal> and <literal>value</literal> pattern</title>
2064
2065 <para>RELAX NG relies on datatype libraries to perform datatyping.
2066 A datatype library is identified by a URI.  A datatype within a
2067 datatype library is identified by an NCName.  A datatype library
2068 provides two services.</para>
2069
2070 <itemizedlist>
2071
2072 <listitem><para>It can determine whether a string is a legal
2073 representation of a datatype. This service accepts a list of zero or
2074 more parameters. For example, a string datatype might have a parameter
2075 specifying the length of a string.  The datatype library determines
2076 what parameters are applicable for each datatype.</para></listitem>
2077
2078 <listitem><para>It can determine whether two strings represent the
2079 same value of a datatype.  This service does not have any
2080 parameters.</para></listitem>
2081
2082 </itemizedlist>
2083
2084 <para>Both services may make use of the context of a string.  For
2085 example, a datatype representing a QName would use the namespace
2086 map.</para>
2087
2088 <para>We use the following additional notation:</para>
2089
2090 <variablelist>
2091 <varlistentry><term><p:judgement name="datatypeAllows">
2092       <p:var range="uri"/>
2093       <p:var range="ncname"/>
2094       <p:var range="params"/>
2095       <p:var range="string"/>
2096       <p:var range="context"/>
2097     </p:judgement></term><listitem><para>
2098
2099 asserts that in the datatype library identified by URI <p:var range="uri"/>, the string <p:var range="string"/> interpreted with
2100 context <p:var range="context"/> is a legal
2101 value of datatype <p:var range="ncname"/> with parameters <p:var range="params"/></para></listitem></varlistentry>
2102
2103 <varlistentry><term><p:judgement name="datatypeEqual">
2104       <p:var range="uri"/>
2105       <p:var range="ncname"/>
2106       <p:var range="string" sub="1"/>
2107       <p:var range="context" sub="1"/>
2108       <p:var range="string" sub="2"/>
2109       <p:var range="context" sub="2"/>
2110     </p:judgement></term><listitem><para>
2111
2112 asserts that in the datatype library identified by URI <p:var range="uri"/>, string <p:var range="string" sub="1"/> interpreted with
2113 context <p:var range="context" sub="1"/> represents the same value of
2114 the datatype <p:var range="ncname"/> as the string <p:var range="string" sub="2"/> interpreted in the context of <p:var range="context" sub="2"/>
2115 </para></listitem></varlistentry>
2116
2117 <varlistentry><term><p:var range="params"/></term><listitem><para>ranges over sequences of parameters</para></listitem></varlistentry>
2118
2119 <varlistentry><term><p:context>
2120      <p:var range="context"/>
2121    </p:context></term><listitem><para>
2122
2123 within the start-tag of a pattern refers to the context
2124 of the pattern element
2125 </para></listitem></varlistentry>
2126
2127 <varlistentry>
2128 <term>
2129   <p:function name="context">
2130      <p:var range="uri"/>
2131      <p:var range="context"/>
2132   </p:function>
2133 </term>
2134 <listitem><para>constructs a context which is the same as <p:var range="context"/>
2135 except that the default namespace is <p:var range="uri"/>; if <p:var
2136 range="uri"/> is the empty string, then there is no default namespace
2137 in the constructed context</para></listitem></varlistentry>
2138
2139 </variablelist>
2140
2141 <para>The datatypeEqual function must be reflexive, transitive
2142 and symmetric, that is, the following inference rules must hold:</para>
2143
2144 <p:proofSystem>
2145   <p:rule name="datatypeEqual reflexive">
2146     <p:judgement name="datatypeAllows">
2147       <p:var range="uri"/>
2148       <p:var range="ncname"/>
2149       <p:var range="params"/>
2150       <p:var range="string"/>
2151       <p:var range="context"/>
2152     </p:judgement>
2153     <p:judgement name="datatypeEqual">
2154       <p:var range="uri"/>
2155       <p:var range="ncname"/>
2156       <p:var range="string"/>
2157       <p:var range="context"/>
2158       <p:var range="string"/>
2159       <p:var range="context"/>
2160     </p:judgement>
2161   </p:rule>
2162   <p:rule name="datatypeEqual transitive">
2163     <p:judgement name="datatypeEqual">
2164       <p:var range="uri"/>
2165       <p:var range="ncname"/>
2166       <p:var range="string" sub="1"/>
2167       <p:var range="context" sub="1"/>
2168       <p:var range="string" sub="2"/>
2169       <p:var range="context" sub="2"/>
2170     </p:judgement>
2171     <p:judgement name="datatypeEqual">
2172       <p:var range="uri"/>
2173       <p:var range="ncname"/>
2174       <p:var range="string" sub="2"/>
2175       <p:var range="context" sub="3"/>
2176       <p:var range="string" sub="3"/>
2177       <p:var range="context" sub="3"/>
2178     </p:judgement>
2179     <p:judgement name="datatypeEqual">
2180       <p:var range="uri"/>
2181       <p:var range="ncname"/>
2182       <p:var range="string" sub="1"/>
2183       <p:var range="context" sub="1"/>
2184       <p:var range="string" sub="3"/>
2185       <p:var range="context" sub="3"/>
2186     </p:judgement>
2187   </p:rule>
2188   <p:rule name="datatypeEqual symmetric">
2189     <p:judgement name="datatypeEqual">
2190       <p:var range="uri"/>
2191       <p:var range="ncname"/>
2192       <p:var range="string" sub="1"/>
2193       <p:var range="context" sub="1"/>
2194       <p:var range="string" sub="2"/>
2195       <p:var range="context" sub="2"/>
2196     </p:judgement>
2197     <p:judgement name="datatypeEqual">
2198       <p:var range="uri"/>
2199       <p:var range="ncname"/>
2200       <p:var range="string" sub="2"/>
2201       <p:var range="context" sub="2"/>
2202       <p:var range="string" sub="1"/>
2203       <p:var range="context" sub="1"/>
2204     </p:judgement>
2205   </p:rule>
2206 </p:proofSystem>
2207
2208 <para>The semantics of the <literal>data</literal> and
2209 <literal>value</literal> patterns are as follows:</para>
2210
2211 <p:proofSystem>
2212   <p:rule name="value">
2213     <p:judgement name="datatypeEqual">
2214       <p:var range="uri" sub="1"/>
2215       <p:var range="ncname"/>
2216       <p:var range="string" sub="1"/>
2217       <p:var range="context" sub="1"/>
2218       <p:var range="string" sub="2"/>
2219       <p:function name="context">
2220         <p:var range="uri" sub="2"/>
2221         <p:var range="context" sub="2"/>
2222       </p:function>
2223     </p:judgement>
2224     <p:judgement name="match">
2225       <p:var range="context" sub="1"/>
2226       <p:function name="emptySet"/>
2227       <p:var range="string" sub="1"/>
2228       <p:element name="value">
2229         <p:attribute name="datatypeLibrary">
2230           <p:var range="uri" sub="1"/>
2231         </p:attribute>
2232         <p:attribute name="type">
2233           <p:var range="ncname"/>
2234         </p:attribute>
2235         <p:attribute name="ns">
2236           <p:var range="uri" sub="2"/>
2237         </p:attribute>
2238         <p:context>
2239           <p:var range="context" sub="2"/>
2240         </p:context>
2241         <p:var range="string" sub="2"/>
2242       </p:element>
2243       <p:function name="emptySet"/>
2244       <p:function name="emptySet"/>
2245     </p:judgement>
2246   </p:rule>
2247
2248   <p:rule name="data 1">
2249     <p:judgement name="datatypeAllows">
2250       <p:var range="uri"/>
2251       <p:var range="ncname"/>
2252       <p:var range="params"/>
2253       <p:var range="string"/>
2254       <p:var range="context"/>
2255     </p:judgement>
2256     <p:judgement name="match">
2257       <p:var range="context"/>
2258       <p:function name="emptySet"/>
2259       <p:var range="string"/>
2260       <p:element name="data">
2261         <p:attribute name="datatypeLibrary">
2262           <p:var range="uri"/>
2263         </p:attribute>
2264         <p:attribute name="type">
2265           <p:var range="ncname"/>
2266         </p:attribute>
2267         <p:var range="params"/>
2268       </p:element>
2269       <p:function name="emptySet"/>
2270       <p:function name="emptySet"/>
2271     </p:judgement>
2272   </p:rule>
2273
2274   <p:rule name="data 2">
2275     <p:judgement name="datatypeAllows">
2276       <p:var range="uri"/>
2277       <p:var range="ncname"/>
2278       <p:var range="params"/>
2279       <p:var range="string"/>
2280       <p:var range="context"/>
2281     </p:judgement>
2282     <p:not>
2283       <p:judgement name="match">
2284         <p:var range="context"/>
2285         <p:var range="att"/>
2286         <p:var range="string"/>
2287         <p:var range="pattern"/>
2288       </p:judgement>
2289     </p:not>
2290     <p:judgement name="match">
2291       <p:var range="context"/>
2292       <p:function name="emptySet"/>
2293       <p:var range="string"/>
2294       <p:element name="data">
2295         <p:attribute name="datatypeLibrary">
2296           <p:var range="uri"/>
2297         </p:attribute>
2298         <p:attribute name="type">
2299           <p:var range="ncname"/>
2300         </p:attribute>
2301         <p:var range="params"/>
2302         <p:element name="except">
2303           <p:var range="pattern"/>
2304         </p:element>
2305       </p:element>
2306       <p:function name="emptySet"/>
2307       <p:function name="emptySet"/>
2308     </p:judgement>
2309   </p:rule>
2310
2311 </p:proofSystem>
2312
2313 </section>
2314
2315 <section id="built-in-datatype">
2316 <title>Built-in datatype library</title>
2317
2318 <para>The empty URI identifies a special built-in datatype library.
2319 This provides two datatypes, <literal>string</literal> and
2320 <literal>token</literal>.  No parameters are allowed for either of
2321 these datatypes.</para>
2322
2323 <variablelist>
2324 <varlistentry><term>
2325     <p:judgement name="equal">
2326       <p:var range="string" sub="1"/>
2327       <p:var range="string" sub="2"/>
2328     </p:judgement></term>
2329 <listitem><para>asserts that <p:var range="string" sub="1"/>
2330 and <p:var range="string" sub="2"/> are identical</para></listitem>
2331 </varlistentry>
2332
2333 <varlistentry><term>
2334       <p:function name="normalizeWhiteSpace">
2335         <p:var range="string"/>
2336       </p:function>
2337 </term>
2338 <listitem><para>returns the string <p:var range="string"/>,
2339 with leading and trailing whitespace characters removed,
2340 and with each other maximal sequence of whitespace characters
2341 replaced by a single space character </para></listitem>
2342 </varlistentry>
2343 </variablelist>
2344
2345 <para>The semantics of the two built-in datatypes are as
2346 follows:</para>
2347
2348 <p:proofSystem>
2349
2350   <p:rule name="string allows">
2351     <p:judgement name="datatypeAllows">
2352       <p:function name="emptyString"/>
2353       <p:string>string</p:string>
2354       <p:function name="emptySequence"/>
2355       <p:var range="string"/>
2356       <p:var range="context"/>
2357     </p:judgement>
2358   </p:rule>
2359
2360   <p:rule name="string equal">
2361     <p:judgement name="datatypeEqual">
2362       <p:function name="emptyString"/>
2363       <p:string>string</p:string>
2364       <p:var range="string"/>
2365       <p:var range="context" sub="1"/>
2366       <p:var range="string"/>
2367       <p:var range="context" sub="2"/>
2368     </p:judgement>
2369   </p:rule>
2370
2371   <p:rule name="token allows">
2372     <p:judgement name="datatypeAllows">
2373       <p:function name="emptyString"/>
2374       <p:string>token</p:string>
2375       <p:function name="emptySequence"/>
2376       <p:var range="string"/>
2377       <p:var range="context"/>
2378     </p:judgement>
2379   </p:rule>
2380
2381   <p:rule name="token equal">
2382     <p:judgement name="equal">
2383       <p:function name="normalizeWhiteSpace">
2384         <p:var range="string" sub="1"/>
2385       </p:function>
2386       <p:function name="normalizeWhiteSpace">
2387         <p:var range="string" sub="2"/>
2388       </p:function>
2389     </p:judgement>
2390     <p:judgement name="datatypeEqual">
2391       <p:function name="emptyString"/>
2392       <p:string>token</p:string>
2393       <p:var range="string" sub="1"/>
2394       <p:var range="context" sub="1"/>
2395       <p:var range="string" sub="2"/>
2396       <p:var range="context" sub="2"/>
2397     </p:judgement>
2398   </p:rule>
2399
2400 </p:proofSystem>
2401
2402 </section>
2403
2404 <section>
2405 <title><literal>list</literal> pattern</title>
2406
2407 <para>We use the following additional notation:</para>
2408
2409 <variablelist>
2410 <varlistentry><term><p:function name="split">
2411         <p:var range="string"/>
2412       </p:function></term><listitem><para>
2413
2414 returns a sequence of strings one for each whitespace delimited token
2415 of <p:var range="string"/>; each string in the returned sequence will
2416 be non-empty and will not contain any
2417 whitespace</para></listitem></varlistentry>
2418
2419 </variablelist>
2420
2421 <para>The semantics of the <literal>list</literal> pattern are as follows:</para>
2422
2423 <p:proofSystem>
2424   <p:rule name="list">
2425
2426     <p:judgement name="match">
2427       <p:var range="context"/>
2428       <p:function name="emptySet"/>
2429       <p:function name="split">
2430         <p:var range="string"/>
2431       </p:function>
2432       <p:var range="pattern"/>
2433     </p:judgement>
2434
2435     <p:judgement name="match">
2436       <p:var range="context"/>
2437       <p:function name="emptySet"/>
2438       <p:var range="string"/>
2439       <p:element name="list">
2440         <p:var range="pattern"/>
2441       </p:element>
2442     </p:judgement>
2443
2444   </p:rule>
2445 </p:proofSystem>
2446
2447 <note><para>It is crucial in the above inference rule that the
2448 sequence that is matched against a pattern can contain consecutive
2449 strings.</para></note>
2450
2451 </section>
2452
2453 </section>
2454
2455 <section id="validity">
2456 <title>Validity</title>
2457
2458 <para>Now we can define when an element is valid with respect to a
2459 schema.  We use the following additional notation:</para>
2460
2461 <variablelist>
2462
2463 <varlistentry><term><p:var range="element"/></term><listitem><para>ranges over elements</para></listitem></varlistentry>
2464
2465 <varlistentry><term><p:judgement name="valid">
2466       <p:var range="element"/>
2467     </p:judgement></term><listitem><para>
2468
2469 asserts that the element <p:var range="element"/> is valid with
2470 respect to the grammar</para></listitem></varlistentry>
2471
2472 <varlistentry><term><p:judgement name="start">
2473       <p:var range="pattern"/>
2474     </p:judgement></term><listitem><para>
2475 asserts that the grammar contains
2476 <p:element name="start"><p:var range="pattern"/> </p:element></para></listitem></varlistentry>
2477
2478 </variablelist>
2479
2480 <para>An element is valid if together with an empty set of attributes
2481 it matches the <literal>start</literal> pattern of the grammar.</para>
2482
2483 <p:proofSystem>
2484   <p:rule name="valid">
2485     <p:judgement name="start">
2486       <p:var range="pattern"/>
2487     </p:judgement>
2488     <p:judgement name="match">
2489       <p:var range="context"/>
2490       <p:function name="emptySet"/>
2491       <p:var range="element"/>
2492       <p:var range="pattern"/>
2493     </p:judgement>
2494     <p:judgement name="valid">
2495       <p:var range="element"/>
2496     </p:judgement>
2497   </p:rule>
2498
2499
2500 </p:proofSystem>
2501
2502 </section>
2503
2504 <section>
2505 <title>Example</title>
2506
2507 <para>Let <p:var range="element" sub="0"/> be</para>
2508
2509 <p:formula>
2510
2511 <p:function name="element">
2512   <p:function name="name">
2513     <p:function name="emptyString"/>
2514     <p:string>foo</p:string>
2515   </p:function>
2516   <p:var range="context" sub="0"/>
2517   <p:function name="emptySet"/>
2518   <p:var range="mixed"/>
2519 </p:function>
2520
2521 </p:formula>
2522
2523 <para>where <p:var range="mixed"/> is</para>
2524
2525 <p:formula>
2526   <p:function name="append">
2527     <p:var range="element" sub="1"/>
2528     <p:var range="element" sub="2"/>
2529   </p:function>
2530 </p:formula>
2531
2532 <para>and <p:var range="element" sub="1"/> is</para>
2533
2534 <p:formula>
2535   <p:function name="element">
2536     <p:function name="name">
2537       <p:string>http://www.example.com/n1</p:string>
2538       <p:string>bar1</p:string>
2539     </p:function>
2540     <p:var range="context" sub="1"/>
2541     <p:function name="emptySet"/>
2542     <p:function name="emptySequence"/>
2543   </p:function>
2544 </p:formula>
2545
2546 <para>and <p:var range="element" sub="2"/> is</para>
2547
2548 <p:formula>
2549   <p:function name="element">
2550     <p:function name="name">
2551       <p:string>http://www.example.com/n2</p:string>
2552       <p:string>bar2</p:string>
2553     </p:function>
2554     <p:var range="context" sub="2"/>
2555     <p:function name="emptySet"/>
2556     <p:function name="emptySequence"/>
2557   </p:function>
2558 </p:formula>
2559
2560 <para>Assuming appropriate definitions of <p:var range="context"
2561 sub="0"/>, <p:var range="context" sub="1"/> and <p:var range="context"
2562 sub="2"/>, this represents the document in <xref
2563 linkend="data-model-example"/>.</para>
2564
2565 <para>We now show how <p:var range="element" sub="0"/> can be shown to
2566 be valid with respect to the schema in <xref
2567 linkend="simple-syntax-example"/>.  The schema is equivalent to the
2568 following propositions:</para>
2569
2570 <p:formula>
2571   <p:judgement name="start">
2572     <p:element name="ref">
2573       <p:attribute name="name"><p:string>foo</p:string></p:attribute>
2574     </p:element>
2575   </p:judgement>
2576 </p:formula>
2577
2578 <p:formula>
2579   <p:judgement name="bind">
2580     <p:string>foo.element</p:string>
2581     <p:element name="name">
2582       <p:attribute name="ns"><p:function name="emptyString"/></p:attribute>
2583       <p:string>foo</p:string>
2584     </p:element>
2585     <p:element name="group">
2586       <p:element name="ref">
2587         <p:attribute name="name">
2588           <p:string>bar1</p:string>
2589         </p:attribute>
2590       </p:element>
2591       <p:element name="ref">
2592         <p:attribute name="name">
2593           <p:string>bar2</p:string>
2594         </p:attribute>
2595       </p:element>
2596     </p:element>
2597   </p:judgement>
2598 </p:formula>
2599
2600 <p:formula>
2601   <p:judgement name="bind">
2602     <p:string>bar1.element</p:string>
2603     <p:element name="name">
2604       <p:attribute name="ns">
2605         <p:string>http://www.example.com/n1</p:string>
2606       </p:attribute>
2607       <p:string>bar1</p:string>
2608     </p:element>
2609     <p:element name="empty"/>
2610   </p:judgement>
2611 </p:formula>
2612
2613 <p:formula>
2614   <p:judgement name="bind">
2615     <p:string>bar2.element</p:string>
2616     <p:element name="name">
2617       <p:attribute name="ns">
2618         <p:string>http://www.example.com/n2</p:string>
2619       </p:attribute>
2620       <p:string>bar2</p:string>
2621     </p:element>
2622     <p:element name="empty"/>
2623   </p:judgement>
2624 </p:formula>
2625
2626
2627 <para>Let name class <p:var range="nameClass" sub="1"/> be</para>
2628
2629 <p:formula>
2630   <p:element name="name">
2631     <p:attribute name="ns">
2632       <p:string>http://www.example.com/n1</p:string>
2633     </p:attribute>
2634     <p:string>bar1</p:string>
2635   </p:element>
2636 </p:formula>
2637
2638 <para>and let <p:var range="nameClass" sub="2"/> be</para>
2639
2640 <p:formula>
2641   <p:element name="name">
2642     <p:attribute name="ns">
2643       <p:string>http://www.example.com/n2</p:string>
2644     </p:attribute>
2645     <p:string>bar2</p:string>
2646   </p:element>
2647 </p:formula>
2648
2649 <para>Then, by the inference rule (name) in <xref
2650 linkend="name-classes"/>, we have</para>
2651
2652 <p:formula>
2653   <p:judgement name="belongs">
2654     <p:function name="name">
2655       <p:string>http://www.example.com/n1</p:string>
2656       <p:string>bar1</p:string>
2657     </p:function>
2658     <p:var range="nameClass" sub="1"/>
2659   </p:judgement>
2660 </p:formula>
2661
2662 <para>and</para>
2663
2664 <p:formula>
2665   <p:judgement name="belongs">
2666     <p:function name="name">
2667       <p:string>http://www.example.com/n2</p:string>
2668       <p:string>bar2</p:string>
2669     </p:function>
2670     <p:var range="nameClass" sub="2"/>
2671   </p:judgement>
2672 </p:formula>
2673
2674
2675 <para>By the inference rule (empty) in <xref linkend="empty-pattern"/>,
2676 we have</para>
2677
2678 <p:formula>
2679   <p:judgement name="match">
2680     <p:var range="context" sub="1"/>
2681     <p:function name="emptySet"/>
2682     <p:function name="emptySequence"/>
2683     <p:element name="empty"></p:element>
2684   </p:judgement>
2685 </p:formula>
2686
2687 <para>and</para>
2688
2689 <p:formula>
2690   <p:judgement name="match">
2691     <p:var range="context" sub="2"/>
2692     <p:function name="emptySet"/>
2693     <p:function name="emptySequence"/>
2694     <p:element name="empty"></p:element>
2695   </p:judgement>
2696 </p:formula>
2697
2698 <para>Thus by the inference rule (element) in <xref
2699 linkend="element-pattern"/>, we have</para>
2700
2701 <p:formula>
2702   <p:judgement name="match">
2703     <p:var range="context" sub="0"/>
2704     <p:function name="emptySet"/>
2705     <p:var range="element" sub="1"/>
2706     <p:element name="ref">
2707       <p:attribute name="name">
2708         <p:string>bar1</p:string>
2709       </p:attribute>
2710     </p:element>
2711   </p:judgement>
2712 </p:formula>
2713
2714 <para>Note that we have chosen <p:var
2715 range="context" sub="0"/>, since any context is allowed.</para>
2716
2717 <para>Likewise, we have</para>
2718
2719 <p:formula>
2720   <p:judgement name="match">
2721     <p:var range="context" sub="0"/>
2722     <p:function name="emptySet"/>
2723     <p:var range="element" sub="2"/>
2724     <p:element name="ref">
2725       <p:attribute name="name">
2726         <p:string>bar2</p:string>
2727       </p:attribute>
2728     </p:element>
2729   </p:judgement>
2730 </p:formula>
2731
2732 <para>By the inference rule (group) in <xref
2733 linkend="choice-pattern"/>, we have</para>
2734
2735 <p:formula>
2736   <p:judgement name="match">
2737     <p:var range="context" sub="0"/>
2738     <p:function name="emptySet"/>
2739     <p:function name="append">
2740       <p:var range="element" sub="1"/>
2741       <p:var range="element" sub="2"/>
2742     </p:function>
2743     <p:element name="group">
2744       <p:element name="ref">
2745         <p:attribute name="name">
2746           <p:string>bar1</p:string>
2747         </p:attribute>
2748       </p:element>
2749       <p:element name="ref">
2750         <p:attribute name="name">
2751           <p:string>bar2</p:string>
2752         </p:attribute>
2753       </p:element>
2754     </p:element>
2755   </p:judgement>
2756 </p:formula>
2757
2758 <para>By the inference rule (element) in <xref
2759 linkend="element-pattern"/>, we have</para>
2760
2761 <p:formula>
2762   <p:judgement name="match">
2763     <p:var range="context" sub="3"/>
2764     <p:function name="emptySet"/>
2765     <p:function name="element">
2766       <p:function name="name">
2767         <p:function name="emptyString"/>
2768         <p:string>foo</p:string>
2769       </p:function>
2770       <p:var range="context" sub="0"/>
2771       <p:function name="emptySet"/>
2772       <p:var range="mixed"/>
2773     </p:function>
2774     <p:element name="ref">
2775       <p:attribute name="name">
2776         <p:string>foo</p:string>
2777       </p:attribute>
2778     </p:element>
2779   </p:judgement>
2780 </p:formula>
2781
2782 <para>Here <p:var range="context" sub="3"/> is an arbitrary
2783 context.</para>
2784
2785 <para>Thus we can apply the inference rule (valid) in <xref
2786 linkend="validity"/> and obtain</para>
2787
2788 <p:formula>
2789   <p:judgement name="valid">
2790     <p:var range="element" sub="0"/>
2791   </p:judgement>
2792 </p:formula>
2793
2794 </section>
2795
2796 </section>
2797
2798 <section id="restriction">
2799 <title>Restrictions</title>
2800
2801 <para>The following constraints are all checked after the grammar has
2802 been transformed to the simple form described in <xref
2803 linkend="simple-syntax"/>. The purpose of these restrictions is to
2804 catch user errors and to facilitate implementation.</para>
2805
2806 <section id="contextual-restriction">
2807 <title>Contextual restrictions</title>
2808
2809 <para>In this section we describe restrictions on where elements are
2810 allowed in the schema based on the names of the ancestor elements. We
2811 use the concept of a <firstterm>prohibited path</firstterm> to
2812 describe these restrictions. A path is a sequence of NCNames separated
2813 by <literal>/</literal> or <literal>//</literal>.</para>
2814
2815 <itemizedlist>
2816
2817 <listitem><para>An element matches a path
2818 <replaceable>x</replaceable>, where <replaceable>x</replaceable> is an
2819 NCName, if and only if the local name of the element is
2820 <replaceable>x</replaceable></para></listitem>
2821
2822 <listitem><para>An element matches a path
2823 <replaceable>x</replaceable><literal>/</literal><replaceable>p</replaceable>,
2824 where <replaceable>x</replaceable> is an NCName and
2825 <replaceable>p</replaceable> is a path, if and only if the local name
2826 of the element is <replaceable>x</replaceable> and the element has a
2827 child that matches <replaceable>p</replaceable></para></listitem>
2828
2829 <listitem><para>An element matches a path
2830 <replaceable>x</replaceable><literal>//</literal><replaceable>p</replaceable>,
2831 where <replaceable>x</replaceable> is an NCName and
2832 <replaceable>p</replaceable> is a path, if and only if the local name
2833 of the element is <replaceable>x</replaceable> and the element has a
2834 descendant that matches <replaceable>p</replaceable></para></listitem>
2835
2836 </itemizedlist>
2837
2838 <para>For example, the element</para>
2839
2840 <programlisting><![CDATA[<foo>
2841   <bar>
2842     <baz/>
2843   </bar>
2844 </foo>]]></programlisting>
2845
2846 <para>matches the paths <literal>foo</literal>,
2847 <literal>foo/bar</literal>, <literal>foo//bar</literal>,
2848 <literal>foo//baz</literal>, <literal>foo/bar/baz</literal>,
2849 <literal>foo/bar//baz</literal> and <literal>foo//bar/baz</literal>,
2850 but not <literal>foo/baz</literal> or
2851 <literal>foobar</literal>.</para>
2852
2853 <para>A correct RELAX NG schema must be such that, after
2854 transformation to the simple form, it does not contain any element
2855 that matches a prohibited path.</para>
2856
2857 <section>
2858 <title><literal>attribute</literal> pattern</title>
2859
2860 <para>The following paths are prohibited:</para>
2861
2862 <itemizedlist>
2863 <listitem><para><literal>attribute//ref</literal></para></listitem>
2864 <listitem><para><literal>attribute//attribute</literal></para></listitem>
2865 </itemizedlist>
2866
2867 </section>
2868
2869 <section>
2870 <title><literal>oneOrMore</literal> pattern</title>
2871
2872 <para>The following paths are prohibited:</para>
2873
2874 <itemizedlist>
2875 <listitem><para><literal>oneOrMore//group//attribute</literal></para></listitem>
2876 <listitem><para><literal>oneOrMore//interleave//attribute</literal></para></listitem>
2877 </itemizedlist>
2878
2879 </section>
2880
2881 <section id="list-restrictions">
2882 <title><literal>list</literal> pattern</title>
2883
2884 <para>The following paths are prohibited:</para>
2885
2886 <itemizedlist>
2887 <listitem><para><literal>list//list</literal></para></listitem>
2888 <listitem><para><literal>list//ref</literal></para></listitem>
2889 <listitem><para><literal>list//attribute</literal></para></listitem>
2890 <listitem><para><literal>list//text</literal></para></listitem>
2891 <listitem><para><literal>list//interleave</literal></para></listitem>
2892 </itemizedlist>
2893 </section>
2894
2895 <section id="context-data-except">
2896 <title><literal>except</literal> in <literal>data</literal> pattern</title>
2897
2898 <para>The following paths are prohibited:</para>
2899
2900 <itemizedlist>
2901 <listitem><para><literal>data/except//attribute</literal></para></listitem>
2902 <listitem><para><literal>data/except//ref</literal></para></listitem>
2903 <listitem><para><literal>data/except//text</literal></para></listitem>
2904 <listitem><para><literal>data/except//list</literal></para></listitem>
2905 <listitem><para><literal>data/except//group</literal></para></listitem>
2906 <listitem><para><literal>data/except//interleave</literal></para></listitem>
2907 <listitem><para><literal>data/except//oneOrMore</literal></para></listitem>
2908 <listitem><para><literal>data/except//empty</literal></para></listitem>
2909 </itemizedlist>
2910
2911 <note><para>This implies that an <literal>except</literal> element
2912 with a <literal>data</literal> parent can contain only
2913 <literal>data</literal>, <literal>value</literal> and
2914 <literal>choice</literal> elements.</para></note>
2915
2916 </section>
2917
2918 <section id="context-start">
2919 <title><literal>start</literal> element</title>
2920
2921 <para>The following paths are prohibited:</para>
2922
2923 <itemizedlist>
2924 <listitem><para><literal>start//attribute</literal></para></listitem>
2925 <listitem><para><literal>start//data</literal></para></listitem>
2926 <listitem><para><literal>start//value</literal></para></listitem>
2927 <listitem><para><literal>start//text</literal></para></listitem>
2928 <listitem><para><literal>start//list</literal></para></listitem>
2929 <listitem><para><literal>start//group</literal></para></listitem>
2930 <listitem><para><literal>start//interleave</literal></para></listitem>
2931 <listitem><para><literal>start//oneOrMore</literal></para></listitem>
2932 <listitem><para><literal>start//empty</literal></para></listitem>
2933 </itemizedlist>
2934 </section>
2935
2936 </section>
2937
2938 <section id="string-sequences">
2939 <title>String sequences</title>
2940
2941 <para>RELAX NG does not allow a pattern such as:</para>
2942
2943 <programlisting><![CDATA[<element name="foo">
2944   <group>
2945     <data type="int"/>
2946     <element name="bar">
2947       <empty/>
2948     </element>
2949   </group>
2950 </element>]]></programlisting>
2951
2952 <para>Nor does it allow a pattern such as:</para>
2953
2954 <programlisting><![CDATA[<element name="foo">
2955   <group>
2956     <data type="int"/>
2957     <text/>
2958   </group>
2959 </element>]]></programlisting>
2960
2961 <para>More generally, if the pattern for the content of an element or
2962 attribute contains</para>
2963
2964 <itemizedlist>
2965
2966 <listitem><para>a pattern that can match a child
2967 (that is, an <literal>element</literal>, <literal>data</literal>,
2968 <literal>value</literal>, <literal>list</literal> or
2969 <literal>text</literal> pattern), and</para></listitem>
2970
2971 <listitem><para>a pattern that matches a single string (that is, a
2972 <literal>data</literal>, <literal>value</literal> or
2973 <literal>list</literal> pattern),</para></listitem>
2974
2975 </itemizedlist>
2976
2977 <para>then the two patterns must be alternatives to each other.</para>
2978
2979 <para>This rule does not apply to patterns occurring within a
2980 <literal>list</literal> pattern.</para>
2981
2982 <para>To formalize this, we use the concept of a content-type.  A
2983 pattern that is allowable as the content of an element has one of
2984 three content-types: empty, complex and simple.  We use the following
2985 notation.</para>
2986
2987 <variablelist>
2988
2989 <varlistentry>
2990 <term><p:function name="empty"/></term>
2991 <listitem><para>returns the empty content-type</para></listitem>
2992 </varlistentry>
2993
2994 <varlistentry>
2995 <term><p:function name="complex"/></term>
2996 <listitem><para>returns the complex content-type</para></listitem>
2997 </varlistentry>
2998
2999 <varlistentry>
3000 <term><p:function name="simple"/></term>
3001 <listitem><para>returns the simple content-type</para></listitem>
3002 </varlistentry>
3003
3004 <varlistentry><term><p:var range="contentType"/></term>
3005 <listitem><para>ranges over content-types</para></listitem>
3006 </varlistentry>
3007
3008 <varlistentry><term>
3009   <p:judgement name="groupable">
3010     <p:var range="contentType" sub="1"/>
3011     <p:var range="contentType" sub="2"/>
3012   </p:judgement>
3013 </term>
3014 <listitem><para>asserts that the content-types <p:var
3015 range="contentType" sub="1"/> and <p:var range="contentType" sub="2"/>
3016 are groupable</para></listitem>
3017 </varlistentry>
3018
3019 </variablelist>
3020
3021 <para>The empty content-type is groupable with anything.  In addition,
3022 the complex content-type is groupable with the complex content-type. The
3023 following rules formalize this.</para>
3024
3025 <p:proofSystem>
3026 <p:rule name="group empty 1">
3027   <p:judgement name="groupable">
3028     <p:function name="empty"/>
3029     <p:var range="contentType"/>
3030   </p:judgement>
3031 </p:rule>
3032 <p:rule name="group empty 2">
3033   <p:judgement name="groupable">
3034     <p:var range="contentType"/>
3035     <p:function name="empty"/>
3036   </p:judgement>
3037 </p:rule>
3038 <p:rule name="group complex">
3039   <p:judgement name="groupable">
3040     <p:function name="complex"/>
3041     <p:function name="complex"/>
3042   </p:judgement>
3043 </p:rule>
3044 </p:proofSystem>
3045
3046 <para>Some patterns have a content-type. We use the following
3047 additional notation.</para>
3048
3049 <variablelist>
3050
3051 <varlistentry><term>
3052   <p:judgement name="contentType">
3053     <p:var range="pattern"/>
3054     <p:var range="contentType"/>
3055   </p:judgement>
3056 </term>
3057 <listitem><para>asserts that pattern <p:var range="pattern"/> has
3058 content-type <p:var range="contentType"/></para></listitem>
3059 </varlistentry>
3060
3061 <varlistentry><term>
3062   <p:function name="max">
3063     <p:var range="contentType" sub="1"/>
3064     <p:var range="contentType" sub="2"/>
3065   </p:function>
3066 </term>
3067 <listitem><para>returns the maximum of <p:var range="contentType"
3068 sub="1"/> and <p:var range="contentType" sub="2"/> where the
3069 content-types in increasing order are <p:function name="empty"/>,
3070 <p:function name="complex"/>, <p:function
3071 name="simple"/></para></listitem>
3072 </varlistentry>
3073
3074 </variablelist>
3075
3076 <para>The following rules define when a pattern has a content-type and,
3077 if so, what it is.</para>
3078
3079 <p:proofSystem>
3080 <p:rule name="value">
3081   <p:judgement name="contentType">
3082     <p:element name="value">
3083       <p:attribute name="datatypeLibrary">
3084         <p:var range="uri" sub="1"/>
3085       </p:attribute>
3086       <p:attribute name="type">
3087         <p:var range="ncname"/>
3088       </p:attribute>
3089       <p:attribute name="ns">
3090         <p:var range="uri" sub="2"/>
3091       </p:attribute>
3092       <p:var range="string"/>
3093     </p:element>
3094     <p:function name="simple"/>
3095   </p:judgement>
3096 </p:rule>
3097
3098 <p:rule name="data 1">
3099   <p:judgement name="contentType">
3100     <p:element name="data">
3101       <p:attribute name="datatypeLibrary">
3102         <p:var range="uri"/>
3103       </p:attribute>
3104       <p:attribute name="type">
3105         <p:var range="ncname"/>
3106       </p:attribute>
3107       <p:var range="params"/>
3108     </p:element>
3109     <p:function name="simple"/>
3110   </p:judgement>
3111 </p:rule>
3112
3113 <p:rule name="data 2">
3114   <p:judgement name="contentType">
3115     <p:var range="pattern"/>
3116     <p:var range="contentType"/>
3117   </p:judgement>
3118   <p:judgement name="contentType">
3119     <p:element name="data">
3120       <p:attribute name="datatypeLibrary">
3121         <p:var range="uri"/>
3122       </p:attribute>
3123       <p:attribute name="type">
3124         <p:var range="ncname"/>
3125       </p:attribute>
3126       <p:var range="params"/>
3127       <p:element name="except">
3128         <p:var range="pattern"/>
3129       </p:element>
3130     </p:element>
3131     <p:function name="simple"/>
3132   </p:judgement>
3133 </p:rule>
3134
3135 <p:rule name="list">
3136   <p:judgement name="contentType">
3137     <p:element name="list">
3138       <p:var range="pattern"/>
3139     </p:element>
3140     <p:function name="simple"/>
3141   </p:judgement>
3142 </p:rule>
3143
3144 <p:rule name="text">
3145   <p:judgement name="contentType">
3146     <p:element name="text"/>
3147     <p:function name="complex"/>
3148   </p:judgement>
3149 </p:rule>
3150
3151 <p:rule name="ref">
3152   <p:judgement name="contentType">
3153     <p:element name="ref">
3154       <p:attribute name="name">
3155         <p:var range="ncname"/>
3156       </p:attribute>
3157     </p:element>
3158     <p:function name="complex"/>
3159   </p:judgement>
3160 </p:rule>
3161
3162 <p:rule name="empty">
3163   <p:judgement name="contentType">
3164     <p:element name="empty"/>
3165     <p:function name="empty"/>
3166   </p:judgement>
3167 </p:rule>
3168
3169 <p:rule name="attribute">
3170   <p:judgement name="contentType">
3171     <p:var range="pattern"/>
3172     <p:var range="contentType"/>
3173   </p:judgement>
3174   <p:judgement name="contentType">
3175     <p:element name="attribute">
3176       <p:var range="nameClass"/>
3177       <p:var range="pattern"/>
3178     </p:element>
3179     <p:function name="empty"/>
3180   </p:judgement>
3181 </p:rule>
3182
3183 <p:rule name="group">
3184   <p:judgement name="contentType">
3185     <p:var range="pattern" sub="1"/>
3186     <p:var range="contentType" sub="1"/>
3187   </p:judgement>
3188   <p:judgement name="contentType">
3189     <p:var range="pattern" sub="2"/>
3190     <p:var range="contentType" sub="2"/>
3191   </p:judgement>
3192   <p:judgement name="groupable">
3193     <p:var range="contentType" sub="1"/>
3194     <p:var range="contentType" sub="2"/>
3195   </p:judgement>
3196   <p:judgement name="contentType">
3197     <p:element name="group">
3198       <p:var range="pattern" sub="1"/>
3199       <p:var range="pattern" sub="2"/>
3200     </p:element>
3201     <p:function name="max">
3202       <p:var range="contentType" sub="1"/>
3203       <p:var range="contentType" sub="2"/>
3204     </p:function>
3205   </p:judgement>
3206 </p:rule>
3207
3208 <p:rule name="interleave">
3209   <p:judgement name="contentType">
3210     <p:var range="pattern" sub="1"/>
3211     <p:var range="contentType" sub="1"/>
3212   </p:judgement>
3213   <p:judgement name="contentType">
3214     <p:var range="pattern" sub="2"/>
3215     <p:var range="contentType" sub="2"/>
3216   </p:judgement>
3217   <p:judgement name="groupable">
3218     <p:var range="contentType" sub="1"/>
3219     <p:var range="contentType" sub="2"/>
3220   </p:judgement>
3221   <p:judgement name="contentType">
3222     <p:element name="interleave">
3223       <p:var range="pattern" sub="1"/>
3224       <p:var range="pattern" sub="2"/>
3225     </p:element>
3226     <p:function name="max">
3227       <p:var range="contentType" sub="1"/>
3228       <p:var range="contentType" sub="2"/>
3229     </p:function>
3230   </p:judgement>
3231 </p:rule>
3232
3233 <p:rule name="oneOrMore">
3234   <p:judgement name="contentType">
3235     <p:var range="pattern"/>
3236     <p:var range="contentType"/>
3237   </p:judgement>
3238   <p:judgement name="groupable">
3239     <p:var range="contentType"/>
3240     <p:var range="contentType"/>
3241   </p:judgement>
3242   <p:judgement name="contentType">
3243     <p:element name="oneOrMore">
3244       <p:var range="pattern"/>
3245     </p:element>
3246     <p:var range="contentType"/>
3247   </p:judgement>
3248 </p:rule>
3249
3250 <p:rule name="choice">
3251   <p:judgement name="contentType">
3252     <p:var range="pattern" sub="1"/>
3253     <p:var range="contentType" sub="1"/>
3254   </p:judgement>
3255   <p:judgement name="contentType">
3256     <p:var range="pattern" sub="2"/>
3257     <p:var range="contentType" sub="2"/>
3258   </p:judgement>
3259   <p:judgement name="contentType">
3260     <p:element name="choice">
3261       <p:var range="pattern" sub="1"/>
3262       <p:var range="pattern" sub="2"/>
3263     </p:element>
3264     <p:function name="max">
3265       <p:var range="contentType" sub="1"/>
3266       <p:var range="contentType" sub="2"/>
3267     </p:function>
3268   </p:judgement>
3269 </p:rule>
3270
3271 </p:proofSystem>
3272
3273 <note><para>The antecedent in the (data 2) rule above is in fact
3274 redundant because of the prohibited paths in <xref
3275 linkend="context-data-except"/>.</para></note>
3276
3277 <para>Now we can describe the restriction. We use the following
3278 notation.</para>
3279
3280 <variablelist>
3281
3282 <varlistentry><term>
3283   <p:judgement name="incorrectSchema"/>
3284 </term>
3285 <listitem><para>asserts that the schema is incorrect</para></listitem>
3286 </varlistentry>
3287
3288 </variablelist>
3289
3290 <para>All patterns occurring as the content of an element pattern must
3291 have a content-type.</para>
3292
3293 <p:proofSystem>
3294
3295 <p:rule name="element">
3296   <p:judgement name="bind">
3297     <p:var range="ncname"/>
3298     <p:var range="nameClass"/>
3299     <p:var range="pattern"/>
3300   </p:judgement>
3301   <p:not>
3302     <p:judgement name="contentType">
3303       <p:var range="pattern"/>
3304       <p:var range="contentType"/>
3305     </p:judgement>
3306   </p:not>
3307   <p:judgement name="incorrectSchema"/>
3308 </p:rule>
3309
3310 </p:proofSystem>
3311
3312 </section>
3313
3314 <section id="attribute-restrictions">
3315 <title>Restrictions on attributes</title>
3316
3317 <para>Duplicate attributes are not allowed.  More precisely, for a
3318 pattern <literal>&lt;group> <replaceable>p1</replaceable>
3319 <replaceable>p2</replaceable> &lt;/group></literal> or
3320 <literal>&lt;interleave> <replaceable>p1</replaceable>
3321 <replaceable>p2</replaceable> &lt;/interleave></literal>, there must
3322 not be a name that belongs to both the name class of an
3323 <literal>attribute</literal> pattern occurring in
3324 <replaceable>p1</replaceable> and the name class of an
3325 <literal>attribute</literal> pattern occurring in
3326 <replaceable>p2</replaceable>. A pattern <replaceable>p1</replaceable>
3327 is defined to <firstterm>occur in</firstterm> a pattern
3328 <replaceable>p2</replaceable> if</para>
3329
3330 <itemizedlist>
3331
3332 <listitem><para><replaceable>p1</replaceable> is
3333 <replaceable>p2</replaceable>, or</para></listitem>
3334
3335 <listitem><para><replaceable>p2</replaceable> is a
3336 <literal>choice</literal>, <literal>interleave</literal>,
3337 <literal>group</literal> or <literal>oneOrMore</literal> element and
3338 <replaceable>p1</replaceable> occurs in one or more children of
3339 <replaceable>p2</replaceable>.</para></listitem>
3340
3341 </itemizedlist>
3342
3343 <para>Attributes using infinite name classes must be repeated.  More
3344 precisely, an <literal>attribute</literal> element that has an
3345 <literal>anyName</literal> or <literal>nsName</literal> descendant
3346 element must have a <literal>oneOrMore</literal> ancestor
3347 element.</para>
3348
3349 <note><para>This restriction is necessary for closure under
3350 negation.</para></note>
3351
3352 </section>
3353
3354 <section id="interleave-restrictions">
3355 <title>Restrictions on <literal>interleave</literal></title>
3356
3357 <para>For a pattern <literal>&lt;interleave>
3358 <replaceable>p1</replaceable> <replaceable>p2</replaceable>
3359 &lt;/interleave></literal>,</para>
3360
3361 <itemizedlist>
3362
3363 <listitem><para>there must not be a name that belongs to both the name
3364 class of an <literal>element</literal> pattern referenced by a
3365 <literal>ref</literal> pattern occurring in
3366 <replaceable>p1</replaceable> and the name class of an
3367 <literal>element</literal> pattern referenced by a
3368 <literal>ref</literal> pattern occurring in
3369 <replaceable>p2</replaceable>, and</para></listitem>
3370
3371 <listitem><para>a <literal>text</literal> pattern must not occur in
3372 both <replaceable>p1</replaceable> and
3373 <replaceable>p2</replaceable>.</para></listitem>
3374
3375 </itemizedlist>
3376
3377 <para><xref linkend="attribute-restrictions"/> defines when one
3378 pattern is considered to occur in another pattern.</para>
3379
3380 </section>
3381
3382 </section>
3383
3384 <section id="conformance">
3385 <title>Conformance</title>
3386
3387 <para>A conforming RELAX NG validator must be able to determine for
3388 any XML document whether it is a correct RELAX NG schema.  A
3389 conforming RELAX NG validator must be able to determine for any XML
3390 document and for any correct RELAX NG schema whether the document is
3391 valid with respect to the schema.</para>
3392
3393 <para>However, the requirements in the preceding paragraph do not
3394 apply if the schema uses a datatype library that the validator does
3395 not support.  A conforming RELAX NG validator is only required to
3396 support the built-in datatype library described in <xref
3397 linkend="built-in-datatype"/>.  A validator that claims conformance to
3398 RELAX NG should document which datatype libraries it supports.  The
3399 requirements in the preceding paragraph also do not apply if the
3400 schema includes <literal>externalRef</literal> or
3401 <literal>include</literal> elements and the validator is unable to
3402 retrieve the resource identified by the URI or is unable to construct
3403 an element from the retrieved resource.  A validator that claims
3404 conformance to RELAX NG should document its capabilities for handling
3405 URI references.</para>
3406
3407 </section>
3408
3409 <appendix>
3410 <title>RELAX NG schema for RELAX NG</title>
3411
3412 <rngref src="relaxng.rng"/>
3413
3414 </appendix>
3415
3416 <appendix>
3417 <title>Changes since version 0.9</title>
3418
3419 <para>The changes in this version relative to version 0.9
3420 are as follows:</para>
3421
3422 <itemizedlist>
3423
3424 <listitem><para>in the namespace URI, <literal>0.9</literal> has been
3425 changed to <literal>1.0</literal></para></listitem>
3426
3427 <listitem><para><literal>data/except//empty</literal> has been added
3428 as a prohibited path (see <xref
3429 linkend="context-data-except"/>)</para></listitem>
3430
3431 <listitem><para><literal>start//empty</literal> has been added
3432 as a prohibited path (see <xref
3433 linkend="context-start"/>)</para></listitem>
3434
3435 <listitem><para><xref linkend="number-child-elements"/> now specifies how a
3436 <literal>list</literal> element with more than one child element is
3437 transformed</para></listitem>
3438
3439 <listitem><para><xref linkend="notAllowed"/> now specifies how a
3440 <literal>notAllowed</literal> element occurring in an
3441 <literal>except</literal> element is transformed</para></listitem>
3442
3443 <listitem><para>although a relative URI is not allowed as the value of
3444 the <literal>ns</literal> and <literal>datatypeLibrary</literal>
3445 attributes, an empty string is allowed (see <xref
3446 linkend="full-syntax"/>)</para></listitem>
3447
3448 <listitem><para>the removal of unreachable definitions in <xref
3449 linkend="define-ref"/> is now correctly specified</para></listitem>
3450
3451 <listitem><para><xref linkend="notAllowed"/> now specifies that
3452 <literal>define</literal> elements that are no longer reachable are
3453 removed</para></listitem>
3454
3455 <listitem><para><xref linkend="constraints"/> has been added; the
3456 restrictions on the contents of <literal>except</literal> in name
3457 classes that are now specified in the newly added section were
3458 previously specified in a subsection of <xref
3459 linkend="contextual-restriction"/>, which has been
3460 removed</para></listitem>
3461
3462 <listitem><para>the treatment of element and attribute values that
3463 consist only of whitespace has been refined (see <xref
3464 linkend="element-pattern"/> and <xref
3465 linkend="data-pattern"/>)</para></listitem>
3466
3467 <listitem><para>attributes with infinite name classes are now required
3468 to be repeated (see <xref
3469 linkend="attribute-restrictions"/>)</para></listitem>
3470
3471 <listitem><para>restrictions have been imposed on
3472 <literal>interleave</literal> (see <xref
3473 linkend="interleave-restrictions"/>); <literal>list//interleave</literal>
3474 has been added as a prohibited path (see <xref
3475 linkend="list-restrictions"/>)</para></listitem>
3476
3477 <listitem><para>some of the prohibited paths in <xref
3478 linkend="contextual-restriction"/> have been corrected to use
3479 <literal>ref</literal> rather than
3480 <literal>element</literal></para></listitem>
3481
3482 <listitem><para>an error in the inference rule (text 1) in <xref
3483 linkend="text-pattern"/> has been corrected</para></listitem>
3484
3485 <listitem><para>the value of the <literal>ns</literal> attribute is
3486 now unconstrained (see <xref
3487 linkend="full-syntax"/>)</para></listitem>
3488
3489 </itemizedlist>
3490
3491 </appendix>
3492
3493 <appendix>
3494 <title>RELAX NG TC (Non-Normative)</title>
3495
3496 <para>This specification was prepared and approved for publication by
3497 the RELAX NG TC. The current members of the TC are:</para>
3498
3499 <itemizedlist>
3500 <listitem><para>Fabio Arciniegas</para></listitem>
3501 <listitem><para>James Clark</para></listitem>
3502 <listitem><para>Mike Fitzgerald</para></listitem>
3503 <listitem><para>KAWAGUCHI Kohsuke</para></listitem>
3504 <listitem><para>Josh Lubell</para></listitem>
3505 <listitem><para>MURATA Makoto</para></listitem>
3506 <listitem><para>Norman Walsh</para></listitem>
3507 <listitem><para>David Webber</para></listitem>
3508 </itemizedlist>
3509
3510 </appendix>
3511
3512 <bibliography><title>References</title>
3513
3514 <bibliodiv><title>Normative</title>
3515
3516 <bibliomixed id="xml-rec"><abbrev>XML 1.0</abbrev>Tim Bray,
3517 Jean Paoli, and
3518 C. M. Sperberg-McQueen, Eve Maler, editors.
3519 <citetitle><ulink url="http://www.w3.org/TR/REC-xml">Extensible Markup
3520 Language (XML) 1.0 Second Edition</ulink></citetitle>.
3521 W3C (World Wide Web Consortium), 2000.</bibliomixed>
3522
3523 <bibliomixed id="xml-names"><abbrev>XML Namespaces</abbrev>Tim Bray,
3524 Dave Hollander,
3525 and Andrew Layman, editors.
3526 <citetitle><ulink url="http://www.w3.org/TR/REC-xml-names/">Namespaces in
3527 XML</ulink></citetitle>.
3528 W3C (World Wide Web Consortium), 1999.</bibliomixed>
3529
3530 <bibliomixed id="xlink"><abbrev>XLink</abbrev>Steve DeRose, Eve Maler
3531 and David Orchard, editors.
3532 <citetitle><ulink url="http://www.w3.org/TR/xlink/">XML Linking
3533 Language (XLink) Version 1.0</ulink></citetitle>.
3534 W3C (World Wide Web Consortium), 2001.</bibliomixed>
3535
3536 <bibliomixed id="infoset"><abbrev>XML Infoset</abbrev>John Cowan, Richard Tobin,
3537 editors.
3538 <citetitle><ulink url="http://www.w3.org/TR/xml-infoset/">XML
3539 Information Set</ulink></citetitle>.
3540 W3C (World Wide Web Consortium), 2001.</bibliomixed>
3541
3542 <bibliomixed id="rfc2396"><abbrev>RFC 2396</abbrev>T. Berners-Lee, R. Fielding, L. Masinter.
3543 <citetitle><ulink url="http://www.ietf.org/rfc/rfc2396.txt" >RFC 2396:
3544 Uniform Resource Identifiers (URI): Generic
3545 Syntax</ulink></citetitle>.
3546 IETF (Internet Engineering Task Force). 1998.</bibliomixed>
3547
3548 <bibliomixed id="rfc2732"><abbrev>RFC 2732</abbrev>R. Hinden, B. Carpenter, L. Masinter.
3549 <citetitle><ulink url="http://www.ietf.org/rfc/rfc2732.txt">RFC 2732: Format for Literal IPv6 Addresses in URL's</ulink></citetitle>.
3550 IETF (Internet Engineering Task Force), 1999.</bibliomixed>
3551
3552 <bibliomixed id="rfc3023"><abbrev>RFC 3023</abbrev> M. Murata,
3553 S. St.Laurent, D. Kohn.  <citetitle><ulink
3554 url="http://www.ietf.org/rfc/rfc3023.txt">RFC 3023: XML Media
3555 Types</ulink></citetitle>. IETF (Internet Engineering Task Force),
3556 2001.</bibliomixed>
3557
3558 </bibliodiv>
3559
3560 <bibliodiv><title>Non-Normative</title>
3561
3562 <bibliomixed id="xmlschema-2"><abbrev>W3C XML Schema Datatypes</abbrev>Paul V. Biron, Ashok Malhotra, editors.
3563 <citetitle><ulink url="http://www.w3.org/TR/xmlschema-2/">XML Schema Part 2: Datatypes</ulink></citetitle>.
3564 W3C (World Wide Web Consortium), 2001.</bibliomixed>
3565
3566 <bibliomixed id="trex"><abbrev>TREX</abbrev>James Clark.
3567 <citetitle><ulink url="http://www.thaiopensource.com/trex/">TREX - Tree Regular Expressions for XML</ulink></citetitle>.
3568 Thai Open Source Software Center, 2001.</bibliomixed>
3569
3570 <bibliomixed id="relax"><abbrev>RELAX</abbrev>MURATA Makoto.
3571 <citetitle><ulink url="http://www.xml.gr.jp/relax/">RELAX (Regular
3572 Language description for XML)</ulink></citetitle>.  INSTAC
3573 (Information Technology Research and Standardization Center), 2001.</bibliomixed>
3574
3575 <bibliomixed id="xsfd"><abbrev>XML Schema Formal</abbrev>Allen Brown,
3576 Matthew Fuchs, Jonathan Robie, Philip Wadler, editors.
3577 <citetitle><ulink url="http://www.w3.org/TR/xmlschema-formal/">XML Schema: Formal Description</ulink></citetitle>.
3578 W3C (World Wide Web Consortium), 2001.</bibliomixed>
3579
3580 <bibliomixed id="tutorial"><abbrev>Tutorial</abbrev>James Clark,
3581 Makoto MURATA, editors.  <citetitle><ulink
3582 url="http://www.oasis-open.org/committees/relax-ng/tutorial.html">RELAX
3583 NG Tutorial</ulink></citetitle>.  OASIS, 2001.</bibliomixed>
3584
3585 </bibliodiv>
3586
3587 </bibliography>
3588
3589 </article>