- From: Paul Pierce <prp@teleport.com>
- Date: 21 Feb 2006 20:34:45
- To: "W3C EXI Public" <public-exi@w3.org>
In-Reply-To=<200602071342.k17DgeXp014501@ender.inria.fr>
References=<200602071342.k17DgeXp014501@ender.inria.fr>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=--etoianshrdlu-1"
This is a multi-part message in MIME format.
--=--etoianshrdlu-1
Content-Disposition: inline
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Attached is my evaluation of the BX proposal. I think it meets =
all the requirements rather well, except that implementing =
the whole thing is not a one-night hack. Also below is a statement =
on intellectual property.
The two documents: the original "BX" Proposal for XML Binary =
Format and the attached Self-Evaluation of the "BX" Proposal =
are in the public domain. I am the sole author of these documents =
and I waive all rights of copyright except any that allow me =
to disclaim any warranty of correctness or fitness for any =
particular purpose, and I do so disclaim. I hold no patent =
or other intellectual property interest in any of the mechanisms =
described and have not filed nor intend to file for patent =
protection on them. I do not know of any existing patents on =
any of the mechanisms described but have not made any search =
to find out if there might be any.
Paul R. Pierce
Portland, Oregon USA
prp@teleport.com
--=--etoianshrdlu-1
MIME-Version: 1.0
Content-Type: multipart/related; boundary="=--etoianshrdlu-2"
Content-Transfer-Encoding: 7bit
--=--etoianshrdlu-2
Content-Disposition: attachment; filename="bxproposal.html"
Content-Id: <bxproposal.html>
Content-Type: text/html; name="bxproposal.html"
Content-Transfer-Encoding: 7bit
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<!-- ======================================================= -->
<!-- Created by AbiWord, a free, Open Source wordprocessor. -->
<!-- For more information visit http://www.abisource.com. -->
<!-- ======================================================= -->
<meta http-equiv="content-type" content="text/html;charset=UTF-8" />
<title>bxevaluation.html</title>
<style type="text/css">
<!--
@media print, projection, embossed {
body {
padding-top:1in;
padding-bottom:1in;
padding-left:1in;
padding-right:1in;
}
}
body {
text-indent:0in;
text-align:left;
font-weight:normal;
text-decoration:none;
font-variant:normal;
color:#000000;
font-size:12pt;
font-style:normal;
widows:2;
font-family:'Times New Roman';
}
table {
}
td {
border-collapse:collapse;
text-align:left;
vertical-align:top;
}
p, h1, h2, h3, li {
color:#000000;
font-family:'Times New Roman';
font-size:12pt;
margin-bottom:0.1667in;
text-align:left;
vertical-align:normal;
}
*.head1 {
font-size:14pt;
font-weight:bold;
}
*.head2 {
font-size:12pt;
}
*.code {
font-family:'Courier';
margin-bottom:0pt;
}
*.title {
color:#000000;
font-family:'Bitstream Vera Sans';
font-size:22pt;
font-weight:bold;
text-align:center;
}
-->
</style>
</head>
<body>
<div>
<p class="title">Self-Evaluation of the "BX" Proposal</p>
<p style="text-align:center"><span style="font-size:14pt">Paul R. Pierce</span></p>
<p class="head1">Abstract</p>
<p>An evaluation of the "BX" proposal for binary XML against the properties described by the XML Binary Characterization working group.</p>
<p class="head1">Revision</p>
<p>February 22, 2006</p>
<p class="head1">Contents</p>
<ul>
<li><a href="#1.">1. Introduction</a></li>
<li><a href="#2.">2. Evaluation</a></li>
<li><a href="#2.1">2.1 (4.1) Processing Efficiency</a></li>
<li><a href="#2.2">2.2 (4.2) Small Footprint</a></li>
<li><a href="#2.3">2.3 (4.3) Space Efficiency</a></li>
<li><a href="#2.4">2.4 (5.1) Accelerated Sequential Access</a></li>
<li><a href="#2.5">2.5 (5.2) Compactness</a></li>
<li><a href="#2.6">2.6 (5.3) Content Type Management</a></li>
<li><a href="#2.7">2.7 (5.4) Deltas</a></li>
<li><a href="#2.8">2.8 (5.5) Directly Readable and Writable</a></li>
<li><a href="#2.9">2.9 (5.6) Efficient Update</a></li>
<li><a href="#2.10">2.10 (5.7) Embedding Support</a></li>
<li><a href="#2.11">2.11 (5.8) Encryptable</a></li>
<li><a href="#2.12">2.12 (5.9) Explicit Typing</a></li>
<li><a href="#2.13">2.13 (5.10) Extension Points</a></li>
<li><a href="#2.14">2.14 (5.11) Format Version Identification</a></li>
<li><a href="#2.15">2.15 (5.12) Fragmentable</a></li>
<li><a href="#2.16">2.16 (5.13) Generality</a></li>
<li><a href="#2.17">2.17 (5.14) Human Language Neutral</a></li>
<li><a href="#2.18">2.18 (5.15) Human Readable and Editable</a></li>
<li><a href="#2.19">2.19 (5.16) Integratable into XML Stack</a></li>
<li><a href="#2.20">2.20 (5.17) Localized Changes</a></li>
<li><a href="#2.21">2.21 (5.18) No Arbitrary Limits</a></li>
<li><a href="#2.22">2.22 (5.19) Platform Neutrality</a></li>
<li><a href="#2.23">2.23 (5.20) Random Access</a></li>
<li><a href="#2.24">2.24 (5.21) Robustness</a></li>
<li><a href="#2.25">2.25 (5.22) Roundtrip Support</a></li>
<li><a href="#2.26">2.26 (5.23) Schema Extensions and Deviations</a></li>
<li><a href="#2.27">2.27 (5.24) Schema Instance Change Resilience</a></li>
<li><a href="#2.28">2.28 (5.25) Self Contained</a></li>
<li><a href="#2.29">2.29 (5.26) Signable</a></li>
<li><a href="#2.30">2.30 (5.27) Specialized Codecs</a></li>
<li><a href="#2.31">2.31 (5.28) Streamable</a></li>
<li><a href="#2.32">2.32 (5.29) Support for Error Correction</a></li>
<li><a href="#2.33">2.33 (5.30) Transport Independence</a></li>
<li><a href="#2.34">2.34 (6.1) Forward Compatibility</a></li>
<li><a href="#2.35">2.35 (6.2) Implementation Cost</a></li>
<li><a href="#2.36">2.36 (6.3) Royalty Free</a></li>
<li><a href="#2.37">2.37 (6.4) Single Conformance Class</a></li>
<li><a href="#2.38">2.38 (6.5) Widespread Adoption</a></li>
<li><a href="#3.">3. Direct Read and Write</a></li>
<li><a href="#4.">4. Summary</a></li>
</ul>
<p class="head1"><a name="1.">1. Introduction</a></p>
<p>The call for proposals for a binary format for XML requested an evaluation of each submitted proposal against the desirable properties set forth in the document "XML Binary Characterization Properties", W3C Working Group Note 31, March 2005. As I've submitted a proposal it follows I should submit an evaluation, and here it is. Section numbers in parentheses refer to the Working Group note.</p>
<p>Briefly, the "BX" proposal outlines a binary format for XML in terms of a set of optional, independent, reversible transformations between standard XML and a binary form. Some of the transformations are concerned with translation between text-oriented XML and a compact binary representation of the information, the rest provide options for compression using well known techniques. The key translation transformations are schema driven, using either XML-Schema as found or annotated with markup specified for the purpose of directing the translation. All transformations operate on symbols, essentially integers of different types and initially the characters of a standard XML document.</p>
<p class="head1"><a name="2.">2. Evaluation</a></p>
<p class="head2 head1"><a name="2.1">2.1 (4.1) Processing Efficiency</a></p>
<p>The processing efficiency for serialization, parsing and data binding will vary depending on the nature of the program or library performing the task and the transformations selected. Applications requiring extreme speed (especially with numerical data) can read or write the format directly from an appropriately designed data model, see section 3, Direct Read and Write.</p>
<p>General purpose libraries within the XML stack should be able to perform most of the transformations at about the same speed as with text XML. Some combinations of transformations might prove to be significantly faster. In particular, it should be possible to code a schema processor that builds parsing tables driven by the numeric tokens produced by the Name, Entity and Value transformations, so that both serialization and parsing can run much faster than a text based implementation.</p>
<p>Compression transformations should be able to run at speeds comparable to that of corresponding existing utilities such as gzip and bzip2. Again there may be an opportunity for higher speed as the transformations are specified to operate on whole symbols instead of bytes as with the existing utilities. As with existing utilities, there is a trade-off between running time and compression efficiency.</p>
<p class="head2 head1"><a name="2.2">2.2 (4.2) Small Footprint</a></p>
<p>Because of its flexibility due to the number of different transformations specified, a full general purpose implementation will not be as small as a standard XML <span xml:lang="en-US" lang="en-US">implementation</span>. However, extremely small footprint is possible with Direct Read and Write as described in section 3, and a small footprint should be possible for other selected sets of transformations.</p>
<p class="head2 head1"><a name="2.3">2.3 (4.3) Space Efficiency</a></p>
<p>A full general purpose implementation, particularly with high performance compression transformations, is likely to require at least as much space as a standard XML implementation, and on the other hand a program using the Direct Read and Write (section 3) features can be very space efficient. In between, it should be possible to create something like a DOM implementation, at least for a useful subset of transformations, that is significantly more space efficient than a general purpose standard XML implementation.</p>
<p class="head2 head1"><a name="2.4">2.4 (5.1) Accelerated Sequential Access</a></p>
<p>The extensive use of length (in bytes) symbols is meant to facilitate quick skips through the data without parsing. I would like to extend this to include optional length symbols after each token but haven't figured out the best way to do that yet.</p>
<p class="head2 head1"><a name="2.5">2.5 (5.2) Compactness</a></p>
<p>The format is theoretically capable of extreme compactness, just short of the best known lossless compression. There is a wide range of trade-off possible between quite compact and very fast to extremely compact but somewhat slow.</p>
<p class="head2 head1"><a name="2.6">2.6 (5.3) Content Type Management</a></p>
<p>The proposed format is specified to be nothing more than an encoding. Thus, content type management is not an issue. However, it includes one transformation (Declaration) that might make it worth considering a single additional media type.</p>
<p class="head2 head1"><a name="2.7">2.7 (5.4) Deltas</a></p>
<p>The proposal does not address deltas. Any work on standard XML with respect to deltas would likely carry forward to this proposed format with little extra effort.</p>
<p class="head2 head1"><a name="2.8">2.8 (5.5) Directly Readable and Writable</a></p>
<p>The proposal is particularly designed to allow tight specification of a data format that might be read or written directly from the in-memory data model, without parsing or serialization at all unless the Octet transformation or some combination of compression transformations are also selected. See section 3.</p>
<p class="head2 head1"><a name="2.9">2.9 (5.6) Efficient Update</a></p>
<p>When using the Direct Read and Write (section 3) features it will sometimes be possible to allow for direct update in place, as long as there is no change in the size of the data or data is only being appended to the end. As these are two common cases there should be many happy opportunities for efficient update.</p>
<p class="head2 head1"><a name="2.10">2.10 (5.7) Embedding Support</a></p>
<p>The proposal does not specify embedding, but contemplates a separate container specification that it might make use of in certain situations.</p>
<p class="head2 head1"><a name="2.11">2.11 (5.8) Encryptable</a></p>
<p>The proposed format conveys all existing XML information and is fragmentable, so it should support existing encryption techniques.</p>
<p class="head2 head1"><a name="2.12">2.12 (5.9) Explicit Typing</a></p>
<p>The Octet transformation, when selected for serialization, produces a stream that includes basic type information gleaned from the schema.</p>
<p class="head2 head1"><a name="2.13">2.13 (5.10) Extension Points</a></p>
<p>There is no explicit general mechanism for extension in the proposal. Instead, its overall design lends itself to extension by adding new transforms that can be selected directly in the XML declaration, or by adding new schema annotation to select new options in the existing transformations. There is also some room in the value space of type tokens for new basic types.</p>
<p class="head2 head1"><a name="2.14">2.14 (5.11) Format Version Identification</a></p>
<p>Yes. (Its in the XML declaration).</p>
<p class="head2 head1"><a name="2.15">2.15 (5.12) Fragmentable</a></p>
<p>The proposal inherently supports fragments to the same degree as standard XML. In particular, consider that a block might contain a fragment, and all transformations are block-aware.</p>
<p class="head2 head1"><a name="2.16">2.16 (5.13) Generality</a></p>
<p>The proposal is all about flexibility, in order to be as general as possible. It is particularly designed to be useful for very short or long documents; to make the best of highly structured (especially numeric) documents while still providing advantages for loosely structured documents; and while many important transformations are schema driven others do not need a schema and for those that do there may be an alternative.</p>
<p class="head2 head1"><a name="2.17">2.17 (5.14) Human Language Neutral</a></p>
<p>The proposal is as neutral as standard XML and XML-Schema are already.</p>
<p class="head2 head1"><a name="2.18">2.18 (5.15) Human Readable and Editable</a></p>
<p>The proposed format is not in general directly human readable in any of its optional forms except when only trivial transforms are selected. Of the considerations mentioned in the Binary Characterization Properties report two of note are the property of being self-contained (see below) and the principle of keeping things in their original order, which happens unless the Transpose or Block Sort transformations are selected.</p>
<p class="head2 head1"><a name="2.19">2.19 (5.16) Integratable into XML Stack</a></p>
<p>By appearing as an encoding and supporting all of XML this proposed format is intended to be completely and transparently integratable into the XML stack. A full, general purpose implementation can be hidden behind the existing SAX or DOM API, activated automatically when the desired encoding is specified in the XML declaration of a document.</p>
<p class="head2 head1"><a name="2.20">2.20 (5.17) Localized Changes</a></p>
<p>In general the proposed format supports this property as well as or better than existing XML, except when the more aggressive compression transformations are selected.</p>
<p class="head2 head1"><a name="2.21">2.21 (5.18) No Arbitrary Limits</a></p>
<p>A few aspects of the proposal are limited to the range of a 64-bit integer, otherwise the proposed format does not impose any limits that do not already exist in standard XML. Block sizes are limited to 1 megabyte, however that does not limit the range of expression of the format since data items (including strings and lists)<span xml:lang="en-US" lang="en-US"> can cross block boundaries</span> down to (but not including) the lowest, atomic level.</p>
<p class="head2 head1"><a name="2.22">2.22 (5.19) Platform Neutrality</a></p>
<p>The proposal is entirely platform neutral except in the use of "network byte order", which is of course standard but the opposite of most of the general purpose computers in the world. It might be a very good idea to add options via the schema annotation namespace to force a particular byte order or to allow for "reader makes right".</p>
<p class="head2 head1"><a name="2.23">2.23 (5.20) Random Access</a></p>
<p>The proposed format does not specifically support random access but is more or less indexable. Even in the most compressed form, it would be possible to create some sort of index to each of the lowest level data items or to fragments, though to access them might require decompression of their block.</p>
<p class="head2 head1"><a name="2.24">2.24 (5.21) Robustness</a></p>
<p>The proposed format is fairly robust at the most basic level, in that the separate blocks of a document are mostly independent. It is possible to do better within the constraints of the specified format, by forcing block boundaries at specified fragment boundaries through schema annotation, and by including error codes within the regular data items of each fragment.</p>
<p class="head2 head1"><a name="2.25">2.25 (5.22) Roundtrip Support</a></p>
<p>The proposed format is specified in terms of round tripping, full support is inherent in its design.</p>
<p class="head2 head1"><a name="2.26">2.26 (5.23) Schema Extensions and Deviations</a></p>
<p>Although important transformations are schema driven, the proposal discusses ways to work around this requirement when necessary. Once a workaround has been selected, the Octet transformation provides a means of expressing the extended information in the binary format.</p>
<p class="head2 head1"><a name="2.27">2.27 (5.24) Schema Instance Change Resilience</a></p>
<p>One of the important features of the schema annotation in the proposal is to fix the values of tokens used for elements and attributes. With these annotations a schema can be designed so that changes will not affect existing applications (without schema update) as long as communication with those applications is restricted to the common subset of the old and new schema. Alternatively, the Octet transformation can be used (as it would be for Schema Extensions and Deviations) so that applications parsing data from a new schema can detect that there have been changes. Also see Self Contained below.</p>
<p class="head2 head1"><a name="2.28">2.28 (5.25) Self Contained</a></p>
<p>Although schema driven, the binary format can be self contained in one of two ways. As noted above, the Octet transformation can be selected to embed schema information in the data. This is the main reason for the existence of the Octet transformation. Alternatively, as noted in the proposal, a separately specified XML container format can be used to encapsulate the schema with the data.</p>
<p class="head2 head1"><a name="2.29">2.29 (5.26) Signable</a></p>
<p>See Encryptable, the proposed format is intended to be compatible with existing techniques for signing documents.</p>
<p class="head2 head1"><a name="2.30">2.30 (5.27) Specialized Codecs</a></p>
<p>I feel this should be addressed in an XML container specification.</p>
<p class="head2 head1"><a name="2.31">2.31 (5.28) Streamable</a></p>
<p>The proposed format supports streamable data in two ways. First, the configurable block size limits the amount of data that must be handled at one time. Second, for finer streamability the block oriented transformations might not be selected; then the format is at least as streamable as standard XML.</p>
<p class="head2 head1"><a name="2.32">2.32 (5.29) Support for Error Correction</a></p>
<p>The proposed format does not specify support for error correction. However, see Robustness above.</p>
<p class="head2 head1"><a name="2.33">2.33 (5.30) Transport Independence</a></p>
<p>The proposed format is transport independent as long as the transport can convey arbitrary binary data.</p>
<p class="head2 head1"><a name="2.34">2.34 (6.1) Forward Compatibility</a></p>
<p>The proposed format is designed for forward compatibility as discussed in the Binary Characterization Properties report.</p>
<p class="head2 head1"><a name="2.35">2.35 (6.2) Implementation Cost</a></p>
<p>The proposal is complex due to its high flexibility and ambitious reach. It is reasonable to expect that the total cost for a full implementation would be significantly greater than for a corresponding implementation for standard XML. As with other properties, a Direct Read and Write implementation, on the other hand, is very easy.</p>
<p>The proposal is particularly designed with the problem of a full implementation in mind, through the use of independent transformations. After a relatively small amount of base development, each transformation (and its reverse) can be implemented independently or not at all if it will not be used in a particular application. In addition, once full implementations become available it will be possible to very quickly implement and test individual applications that use the Direct Read and Write feature. These applications will immediately be able to interchange data with other applications that make use of the full implementation.</p>
<p class="head2 head1"><a name="2.36">2.36 (6.3) Royalty Free</a></p>
<p>The proposal is in the public domain, and I have no patents or other intellectual property rights on any of the specified mechanisms.</p>
<p class="head2 head1"><a name="2.37">2.37 (6.4) Single Conformance Class</a></p>
<p>The proposal does not define conformance class(es). Although a single conformance class might be assumed, the complexity of the proposal allows for an argument to consider multiple classes.</p>
<p class="head2 head1"><a name="2.38">2.38 (6.5) Widespread Adoption</a></p>
<p>Several of the above properties, especially the ease of integration into the XML stack, argue for the possibility of widespread adoption. The main hurdle, due to total implementation cost, would be to integrate a full implementation into one or more of the most popular XML libraries.</p>
<p class="head1"><a name="3.">3. Direct Read and Write</a></p>
<p>The example in the proposal does not clearly show how the format can be easily manipulated to map XML directly to a useful (though not arbitrary) data model.</p>
<p>Consider this XML document:</p>
<table cellpadding="0" border="0" rules="all" style="width:100%;border:1pt;border-collapse:collapse;empty-cells:show;table-layout:fixed;border-style:solid">
<colgroup>
<col />
</colgroup>
<tbody style="border:inherit">
<tr style="border:inherit">
<td style="padding: 0.00pt;border:inherit inherit inherit">
<p class="code"> </p>
<p class="code"><?xml version="1.0"?></p>
<p class="code"><run xmlns="http://example.com/run"></p>
<p class="code"> <description date="2004-02-07"></p>
<p class="code">Morning run, west side</p>
<p class="code"> </description></p>
<p class="code"> <data mark="1600" top="-31" length="3"></p>
<p class="code"><span xml:lang="en-US" lang="en-US"> <sample x="123.456" y="107.89" flow="76.414" count="5662"/></span></p>
<p class="code"><span xml:lang="en-US" lang="en-US"> <sample x="127.564" y="102.91" flow="72.952" count="4828"/></span></p>
<p class="code"> <sample x="128.654" y="101.32" flow="76.385" count="5503"/></p>
<p class="code"> </data></p>
<p class="code"></run></p>
<p class="code"> </p>
</td>
</tr>
</tbody>
</table>
<p> </p>
<p>And a corresponding schema:</p>
<table cellpadding="0" border="0" rules="all" style="width:100%;border:1pt;border-collapse:collapse;empty-cells:show;table-layout:fixed;border-style:solid">
<colgroup>
<col />
</colgroup>
<tbody style="border:inherit">
<tr style="border:inherit">
<td style="padding: 0.00pt;border:inherit inherit inherit">
<p class="code"> </p>
<p class="code"><?xml version="1.0"?></p>
<p class="code"><xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema"</p>
<p class="code"> xmlns:bx="http://example.org/BX"></p>
<p class="code"> <bx:binary></p>
<p class="code"> <bx:required bx:encoding="BX-1.0-DSNV"/></p>
<p class="code"> </bx:binary></p>
<p class="code"> <xsd:element name="run"></p>
<p class="code"> <xsd:sequence></p>
<p class="code"> </p>
<p class="code"> <xsd:element name="description"></p>
<p class="code"> <xsd:attribute name="date"</p>
<p class="code"> type="xsd:date"</p>
<p class="code"><span xml:lang="en-US" lang="en-US"> use="required"</span>/></p>
<p class="code"> <xsd:simpleType></p>
<p class="code"> <xsd:restriction base="string"></p>
<p class="code"> <xsd:length value="40"/></p>
<p class="code"> </xsd:restriction></p>
<p class="code"> </xsd:simpleType></p>
<p class="code"> </xsd:element></p>
<p class="code"> </p>
<p class="code"> <xsd:element name="data"></p>
<p class="code"> <xsd:attribute name="mark"</p>
<p class="code"><span xml:lang="en-US" lang="en-US"> use="required"</span>></p>
<p class="code"> <xsd:simpleType></p>
<p class="code"> <xsd:restriction base="xsd:positiveInteger"></p>
<p class="code"> <xsd:maxExclusive value="65536"/></p>
<p class="code"> </xsd:restriction></p>
<p class="code"> </xsd:simpleType></p>
<p class="code"> </xsd:attribute></p>
<p class="code"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="top"</span></p>
<p class="code"><span xml:lang="en-US" lang="en-US"> use="required"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:restriction base="xsd:integer"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:maxExclusive value="32768"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:minInclusive value="-32768"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:restriction></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:attribute></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="length"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> use="required"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:restriction base="xsd:positiveInteger"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:maxExclusive value="4194304"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:restriction></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:attribute></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:sequence></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:element name="sample"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> minOccurs="0"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> maxOccurs="unbounded"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="x"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> type="xsd:float"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> use="required"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="x"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> type="xsd:float"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> use="required"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="flow"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> type="xsd:float"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> use="required"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:attribute name="count"</span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> use="required"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:restriction base="xsd:positiveInteger"></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> <xsd:maxExclusive value="1000000"/></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:restriction></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:simpleType></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:attribute></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:element></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:sequence></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:element></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:sequence></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"> </xsd:element></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"><span xml:lang="en-US" lang="en-US"></xsd:schema></span></p>
<p class="code" dir="ltr" style="text-align:left;margin-bottom:0.0000in;margin-top:0.0000in;margin-right:0.0000in"> </p>
</td>
</tr>
</tbody>
</table>
<p> </p>
<p>The schema tells exactly which transforms to select. It defines a fixed structure, with the only variable being the number of sample elements, and since these come at the end the number can be easily deduced from the file size of the binary document. It also defines a fixed length or value range for every type.</p>
<p>Everything is sufficiently constrained that a parser would need no hints about element or attribute order or data size. Thus, the name and value transformations would mark all tokens of width zero, so that they don't appear.</p>
<p>Every document serialized using this schema would map to the following C structure:</p>
<table cellpadding="0" border="0" rules="all" style="width:100%;border:1pt;border-collapse:collapse;empty-cells:show;table-layout:fixed;border-style:solid">
<colgroup>
<col />
</colgroup>
<tbody style="border:inherit">
<tr style="border:inherit">
<td style="padding: 0.00pt;border:inherit inherit inherit">
<p class="code"> </p>
<p class="code"> typedef struct { char ch[3]; } unicode;</p>
<p class="code"> </p>
<p class="code"> struct {</p>
<p class="code"> char declaration[6];</p>
<p class="code"> unsigned long schemaLength;</p>
<p class="code"> unsigned long schemaParty;</p>
<p class="code"> unsigned long schemaDocument;</p>
<p class="code"> unsigned long date;</p>
<p class="code"> unicode description[40];</p>
<p class="code"> unsigned short mark;</p>
<p class="code"> signed short top;</p>
<p class="code"> unsigned long length;</p>
<p class="code"> struct {</p>
<p class="code"> float x;</p>
<p class="code"> float y;</p>
<p class="code"> float flow;</p>
<p class="code"> unsigned long count;</p>
<p class="code"> } sample[*];</p>
<p class="code"> };</p>
<p class="code"> </p>
</td>
</tr>
</tbody>
</table>
<p> </p>
<p>Suppose that one wanted to build a data logger that would take samples in this format, then use off-the-shelf data reduction software to process them. The code for the embedded microprocessor in the data logger could be written in C using the structure above, where it records samples directly into memory and then writes the data file directly out from memory. The data reduction software from vendor A would use an existing XML library that had been augmented by its vendor B with a full implementation of the binary format. On being presented with the schema, the data reduction tool would display the available fields to the user who would instruct it how to deal with the data. The tool could then read any file produced by the data logger.</p>
<p>The proposal as written is particularly good for numerical data, since that easily conforms to fixed width fields. It might be interesting to explore the possibility of an additional transformation that would map strings to a separate, efficiently stored string table at one end or the other of the document or in each block, replacing each instance of a string value with a token that is an index into the string table.</p>
<p class="head1"><a name="4.">4. Summary</a></p>
<p>The proposed binary format has all of the properties listed as requirements in the XML Binary Characterization report. It meets several of the requirements at the top of the list spectacularly well, even though some are contradictory. At the opposite end is Implementation Cost, which is met with qualifications as discussed in that section above.</p>
</div>
</body>
</html>
--=--etoianshrdlu-2--
--=--etoianshrdlu-1--
Received on Tuesday, 21 February 2006 21:04:20 UTC