Copyright �2001 W3C� (MIT, INRIA, Keio), All Rights Reserved. W3C liability, trademark, document use and software licensing rules apply.
XML Schema: Formal Description is a formal description of XML types and validity as specified by XML Schema Part 1: Structures.
This is a W3C Working Draft for review by members of the W3C and other interested parties in the general public.
It has been reviewed by the XML Schema Working Group and the Working Group has agreed to its publication. Note that not that all sections of the draft represent the current consensus of the WG. Different sections of the specification may well command different levels of consensus in the WG. Public comments on this draft will be instrumental in the WG's deliberations.
Please review and send comments to<EMAIL_ADDRESS>(archive).
This specification of the formal description of XML Schema is a working draft of the XML Schema Working Group and has been adopted by the working group as the formalization of the XML Schema Definition Language, in fulfillment of its commitment to provide such a formalization at the conclusion of the Candidate Recommendation phase for XML Schema. This material is current with the Proposed Recommendation draft but not perfectly aligned with it. In the foreseeable future, work on this document will focus on improving the alignment with the normative parts of XML Schema and resolving the issues on the current issues list (http://www.w3.org/2001/03/xmlschema-fd-issues.html).
As with all working drafts, the reader is advised that all the material within is subject to change. The reader is advised that material found here may change drastically from draft to draft. In particular, future versions will incorporate some or all of the XML Schema Part 2: Datatypes specification, the key/keyref facility, and a bidirectional mapping between the XML Schema component model and the corresponding part of this formalization. Parts of this specification, such as the normalization of names, may eventually find a broader use. However the reader should be advised that these features will probably undergo revision before the working group warrants them for such uses.
The Schema Working Group expects this work to be of use to other Working Groups within the W3C as well as to others building tools and systems hoping to leverage XML Schemas.
A list of current W3C working drafts can be found at http://www.w3.org/TR/. They may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use W3C Working Drafts as reference material or to cite them as other than "work in progress".
2 Overview
2.1 Normalization
2.2 Components
2.3 Documents and Forests
3 Structures
3.1 Names
3.2 Wildcards
3.3 Atomic datatypes
3.4 Content groups
3.5 Components
3.6 Constraints
3.7 Ordered Forests
3.8 Inference rules
5 Derivation
5.1 Base chain
5.2 Extension
5.3 Restriction
5.4 Constraints
6 Validation
6.1 Content validation
6.2 ID/IDREF validation
7 XML Schema to Formalization Mapping
7.1 Conversions for content model
particles
7.2 Correspondences from XML Schema to
sorts
Appendix A Auxiliary Grammar
Appendix B Infidelities in the current formalization of XML Schema
Appendix C Bibliography
This formalization is a formal, declarative system for describing and naming XML Schema information, specifying XML instance type information, and validating instances against schemas. The goals of the formalization are to:
Many potential applications of XML Schema may benefit from the definition of a formal model. We have focused on the material in Part I (Structures), as this is the most complex.
A basic understanding of first-order predicate logic, which is part of most computer science curricula, is adequate to understand this document. Where other notations are used, they are explained before use. Though the mathematical notation used in this formalization may be somewhat daunting for those not accustomed to formalisms, it should be possible to prepare a prose description directly from this formalism, which may be more approachable than a description based on an ad hoc understanding of XML Schema [11,3].
The approach followed here follows the best practices currently used in the programming languages community, although somewhat adapted for XML. The hallmark of this approach is the use of context free grammars to provide syntactic checking and the use of inference rules to provide the semantics associated with each piece of syntax. This means there is, essentially, one inference rule per context free grammar production. This set of inference rules is not intended to be in any way minimal, but it is helpful from both a pedagogical and implementation standpoint - for each syntactic construct it is straightforward to identify its underlying semantics.
The remainder of this document is organized as follows.
This section uses a running example to introduce our representation of a schema, which uses a mathematical notation that is easier to manipulate formally than the XML syntax of Schema. This formalism divides a schema into a set of components, where each component can match against a particular fragment of XML in an instance. Particular attention will be given to the use of normalization to provide a unique name for each component of a schema.
Here is a sample schema written in W3C XML Schema syntax.
<xsd:schema targetNamespace = "http://www.example.com/baz.xsd" xmlns = "http://www.example.com/baz.xsd" xmlns:xsd = "http://www.w3.org/2001/XMLSchema"> <xsd:element name="a" type="t"/> <xsd:simpleType name="b"> <xsd:list itemType="xsd:integer"/> </xsd:simpleType> <xsd:complexType name="t"> <xsd:attribute name="b" type="xsd:string"/> <xsd:attribute name="c" type="b" use="optional"/> </xsd:complexType> <xsd:complexType name="u"> <xsd:complexContent> <xsd:extension base="t"> <xsd:choice> <xsd:element name="d"> <xsd:complexType> <xsd:sequence> <xsd:element name="a" type="xsd:string" minOccurs="1" maxOccurs="unbounded"/>
</xsd:sequence> </xsd:complexType> </xsd:element> <xsd:element name="e" type="xsd:string"/> </xsd:choice> </xsd:extension> </xsd:complexContent> </xsd:complexType> </xsd:schema>
And here is an XML document which matches the above schema
<baz:a xmlns:baz="http://www.example.com/baz.xsd" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="baz:u" b="zero" c="1 2"> <d> three four </d> </baz:a>
We use a normalized form of a schema, which assigns a unique universal name to each component of a schema, and "flattens" the structure. (A component is anything which may be defined or declared: an element, an attribute, a simple type, a complex type, a group, an attribute group, or an identity constraint.)
Here are the normalized (universal) names of the components in our sample schema. For each name, we list two forms: the long form is the name proper, while the short form is an abbreviated version we use in examples to improve readability.
|
The normalized names reflect the nesting structure of the original schema. Note that the nesting of declarations in W3C XML Schema also determines their scope. In the representation of a Schema, the names of nested components are constructed by appending their schema names to the normalized names of their parents; if a component is anonymous, it is given the name *. The syntax of names is chosen to be similar to XPath [5,12], but unlike XPath, * does not function as a wildcard in normalized names.
These normalized names clearly distinguish local names from global names. Where previously it might be possible to confuse the global a element with the local a element, now these are given distinct names, a and u/d/*/a respectively. The latter indicates that the global type u contains a local element d which contain an anonymous type * which contains a local element a. Each attribute or element contains at most one anonymous type, so using the name * for such types leads to no confusion. In order to reflect the attribute form and element form attributes from XSDL, these names also reflect whether an element is to be qualified or not by a "-" or a "+" immediately following the # in the name. A "+" indicates the name is to be qualified. By default, only top-level elements (such as the "a") are qualified. However, for example, if the declaration of the "b" attribute of type "t" had been:
<xsd:attribute name="b" type="xsd:string" formDefault="qualified"/>
then its normalized name would have been:
http://www.example.com/baz.xsd#+type::t/attribute::b
NOTE: The normalized names described in this document exist only for the purposes described herein. There is a separate effort underway by the Schema WG to generalize these names so they will be suitable for a variety of other uses. When that effort is complete, this document will adopt that syntax.
Next, we show how components are represented in this notation. Each component is one of six sorts: element, attribute, simple type, complex type, attribute group, or model group. Regardless of sort, each component is represented uniformly as a constructor (one of attribute, element, simpleType, complexType, attributeGroup, modelGroup, or identityConstraint) of a record with six fields:
Note that all seven sorts have a very consistent structure consisting of six properties, which have the same interpretation regardless of the sort.
The formalism uses standard regular expression notation [2] for component content. Component content corresponds roughly to a union of both model groups and attributes groups. In what follows, g stands for a content group (as does g1, g2, and so on). The constructors for groups include the following:
EDITOR'S NOTE: The grammar above does not distinguish between the precedence of the various connectors ("|", "&", and ","). This will not be a concern as in our examples we will always parenthesize appropriately. Rather than significantly expanding the grammar, we will provide a full grammar with parentheses in an appendix in a future version.
A nameset corresponds to a set of names. A nameset may be a single element or attribute name, a substitution group, or the equivalent of an XSDL wildcard. The syntax for defining a nameset will be given later.
Need to explain what a nameset is.
Here is an example of a model group in our notation, which corresponds to an a element with content of type u in our running example
+a[ (-@t/b[xsi:string] & -@t/c[xsi:integer{0,8}]{0,1}), (-u/d[u/d/*/a[xsi:string]{1,8}] | -u/d/*/e[xsi:string]) ]
Note that the group constructors are used uniformly in several contexts. Repetition (g{m,n}) is used for lists of atomic datatypes, to indicate whether an attribute is optional, and for elements. Similarly, all (g1 & g2) is used for attributes and for elements.
Here are the components of the normalized schema represented in this notation
element( name = +a, base = xsi:UrElement, derivation = restriction, refinement = {restriction,extension}, abstract = false, content = a[t] )
simpleType( name = s, base = xsi:UrSimpleType, derivation = restriction, refinement = {restriction}, abstract = false, content = xsi:integer{0,8} )
complexType( name = t, base = xsi:UrType, derivation = restriction, refinement = {restriction,extension}, abstract = false, content = @t/b & @t/c )
attribute( name = -@t/b, base = xsi:UrAttribute, derivation = restriction, refinement = {restriction}, abstract = false, content = @t/b[xsi:string] )
attribute( name = -@t/c, base = xsi:UrAttribute, derivation = restriction, derivation = {restricition}, abstract = false, content = @t/c[s]{0,1} )
complexType( name = u, base = t, derivation = extension, refinement = {restriction,extension}, abstract = false, content = (-@t/b & @t/c), (u/d | u/e) )
element( name = u/d, base = xsi:UrElement, derivation = restriction, refinement = {}, abstract = false, content = u/d[u/d/*] )
complexType( name = u/d/*, base = xsi:UrType, derivation = restriction, refinement = {}, abstract = false, content = u/d/*{0,8} )
element( name = -u/d/*/a, base = xsi:UrElement, derivation = restriction, refinement = {}, abstract = false, content = u/d/*/a[xsi:string] )
element( name = -u/e, base = xsi:UrElement, derivation = restriction, refinement = {}, abstract = false, content = -u/e[xsi:string] )
Note that we do not nest declarations to express their scope. The scope of a declaration is reflected in its normalized name.
It is not clear to me from our discussions whether this notation will stay. There's some suggestion that we need a notation that borders on the verbosity of the underlying XML.
There is also a compact notation for representing XML, both before and after normalization. This notation is not intended in any way to be used as a replacement for traditional XML syntax. Having a more compact, but equally expressive, equivalent notation will aid significantly in the exposition below (in particular it keeps the inference rules to a reasonable size). Here is the original document in this notation:
a[ @xsi:type["u"], @b["zero"], @c[1,2], d[ a["three"], a["four"] ] ]
Note that attributes and elements are represented uniformly, as are sequences of attributes, sequences of elements, and lists of atomic datatypes. Note also that from this perspective a document is just a element without a parent. Therefore we will drop the term "document" and simply use the term element. The term "this document" will continue to refer to the document you are reading.
Here is the normalized element:
a[ @xsi:type["u"], @t/b["zero"], @t/c[1,2], u/d[ u/d/*/a["three"], u/d/*/a["four"] ] ]
Given an input document such as this, validation can both establish the validity of the document and assert which types, elements, and attributes were used. This can be conveyed textually by writing the document using normalized names.
Finally, here is the normalized element with type information added
a[ u types @t/b[xsi:string types "zero"], @t/c[s types 1,2], u/d[ u/d/* types u/d/*/a[xsi:string types "three"], u/d/*/a[xsi:string types "four"] ] ]
Unlike the xsi:type convention, this notation allows one to uniformly express information about element and attribute types. The type of an element or attribute is indicated by writing x[t types d] where x is an attribute or element name, t is a type name, and d is the content of the attribute or element.
We will use the term forest or ordered forest when referring to lists of attributes and elements, as in the content of a element. For example, while the above is an element its content:
u types @t/b[xsi:string types "zero"], @t/c[s types 1,2], u/d[ u/d/* types u/d/*/a[xsi:string types "three"], u/d/*/a[xsi:string types "four"] ]
is an ordered forest. Note that a single element is itself an ordered forest.
The content of the components described above takes advantage of derivation and namesets to provide a compact description of the actual allowed content of an element in an instance. This can be viewed as an intentional description of a regular expression. However, we can also provide the full extensional description of the regular expression, given a finite set of components. Doing so allows us to describe validation in terms of a more primitive model and would allow XML Schema to evolve without needing to change the core of the formalism -- as XML Schema evolves, the mapping from the intensional descriptions contained by the components to the extensional descriptions may change, but a formalism built around the extensional versions remains stable.
As an example of this conversion, we will unroll the content of the "a" element from our sample schema. Note that "a" has declared type "t", and "t" has one subtype, "u". Therefore the contents of an "a" are either the contents of "t", with an optional xsi:type attribute, or the contents of "u" with an obligatory xsi:type attribute with value "u":
a[(xsi:type="t"? & @t/b & @t/c) | ((xsi:type="u" & @t/b & @t/c), (u/d | u/e))]
A validator can validate against this extended regular expression and map back to the components by way of the value of xsi:type. At this lowest level, xsi:type functions as an implied attribute, but takes on added signficance once we map from this level back into the level of schema. It should also be noted that this expression does not follow the single attribution and unambiguity constraints of DTDs or Schema. Those constraints are applied at the component level.
Another aspect of this translation is to treat element names in regular expressions as namesets containing the names of the elements in the substitution group of the base element. For example, suppose there were an element "foo" whose content was just an "a" element, and that there also existed an element "f" in the substitution group of "a". The the content of the "foo" component would be:
foo[a]
and the full regular expression would expand to:
foo[(a | f)].
2.n Description of general forest grammars and general description of how the component grammars can be converted into full forest grammars. Convert some extended type to a full grammar.
This section defines the structures used in this formalism: names, namesets, atomic datatypes, model groups, components, and forests.
It is not clear how much of this needs to remain here now that NUNs are moving out. Perhaps we stick with this, as why make changes that will just be rendered irrelevant?
The other significant issue here, is that we don't take into account the 208 prefixing issues. However, to be complete, we need to do so. The least disturbing way I can find to do so is to include them in the names - so that a name also specifies if it matches a qualified or unqualified element/attribute (keeps it out of the components).
A namespace is a URI reference, and a local name is an NCName, as in the Namespace recommendation. We let i range over namespaces and the "non-namespace" (where items not in a namespace reside) and j range over local names. In order to cover the case of naming components that are not in a namespace, i may be empty. Using these names we can create unique identifiers for the components of a schema. These names are for the abstract components of the schema and ultimately are not dependent on the XML Schema transfer syntax or any configuration of files the schema may be stored in.
|
A symbol space is one of the six symbol spaces in XML Schema. We let ss range over symbol spaces.
|
A symbol name consists of a symbol space paired with a local name or with * (the latter names an anonymous component). A name consists of a URI reference followed by a sequence of one or more symbol names. We let sn range over symbol names, and x range over names.
|
Here n = 1 is the scope length of the name.
An example of a name is:
|
The scope length of this name is 4.
In this document we've found it convenient to use a short form of names. Symbol names in the attribute symbol space are written @j, all other symbol names are written j (or * for the oxymoronic anonymous names) - in our examples we've ensured our local names are unique across all symbol spaces. The URI reference may be dropped when it is obvious from context. For example, the short form of the name above is u/d/*/a. Additional examples of names and short forms appear in Section 2.1.
Before normalization, all names in a forest have scope length equal to one. It is helpful to define functions to extract the namespace from a name, and to extract the symbol space and local name of the last symbol name. We define namespace(x) = i, symbol(x) = ss, and local(x) = j when x = i#sn1/…/snn and snn = ss::j.
We also introduce several subclasses of names. An attribute name is the name of an attribute component, and similarly for element, simple type, and complex type names. We let a, e, s, k range over attribute, element, simple type, and complex type names.
|
A type name is a simple or complex type name. We let t range over type names.
|
The class of a name must be consistent with its symbol space.
|
Generalization of wildcards and substitution groups - note that x1 UNION x2 is the same thing as putting x2 in the substitution group of x1. All leaves in regex's are now namesets.
A nameset denotes a set of qualified names. The form *:* denotes any name in any namespace (note this is a namespace name, not a prefix), i:* denotes any name in namespace i, and the form x denotes the single name x. Namesets may be combined by union or difference. Namesets constructed in this way have the functionality of wildcards. We let w range over wildcard items, and w range over wildcards.
|
For example, the nameset *:* DIFFERENCE(baz:* UNION xsi:string)%strict denotes any name in any namespace, except for names in namespace baz, and the local name string in namespace xsi. Since it will be convenient to write wildcards with minimal parentheses, we will assume the precedence UNION > DIFFERENCE > %.
This part will require significant work. I'd like to treat a simple type as a union over facets - treating the value space as a facet, rather than something intrisic to some simple type. It makes unions just disjunctive normal forms of facets.
We take as given the atomic datatypes from XML Schema Part 2. We let p range over atomic datatypes, and c range over constants of such datatypes.
Typically, an atomic datatype is either a primitive datatype, or is derived from another atomic datatype by specifying a set of facets. Note lists of atomic datatypes are specified using repetition while unions are specified using alternation, as defined below.
An example of an atomic datatype is xsi:string, and a constant of that datatype is "zero".
Let g range over content groups.
|
An example of a group appears in Section 2.2.1.
The empty sequence matches only the empty forest; it is an identity for sequence and all. The empty choice matches no forest; it is an identity for choice.
|
For use with repetitions, we extend arithmetic to include 8 in the obvious way. For any n we have n + 8 = 8+ n = 8 and n = 8 is always true, and 8 < n is always false.
A sort is one of the six sorts of component in XML Schema. We let srt range over sorts.
|
(Shortcoming: we make no further use of attributeGroup or modelGroup in this document.)
A derivation specifies how a component is derived from its base. We let der range over derivations, and ders range over sets of derivations.
|
We let b range over booleans.
|
A component is a record consisting of a constructor (srt) with six fields.
We let cmp range over components.
|
Examples of components appear in Section 2.2.2.
This general model of components is far looser than the is strictly allowed by XSDL. While this is not a problem because the creation of components is strongly controlled by the languages they are generated from (currently either an XSDL Schema or a set of XSDL components as described in Structures[11]), a "tighter" grammar, more closely corresponding to what is accepted by XSDL, is found in appendix A.
For a given schema, we assume a fixed dereferencing map that takes names to the corresponding components. We write deref(x) = cmp if name x corresponds to component cmp.
The dereferencing map must map attribute names to attribute components, and similarly for elements, simple types, and complex types.
|
Recall that the group constructs are used uniformly in several contexts. Repetition (g{m,n}) is used for lists of atomic datatypes, to indicate whether an attribute is optional, and for elements. Similarly, all (g1 & g2) is used for attributes and for elements. The advantage of this approach is that the semantics of groups is uniform, and need be given only once. Thus, for instance, how repetition acts is defined once, not separately for attributes and elements.
The group grammar is rather more accommodating than that implicit in XML schemas. It permits attributes to have complex local type definitions, multiple occurrences of the declaration of a given attribute name, and the mentioning of an attribute anywhere in the defintion of a group. As we do not generally translate our group grammars back into XML schemas, this permissiveness is of little consequence. We can, nonetheless, define various sub-grammars of the group grammar to constrain matters in so as to be consistent with the XML schemas specification.
However, it is helpful to define additional syntactic categories that specify various subsets of groups. These syntactic classes are then used to constrain the content of components, for instance, to indicate that the content of an element component should be an element, and that the content of a type component should consist of attributes followed by elements.
An attribute group contains only attribute names, combined using the all connector (&). An element group contains no attribute names. (Shortcoming: all groups in element groups should be further constrained as in Schema Part 1, Section 5.7, All Group Limited.)
|
Given the above, we can specify the allowed contents of the four sort of component as follows. An attribute content is either an attribute or an optional attribute, where the content is a simple type name. An element content is an element where the content is a type name. A simple type content is an atomic datatype or a list of atomic datatype. A complex type content is an attribute group followed by either a simple type content or an element group.
|
The content of each sort of component corresponds to the syntax above. That is, the content of an attribute component is always an attribute content ac; the content of an element component is always an element content ec; the content of a simple type component is always a simple content sc; and the content of a complex type component is always a complex content kc. Further, for an attribute or element component the name of the component is the same as the name of the attribute or element in its content.
It is easy to confirm that the example components in Section 2.2.2 satisfy these constraints.
A forest is a sequence of items, where each item is either an atomic datatype, or an attribute (with a list of items of a single atomic datatype as content), or an element (with a forest as content). We let d range over forests.
|
Examples of forests appear in Section 2.3.
A typed forest is an ordered forest with added type information for each element and attribute. We let td range over typed ordered forests.
|
Add a section describing any additional rules for the full forest grammars.
Operations such as normalization and matching are described with an inference rule notation. Originally developed by logicians [15,16,7], this notation is now widely used for describing type systems and semantics of programming languages [10]. In this notation, when all judgements above the line hold, then the judgement below the line holds as well. Here is an example of a rule used later on. We write d in g if forest d matches group g.
Sequence:
d1 in g1 d2 in g2
d1 ,d2 in g1, g2
The rule says that if both d1 in g1 and d2 in g2 hold, then d1 ,d2 in g1 , g2 holds as well. For instance, take d1 = a[1], d2 = b["two"], g1 = a[xsi:integer], and g2 = b[xsi:string]. Then since both
|
hold, we may conclude that
|
holds.
This section needs to be drastically revised, as normalization will need to occur as part of validation. Therefore the inference rules are certainly misplaced.
Normalization of a forest replaces each name by the corresponding normalized name, and adds type information to the forest. Normalization is performed with respect to a given schema; in our formalism the schema is determined by the dereferencing map, deref(). Section 2.3 gives an example of a document before and after normalization.
Prior to normalization, all names in the forest have exactly one symbol name. We build normalized names by extending a name with an additional symbol name. Let x1 and x2 be two names, with namespace(x1) = namespace(x2), and where the second forest has only one symbol name. We write x1 |> x2 for the operation that extends x1 by adding the symbol name of x2, defined as follows.
|
On the other hand, if x1 and x2 are from different namespaces (namespace(x1 ) = i, namespace(x2) = j and i ? j), then x1 |> x2 is defined as:
|
Finally, for each sort there is a root type (AnyType, AnyElement, etc.) These are fixed points, i.e.,
|
(Since these constants will eventually be defined in a fixed namespace, this is really subsumed by the previous rule.)
We write x |- a ?a' and x |- e ?e' to indicate that in the context specified by name x that attribute name a normalizes to a' or that element name e normalizes to e'. To normalize an attribute or element we extend the context (if the extended name is in the domain of deref(); these are the `extend' rules), or use the element name directly (otherwise; these are the `reset' rules). We write x in dom(deref()) and x notin dom(deref()) to indicate whether or not x is in the domain of the dereferencing map; that is, whether or not deref(x) is defined. If x1 and x2 are in different namespaces, then x1 |> x2 is undefined, and we say x notin deref() holds.
Extend Attribute Transitive:
y |> a in dom(deref())
x <: y
x |- a ? y |> a
If the attribute name does not appear for the current type, check for that name among supertypes.
Extend Element Transitive:
y |> e in dom(deref())
x <: y
x |- e ? y |> e
If the element name does not appear for the current type, check for that name among supertypes.
Extend Attribute Base:
a in dom(deref())
x |- a ? a
An attribute name can be normalized if it corresponds to a known name.
Extend Element Base:
e in dom(deref())
x |- e ? e
An attribute name can be normalized if it corresponds to a known name.
EDITORS NOTE: These inference rules will need to be revisited with regards to the typing of wildcards, and inclusion of model and attribute groups.
We write x |- d ?dt to indicate that in the context specified by name x that forest d normalizes to typed forest td. We write @xsi:type notin d if d does not contain an xsi:type attribute. Note that the type names in xsi:type attributes always refer to global types and need not be normalized.
Constant:
x |- c ? c'
Empty Document:
x |- e ? e
Sequence:
x |- d1 ? td1 x |- d2 ? td2
x |- d1,d1 ? td1 , td2
Attribute:
x |- a ? a'
deref(a').content = a'[s] or deref(a').content = a'[s]{0,1}
s |- d ? td
x |- a[d] ? a'[s types td]
Untyped Element:
x |- e ? e'
@xsi:type notin d
deref(e').content = e'[t]
t |- d ? td
x |- e[d] ? e'[t types td]
Typed Element:
x |- e ? e'
deref(e').content = e'[t]
t <: t'
t |- d ? td
x |- e[@xsi:type[t], d] ? e'[t types td]
The (Typed Element) rule uses the relation x < :x', which is defined Section 5.1.
We write x <: :x' if starting from the component with name x one can reach the component with name x' by successively following base links.
Reflexive:
x <: x
Transitive:
x <: x' x' <: x''
x <: x''
Base:
deref(x).base = x'
x <: x'
We write g <:ext g' if group g is derived from group g' by adding attributes and elements. It is specified using attribute groups ag and element groups ag as defined in Section 3.6.
Extend:
(ag & ag') , eg , eg' < :ext ag , eg
We write g < :res g' if the instances of group g are a subset of the instances of group g'. That is, g <:res g' if for every forest d such that d in g it is also the case that d in g'.
A schema must satisfy certain constraints on derivation to be well-formed. Define x <:der x' to be x <:res x' if der = restriction and x <:ext x' if der = extension. We write |- x to indicate that the component with name x is well-formed with respect to derivation. (N.B. This use of turnstile differs from that in normalization. One of us [ALB] suggests that the normalization turnstile should be replaced with |~.)
Refinement:
x' = deref(x).base
der = deref(x').derivation
deref(x).content < :der deref(x').content
|- x
We have already introduced a linear representation of an ordered (typed) forest. Content models are, in effect, grammars for such forests. Indeed, content models can be converted to regular tree grammars [ref]. We call the result of this conversion the tree closure of the content model. This conversion process, roughly speaking,
From the tree closure we can construct by well known methods [ref] a regular tree automaton. Validation is then a question of whether a forest of the kind defined earlier is accepted by the automaton constructed from the tree closure. We contrast this "compiled" version of validation with its "interpreted" alternative. In the latter case we would deconstruct forests and content groups in parallel, demonstrating that each constituent of the forest had a corresponding constituent in the content group. As for compiled validation, the terminal symbols of the tree grammar are, in fact, arbitrary strings, constrained only by the atomic datatypes of which they are declared to be instances: strings, dates, integers, etc. Of course, all of these lexical forms have corresponding regular expression definitions are just special cases of regular tree grammars. For the primitive atomic datatype p we will assume that π(p) yields the regular tree grammar for that type and that a is the generic
Let tk range over tree closures.
|
We see that (syntactically) a tree closure is a kind of content group. It is natural then to think of the relation ship between a content group and its tree closure as simply another kind of reduction relationship on content groups, hence we write it as < :tk. < :tk is preserved by rewriting content models using any of the matching rules of section 3.4
empty sequence:
e < :tk e
empty choice:
� < :tk �
nonempty Sequence:
tk1 < :tkg1 tk2 < :tk g2
tk1 , tk2 < :tk g1 , g2
nonempty choice:
tk1 < :tkg1 tk2 < :tk g2
tk1 | tk2 < :tk g1 | g2
Ordered alternative:
tk1 < :tkg1 tk2 < :tk g2
tk1 & tk2 < :tk g1 & g2
Group repetition:
tk < :tk g
tk{m,n} < :tk g{m,n}
attribute nameset:
tk < :tk ag w = w' UNION {a} tk' < :tk w'[tk]
@a[tk] | tk' < :tk @w[ag]
element nameset:
tk < :tk eg w = w' UNION {e} tk' < :tk w'[tk]
e[tk] | tk' < :tk w[eg]
mixed content:
tk1 < :tk mixed(eg1) tk2 < :tk mixed(eg2)
xsd:string{0,1} , tk1 , xsd:string{0,1} , tk2 , xsd:string{0,1} < :tk mixed(eg1,eg2)
A fine point : What is the status of a string followed by a string in a mixed content model? It is presumed here that it's still just a string not a sequence of strings.
Model group component:
deref(x)..content = eg tk < :tk eg x.srt = modelGroup
tk < :tk x
Attribute group component:
deref(x)..content = ag tk < :tk ag x.srt = attributeGroup
tk < :tk x
Element component:
deref(x)..content = c tk < :tk w[tk'] tk' < :tk c
w = {y s.t. y <: x deref(y).abstract = false y.srt = element}
tk < :tk x
attribute component:
deref(x)..content = c tk < :tk c x.srt = group
@x[tk] < :tk x
unsubtyped concrete complex Type component:
deref(x).content = false deref(x)..content = c tk < :tk c x.srt = complexType
There is no y s.t. y <: x
tk < :tk x
unsubtyped abstract complex Type component:
deref(x).content != abstract deref(x)..content = c tk < :tk c x.srt = complexType
There is no y s.t. y <: x
� < :tk x
subtyped concrete complex Type component:
y1 ... ym are the immediate subtypes of x by extension
z1 ... zn are the immediate subtypes of x by restriction
tk < :tk deref(x)..content x.srt = complexType deref(x).abstract = false
sk1 < :tk deref(y1)..content ... skm < :tk deref(ym)..content
rk1 < :tk deref(z1)..content ... rkn < :tk deref(zn)..content
tk | (tk , (( sk1 | ... | skm ) | ( rk1 | ... | rkn ))) < :tk x
subtyped abstract complex Type component:
y1 ... ym are the immediate subtypes of x by extension
z1 ... zn are the immediate subtypes of x by restriction
tk < :tk deref(x)..content x.srt = complexType deref(x).abstract = true
sk1 < :tk deref(y1)..content ... skm < :tk deref(ym)..content
rk1 < :tk deref(z1)..content ... rkn < :tk deref(zn)..content
tk , (( sk1 | ... | skm ) | ( rk1 | ... | rkn )) < :tk x
unsubtyped concrete simple Type component:
deref(x).content = false deref(x)..content = c tk < :tk c x.srt = simpleType
There is no y s.t. y <: x
tk < :tk x
unsubtyped abstract simple Type component:
deref(x).content != abstract deref(x)..content = c tk < :tk c x.srt = simpleType
There is no y s.t. y <: x
� < :tk x
subtyped concrete simple Type component:
z1 ... zn are the immediate subtypes of x by restriction
tk < :tk deref(x)..content x.srt = complexType deref(x).abstract = false
rk1 < :tk deref(z1)..content ... rkn < :tk deref(zn)..content
tk | rk1 | ... | rkn < :tk x
subtyped abstract simple Type component:
z1 ... zn are the immediate subtypes of x by restriction
tk < :tk deref(x)..content x.srt = complexType deref(x).abstract = true
rk1 < :tk deref(z1)..content ... rkn < :tk deref(zn)..content
rk1 | ... | rkn < :tk x
Primitive Atomic datatype:
π(p) < :tk p
This section is largely made obsolete by the previous section. Some of the rules above depend on element and type reducibility defined in this section. In some future iteration of this document we elide the irrelevant rules.
We write c inp p if constant c matches atomic datatype p. We do not specify this relation further, but simply assume it is as defined in XML Schema Part 2.
We write x inw w and e inw w if name x belongs to nameset w. We write e notinw w if it is not the case that x inw w.
Any Namespace:
x inw*:*
Given Namespace:
namespace(x) = i
x inw i:*
Singleton Namespace:
deref(x) <: deref(i#j)
x inw i#j
Wildcard Union 1:
x inW w1
x inW w1 UNION w2
Wildcard Union 2:
x inW w2
x inW w1 UNION w2
Wildcard Difference:
x inW w1 e notinW w2
e inW w1 DIFFERENCE w2
We write d |?unmix d' (read ``d unmixes to d''') if d is a sequence of elements and characters and d' is the same sequence with all character data removed. This is used for processing mixed content.
Unmix Empty:
e |?unmix e
Unmix Sequence:
d1 |?unmixd'1 d2 |?unmix d'2
d1 , d2 |?unmix d'1 , d'2
Unmix Element:
e[d] |?unmix e[d']
Unmix Character Data:
c |?unmix e
We write d |?inter d';d'' (read "d interleaves d' and d'' ") if some interleaving of d' and d'' yields d. This relates one sequence to many pairs of sequences. This is used for processing g1 &g2.
Interleave Empty:
e |?inter e;e
Interleave Sequence:
d1 |?interd'1;d"1 d2 |?inter d'2;d"2
d1 , d2 |?inter d'1 , d'2 ;d"1,d"2
Interleave Item 1:
d |?inter d;e
Interleave Item 2:
d |?inter e;d
We write d in g if forest d matches group g.
Empty:
e in e
Sequence:
d1 in g1 d2 in g2
d1 , d2 in g1 , g2
Choice 1:
d in g1
d in g1 | g2
Choice 2:
d in g2
d in g1 | g2
Interleave:
d |?inter d'1;d"2 d1 in g1 d2 in g2
d in g1 & g2
Repetition 1:
d1 in g d2 in g{m,n}
d1 ,d2 in g{m +1,n+1}
Repetition 2:
d1 in g d2 in g{0,n}
d1 ,d2 in g{0,n+1}
Repetition 3:
e in g{0,n}
Attribute:
d in g a inww deref(a).content=g
a[d] in @w
Element:
d in g e inww deref(e).content=g
e[d] in w
Attribute Skip:
a inww
a[d] in @w%skip
Element Skip:
e inww
e[d] in w%skip
Mixed Group:
d |?unmix d' d' in g
d in mixed(g}
Typed Attribute:
d in s
e[s types d] in e[s]
Typed Element:
d in t t <: t'
e[t types d] in e[t']
Atomic Datatype:
c inp p
c in p
Element Refinement:
d in e e <: e'
d in e'
Component Name:
d in g g = deref(x).content
d in x
The (Typed Element) and (Element Derivation) rules use the relation x < :x', which is defined in Section 5.1. The check that t < :t' in the (Typed Element) rule is redundant, as it is also performed during normalization.
When processing a normalized document with types, the ( Attribute) and (Element) rules are not required, the (Typed Attribute) and ( Typed Element) rules are used instead. However, we will write td in g whenever |- d ?td and d in g.
Append section on identity constraints.
We write nc in IDREFs(td) if nmtoken constant nc appears as the content of an attribute or element of type IDREF with typed forest td. We write nc in IDs(td) if nmtoken constant nc appears as the content of an attribute or element of type ID somewhere with typed forest td. We write nc in ! IDs(td) if nmtoken constant nc appears exactly once as the content of an attribute or element of type ID somewhere with typed forest td. We write nc in IDs!(td) if nc in! IDs(td). We write td OK if typed forest td is valid with respect to ID and IDREF, that is, if no ID is defined twice, and every IDREF has a corresponding ID.
IDREFs(d) ? IDREFs(td) IDs(td) ? IDs!(tc)
td OK
A value nc counts as a reference whenever there is an element or attribute of type IDREF in an instance having nc as its value:
A-Refs:
nc in IDREFs(a[IDREF types nc])
E-Refs:
nc in IDREFs(e[IDREF types nc])
A value nc counts as a referenece whenever there is an element among whose children nc counts as a referenece:
Child-Refs:
nc in IDREFs(td')
nc in IDREFs(e[t' types td'])
A value nc counts as a reference among a sequence of instances whenever it counts as a reference among a subsequence of those instances:
Subref 1:
nc in IDREFs(td1)
nc in IDREFs(e[td1 , td2])
Subref 2:
nc in IDREFs(td2)
nc in IDREFs(e[td1 , td2])
The notation in! indicates that a structure of a given shape occurs uniquely within another. An instance td satisfies the id-uniqueness criterion whenever any NCNAME that is among the IDs of td is also among its uniquely occurring IDs:
Not-ID:
nc notin IDs(td)
nc in IDs(td) ? nc in! IDs(td)
ID:
nc in! IDs(td)
nc in IDs(td) ? nc in! IDs(td)
A value nc counts as an ``id'' whenever there is an element or attribute of type ID in an instance having nc as its value::
A-ID:
nc in! IDs(a[ID types nc])
E-ID:
nc in! IDs(e[ID types nc])
A value nc counts as an ``id'' among a sequence of instances whenever it counts as an ``id'' among a subsequence of those instances, and does not count as an ``id'' among the remaining subsequence of those instances:
ID 1:
nc in IDs(td1)
nc in IDs(td1 , td2)
ID 2:
nc in IDs(td2)
nc in IDs(td1 , td2)
A value nc counts as a unique ``id'' among a sequence of instances whenever it counts as an ``id'' among a subsequence of those instances, and does not count as an ``id''among the remaining subsequence of those instances:
UN-ID 1:
nc in! IDs(td1) nc notin IDs(td2)
nc in! IDs(td1 , td2)
UN-ID 2:
nc in! IDs(td2) nc notin IDs(td1)
nc in IDs(td1 , td2)
Lastly, we have the following obvious relationship between occurrence in IDs and unique occurrence in IDs:
InnIDs-InIDs:
nc in! IDs(td)
nc in IDs(td)
EDITOR'S NOTE: Future versions of this document will contain a mapping from the XML Schema components described in [11] to sorts. Both XML Schema and models make a distinction between the underlying model (components in the case of XML Schema, sorts in the current case) and the surface syntax (the set of valid <schema> elements accepted for either). In both cases, the underlying model is considered more significant.
This section will describe the mapping from XML Schema instance syntax to sorts. This requires performing two mutually recursive activities:
To do so, we also introduce two new relations:
In any language of the complexity of XML Schema, there are both syntactic constraints expressible directly in the syntax of the language, and semantic constraints which further limit allowed expressions. In the following we enumerate those fragments of XML Schema which correspond to semantically valid expressions. While this could be done by enumerating all such sequences, that would include enumerating all the different cases of optionality and order - a daunting task. Instead, we reuse the grammars for content models developed above to specify fragments of XML and then pattern match against portions of this. The goal is to cover all fragments of XML Schema which are semantically coherent - other fragments may be syntactically valid, but not correspond to useable constructs. In each of the inference rules, the left hand side will be a string in this grammar. Strings in bold match strings in the XML instance. Strings in italics pattern match as variables to be used in the inference rule. As these represent fragments of schemas valid against the Schema for Schemas, we assume they have been validated and all default/fixed values for attributes are present. The only particular addition to this is to consider ``*'' as the default value for the name attribute of a nested complexType.
The following fragment gives an example:
anElem[@attr1[val1], @attr2[val2], nest[eg], ev]
Here we have:
Note that we provide a sequence for the attributes. This is purely for the convenience of the reader - in an actual instance these would appear in any order.
We also make the following additions to the grammar specified up to this point:
|
This formalism extends derivation to cover all sorts. Therefore, every kind of sort has a base sort from which all user-defined sorts must, ultimately, be derived. Of these, only two, for complex and simple types, are currently available from XML Schema. For the time being, the rest (such as for elements and attributes) are restricted to sorts and are not available to users.
Write All:
x |- ev1 -? e1
...
x |- evn -? en
x |- all[ev1...evn] -? (e1&...&en)
If there is an idall element with content ev1,...,evn and each evi converts to ei in the context of x, then the element converts to (e1,...,en).
Write Sequence:
x |- ev1 -? e1
...
x |- evn -? en
x |- sequence[@minOccurs[m] , @maxOccurs[k], ev1...evn] -? (e1&...&en){m.k}
Write Choice:
x |- ev1 -? e1
...
x |- evn -? en
x |- choice[@minOccurs[m] , @maxOccurs[k], ev1...evn] -? (e1|...|en){m.k}
For a sequence or choice with minOccurs or maxOccurs, where one or the other has a value other than 1, that sequence or choice converts to a representation with min and max values indicated at the end.
Write Model Ref:
g = deref(x |> n).content
x |- group[@ref[n]] -? g
A reference to a group writes as the contents of the corresponding group sort.
Write AttGroup Ref:
g = deref(x |> n).content
x |- attributeGroup[@ref[n]] -? g
A reference to an attributeGroup writes as the contents of the corresponding group sort.
Write Complex:
x |- complexType[t] =? c
x |- complexType[t] -? c.name
If a complexType corresponds to some sort, c, then it writes as the name of that sort.
Write Attribute:
x |- attribute[@name[s] , ag , eg] =? c
x |- attribute[@name[s] , ag , eg] -? c.name
If an attribute corresponds to some sort, c, then it writes as the name of that sort.
Write Attribute Ref:
x |- attribute[@ref[s] , ag , ev1,...,evn] ? deref(x |> s).name
If an attribute (in a content model) refers to some other attribute, c, then it writes as the name of the sort corresponding to that attribute.
Write Element Ref 1:
x |- element[@name[s] , ag , eg] =? c
x |- element[@name[s] , ag , eg] -? c.name
If an element corresponds to some sort, then it writes as the name of that sort.
Write Occurs:
x |- element[ag , eg] -? y
x |- element[@minOccurs[m] , @maxOccurs[k] , ag , eg] -? y{m, k}
If an element has minOccurs or maxOccurs attributes, one of which has a value other than 1, and the element without the attributes writes as y, then the element with the attributes writes as y{m, n}, where m and n are the values of the attributes.
Write Element Ref 2:
x |- element[@ref[s] , ag , eg] -? deref( x |> s).name
If an element (in a content model) refers to some other element, c, then it writes as the name of the sort corresponding to that attribute.
Valid Schema Doc:
x|- e1=?srt1
...
x|- ek =? srtk
|- schema[@targetNamespace[x], e1, ..., ek]
A schema element is accepted if all of its children convert to components in the context of its targetNamespace.
Map Complex A:
y = x |> n
y |- cm -? elems y |- am -? atts
x |- complexType[@abstract[a] , @final[f] , @block[b] ,
@mixed[m] , @name[n] , cm , am]
=? complex(name = y, base = xsi:AnyType,
derivation = restriction,
refinement = if (f == ##all) then {restriction, extension} else f,
abstract = a
content = (atts, if (m == true) then mixed(elems) else elems))
Given a complex type which is not a derivation, we determine its name and convert its attribute and content definitions into component content (within the context of the name). We then use these to create a complex sort for the complex type.
Map Restriction 1:
y = x |> n
z = deref(x |> p)
x.content = (am2 ,cm2)
y |- cm -? cont y |- am -? atts
x |- complexType[@abstract[a] , @final[f] , @block[b] ,
@mixed[m] , @name[n] ,
complexContent[restriction[@base[p],cm , am]]
=? complex(name = y, base = x.name,
derivation = restriction,
refinement = if (f == ##all) then {restriction, extension} else f,
abstract = a
content = (((am2 - attrs), attrs), if (m == true) then mixed(cont) else cont))
If a complex type is a restriction of another type, then we proceed as above, except we retrieve the contents of the super type and the set of attributes of the derived type is a combination of its own and those of the parent. In this case, am2 - attrs represents the attributes defined in am2 less any attributes in attrs with the same name. (Note, this definition may require more work.)
Map Complex Extension:
y = x |> n
z = deref( x |> p)
x.content = (am2 ,cm2)
y |- cm -? cont y |- am -? atts
x |- complexType[@abstract[a] , @final[f] , @block[b] ,
@mixed[m] , @name[n] ,
complexContent[extension[@base[p],cm , am]]
=? complex(name = y, base = z.name,
derivation = extension,
refinement = if (f == ##all) then {restriction, extension} else f,
abstract = a
content = (((am2 - attrs), attrs), if (m == true) then mixed(cm2,
cont) else cm2 , cont))
If the complex type is an extension of the complex type, then we retrieve the contents of the super type. The attributes of the derived type is the union of its attributes and those of the supertype. Its content model is a sequence consisting of the content model of the supertype followed by that of the subtype declaration.
Map Restriction 2:
y = x |> n
z = deref( x |> p)
x.content = (st2 ,am2)
y |- st -? simp y |- am -? attrs
x |- complexType[@abstract[a] , @final[f , @block[b] ,
@mixed[m] , @name[n] ,
simpleContent[restriction[@base[p],st , am]]
=? complex(name = y, base = z.name,
derivation = extension,
refinement = if (f == ##all) then {restriction, extension} else f,
abstract = a
content = ((am2 , attrs), if (m == true) then mixed(simp) else cm2 ,
simp))
If a complex type is a restriction with simple content, then the base type refers to a complex type with simple content. The content of that type (z, above) must be a simple type and 0 or more attributes. We convert the simple type description and create a new complex sort.
Map Model Group Definition
y = x |> n
y |- mg --> g
x |- group[@name[n], mg]
=? modelGroup(name = y,
base = AnyGroup,
derivation = restriction,
refinement = {},
abstract = false
content = g)
Map Attribute Group Definition
y = x |> n
y |- mg --> g
x |- attributeGroup[@name[n], mg]
=? attributeGroup(name = y,
base = AnyGroup,
derivation = restriction,
refinement = {},
abstract = false
content = g)
Map Global Element 1:
y = x |> n
z = x |> s
c = deref( x |> t)
c in complex
x |- element[@abstract[a] , @final[f , @block[b] , @name[n]
,
@nillable[u], @substitutionGroup[s] , @type[t]]
=? element(name = y,
base = if (z |- null) then z else AnyElement,
derivation = c.derivation,
refinement = {restriction, extension},
abstract = a
content = c.name)
To create an element sort using a type reference to a complex type.
Map Global Element 2:
y = x |> n
z = x |> s
y |- t ? c
x |- element[@abstract[a] , @final[f , @block[b] , @name[n]
, @form[o] , default[d] ,
@fixed[i] , @nillable[u], @substitutionGroup[s] , @type[t]]
=? element(name = y,
base = if (z |- null) then z else AnyElement,
derivation = c.derivation,
refinement = {restriction, extension},
abstract = a
content = c.name)
To create an element containing an inlined type definition, find the sort corresponding to the type definition and create the element sort using the name of the type definition for the content.
Map Local Element 1:
y = x |> n
c = x |> t
x |- element[@default[d], @fixed[i] , @name[n] ,
@form[o] ,
@maxOccurs[m] , @minOccurs[n] , @nullable[u], @type[t]]
=? element(name = y,
base = AnyElement,
derivation = restriction,
refinement = {},
abstract = false
content = c.name)
A local element which references a type creates a new element structure, whose content is the name of the referenced type.
Map Local Element 2:
y = x |> n
y |- t ? c
x |- element[@default[d], @fixed[i] , @name[n] ,
@form[o] ,
@maxOccurs[m] , @minOccurs[n] , @nullable[u], t]
=? element(name = y,
base = AnyElement,
derivation = restriction,
refinement = {},
abstract = false
content = c.name)
A local element with an inlined type declaration.
Map Attribute 1:
y = x |> n
c = x |> t
x |- attribute[@name[nd], @form[o] , @type[tn] , @use[u]
, @value[v]]
=? attribute(name = y,
base = AnyAttribute,
derivation = restriction,
refinement = {},
abstract = false
content = c)
An attribute declaration referencing a type.
Map Attribute 2:
y = x |> n
y |- s ? c
x |- attribute[@name[nd], @form[o] ,
@use[u] , @value[v], s]
? attribute(name = y,
base = AnyAttribute,
derivation = restriction,
refinement = {},
abstract = false
content = c.name)
An attribute with an inlined type definition.
This section specifies the mapping from the components described in XML Schemas, Part II, to the sorts described in this document. The consequent of each rule provides the XSDL component on the left and the corresponding formal component on the right. We've represented each XSDL component type as a structure similar to our own, so, for example, an XSDL particle is represented as a structure with name particle and three fields, minOccurs, maxOccurs, and term. The value of each field is a variable which can be used either in the antecedent, or in the second part of the consequent, which specifies the corresponding formal structure. In the case of a particle or model group, the formal correspondance is to a piece of content group syntax, but in the other cases it is to a sort. As there are a number of optional fields in the XSDL components, if a field does not have a value we assume it is null.
We represent the mapping from an XSDL component to a formal component by:
Global Element:
s = global
u |> n |- t ~> t'
e ~> e'
element(name=n,
targetNamespace=u,
typeDefinition=t,
scope=s,
valueConstraint=v,
nillable=b,
identityConstraintDefinitions=d,
substitutionGroup=e,
substitutionGroupExclusions=x,
disallowedSubstitutions=d,
abstract=a,
annotation=z)
~>
element(name= u|>n
abstract= a
base= if e' = null then UrElement else e'.name
content= u|>n[t'.name]
derivation= if t' != e'.type then deref(t').derivation else restriction
refinement= if substitutions EO d then {} else x)
local element
s=local
y = e |> n
y |- t ~> t'
e |- element(name=n,
targetNamespace=u,
typeDefinition=t,
scope=s,
valueConstraint=v,
nillable=b,
identityConstraintDefinitions=d,
substitutionGroup=e,
substitutionGroupExclusions=x,
disallowedSubstitutions=d,
annotation=z)
~>
element(name= y,
abstract= false,
base= UrElement,
content= y[t'.name],
derivation= restriction,
refinement= {} )
complex type
y = if n == null then e/type::* else t |> n
b ~> b'
y |- a ~> a'
y |- g ~> g'
e |- complexType(name= n
targetNamespace= t
baseTypeDefinition= b
derivationMethod= m
final= f
abstract= a
attributeUsePairs= a
attributeWildcard= aw
contentType= g
prohibitedSubstitutions= r
annotations= ann)
~>
complex(name= y
abstract= a,
base= if b' = null then UrType else b'
content= (a', g'),
derivation= if b' == null then restrictionion else m
refinement= {refinement, restriction} - r)
Attribute Type - Global
sc=global
t |- s ~> s'
n' = t |> n
|- attribute(
name= n
target namespace= t
type definition= s
scope= sc
valueConstraint= vc
annotation= an)
~>
attribute(name= n'
abstract= false,
base= AnyAttribute
content= n'[s'.name]
derivation= restriction
refinement= {})
Attribute Type - Local
sc=local
t |- s ~> s'
n' = x |> n
x |- attribute(
name= n
target namespace= t
type definition= s
scope= sc
valueConstraint= vc
annotation= an)
~>
attribute(name= n'
abstract= false,
base= AnyAttribute
content= n'[s'.name]
derivation= restriction
refinement= {})
Model Group - Sequence
{x|- p_1 ~> g_1
...
x|- p_n ~> g_n
{x |- modelGroup(
compositor= sequence,
particles= p_1,...,p_n
annotation)
~>
(g_1 , ... , g_n)
Model Group - Choice
{x|- p_1 ~> g_1
...
x|- p_n ~> g_n
{x |- modelGroup(
compositor= choice,
particles= p_1,...,p_n
annotation)
~>
(g_1 | ... | g_n)
Model Group - All
{x|- p_1 ~> g_1
...
x|- p_n ~> g_n
{x |- modelGroup(
compositor= all,
particles= p_1,...,p_n
annotation)
~>
(g_1 & ... & g_n)
Particle
x|- t ~> g
{x |- particle(
minOccurs= m
maxOccurs= n
term= t)
~>
g{m,n}
This section contains stricter definitions of some of the non-terminals found in the context free grammars found throughout the main body of the description. In general, these more restricted forms are not required, as sorts will be constructed from XSDL transfer syntax or XSDL components which already enforce these restrictions. In addition, they are considerably longer than the versions in the main body of the text. We separate them out here so they do not interfere with understanding the main text.
We start by redefining sorts so as to constrain the values of the different fields. To do this we introduce new non-terminals for the different types of sorts. A sort is one of the six sorts of component in XML Schema. We let srt range over sorts.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
This document is based on the syntax of XML Schema in the proposed recommendation draft. The Formalization Taskforce will continue in operation until XML Schema becomes a recommendation.
Also, in a few places the specification is not quite equivalent to that in XML Schema, notably for the definition of derivation. We believe that with extra time it should be possible to model all or most of XML Schema.
[1] Serge Abiteboul and Peter Buneman and Dan Suciu, Data on the Web : From Relations to Semistructured Data and XML Morgan Kaufmann, 1999
[2] Alfred V. Aho, "Algorithms for Finding Patterns in Strings", Handbook of Theoretical Computer Science, Jan van Leeuwen, MIT Press Elsevier, Cambridge, Massachusetts, 1990
[3] Paul V. Biron and Ashok Malhotra, XML Schema Part 2: Datatypes, , World Wide Web Consortium, 2001, available at http://www.w3.org/TR/xmlschema-2/
[4] Tim Bray and Jean Paoli and C. M. Sperberg-McQueen, Extensible Markup Language (XML) 1.0, , World Wide Web Consortium, 1998, available at http://www.w3.org/TR/REC-xml
[5] James Clark and Steve DeRose, XML path language (XPath) version 1.0, World Wide Web Consortium, 1999, available at http://www.w3.org/TR/xpath
[6] David C. Fallside, XML Schema Part 0: Primer , World Wide Web Consortium, 2001, available at http://www.w3.org/TR/xmlschema-0/
[7] Gottlob Frege, "Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought (1879)", From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, ed. Jan van Heijenoort, , Harvard University Press, Cambridge, Massachusetts, 1967
[8] Haruo Hosoya and Jerome Vouillon and Benjamin C. Pierce, "Regular Expression Types for XML", Proceedings of the International Conference on Functional Programming (ICFP), 2000
[9] Tova Milo and Dan Suciu, "Type Inference for Queries on Semistructured Data", Proceedings of the ACM Symposium on Principles of Database Systems, 1999
[10] John C. Mitchell, Foundations for Programming Languages, , MIT Press, 1996, Cambridge, Massachusetts
[11] Henry S. Thompson, David Beech, Murray Maloney and Noah Mendelsohn, XML Schema Part 1: Structures, , World Wide Web Consortium, 2001, available at http://www.w3.org/TR/xmlschema-1/
[12] Philip Wadler, "A formal semantics of patterns in XSLT", Proceedings of Markup Technologies, ed. B. Tommie Usdin and Deborah A. Lapeyre and C. M. Sperberg-McQueen, Philadelphia, 1999
[13] Philip Wadler, "New Language, Old Logic", Dr Dobbs Journal, December, 2000
[14] Allen L. Brown, Jr., "Derivation, tolerance and validity: a formal model of type definition in XML Schemas", Proceedings of XML Europe 2000, ed. Pamela Gennusa, Paris, 2000
[15] Gaisi Takeuti, Proof Theory, Studies in Logic and the Foundations of Mathematics, vol. 81, North-Holland/American Elsevier, Amsterdam, 1975
[16] Dag Prawitz, Natural Deduction: A Proof-Theoretical Study, , Almqvist & Wiksell, Stockholm, 1965,
[17] Solomon Feferman, "Theories of Finite Type Related to Mathematical Practice", Handbook of Mathematical Logic, ed. Jon Barwise, Elsevier North Holland, Amsterdam, 1977


| Sporadic |
|
Soldner et al. |
2009 |
Skin fibroblasts |
NA |
Generation of iPSC line |
|
Cooper et al. |
2010 |
Skin fibroblasts |
NA |
Improved small molecule differentiation protocol for generation of midbrain DA neurons |
|
Sánchez-Danés et al. |
2012 |
Epidermal keratinocutes and fibroblasts |
Unrelated healthy individual |
Dysfunctional autographic system described in sporadic and LRRK2 lines |
|
Zhang et al. |
2017 |
PBMCs |
NA |
Generation of iPSC line |
| LRRK2 |
p.Gly2019Ser |
Nguyen et al. |
2011 |
Skin fibroblasts |
Unrelated healthy individual |
First study showing a pathological phenotype in PD iPSC-derived neurons |
| p.Gly2019Ser |
Sánchez-Danés et al. |
2012 |
Skin fibroblasts |
Unrelated healthy individual |
Dysfunctional autographic system described in sporadic and LRRK2 lines |
p.Gly2019Ser/
p.Arg1441Cys
|
Cooper et al. |
2012 |
Skin fibroblasts |
Unrelated healthy individual |
Mitochondrial dysfunction in patient lines |
| p.Gly2019Ser |
Orenstein et al. |
2013 |
Skin fibroblasts |
Unrelated healthy individual |
Effect of LRRK2 mutation on chaperone-mediated autophagy |
p.Gly2019Ser/
p.Arg1441Cys
|
Lopez-de Maturana et al. |
2016 |
Skin fibroblasts |
Unrelated healthy individual |
Effect of mutations on NFkB pathway |
pAsn551Lys/
p.Ser1647Thr/
p.Arg1398His/
p.Arg1628Pro
|
Ma et al. |
2017 |
PBMCs |
NA |
Generation of iPSC lines |
| PINK1 |
p.Gln456Xaa /
p.Val170Gly
|
Seiber et al. |
2011 |
Skin fibroblasts |
Healthy family member |
Mitochondrial defects in mutant lines |
| p.Gln456Xaa |
Chung et al. |
2016 |
Skin fibroblasts |
Unrelated healthy individual |
Compared floor-plate vs neural-rosette differentiation protocols |
| p.Gln456Xaa |
Cooper et al. |
2012 |
Skin fibroblasts |
Unrelated healthy individual |
Mitochondrial dysfunction in patient lines |
| SNCA (
α-synuclein)
|
p.Ala53Thr/
p.Glu46Lys
|
Soldner et al. |
2011 |
Skin fibroblasts |
| Triplication |
Byers et al. |
2011 |
Skin fibroblasts |
Healthy family member |
Confirmed synuclein over expression in the triplication line |
| Triplication |
Devine et al. |
2011 |
Skin fibroblasts |
Healthy family member |
Confirmed synuclein over expression in the triplication line |
| Triplication |
Oliveira et al. |
2015 |
Skin fibroblasts |
Unrelated healthy individual and healthy family member |
Impact of synuclein over expression on DA neuron differentiation |
| GBA-1 (GCase) |
p.Asn370Ser/ c.84dupG |
Mazulli et al. |
2011 |
Skin fibroblasts |
Unrelated healthy individual |
Relation between synuclein and GCase mutation |
| PARK2 (Parkin) |
Deletion |
Imaizumi et al. |
2012 |
Skin fibroblasts |
Unrelated healthy individual |
Oxidative stress and mitochondrial dysfunction in PARK2 lines |
| Deletion |
Jiang et al. |
2012 |
Skin fibroblasts |
Unrelated healthy individual |
Link between Parkin and dopamine use in DA neurons |
| Deletion |
Ren et al. |
2015 |
Skin fibroblasts |
Unrelated healthy individual |
Effect of deletions on neuronal arborization |
| Deletion |
Chang et al. |
2015 |
Skin fibroblasts |
Unrelated healthy individual |
Proteasomal dysfunction and oxidative stress in mutant neurons |
| p.Val324Ala |
Chung et al. |
2016 |
Skin fibroblasts |
Unrelated healthy individual |
Compared floor-plate vs neural-rosette differentiation protocols |
| Deletion |
Suzuki et al. |
2017 |
Skin fibroblasts |
Unrelated healthy individual |
Monitored mitophag in iPSC using mtKeima |
| Familial (LRRK2, SNCA, PARK2, GBA-1, PINK1) |
Refer to paper for specific mutations |
Holmqvist et al. |
2016 |
Skin fibroblasts |
NA |
Generation of iPSC lines from 43 PD patients |
| Refer to paper for specific mutations |
Momcilovic et al. |
2016 |
Skin fibroblasts |
NA |
Generation of iPSC lines from 10 PD patients |


I am currently a graduate student at Stanford University. I was previously at UC Berkeley where I studied Electrical Engineering and Computer Science. I spent most of my time there researching systems and deep learning at the Berkeley RISE/Sky Computing Lab, Google Brain, and Tesla Autopilot. I am interested in real-world applications of deep learning, data systems, computer- and human-generated art, jazz, and the design of products and systems.
To get in touch, send me an email.
Towards Language Models That Can See: Vision Through the LENS of Natural Language
William Berrios, Gautam Mittal, Tristan Thrush, Douwe Kiela, Amanpreet Singh
arXiv 2023
pdf
Code
Blog
Demo
SkyPilot: An Intercloud Broker for Sky Computing
Zongheng Yang*, Zhanghao Wu*, Michael Luo, Wei-Lin Chiang, Romil Bhardwaj, Woosuk Kwon, Siyuan Zhuang, Frank Sifei Luan, Gautam Mittal, Scott Shenker, Ion Stoica
USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2023
pdf
Code
Balsa: Learning a Query Optimizer Without Expert Demonstrations
Zongheng Yang, Wei-Lin Chiang*, Sifei Luan*, Gautam Mittal, Michael Luo, Ion Stoica
ACM Special Interest Group on Management of Data (SIGMOD), 2022
pdf
Code
Symbolic Music Generation with Diffusion Models
Gautam Mittal, Jesse Engel, Curtis Hawthorne, Ian Simon
International Society for Music Information Retrieval (ISMIR), 2021
pdf
Code
CS 186 (Databases) at UC Berkeley: Fall 2021 and Spring 2022
Cal Hacks at UC Berkeley: Fall 2019, Spring 2020, and Fall 2020


if i have closed some categories (BBlog, BF3, Forum, General Improvements) by the BBLog Options, than later i open the BBLog Settings and open one of the categories (f.e. forum) the scroll bar is missing. i have to close BBLog Settings and reopen it, to can scroll down. Bug was discovered with FF32
Topicstarter
ORFK
Global Moderator
brain.. please fix it ^^
BrainFooLong
Administrator
I am very busy at the moment, i will fix this later.
Topicstarter
ORFK
Global Moderator
no trouble / no stress ;-)
i just wanted to know that you saw it :-)


The page you are looking for can not be found or doesn't exist. please return to the home page and try again


Page 1 of 1
XenFP
Posted:
Sat Jun 09, 2007 7:03 pm
by a_link_to_the_past
Ya know... I have never really tried playing FP until today... but I am surprised.. Its actually pretty fun.. I'm getting my bum kicked by skeletons.. but hell.. its fun..
Posted:
Sat Jun 09, 2007 8:17 pm
by Karl G.
I could never get past the bug-killing stage
Posted:
Sat Jun 09, 2007 8:20 pm
by a_link_to_the_past
Well... its really tricky to get started... my character is almost lvl 7 I could kill more things if I could find a fire sword or something... but I stuck with a damn silver sword
Posted:
Sun Jun 10, 2007 12:46 am
by Volcomboy99
i could probably get u a f sword if u wanted me to
Posted:
Sun Jun 10, 2007 7:46 am
by a_link_to_the_past
Thanks for the offer but I finally found one... good thing those shadows blow their ventus behind them instead of infront..
Posted:
Tue Jun 12, 2007 4:43 pm
by shadowni
a_link_to_the_past wrote:Thanks for the offer but I finally found one... good thing those shadows blow their ventus behind them instead of infront..
I know lol, When i first saw that I said " What the hell? this is probably a bug" haha. I have a level 8 pally and i was gonna make a cleric but I don't feel like it now.
Posted:
Tue Jun 12, 2007 5:58 pm
by a_link_to_the_past
Caster classes seem to be really feniky (sp?) with killing things... I tried to start a wizard and I got irritated with the whole casting spell process...
Posted:
Tue Jun 12, 2007 6:09 pm
by shadowni
a_link_to_the_past wrote:Caster classes seem to be really feniky (sp?) with killing things... I tried to start a wizard and I got irritated with the whole casting spell process...
Finicky
And yeah, it does suck.
Posted:
Wed Jun 13, 2007 7:39 am
by a_link_to_the_past
I would play TD but for some reason.. it doesn't work anymore... the screen will go black like its getting ready to load the beginning credits... and then it returns to the desktop..
Posted:
Sun Jul 15, 2007 7:29 pm
by Necromadon
FP is wicked fun. I'm level 27 1/2, but I don't have the time or energy to get to 30.
Posted:
Wed Aug 01, 2007 8:25 pm
by Ratiotile
I think he should have ditched the whole spell targetting thing and just made the spell shoot out towards the crosshairs. It would have made it more like a real FPS, as well as faster-paced.
Posted:
Wed Aug 01, 2007 9:14 pm
by Karl G.
I agree, I always thought spell targeting was kinda dumb...but then again, it does make the networking code a LOT easier (that's probably what he was going for)
Posted:
Wed Aug 01, 2007 9:35 pm
by Ratiotile
Is the code easier because the spell is supposed to be guaranteed to hit? What if it hits a tree or hill?
For the spell shooting out like a bullet, he could take a look at code from Quake 2, since it's been released. It's probably loads better than his code...


Defines | |
| #define | ANSI_ESCAPE_SEQUENCE(EscapeSeq) "\33[" EscapeSeq |
Text Display Modifier Escape Sequences | |
| #define | ESC_BOLD_ON ANSI_ESCAPE_SEQUENCE("1m") |
| #define | ESC_ITALICS_ON ANSI_ESCAPE_SEQUENCE("3m") |
| #define | ESC_UNDERLINE_ON ANSI_ESCAPE_SEQUENCE("4m") |
| #define | ESC_INVERSE_ON ANSI_ESCAPE_SEQUENCE("7m") |
| #define | ESC_STRIKETHROUGH_ON ANSI_ESCAPE_SEQUENCE("9m") |
| #define | ESC_BOLD_OFF ANSI_ESCAPE_SEQUENCE("22m") |
| #define | ESC_ITALICS_OFF ANSI_ESCAPE_SEQUENCE("23m") |
| #define | ESC_UNDERLINE_OFF ANSI_ESCAPE_SEQUENCE("24m") |
| #define | ESC_INVERSE_OFF ANSI_ESCAPE_SEQUENCE("27m") |
| #define | ESC_STRIKETHROUGH_OFF ANSI_ESCAPE_SEQUENCE("29m") |
Text Colour Control Sequences | |
| #define | ESC_FG_BLACK ANSI_ESCAPE_SEQUENCE("30m") |
| #define | ESC_FG_RED ANSI_ESCAPE_SEQUENCE("31m") |
| #define | ESC_FG_GREEN ANSI_ESCAPE_SEQUENCE("32m") |
| #define | ESC_FG_YELLOW ANSI_ESCAPE_SEQUENCE("33m") |
| #define | ESC_FG_BLUE ANSI_ESCAPE_SEQUENCE("34m") |
| #define | ESC_FG_MAGENTA ANSI_ESCAPE_SEQUENCE("35m") |
| #define | ESC_FG_CYAN ANSI_ESCAPE_SEQUENCE("36m") |
| #define | ESC_FG_WHITE ANSI_ESCAPE_SEQUENCE("37m") |
| #define | ESC_FG_DEFAULT ANSI_ESCAPE_SEQUENCE("39m") |
| #define | ESC_BG_BLACK ANSI_ESCAPE_SEQUENCE("40m") |
| #define | ESC_BG_RED ANSI_ESCAPE_SEQUENCE("41m") |
| #define | ESC_BG_GREEN ANSI_ESCAPE_SEQUENCE("42m") |
| #define | ESC_BG_YELLOW ANSI_ESCAPE_SEQUENCE("43m") |
| #define | ESC_BG_BLUE ANSI_ESCAPE_SEQUENCE("44m") |
| #define | ESC_BG_MAGENTA ANSI_ESCAPE_SEQUENCE("45m") |
| #define | ESC_BG_CYAN ANSI_ESCAPE_SEQUENCE("46m") |
| #define | ESC_BG_WHITE ANSI_ESCAPE_SEQUENCE("47m") |
| #define | ESC_BG_DEFAULT ANSI_ESCAPE_SEQUENCE("49m") |
Cursor Positioning Control Sequences | |
| #define | ESC_CURSOR_POS_SAVE ANSI_ESCAPE_SEQUENCE("s") |
| #define | ESC_CURSOR_POS_RESTORE ANSI_ESCAPE_SEQUENCE("u") |
| #define | ESC_CURSOR_POS(Line, Column) ANSI_ESCAPE_SEQUENCE(#Line ";" #Column "H") |
| #define | ESC_CURSOR_UP(Lines) ANSI_ESCAPE_SEQUENCE(#Lines "A") |
| #define | ESC_CURSOR_DOWN(Lines) ANSI_ESCAPE_SEQUENCE(#Lines "B") |
| #define | ESC_CURSOR_FORWARD(Columns) ANSI_ESCAPE_SEQUENCE(#Columns "C") |
| #define | ESC_CURSOR_BACKWARD(Columns) ANSI_ESCAPE_SEQUENCE(#Columns "D") |
Miscellaneous Control Sequences | |
| #define | ESC_RESET ANSI_ESCAPE_SEQUENCE("0m") |
| #define | ESC_ERASE_DISPLAY ANSI_ESCAPE_SEQUENCE("2J") |
| #define | ESC_ERASE_LINE ANSI_ESCAPE_SEQUENCE("K") |
The following files must be built with any user project that uses this module:
Escape code macros for ANSI compliant text terminals.
Example Usage:
printf("Some String, " ESC_BOLD_ON " Some bold string");
| #define ANSI_ESCAPE_SEQUENCE | ( | EscapeSeq ) | "\33[" EscapeSeq |
Creates an ANSI escape sequence with the specified payload.
| [in] | EscapeSeq | Payload to encode as an ANSI escape sequence, a ESC_* mask. |
| #define ESC_BG_BLACK ANSI_ESCAPE_SEQUENCE("40m") |
Sets the text background colour to black.
| #define ESC_BG_BLUE ANSI_ESCAPE_SEQUENCE("44m") |
Sets the text background colour to blue.
| #define ESC_BG_CYAN ANSI_ESCAPE_SEQUENCE("46m") |
Sets the text background colour to cyan.
| #define ESC_BG_DEFAULT ANSI_ESCAPE_SEQUENCE("49m") |
Sets the text background colour to the terminal's default.
| #define ESC_BG_GREEN ANSI_ESCAPE_SEQUENCE("42m") |
Sets the text background colour to green.
| #define ESC_BG_MAGENTA ANSI_ESCAPE_SEQUENCE("45m") |
Sets the text background colour to magenta.
| #define ESC_BG_RED ANSI_ESCAPE_SEQUENCE("41m") |
Sets the text background colour to red.
| #define ESC_BG_WHITE ANSI_ESCAPE_SEQUENCE("47m") |
Sets the text background colour to white.
| #define ESC_BG_YELLOW ANSI_ESCAPE_SEQUENCE("43m") |
Sets the text background colour to yellow.
| #define ESC_BOLD_OFF ANSI_ESCAPE_SEQUENCE("22m") |
Turns off bold so that any following text is printed to the terminal in non bold.
| #define ESC_BOLD_ON ANSI_ESCAPE_SEQUENCE("1m") |
Turns on bold so that any following text is printed to the terminal in bold.
| #define ESC_CURSOR_BACKWARD | ( | Columns ) | ANSI_ESCAPE_SEQUENCE(#Columns "D") |
Moves the cursor to the left the given number of columns.
| [in] | Columns | Number of columns to move the cursor position |
| #define ESC_CURSOR_DOWN | ( | Lines ) | ANSI_ESCAPE_SEQUENCE(#Lines "B") |
Moves the cursor down the given number of lines.
| [in] | Lines | Number of lines to move the cursor position |
| #define ESC_CURSOR_FORWARD | ( | Columns ) | ANSI_ESCAPE_SEQUENCE(#Columns "C") |
Moves the cursor to the right the given number of columns.
| [in] | Columns | Number of columns to move the cursor position |
| #define ESC_CURSOR_POS | ( | Line, | |
| Column | |||
| ) | ANSI_ESCAPE_SEQUENCE(#Line ";" #Column "H") |
Sets the cursor position to the given line and column.
| [in] | Line | Line number to position the cursor at |
| [in] | Column | Column number to position the cursor at |
| #define ESC_CURSOR_POS_RESTORE ANSI_ESCAPE_SEQUENCE("u") |
Restores the cursor position to the last position saved with ESC_CURSOR_POS_SAVE.
| #define ESC_CURSOR_POS_SAVE ANSI_ESCAPE_SEQUENCE("s") |
Saves the current cursor position so that it may be restored with ESC_CURSOR_POS_RESTORE.
| #define ESC_CURSOR_UP | ( | Lines ) | ANSI_ESCAPE_SEQUENCE(#Lines "A") |
Moves the cursor up the given number of lines.
| [in] | Lines | Number of lines to move the cursor position |
| #define ESC_ERASE_DISPLAY ANSI_ESCAPE_SEQUENCE("2J") |
Erases the entire display, returning the cursor to the top left.
| #define ESC_ERASE_LINE ANSI_ESCAPE_SEQUENCE("K") |
Erases the current line, returning the cursor to the far left.
| #define ESC_FG_BLACK ANSI_ESCAPE_SEQUENCE("30m") |
Sets the foreground (text) colour to black.
| #define ESC_FG_BLUE ANSI_ESCAPE_SEQUENCE("34m") |
Sets the foreground (text) colour to blue.
| #define ESC_FG_CYAN ANSI_ESCAPE_SEQUENCE("36m") |
Sets the foreground (text) colour to cyan.
| #define ESC_FG_DEFAULT ANSI_ESCAPE_SEQUENCE("39m") |
Sets the foreground (text) colour to the terminal's default.
| #define ESC_FG_GREEN ANSI_ESCAPE_SEQUENCE("32m") |
Sets the foreground (text) colour to green.
| #define ESC_FG_MAGENTA ANSI_ESCAPE_SEQUENCE("35m") |
Sets the foreground (text) colour to magenta.
| #define ESC_FG_RED ANSI_ESCAPE_SEQUENCE("31m") |
Sets the foreground (text) colour to red.
| #define ESC_FG_WHITE ANSI_ESCAPE_SEQUENCE("37m") |
Sets the foreground (text) colour to white.
| #define ESC_FG_YELLOW ANSI_ESCAPE_SEQUENCE("33m") |
Sets the foreground (text) colour to yellow.
| #define ESC_INVERSE_OFF ANSI_ESCAPE_SEQUENCE("27m") |
Turns off inverse so that any following text is printed to the terminal in non inverted colours.
| #define ESC_INVERSE_ON ANSI_ESCAPE_SEQUENCE("7m") |
Turns on inverse so that any following text is printed to the terminal in inverted colours.
| #define ESC_ITALICS_OFF ANSI_ESCAPE_SEQUENCE("23m") |
Turns off italics so that any following text is printed to the terminal in non italics.
| #define ESC_ITALICS_ON ANSI_ESCAPE_SEQUENCE("3m") |
Turns on italics so that any following text is printed to the terminal in italics.
| #define ESC_RESET ANSI_ESCAPE_SEQUENCE("0m") |
Resets any escape sequence modifiers back to their defaults.
| #define ESC_STRIKETHROUGH_OFF ANSI_ESCAPE_SEQUENCE("29m") |
Turns off strikethrough so that any following text is printed to the terminal without a line through the center.
| #define ESC_STRIKETHROUGH_ON ANSI_ESCAPE_SEQUENCE("9m") |
Turns on strikethrough so that any following text is printed to the terminal with a line through the center.
| #define ESC_UNDERLINE_OFF ANSI_ESCAPE_SEQUENCE("24m") |
Turns off underline so that any following text is printed to the terminal non underlined.
| #define ESC_UNDERLINE_ON ANSI_ESCAPE_SEQUENCE("4m") |
Turns on underline so that any following text is printed to the terminal underlined.


htmltools
Although RStudio markdown supports LaTeX with MathJax , KaTeX from Khan Academy contends to be faster and better. This short example shows how we can employ KaTeX in R. We'll borrow heavily from the demo page code in the gh-pages branch of KaTeX for this quick set of examples.
As a direct comparision with the inline LaTeX, we'll use the same simple arithmetic mean example used in the RStudio tutorial.
For fun, let's grab the Greek letters from this list by scraping in R.


{% trans 'What is PyCon' %}
{% blocktrans trimmed %}The original PyCon was formed in North America in 2003, and now there are many other conferences being run in the PyCon spirit around the world.
{% endblocktrans %}{% extends 'base.html' %} {% load i18n static %} {% block styles %} {% endblock %} {% block extra_css %} {% endblock extra_css %} {% block titletag %}
The original PyCon was formed in North America in 2003, and now there are many other conferences being run in the PyCon spirit around the world.
{% endblocktrans %}PyCon Taiwan is an annual convention in Taiwan for the discussion and promotion of the Python programming language. It is held by enthusiasts and focuses on Python technology and its versatile applications. We welcome people who are interested in Python to join PyCon Taiwan to share knowledge, exchange ideas, make connections and to help us grow our network.
{% endblocktrans %}


--- layout: page title: Home ---
Brandon Spirito, a Systems and Embedded Software Engineer, is a Senior Member of Technical Staff in Secure and Assured System Software Division, supporting Software Modeling, Analysis & Validation at Charles Stark Draper Laboratory. He supported the analysis of submarine inertial navigation system algorithms, led a fault tolerant space application for United Launch Alliance’s Next Generation Flight Computer Redundancy Management to be used on the Vulcan rocket, and is currently supporting Flight Software Test development of the Cargo Resupply Services (CRS-2) program for the uncrewed Dream Chaser Space System (UDC). Prior to Draper Labs, Brandon worked as a Software Engineer for Harmonia subcontracting to General Dynamics Mission Systems on Submarine Weapon Control Systems. He supported the maintenance of weapon systems for 10 variants of submarines with weapons including Harpoon and Tomahawk missiles, ADCAP torpedos, and countermeasures. Additionally, he supported the development of harpoon missile reintegration on a legacy platform. He also worked for General Dynamics Electric Boat as a Software Engineer supporting the development of Submarine Ship Control Systems for the Ohio Class and Virginia Class submarines. Brandon received his B.S. in Electrical Engineering from the University of Rhode Island and his M.S. in Systems Engineering from the Worcester Polytechnic Institute.


|
Name
|
Type
|
Description
|
| limit | xsd:long |
The bandwidth limit for the virtual network adapter.
The utilization of the virtual network adapter will not
exceed this limit, even if there are available resources.
To clear the value of this property and revert it to unset,
set the vaule to "-1" in an update operation.
Units in Mbits/sec.
|
| reservation | xsd:long |
Amount of network bandwidth that is guaranteed to the
virtual network adapter.
If utilization is less than reservation, the resource can be used by
other virtual network adapters. Reservation is not allowed to exceed the
value of limit if
limit is set.
Units in Mbits/sec.
|
| share | SharesInfo |
Network share. The value is used as a relative weight in
competing for shared bandwidth, in case of resource contention.
|
|
Properties inherited from DynamicData |
| None |


As a software engineer I have a vested interest in disproving this statement. Bjarne Stroustroup says C++ is designed to create efficient abstractions. A software engineer’s job is to create simple abstractions to complex systems. State machines form a large part of many systems. The other day, a co-worker came to me, and asked, “Is it better to make straight line code for each case statement, even if it repeats, or is it better to abstraction into functions and make the code ‘cleaner’.” Is “cleaner” code faster?
The Experiment
The experiment I propose is to make a peanut butter and jelly sandwich, using a finite state machine.
[caption id="attachment_1089” align="alignleft” width="97”] State Machine expressed in 4 separate methods.[/caption]
The state machine has a series of steps, each of which take a number of ticks. The tick simply counts the amount of time in each state. The ticks simulate work being done in that state. For this experiment we are defining monolithic code to mean a switch() statement with no function calls. For modular code we offer 3 solutions:
-
a switch statement with the state code abstracted into functions. Each function then returns the state transition.
-
States abstracted into C++ objects
-
Lastly, a high level state machine using Boost MSM.
Code Overview
For each state machine type, lets look at the an example state to compare their structure. Firstly, the “monolithic” state:
case EAT_SANDWICH:
if(step_tick <= 0 && sandwiches_to_eat <= 0) //We've eaten all sandwiches
{
step_tick = 20;
s = GO_TO_WORK;
}
else if(step_tick <= 0) //We've eaten 1 more sandwich
{
--sandwiches_to_eat;
step_tick = 10;
s = REMOVE_BREAD;
}
// else Continue eating current sandwich
break;
Here s is the state. At the top of the machine is a switch(s). When the ticks are up, the state transitions to the next state. In this case Go To Work or Remove Bread to make another sandwich.
SandwichState_t eat_sandwich_process()
{
static int sandwiches_to_eat = 3;
static int tick = 10;
--tick;
if(tick <= 0 && sandwiches_to_eat <= 0)
{
sandwiches_to_eat = 3;
tick = 10;
return REMOVE_BREAD;
}
else if(tick <= 0)
{
--sandwiches_to_eat;
tick = 10;
return GO_TO_WORK;
}
return EAT_SANDWICH;
}
This state is the identical to the monolithic, except the state is moved into a function, and the state is returned instead of mutating a variable.
int eat_sandwich()
{
static int sandwiches_to_eat = 3;
static int tick = 10;
--tick;
if(tick <= 0 && sandwiches_to_eat <= 0)
{
sandwiches_to_eat = 3;
tick = 10;
s.f = remove_bread;
}
else if(tick <= 0)
{
--sandwiches_to_eat;
tick = 10;
s.f = go_to_work;
}
else
s.f = eat_sandwich;
return 0;
}
This third method is a uses a function pointer s.f. State transitions are performed by mutating the function pointer, and jumping to it e.g. sf();
Row < EatSandwich , none , GoToWork , ResetTick, user_is_full >,
Row < EatSandwich , none , RemoveBread , ResetTick, user_is_hungry >,
This is Boost’s MSM. essentially, MSM is a domain specific language described completely within a C++ template.
Results
[caption id="attachment_1097” align="alignleft” width="300”] Speedup normalized against the monolithic case. (Compiled with O2 optimization)[/caption]
I started this project with the full intention of cheating to assure monolithic code is slower than “proper” code. However, the evidence shows, properly abstracted code can be faster, but there is a limit. As MSM shows one can take abstraction too far or too general such that performance becomes difficult. So How does this happen? One of the most impacting tool for code performance, caching, and compilers have a fancy trick to optimize cache performance. Inlining.
Inlining
Function inlining is simply a copy-paste operation by the compiler to remove the overhead of a function call. In gcc, and Visual Studio, the compiler is free to inline any function it wills. Conversely, the inline keyword simply provides a suggestion or a hint to the compiler to inline a function. The compiler is free to ignore the suggestion. Once the compiler chooses to inline a function, it simply copies the source from the function and replaces the function call itself.
However, additional performance is offered beyond simply eliminating the CALL instruction. Optimization is performed in multiple passes. As such removing function calls, can simplify optimization techniques such as global-flow analysis, and register allocation. Therefore, once a function is inlined, additional performance tweaks may be made specific to the environment of the original call. This means the while a function may be optimized on it’s own. It will be done so only once. However an inlined function, since the source of the function is laid directly into flow of the program, the compiler can optimize the function specific to that region.
Many language support function inlining. Java, C++ have an inline keyword. During compilation inlining seems straight forward, however what about dynamic languages? I was surprised to learn that Python inlines. PyPy uses a Just-In-Time compiler to make inline decisions at runtime. The benefit of inline decisions deferred to runtime, is the JIT is able to see the full program at once, as opposed to only a single file at a time as a batch compiler does.
Conclusion
Cleanly abstracted code can be faster than monolithic code. Even without cheating the benchmark :-). Compilers make advanced optimizations, as such it’s of little benefit to immediately make a blanket statement to try to beat the performance of an optimizing compiler. For dynamic languages, JIT systems make even more comprehensive enhancements offering staggering performance.
Reference: http://en.wikipedia.org/wiki/Inline_expansion http://en.wikipedia.org/wiki/Inline_caching http://www.iecc.com/linker/linker11.html
http://morepypy.blogspot.com/2011/02/pypy-faster-than-c-on-carefully-crafted.html


This example application demonstrates how to work with FreeFeed application tokens. It allows you to create a post on the test site candy.freefeed.net.


File Search Tool
问题描述 :
WisKey downloaded much software in winter vacation, and the disk was in a state of confusion. He wastes many times to find the file everyday. So he wants a tool to help him do this work.
The file name consists of lowercase letters.
The name pattern is a string of lowercases, ‘?’s and ‘*’s. In a pattern, a ‘?’ matches any single lowercase, and a ‘*’ matches none or more lowercases.
Let’s do this~
The file name consists of lowercase letters.
The name pattern is a string of lowercases, ‘?’s and ‘*’s. In a pattern, a ‘?’ matches any single lowercase, and a ‘*’ matches none or more lowercases.
Let’s do this~
输入:
The first line of input contains two integers N (0 < N <= 10000) and M (0 < M <=100), representing the number of file names and the number of word patterns.
Each of the following N lines contains a file name. After those, each of the last M lines contains a name pattern.
You can assume that the length of patterns will not exceed 6, and the length of file names will not exceed 20.
There are multiple cases in the data file, process to end of file.
Each of the following N lines contains a file name. After those, each of the last M lines contains a name pattern.
You can assume that the length of patterns will not exceed 6, and the length of file names will not exceed 20.
There are multiple cases in the data file, process to end of file.
输出:
The first line of input contains two integers N (0 < N <= 10000) and M (0 < M <=100), representing the number of file names and the number of word patterns.
Each of the following N lines contains a file name. After those, each of the last M lines contains a name pattern.
You can assume that the length of patterns will not exceed 6, and the length of file names will not exceed 20.
There are multiple cases in the data file, process to end of file.
Each of the following N lines contains a file name. After those, each of the last M lines contains a name pattern.
You can assume that the length of patterns will not exceed 6, and the length of file names will not exceed 20.
There are multiple cases in the data file, process to end of file.
样例输入:
4 5 this the an is t* ?h*s ??e* *s e
样例输出:
2 1 1 2 Not match
import java.util.Scanner; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); while(scanner.hasNext()) { int n=scanner.nextInt(); int m=scanner.nextInt(); String string[]=new String[n+1]; for(int i=0;i<n;i++) { string[i]=scanner.next(); } for(int i=0;i<m;i++) { String string2=scanner.next(); String ss="^"; string2=string2.replace("?", "."); string2=string2.replace("*", ".*");//.*表示0个或多个字母，因为“.”就表示一个字符 ss+=string2; ss+="$"; int count=0; Pattern pattern=Pattern.compile(ss); for(int j=0;j<n;j++) { Matcher matcher=pattern.matcher(string[j]); if(matcher.find())count++; } if(count==0)System.out.println("Not match"); else System.out.println(count); } } } }
解题转自：http://blog.csdn.net/taotaotaotao910429/article/details/8246369
(adsbygoogle = window.adsbygoogle || []).push({});
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
xx 不用感谢我
好的，多谢指出
L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）
程序员会算法，等于一个古惑仔带了zhi抢啊
整理的很好，学习了
.net中char类型不是两个字节么
第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确
好厉害～
还是有些难度的！
為甚麼fln*20+0.5f
m /= i; 是一直在变的。参考这一篇关于质因数的http://www.acmerblog.com/integer-factorization-5124.html
yeah, This is very tricky. If you use Cpp,you need more code
http://beeder.me 这个网站上有很多poj和hihoCoder的题解，质量不错，欢迎转载。
很好，找的就是这一题


You've (maybe) heard of it
You've (maybe) heard of us
5W1H
What is it?
Why?
When?
Where?
Who?
How?
What?
Recording of all talks, including the slides
in 720p
Why?
Because we have some really cool speakers and talks
Because not everyone could make it
To put them on the Internet!
When/Where?
All the time!
3 main talk/tutorial rooms (unfortunately not open spaces)
Who?
A whole bunch, and first special thanks to the daytime volunteers who get suckered into doing this
How?
This is the fun part :D
Voctomix
Thanks Germans (CCC teams)
https://github.com/voc/voctomix
TimVideos
Thanks TimVideos
https://code.timvideos.us/home/
What goes wrong?
chromebooks don't like modes
rebooting board is needed
mode differences between outputs
VGA (yes, in 2016)
different GPU
What else goes wrong?
software happens
ffmpeg just ... stops
other recording pipelines aren't as well tested
capture board in the shape of a webcam, supplies MJPEG
firmware (can be) an issue
Are we done yet?
Power trips/breaks/whatever
Audio levels
Camera bumps
Batteries
Running out of volunteers


| Package | Description |
|---|---|
| controller |
| Modifier and Type | Method and Description |
|---|---|
void |
State.computeDeliveries(CityMap map,
TypicalDay typicalDay,
DeliveryRound deliveryRound,
Window window,
Graph graph)
Method called by controller when the button 'Compute Deliveries' is
clicked.
|
void |
RequestState.computeDeliveries(CityMap map,
TypicalDay typicalDay,
DeliveryRound deliveryRound,
Window window,
Graph graph) |
void |
DefaultState.computeDeliveries(CityMap map,
TypicalDay typicalDay,
DeliveryRound deliveryRound,
Window window,
Graph graph) |
void |
State.loadDeliveries(TypicalDay typicalDay,
Window window)
Method called by controller when the button 'Load Request' is clicked.
|
void |
RequestState.loadDeliveries(TypicalDay typicalDay,
Window window) |
void |
DeliveryState.loadDeliveries(TypicalDay typicalDay,
Window window) |
void |
DefaultState.loadDeliveries(TypicalDay typicalDay,
Window window) |
void |
CityMapState.loadDeliveries(TypicalDay typicalDay,
Window window) |
void |
State.loadMap(CityMap map,
Window window)
Method called by controller when the button 'Load Map' is clicked.
|
void |
RequestState.loadMap(CityMap map,
Window window) |
void |
InitState.loadMap(CityMap map,
Window window) |
void |
DeliveryState.loadMap(CityMap map,
Window window)
Set controller state to CityMapState after a click on LoadMapButton
|
void |
DefaultState.loadMap(CityMap map,
Window window) |
void |
CityMapState.loadMap(CityMap map,
Window window) |
void |
SwapState.updateVue(Window window) |
void |
State.updateVue(Window window)
Method called by controller to update the view
|
void |
RequestState.updateVue(Window window) |
void |
InitState.updateVue(Window window) |
void |
DeliveryState.updateVue(Window window) |
void |
DeleteState.updateVue(Window window) |
void |
CityMapState.updateVue(Window window) |
void |
AdditionState.updateVue(Window window) |


Apache Flink supports a broad ecosystem and works seamlessly with
many other data processing projects and frameworks.
Connectors provide code for interfacing with various third-party systems.
Currently these systems are supported:
To run an application using one of these connectors, additional third party components are usually required to be installed and launched, e.g., the servers for the message queues. Further instructions for these can be found in the corresponding subsections.
This is a list of third party packages (i.e., libraries, system extensions, or examples) built on Flink. The Flink community collects links to these packages but does not maintain them. Thus, they do not belong to the Apache Flink project, and the community cannot give any support for them. Is your project missing? Please let us know on the user/dev mailing list.
Apache Zeppelin
Apache Zeppelin is a web-based notebook that enables interactive data analytics and can be used with Flink as an execution engine. See also Jim Dowling’s Flink Forward talk about Zeppelin on Flink.
Apache Mahout
Apache Mahout is a machine learning library that will feature Flink as an execution engine soon. Check out Sebastian Schelter’s Flink Forward talk about Mahout-Samsara DSL.
Cascading
Cascading enables a user to build complex workflows easily on Flink and other execution engines. Cascading on Flink is built by dataArtisans and Driven, Inc. See Fabian Hueske’s Flink Forward talk for more details.
Apache Beam
Apache Beam is an open-source, unified programming model that you can use to create a data processing pipeline. Flink is one of the back-ends supported by the Beam programming model.
GRADOOP
GRADOOP enables scalable graph analytics on top of Flink and is developed at Leipzig University. Check out Martin Junghanns’ Flink Forward talk.
BigPetStore
BigPetStore is a benchmarking suite including a data generator and will be available for Flink soon. See Suneel Marthi’s Flink Forward talk as preview.
FastR
FastR is an implemenation of the R language in Java. FastR Flink executes R workloads on top of Flink.
Apache SAMOA
Apache SAMOA (incubating) is a streaming ML library featuring Flink as an execution engine soon. Albert Bifet introduced SAMOA on Flink at his Flink Forward talk.
Alluxio
Alluxio is an open-source memory-speed virtual distributed storage that enables applications to efficiently share data and access data across different storage systems in a unified namespace. Here is an example of using Flink to access data through Alluxio.
Python Examples on Flink
A collection of examples using Apache Flink’s Python API.
WordCount Example in Clojure
A small WordCount example on how to write a Flink program in Clojure.
Anomaly Detection and Prediction in Flink
flink-htm is a library for anomaly detection and prediction in Apache Flink. The algorithms are based on Hierarchical Temporal Memory (HTM) as implemented by the Numenta Platform for Intelligent Computing (NuPIC).
Apache Ignite
Apache Ignite is a high-performance, integrated and distributed in-memory platform for computing and transacting on large-scale data sets in real-time. See Flink sink streaming connector to inject data into Ignite cache.
Tink temporal graph library
Tink is a temporal graph library built on top of Flink. It allows for temporal graph analytics like different interpretations of the shortest temporal path algorithm and metrics like temporal betweenness and temporal closeness. This library was the result of the Thesis of Wouter Ligtenberg.


Utilities
Hopefully this page helps you do something.
Balance to Hex (Little Endian)
⇄
AccountId to Hex
⇄
Blake-256 a String
→
Hash
XXHash 128 a String
→
Hash
Seed to Address
→
Address


As part of a new lifestyle experiment, I've tweaked my router to block my laptop from all net access after 8pm.
The idea isn't to put a total ban on all nocturnal net activity, but rather to make a space for other things in my life. I'll still be available for scheduled calls and such, of course, but no unplanned activity.
I'll know if it works if I deng about less online, and become more focused in my evenings. I'll give the experiment a couple of months at least.
http://life.mumak.net/2008/10/attention.html gets at what I mean, I think.


Cyber UI provides capabilities for attention management.
Agenda is empty
cyber-ui-attentional-agenda-display-component


Hasenhuttl believes Southampton have a ‘big opportunity’ against Everton
by By Press AssociationSouthampton boss Ralph Hasenhuttl has conceded his side have a huge point to prove as they prepare to return to the scene of their recent humiliation on Saturday.
Saints face Everton in their first game back at St Mary’s since their 9-0 horror show against Leicester last month, but steeled by two strong subsequent performances at Manchester City.
Those results have given Hasenhuttl plenty of optimism that they can make the most of the pressure currently afflicting their opponents and seal an overdue first home win of the season.
Hasenhuttl said at a press conference: “After the last home game we want to show that we can do it better.
“This is a big opportunity for us to win, because we have to win. Everybody knows this and the players are very focused.
“We had a very intense game in the last Premier League game against Manchester City. We were close to taking something there and the performance was much better.”
Hasenhuttl expects to have a full squad to choose from with the exception of defender Ryan Bertrand, who serves the last game of a three-match ban following his sending-off early in the Foxes fixture.
And he is hopeful winger Moussa Djenepo could figure after he recently made a successful return from a muscle injury.
Hasenhuttl added: “Moussa is one of the only guys who has scored important goals for us so far, so he’s a big option for the weekend.
“He gives our a game a new part, which we’ve missed. He can be a boost for us.”
Victory could dramatically change Saints’ outlook ahead of the Christmas period, as well as pulling them level on points with opponents who are still searching for their first away win.
“I think they (Everton) know about the importance of the game,” added Hasenhuttl. “They have quality up front with Richarlison and a few other guys. It’s the Premier League – it’s always a tough game.”
READ MORE
We won’t lose because of Claudio – Guardiola content to put faith in Bravo