james anderson<james.anderson@setf.de> |
An interpretation sematics for XML-1.0+names document type definitions is demonstrated
which is adquate to qualifiy such encodings as minimally-schema conformant. This note introduces the interpretive problems associated with DTD-encoded schemas, defines an abstract document model to support their interpretation, describes the interpretations semantics, and illustrates its use for typical |
The expressions which appear in an XML document type definition (DTD) are intended to be interpreted by a XML processor so as "to determine whether the mark-up for an individual document is correct and also to supply the mark-up that is missing because it can be inferred unambiguously from other mark-up present". [iso-sgml] One issue central to this interpretation is that of the identity of names: when do two lexical names strings encode the same name taken from the domain in whcih correctness is judged and completion is inferred. Prior to the recommendation on namespaces, literal name strings were directly used to assess correctness and to effect defaults, as the names were understood to be globally unique. Names were identified according to literal, lexical equality. Were a namestring to appear more than in more than one element declaration as an element's generic identifier, the instance document was categorized as not well-formed, which precluded a correctness assessment. Were a namestring to appear as an attribute name in more than one attribute declaration for a given element, the second and subsequent declarations were ignored. In order to avoid such spurious conflicts among combined document type definitions, it was recognized that names were not necessarily globally unique and methods were developed to rewrite namestrings in component definitions so as to avoid conflicts for a given combination of definitions.
As of the ratification of the namespace recommendation, the presumption of universal uniqueness among literal names no longer applies when interpreting XML documents. Literal name strings are no longer the basis for identity among names. Which means that a DTD, where interpreted literally, can no longer serve its intended purpose. The consequences are several. On approach has been to described encoding conventions which employ rules for declaration and appearance of parameter entities as a means to effect aspects of the name-rewriting from enabling architectures. Another approach has been to develop alternative schema languages which use XML element syntax to express document definitions. This approach offers the lattitude to interpret qualified namestrings in declarations in a manner consistent with the namespace recommendation, either by direct application of the specified scoping rules, or according to schema-specific rules.
These developments constitute a remarkable paradox. On the one hand, they manifest the assertion that it is possible to transcend the incompatibility between DTD-encoded document definitions and universal names only by replacing DTDs with schemas which themselves constitute incompatible encodings and interpretation algorithms. On the other hand, they ignore evidence that a much less severe algorithmic break would make it possible to interpret universal names within a DTD without ambiguity, and, as a consequence, to perform namespace-aware validation and default inference. The core of this progressive approach, is to simply apply to a DTD-encoded document type definition the same interpretation rules which the namespaces recommendation specifies for the document entity.
This note demonstrates the consequences of this alternative approach for the use of namespace-aware DTDs. In particular it demonstrates that the approach itself follows from a interpretation of both the DTD and document entity on the basis a s single consistent abstract model, that the approach is adequate to unambiguously interpret names in the presence of synonomy and homography, and that the approach is sufficient to generate a post validation information set which comprises those of the constraints and inferences specified by the schemas recommentation which can be encoded in a DTD. Which, according to the provisions for alternative encodings, establishes DTD-syntax as permissible encoding for schemas.
The remainder of the note is divided into three sections. The next section describes and illustrates the interpretation process with reference to the concrete DTD syntax and an abstract document model. It includes a sematics which specifies how the model is generated from a concrete document instance as well as examples of the interpretation. The succeeding section describes those aspects of the schema component model which can be encoded in a DTD, It includes the RDF expression for examples of this schema subset. The final section describes the validation process and illustrates generation of the PSVI for the example documents.
This section presents an interpretation semantics for namespace-aware XML-1.0 documents, which, given a namespace-conformant document, yields instances of a document model which is expressed entirely in terms of universal names. As the first step, a simplified concrete syntax for document type definitions is introduced, which is restricted to those expressions which are related to names. From this an abstract syntax is
The syntax of element and attribute declarations in a DTD expresses various relations among element names for generic identifiers, names in content models, attribute names, and attribute types. The concrete expression of these relations is governed by the BNF for XML. The following simplified excerpt from the XML 1.0 recommendation comprises the relevant syntactic forms.
[[1]] Document ::=DoctypeDecl?Element [[10]] AttValue ::= '"' [^<&"]* '"' | "'" [^<&']* "'"[[28]] DoctypeDecl ::= '<!DOCTYPE' S+ QName S* ('[' MarkupDecl* ']' S* )? '>' [[29]] MarkupDecl ::= ElementDecl | AttlistDecl[[39]] Element ::= STag ( '/>' | ( '>' Content* ETag ) ) [[40]] STag ::= '<' QName AttributeSequence? S* AttributeSequence ::= Attribute AttributeSequence? [[41]] Attribute ::= S+ QName Eq AttValue [[42]] ETag ::= '</' QName S* '>'[[45]] ElementDecl ::= '<!ELEMENT' S+ QName S+ ContentSpec S* '>' [[46]] ContentSpec ::= 'EMPTY' | 'ANY' | Mixed | Children [[47]] Children ::= ChoiceOrSeq Cardinality? [[48]] Cp ::= ( QName | ChoiceOrSeq ) Cardinality? ChoiceOrSeq ::= '(' S* Cp ( Choice | Seq )? S* ')' [[49]] Choice ::= ( S* '|' S* Cp )+ [[50]] Seq ::= ( S* ',' S* Cp )+ [[51]] Mixed ::= ( '(' S* '#PCDATA' ( S* '|' S* QName )* S* ')' MixedCardinality ) | ( '(' S* '#PCDATA' S* ')' ) Cardinality ::= '?' | '+' | '*' MixedCardinality ::= '*' [[52]] AttlistDecl ::= '<!ATTLIST' S+ QName AttDefSequence? S* '>' AttDefSequence ::= AttDef AttDefSequence? [[53]] AttDef ::= S+ QName S+ AttType S+ DefaultDecl [[54]] AttType ::= StringType | TokenizedType | EnumeratedType [[55]] StringType ::= 'CDATA' [[56]] TokenizedType ::= 'ID' | 'IDREF' | 'IDREFS' | 'ENTITY' | 'ENTITIES' | 'NMTOKEN' | 'NMTOKENS' [[57]] EnumeratedType ::= NotationType | Enumeration [[58]] NotationType ::= 'NOTATION' S+ '(' S* NotationTypeSequence S* ')' NotationTypeSequence ::= NCName (S* '|' S* NotationTypeSequence )? [[59]] Enumeration ::= '(' EnumerationSequence S* ')' EnumerationSequence ::= S* Nmtoken ( S* '|' EnumerationSequence )? [[60]] DefaultDecl ::= '#REQUIRED' | '#IMPLIED' | (( '#FIXED' S)? DefaultAttValue) QName ::= Prefix? LocalPart Prefix ::= NCName ':' LocalPart ::= NCName
As this note will limit itself to the interpretation of names, one may restrict the syntax to those terms which concern generic identifiers in start tags and end tags, attribute names in start tags, and the analogous identifiers in the respective declarations, the syntax can be simplfied to the following phrases:
[[1]] Document ::=DoctypeDecl?Element [[10]] AttValue ::= '"' [^<&"]* '"' | "'" [^<&']* "'"[[28]] DoctypeDecl ::= '<!DOCTYPE' QName MarkupDecl* '>' [[29]] MarkupDecl ::= ElementDecl | AttlistDecl[[39]] Element ::= STag ( '/>' | ( '>' Content* ETag ) ) [[40]] STag ::= '<' QName AttributeSequence? AttributeSequence ::= Attribute AttributeSequence? [[41]] Attribute ::= QName AttValue [[42]] ETag ::= '</' QName '>'[[45]] ElementDecl ::= '<!ELEMENT' QName Qname* '>' [[52]] AttlistDecl ::= '<!ATTLIST' QName AttDef '>' [[53]] AttDef ::= QName AttValue QName ::= Prefix? LocalPart Prefix ::= NCName ':' LocalPart ::= NCName
In keeping this simplified description of an XML document, examples can be expressed in an equivalent abstract syntax will serve is ,ore readily generated and parsed in the testing environment.
p |
in |
Prefix |
::= |
NCName |
l |
in |
LocalPart |
::= |
NCName |
nsn |
|
NamespaceName |
::= |
Character+ |
qn |
in |
QualifiedName |
::= |
(:qn (Prefix + null) X LocalPart ) |
un |
in |
UniversalName |
::= |
(:un (Namespace + null) X LocalPart ) |
n |
in |
Name |
::= |
( UniversalName + QualifiedName ) |
nsb |
in |
NamespaceBinding |
::= |
(:nsb . ((LocalPart X NamespaceName) + (null X (NamespaceName + null))) ) |
a |
in |
Attribute |
::= |
(:a Name ) |
e |
in |
Element |
::= |
(:e Name X NamespaceBinding* X Attribute* X Element* ) |
ed |
in |
ElementDeclaration |
::= |
(:ed Name X (Name* + 'ANY' +'EMPTY') ) |
ad |
in |
AttributeDeclaration |
::= |
(:ad Name X NamespaceBinding* X Attribute* ) |
dcl |
in |
DeclarationContext |
::= |
(:dcl (ElementDeclaration + AttributeDeclaration + DeclarationContext)* ) |
doc |
in |
Document |
::= |
(:doc Name DeclarationContext X Element ) |
Note that this abstract syntax constitutes a superset of the concrete syntax,
in that it incorporates forms for for expressions which do not appear in the concrete
syntax. Forms for universal names (un) and collections of declarations
(dcl) serve to express elements of domains present in the abstract interpretation
models.
The namespaces recommendation specifies the essential properties and interpretation methods for qualified and universal names. Within the document entity stipulations suffice to identify the denoted universal name for each qualified name. The recommendation describes rules for combining element containment relations with element attribute relations (scoping rules) so as to interpret relations between prefixes and namespace bindings within the document entity unambiguously and thereby to determine the URI associated with a given prefix:
The namespace declaration is considered to apply to the element where it is specified and to all elements within the content of that element, unless overridden by another namespace declaration....
On this basis the universal denotation of each qualified name is then derived. The recommendation also describes a conformance standard which derives from the identity of universal attribute names within the document entity:
In XML documents conforming to this specification, no tag may contain two attributes which:
- have identical names, or
- have qualified names with the same local part and with prefixes which have been bound to namespace names that are identical.
The recommendation neglects to specify means to determine either attribute or element name identity between the document entity and the document type definition. It also neglects to specify means to determine attribute or element name identity within the document type definition itself. The effect has been to impair XML processors' ability to validate namespace-aware documents. The accepted response to this difficulty has be to abandon DTD-encoded schemas as a means to express documents which express universal names.
There is no logical reason for this failure. If one examines item (2) above more closely, it establishes a principle which serves as the basis the core of an effective approach. The key insight is, the principle is to be applied to the entire document instead of to the root element only. Although it is expressed in lexical terms apprent in the concrete syntax, the rule describes a comparison which no longer takes place in the lexical domain: it stipulates a comparison between universal names
This is the approach followed by all namespace aware schemas. The XML schema formal description, for example, describes validation with respect to matching attribute names in terms of either normalized universal names. RELAX NG, for example, also expresses validation directly in terms of universal names. It describes the central judgement of element validation in terms of the expression
E; ns |- a; m =~ p => k; kr
in which the atttribute and element components - a and m respetively, denote domains
which comprise universal names. Which suggests, that one might well assume a simillar
approach for DTD-encoded schemas. That is, define an abstract model in which the
schema is described in terms of universal names together with a mechanism which interprets
a DTD-encoded schema in terms of this abstract model. If the approach is to succeed,
the interpretation must yield a model consistent with an equivalent xml-schema-encoded
document definition.
One such model for universal documents comprises the following semantic domains:
| ncn | in | NameCharacterName | ||
| null | in | NullName | ||
| p | in | Prefix | ::= | NameCharacterName + NullName |
| wn | in | WildName | ||
| l | in | LocalPart | ::= | NameCharacterName + NullName |
| uri | in | UniformResourceIdentifier | ||
| nsn | in | NamespaceName | ::= | UniformResourceIdentifier + NullName |
| qn | in | QualifiedName | ::= | ( Prefix X LocalPart ) |
| un | in | UniversalName | ::= | ( Namespace X LocalPart ) |
| ns | in | Namespace | ::= | ( NamespaceName X ( LocalPart => UniversalName ) ) |
| n | in | Name | ::= | ( UniversalName + QualifiedName ) |
| nsb | in | NamespaceBinding | ::= | ( Prefix X Namespace ) |
| nse | in | NamespaceEnvironment | ::= | Prefix => Namespace |
| a | in | Attribute | ::= | Name |
| e | in | Element | ::= | ( Name X NamespaceBinding* X Attribute* X Element* ) |
| ed | in | ElementDeclaration | ::= | ( Name X ( Name* + WildName ) ) |
| ad | in | AttributeDeclaration | ::= | ( Name X Name ) |
| md | in | MarkupDeclaration | ::= | ( ElementDeclaration + AttributeDeclaration ) |
| dcl | in | DeclarationContext | ::= | ( MarkupDeclaration + DeclarationContext )* |
| doc | in | Document | ::= | ( Name X DeclarationContext X Element ) |
On the basis of the abstract syntax and this abstract model, a collection of valuation functions describe how to interpret an instance document as a document model.
can be formulated to generate a Document for which all encoded qualified names are interpreted as universal names for all documents which conform to the namespaces recommendation. this set of documents includes a significant subset of those which exhibit synonomy and/or homography artifacts. Once a generated Document model contains no qualified names, it is possible to produce a pre-validation infoset which conforms to the requirements for xml schemas. The succeeding sections describe these valuation
[[<!ATTLIST (pi li vi),
(xmlns, pj), u)> (ED, (pi, li, u) EU)]]
==> EU' = (EU, (pi, u)) in (TEu (I[[(pi, li)]], EU') (TAu, (I[[(pi, li)]], EU'),
(I[[(xmlns, li, u)]], EU') )
nse0 = ( (xmlns {xmlns}), (xml {}), (|| {}) )
intern DTD : ID == ( DoctypeDecl NamespaceEnvironment ) ==> Schema
initial reduction
ID[[ ( <!DOCTYPE q MarkupDecl* >, (# ø), nse ) |
|
| ==> | (mdSet nse') := IMD[[ MarkupDecl* (# ø) nse ]] in (IQ[[ q nse' ]] . mdSet) |
terminal reduction
| IMD[[ () sc0 nse0 ]] | |
| ==> | sc0 nse0 |
multiple element declarations are an error
| qNamea == qNamei |- IMD[[ ( <!ELEMENT qNamea qName* >, MarkupDecl*, <!ELEMENT qNamei qName* >, MarkupDecl*) sc nse ]] |
|
| ==> | error |
augment an existing element declaration based on an element declaration form or
introduce a new one:
| u0 ==modns IN[[ qNamei ]] |- IMD[[ <!ELEMENT qNamei (qNamej . qName*) > MarkupDecl* ]] (sc, ( (ed u0 u* ad* nse1) . md* ) ) nse0 |
|
| ==> | IMD [[ MarkupDecl* <!ELEMENT qNamei qName* > ]] (sc ( (ed u0 ( NewU[[ qNamej ]] . u* ) ) ad* nse1 ) . md* ) nse0 |
| IMD[[ ( <!ELEMENT qNamei QName* > . MarkupDecl* ) (sc md*) nse0 ]] | |
| ==> | IMD[[ ( <!ELEMENT qNamei QName* > . MarkupDecl* ) (sc, ( NewEd[[ qNamei nse0]] . md* ) ) nse0 ]] |
augment an existing element declaration based on an attribute declaration form or
introduce a new one:
| IMD[[ <!ATTLIST ncNamei : ncNamej ncNamek : ncNamel attValuem > MarkupDecl* ]] (sc md*) nse0 | |
| ==> | let sc' := ( sc ( NewEd[[ ncName : naNamej ]] . md* ) ) in IMD[[ <!ATTLIST ncNamei : ncNamej ncNamek : ncNamel attValuem > MarkupDecl* ]] sc' nse |
A collection of examlpes was drawn up to demonstrate the interaction of various expressions and arrangements with the interpretation of names.
The examples are divided into three sections. one each for literal identity, synonomy, and homography.
"A Formal Data Model and Algebra for XML" proposes an abstract graph model for XML documents in which the generic identifiers and qualified attribute names
"encode the namespace information by representing the name as a tuple consisting of the namespace definition edge and the generic identifier. In the case of qualified elements and attributes, the namespace definition edge is the edge of the attribute that defines the namespace."[p3]
according to which all universal names comprise a reference to the lexical binding of the respective namespace prefix to the namespace name. the model would suggest such operations as uniform mutation of the namespace containment of exactly those names within the scope of a given binding. such operations are, however, absent from the algebra and the model form was not perpetuated in later version of the query algebra.