index.html
27.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html lang="en-US"><head><META http-equiv="Content-Type" content="text/html; charset=utf-8"><title>Efficient XML Interchange (EXI) Profile</title><style type="text/css">
code { font-family: monospace; }
div.constraint,
div.issue,
div.note { margin-left: 2em; }
div.notice { margin-left: 2em; font-weight: bold; font-size: larger; color: red }
ol.enumar { list-style-type: decimal; }
ol.enumla { list-style-type: lower-alpha; }
ol.enumlr { list-style-type: lower-roman; }
ol.enumua { list-style-type: upper-alpha; }
ol.enumur { list-style-type: upper-roman; }
div.exampleInner pre { margin-left: 1em;
margin-top: 0em; margin-bottom: 0em}
div.exampleOuter {border: 4px double gray;
margin: 0em; padding: 0em}
div.exampleInner { background-color: #d5dee3;
border-top-width: 4px;
border-top-style: double;
border-top-color: #d3d3d3;
border-bottom-width: 4px;
border-bottom-style: double;
border-bottom-color: #d3d3d3;
padding: 4px; margin: 0em }
div.exampleWrapper { margin: 4px }
div.exampleHeader { font-weight: bold;
margin: 4px}
tr.silver td { color: silver; font-style: italic }
tr.bold td { font-weight: bold }
td.xml { background-color: black; color: white; font-weight: bold; font-size: 100% }
.schema-less { background-color: silver; font-style: italic }
.schema-informed { background-color: gray; }
td.footnote { font-size: 75% }
</style><link rel="stylesheet" type="text/css" href="http://www.w3.org/StyleSheets/TR/W3C-WD.css"></head><body><div class="head"><p><a href="http://www.w3.org/"><img src="http://www.w3.org/Icons/w3c_home" alt="W3C" height="48" width="72"></a></p>
<h1><a name="title" id="title"></a>Efficient XML Interchange (EXI) Profile</h1>
<h2><a name="w3c-doctype" id="w3c-doctype"></a>W3C Working Draft 16 August 2011</h2><dl><dt>This version:</dt><dd>
<a href="http://www.w3.org/TR/2011/WD-exi-profile-20110816/">http://www.w3.org/TR/2011/WD-exi-profile-20110816/</a>
</dd><dt>Latest version:</dt><dd>
<a href="http://www.w3.org/TR/exi-profile/">http://www.w3.org/TR/exi-profile/</a>
</dd><dt>Editors:</dt><dd>Youenn Fablet, Canon Research Centre France</dd><dd>Daniel Peintner, Siemens AG</dd></dl><p class="copyright"><a href="http://www.w3.org/Consortium/Legal/ipr-notice#Copyright">Copyright</a> © 2011 <a href="http://www.w3.org/"><acronym title="World Wide Web Consortium">W3C</acronym></a><sup>®</sup> (<a href="http://www.csail.mit.edu/"><acronym title="Massachusetts Institute of Technology">MIT</acronym></a>, <a href="http://www.ercim.org/"><acronym title="European Research Consortium for Informatics and Mathematics">ERCIM</acronym></a>, <a href="http://www.keio.ac.jp/">Keio</a>), All Rights Reserved. W3C <a href="http://www.w3.org/Consortium/Legal/ipr-notice#Legal_Disclaimer">liability</a>, <a href="http://www.w3.org/Consortium/Legal/ipr-notice#W3C_Trademarks">trademark</a> and <a href="http://www.w3.org/Consortium/Legal/copyright-documents">document use</a> rules apply.</p></div><hr><div>
<h2><a name="abstract" id="abstract"></a>Abstract</h2><p>This document describes a profile of the EXI 1.0 specification that allows bounding
the memory consumption of EXI internal structures such as grammars and string
partitions. </p></div><div>
<h2><a name="status" id="status"></a>Status of this Document</h2><p>
<em>This section describes the status of this document at the time of its
publication. Other documents may supersede this document. A list of current W3C
publications and the latest revision of this technical report can be found in
the W3C technical reports index at <a href="http://www.w3.org/TR/">http://www.w3.org/TR/</a>.</em>
</p><p>Ths is the first Public Working Draft of the Efficient XML Interchange (EXI)
Profile specification. It is intended for review by W3C members and other interested parties. Although still incomplete, this document identifies all the indexing structures that are currently in the final scope of this profile.
Except for the prefix partitions, the processing rules that kick in when a
memory bound is reached are defined. This document also includes Editorial notes on topics that the Working Group is still discussing. Feedback is welcome on the document content as well as on topics covered by the editorial notes.</p><p>Please send comments about this document to the <a href="mailto:public-exi@w3.org">public-exi@w3.org</a> mailing list (<a href="http://lists.w3.org/Archives/Public/public-exi/">Archives</a>).</p><p>This document has been produced by the <a href="http://www.w3.org/XML/EXI/">Efficient XML Interchange Working Group</a> as part of the W3C <a href="http://www.w3.org/XML/Activity">XML Activity</a>. The goals of the Efficient XML Interchange (EXI) Format are discussed in the <a href="http://www.w3.org/TR/exi/">Efficient XML Interchange (EXI) Format 1.0</a> document. The authors of this document are the members of the Efficient XML Interchange Working Group.</p><p>Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.</p><p> This document was produced by a group operating under the <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/">5 February 2004 W3C Patent Policy</a>. W3C maintains a <a href="http://www.w3.org/2004/01/pp-impl/38502/status#specs">public list of any patent disclosures</a> made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#def-essential">Essential Claim(s)</a> must disclose the information in accordance with <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#sec-Disclosure">section 6 of the W3C Patent Policy</a>. </p></div><div class="toc">
<h2><a name="contents" id="contents"></a>Table of Contents</h2><p class="toc">1. <a href="#introduction">Introduction</a><br>
2. <a href="#conceptAndVocabulary">Capping Rules</a><br>
2.1 <a href="#N65762">Name Partitions Capping Definition</a><br>
2.1.1 <a href="#N65767">Uri Partition Capping Definition</a><br>
2.1.2 <a href="#N65777">Local-name Partition Capping Definition</a><br>
2.1.3 <a href="#N65790">Prefix Partition Capping Definition</a><br>
2.2 <a href="#N65809">Grammar Capping Definition</a><br>
2.2.1 <a href="#N65812">Built-in Capping Definition</a><br>
2.3 <a href="#N65853">Local Value Capping Definition</a><br>
3. <a href="#thresholds">Capping Parameters</a><br>
3.1 <a href="#namePartitionThresholds">Name Partitions Capping Thresholds</a><br>
3.2 <a href="#grammarLearningThreshold">Grammar Capping Thresholds</a><br>
3.3 <a href="#localValuePartitionsThreshold">Local Value Partitions Threshold</a><br>
4. <a href="#exi10Integration">Integration with EXI 1.0</a><br>
4.1 <a href="#exiProfileVersionNumber">EXI Stream Detection</a><br>
4.2 <a href="#exiProfileHeaderOptions">EXI Profile Header Parameters</a><br>
</p>
<h3><a name="appendices" id="appendices"></a>Appendix</h3><p class="toc">A <a href="#references">References</a><br>
</p></div><hr><div class="body"><div class="div1">
<h2><a name="introduction" id="introduction"></a>1. Introduction</h2><p>Many device classes and use-cases desire to use EXI as its exchange format. Due to
various restrictions some of those application areas are not capable or allowed to
require arbitrary memory growth at runtime. Certain evaluations of EXI in the context
of such areas exposed some challenges to the attempt to restrict memory usage
predictably within their limited respective threshold.</p><p>This EXI profile document specifies capping rules
to ensure that the memory restrictions are respected.
Section <a href="#conceptAndVocabulary"><b>2. Capping Rules</b></a> states these rules that have to be
followed by any EXI profile.
Section <a href="#thresholds"><b>3. Capping Parameters</b></a> provides
means to parameterize these rules according different memory restriction levels.
Other groups and standardization bodies may rely on these capping parameters or build their
own profile if the suggested thresholds and parameters are not sufficient.
Section <a href="#exi10Integration"><b>4. Integration with EXI 1.0</b></a> describes the integration of the EXI profile
with EXI 1.0. In particular, it details how the profile parameters can be described in the EXI option header
and how EXI Profile streams can be distinguished from EXI 1.0 streams.
</p><p>As long as the introduced memory restrictions are not reached, an EXI Profile stream is
fully compatible with an <a href="http://www.w3.org/TR/2011/REC-exi-20110310/">EXI 1.0</a>
Stream.</p><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">Control last compatibility statement after all parameters are elaborated. Check also
how this statement fits with the EXI header subject. </td></tr></table></div><div class="div1">
<h2><a name="conceptAndVocabulary" id="conceptAndVocabulary"></a>2. Capping Rules</h2><p>
The <a href="#exiSpec">[Efficient XML Interchange (EXI) Format 1.0]</a> specification defines learning mechanisms that enable a very compact representation of the XML infoset.
These mechanisms are based on EXI internal structures that are augmented during the EXI processing, for instance when a uri is added to the uri partition
or when a production is inserted in a built-in element grammar.
</p><p>This section defines the processing rules that enable capping the memory size of these structures.
Generally, EXI profile stream processing must proceed without adding or inserting an item in a structure
whenever it would exceed the defined memory restriction of that structure.
This section also defines rules that ensure that different structures remain consistent one with the other.
For instance, the rules ensure that a local-name can only be indexed if its related uri can also be indexed.
</p><p>
An EXI event may lead to the augmentation of several different structures.
This specification assumes the following augmentation order:
</p><ol class="enumar"><li><p>uri partition</p></li><li><p>local-name partition</p></li><li><p>prefix partition</p></li><li><p>production creation and event-code incrementation</p></li><li><p>value partition(s)</p></li></ol><p>
An implementation is free to choose any approach and any order as long as the result remains the same.
The capping rules for an event value depend on the value datatype representation.
If the value is represented as a string, the local value partition capping rules are used.
If the value is represented as a QName, the rules are first applied to the QName uri and then to the QName local-name.
</p><div class="div2">
<h3><a name="N65762" id="N65762"></a>2.1 Name Partitions Capping Definition</h3><p>
Name partitions refer to the uri, prefix and local-name partitions.
To limit the memory growing, string insertion in the name partitions is stopped
at a given threshold according the rules described in the following sub-sections.
By definition, when a string is not added to a partition, no compact identifier is assigned to the given string.
</p><div class="div3">
<h4><a name="N65767" id="N65767"></a>2.1.1 Uri Partition Capping Definition</h4><p>
A uri string is represented according section 7.3.2 of the EXI 1.0
specification to the exception that the uri string is NOT added to the uri partition if any of the following conditions is met:
</p><ol class="enumar"><li><p>Adding the uri to the uri partition would exceed the
defined uri partition restriction.</p></li></ol></div><div class="div3">
<h4><a name="N65777" id="N65777"></a>2.1.2 Local-name Partition Capping Definition</h4><p> A local-name string is represented according section 7.3.3 of the EXI 1.0
specification to the exception that the local-name string is NOT added to
the local-name partitions if any of the following conditions is met:
</p><ol class="enumar"><li><p>Adding the local-name to the local-name partition would exceed the
defined local-name partition restriction.</p></li><li><p>The local-name is associated with a namespace uri that is not
present in the uri partition.</p></li></ol></div><div class="div3">
<h4><a name="N65790" id="N65790"></a>2.1.3 Prefix Partition Capping Definition</h4><p>A prefix string can be represented according section 7.3.2 of the EXI 1.0
specification if any of the following conditions is met:
</p><ol class="enumar"><li><p>Adding the prefix to the prefix partition would NOT exceed the
defined prefix partition restriction.</p></li><li><p>The prefix is associated with a namespace uri that is present in
the uri partition.</p></li></ol><p>Otherwise, a prefix string cannot be represented.</p><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">In some cases prefixes cannot be represented. The working group is currently
investigating the issue.</td></tr></table></div></div><div class="div2">
<h3><a name="N65809" id="N65809"></a>2.2 Grammar Capping Definition</h3><div class="div3">
<h4><a name="N65812" id="N65812"></a>2.2.1 Built-in Capping Definition</h4><p>
To limit the memory growing due to grammar learning,
the production creation and event-code incrementation
is stopped at a given threshold according the following rules.
This applies to built-in element and built-in fragment grammars.
</p><p>A production is not added if any of the following conditions is met:</p><ol class="enumar"><li><p>Adding a production to the grammar would exceed the defined grammar restriction.</p></li><li><p>The uri of the element QName, associated to its grammar, is not present in the uri partition.</p></li><li><p>The local-name of the element QName, associated to its grammar, is not present in its local-name partition.</p></li><li><p>The uri of the qname associated to the production, if any, is not present in the uri partition.</p></li><li><p>The local-name of the qname associated to the production, if any, is not present in its local-name partition.
</p></li></ol><p>Note in particular that no other production than the default productions defined in
sections 8.4.2 and 8.4.3 of the EXI 1.0 specification can be added to a built-in
grammar whose element QName is not totally indexed.</p><p>
By definition, a production that is not added to its grammar is evaluated as described in sections 8.4.2 and 8.4.3 of the EXI 1.0 specification to the exception that:
</p><ul><li><p>Step 2 is skipped for a built-in element grammar production of the form LeftHandSide: AT (*) RightHandSide.</p></li><li><p>Steps 3 to 5 are skipped for a built-in element or fragment grammar production of the form LeftHandSide: SE (*) RightHandSide.</p></li><li><p>Step 2 is skipped for a built-in element grammar production of the form LeftHandSide: CH RightHandSide.</p></li><li><p>Steps 1 and 2 are skipped for a built-in element grammar production of the form LeftHandSide: EE</p></li></ul></div></div><div class="div2">
<h3><a name="N65853" id="N65853"></a>2.3 Local Value Capping Definition</h3><p>Local value partitions grow with the insertion of string values to the
partitions, as described in section 7.3.3 of the EXI specification. To limit the
memory growing, local value partitions insertion is stopped at a given threshold
according the following rules.</p><p> A string value is represented according section 7.3.3 of the EXI 1.0
specification to the exception that it is NOT added to its associated local
value partition if any of the following conditions is met:
</p><ol class="enumar"><li><p>Adding the string value to its associated local value partition would exceed the
defined local value partition restriction.</p></li><li><p>The uri of the qname associated to the string value is not present in
the uri partition.</p></li><li><p>The local-name of the qname associated to the string value is not
present in its local-name partition.</p></li></ol></div></div><div class="div1">
<h2><a name="thresholds" id="thresholds"></a>3. Capping Parameters</h2><p>This section describes the threshold rules and associated parameters. Hereby it defines when
a given operation would exceed the defined memory restrictions (see <a href="#conceptAndVocabulary"><b>2. Capping Rules</b></a>). </p><div class="div2">
<h3><a name="namePartitionThresholds" id="namePartitionThresholds"></a>3.1 Name Partitions Capping Thresholds</h3><p> In the remainder of the sections, we will refer to name partitions entries, uri
entries, local-name entries or prefix entries. In all cases, these terms refer
to entries that are added after the pre-population of the name partitions.
Schema-informed or schema-less name partitions pre-population is not constrained
in this section and pre-populated entries are never used in the memory restriction
computations. </p><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">The working group currently elaborates different ways on how to restrict name partitions.
The general idea is to introduce options to restrict the number of characters and/or
the number of entries for different partitions. The chosen approach is not set yet and will be
published in a future version of this document.
</td></tr></table></div><div class="div2">
<h3><a name="grammarLearningThreshold" id="grammarLearningThreshold"></a>3.2 Grammar Capping Thresholds</h3><p>
[<a name="evolvingBuiltInElementGrammar" id="evolvingBuiltInElementGrammar" title="evolvingBuiltInElementGrammar">Definition</a>: A built-in element grammar is
considered to be an <b>evolving built-in element grammar</b> if
a production has been dynamically inserted within the grammar. ]
</p><p>
[<a name="maximumNumberOfEvolvingBuiltInElementGrammars" id="maximumNumberOfEvolvingBuiltInElementGrammars" title="maximumNumberOfEvolvingBuiltInElementGrammars">Definition</a>: The
<b>maximumNumberOfEvolvingBuiltInElementGrammars</b> option is the maximum
number of elements for which evolving built-in element grammars can be instantiated. ]
</p><p>
[<a name="maximumNumberOfBuiltInProductions" id="maximumNumberOfBuiltInProductions" title="maximumNumberOfBuiltInProductions">Definition</a>: The
<b>maximumNumberOfBuiltInProductions</b> option is the maximum
number of top-level productions that can be dynamically inserted in built-in fragment
and built-in element grammars. ]
Note that only dynamically inserted top level productions are counted. In
particular, the top level EE productions of the built-in ElementContent grammar
are not counted since they are added when creating each ElementContent grammar.
</p><p>Grammar augmentation of a built-in grammar does exceed grammar restriction
if any of following condition is true:
</p><ol class="enumar"><li><p>The number of dynamically inserted top level productions of all
built-in fragment and element grammars is equal or greater than the
<a title="maximumNumberOfBuiltInProductions" href="#maximumNumberOfBuiltInProductions">maximumNumberOfBuiltInProductions</a> value.</p></li><li><p>The augmentation process
makes it to be a new evolving built-in element grammar while
the number of already existing evolving built-in element grammars is equal or greater than the <a title="maximumNumberOfEvolvingBuiltInElementGrammars" href="#maximumNumberOfEvolvingBuiltInElementGrammars">maximumNumberOfBuiltInElementGrammars</a> value.</p></li></ol><p>
Note that non evolving built-in element grammars can be shared by different elements and do
not cause to exceed grammar restrictions in any case.
</p><p>By default the <a title="maximumNumberOfEvolvingBuiltInElementGrammars" href="#maximumNumberOfEvolvingBuiltInElementGrammars">maximumNumberOfBuiltInElementGrammars</a> and <a title="maximumNumberOfBuiltInProductions" href="#maximumNumberOfBuiltInProductions">maximumNumberOfBuiltInProductions</a> values are unbounded.</p></div><div class="div2">
<h3><a name="localValuePartitionsThreshold" id="localValuePartitionsThreshold"></a>3.3 Local Value Partitions Threshold</h3><p>
[<a name="localValuePartitions" id="localValuePartitions" title="localValuePartitions">Definition</a>: The
<b>localValuePartitions</b> option is a Boolean used to indicate whether
local value partitions are used. ] The value "false" indicates that no local
value patition is used while "true" represents the behavior of the EXI 1.0 specification.
</p><p>A local value partition does exceed the defined local value partition restriction if
the following condition is true:
</p><ol class="enumar"><li><p>The value <a title="localValuePartitions" href="#localValuePartitions">localValuePartitions</a> is set to "false".</p></li></ol><p>By default the <a title="localValuePartitions" href="#localValuePartitions">localValuePartitions</a> value "true" is assumed.</p><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">The group is still assessing the benefit of this parameter.
Besides more flexible solutions are discussed.</td></tr></table></div></div><div class="div1">
<h2><a name="exi10Integration" id="exi10Integration"></a>4. Integration with EXI 1.0</h2><p>This section describes how this profile integrates with EXI1.0. In particular, it
describes how an implementation can detect whether an EXI stream follows this
profile or not. It also describes how the
parameters, described in the profile, can be communicated in the EXI stream. </p><div class="div2">
<h3><a name="exiProfileVersionNumber" id="exiProfileVersionNumber"></a>4.1 EXI Stream Detection</h3><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">The working group is considering different approaches such as
defining a new version number or making use of the extensibility
of the current EXI Header Options document.
The solution space is not limited to these approaches.
</td></tr></table></div><div class="div2">
<h3><a name="exiProfileHeaderOptions" id="exiProfileHeaderOptions"></a>4.2 EXI Profile Header Parameters</h3><table border="1" summary="Editorial note"><tr><td align="left" valign="top" width="50%"><b>Editorial note</b></td><td align="right" valign="top" width="50%"> </td></tr><tr><td colspan="2" align="left" valign="top">Define which parameters appear in the header, if any and where.
Default values will be defined in the above section, for instance
like it was done in Table 5-1 of the EXI specification.</td></tr></table></div></div></div><div class="back"><div class="div1">
<h2><a name="references" id="references"></a>A References</h2><dl><dt class="label"><a name="exiSpec" id="exiSpec"></a>Efficient XML Interchange (EXI) Format 1.0</dt><dd>
<a href="http://www.w3.org/TR/2011/REC-exi-20110310/"><cite>Efficient XML Interchange (EXI) Format 1.0</cite></a>, John Schneider
and Takuki Kamiya, Editors. World Wide Web Consortium. The latest version is
available at <a href="http://www.w3.org/TR/exi/">
http://www.w3.org/TR/exi/</a>. (See http://www.w3.org/TR/2011/REC-exi-20110310/.)</dd><dt class="label"><a name="exiEval" id="exiEval"></a>EXI Evaluation Note</dt><dd>
<a href="http://www.w3.org/TR/2009/WD-exi-evaluation-20090407/"><cite>Efficient XML Interchange Evaluation</cite></a>, Carine Bournez,
Editor. World Wide Web Consortium. The latest version is available at <a href="http://www.w3.org/TR/exi-evaluation/">
http://www.w3.org/TR/exi-evaluation/</a>. (See http://www.w3.org/TR/2009/WD-exi-evaluation-20090407/.)</dd><dt class="label"><a name="schemaDatatypes2" id="schemaDatatypes2"></a>XML Schema Datatypes</dt><dd>
<a href="http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/"><cite>XML Schema Part 2: Datatypes Second Edition</cite></a>, P. Byron and
A. Malhotra, Editors. World Wide Web Consortium, 2 May 2001, revised 28 October
2004. The latest version is available at <a href="http://www.w3.org/TR/xmlschema-2/">
http://www.w3.org/TR/xmlschema-2</a>. (See http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/.)</dd></dl></div></div></body></html>