XML Binary Characterization Measurement Methodologies

6.1.1 Boolean Properties

• Content Type Management
• Directly Readable and Writeable
• Format Version Identification
• Forward Compatibility
• Fragmentable
• Human Language Independent
• Human Readable and Editable
• Implementation Cost
• Integratable Into the XML Stack
• Localized Changes
• No Arbitrary Limits
• Platform Neutrality
• Robustness
• Roundtrip Support
  • This property is not completely applicable to XML 1.1. The point is that any new format must maintain this property.
• Royalty Free
• Schema instance Change Resilience
• Single Conformance Class
• Small Footprint
• Space Efficiency
• Schema Extensions and Deviations
• Streamable
• Transport Independence
• Widespread Adoption

6.1.2 Trinary Properties

• Accelerated Sequential Access - Does Not Prevent *
• Deltas - Prevents Low Level Deltas.* Does Not Prevent High Level Deltas.
• Efficient Update - Does Not Prevent *
• Encryptable - Does Not Prevent
• Embedding Support - Does Not Prevent *
• Random Access - Does Not Prevent *
• Self Contained - Does Not Prevent
• Signable - Does Not Prevent

6.2.1 Boolean Properties

• Compactness
• Explicit Typing
• Extension Points
• Generality
• Specialized Codecs
• Support for Error Correction
• Processing Efficiency

7.1.1 Description

The Compactness property measurement represents the amount of compression a particular format achieves when encoding an infoset. The degree of compactness achieved with a particular format is highly dependent on the input infoset, strategies enabled, and application characteristics. These characteristics should vary considerably to emulate all important use cases in order to properly measure the compactness property of each competing format. To objectively compare formats for their ability to represent infosets in a compact manner, competing measurements of various formats must be taken using the same scenario.

The amount of compactness achievable for a given XML document is a function if the document's size, structure, schema, regularity and associated application data needs. Because XML documents exist with a wide variety of sizes, structures.schemas, regularity and applications, it is not possible to define a single size threshold or compactness percentage that a binary XML format must achieve on XML documents to be considered sufficiently compact. The amount of compactness a binary XML format achieves will vary from one XML document to the next. Therefore, we define sufficient compactness relative to well known techniques for achieving compactness on XML data. These techniques set user expectations regarding achievable compactness and can be used to measure the compactness of a particular binary format relative to user expectations.

A possible disadvantage of any compact encoding might be the additional computation required to generate or interpret and use the encoding. There is a tendency, exhibited by many space minimization strategies, for space efficiency to be inversely proportional to processing efficiency. If space efficiency is absolutely maximized, processing efficiency will decrease in most cases. Note that for many Abstract Scenarios, it is possible to improve both compactness and processing efficiency relative to the use of XML 1.1. It is desirable for a format to support the ability to control its space efficiency based on the need for processing efficiency, available memory, or other properties. For example, if the format is processed on a high-end server, the algorithm should be able to be tuned to obtain maximum processing efficiency by sacrificing memory efficiency. On the other hand, if the format is processed on low-end mobile handsets, the algorithm should be able to obtain maximum compactness by sacrificing processing efficiency. A key need is the ability to balance compactness with processing efficiency in an tunable way. Certain strategies, principally frequency-based dynamic analysis such as gzip compression, are more appropriate when size is the overriding concern. Given the constraints of simultaneously minimal size and processing overhead, methods such as tokenization with dictionary tables might be more successful.

Size efficiency, or compactness, concerns the optimization of the storage or transmission resources needed to represent an infoset. Several categories of methods are known to be useful. This section reviews major categories of methods and related topics which provides background for format analysis.

A data object, which is the representation of an infoset, consists of three logical components that usually have a physical representation. These are the data, the structural information, and metadata (including typing). For XML 1.1, the structure and metadata are represented by tag syntax and naming while data is mostly present in attribute values and element text. Some strategies for data representation remove some or all structural and metadata representation and place it in external metadata or embedded in code.

There are three categories of methods to reduce the size of a data object or infoset: compression, decimation, or externalization. Competitive formats may make use of one or more methods from each category. Compression is the transformation of data into corresponding data that takes less storage space through the removal or reuse of redundant information and more efficient coding of data. Compression is often paired with decimation, the process of eliminating some details that are not used or of less importance than more important components of the original data. This is called "lossy compression" as opposed to "lossless compression".

Externalization is the process of representing an original infoset as an external representation with varying degrees of reuse and a data object that relies on that external instance as a source of redundancy. Besides the trivial replacement of an object with a reference, there are two main externalization methods, schema-based and delta-based. A schema-based method relies on a specification for certain aggregate data types, structure, and/or values. Trivially, this could mean sending and receiving code that simply writes and reads values in a certain order with no explicit structure. In this case, the structure and data type metadata is implicitly present in the code. More sophisticated methods rely on interface definition languages (IDL) or the reuse of validation schema such as XML Schema for externalization purposes. The use of these structural and metadata specifications may result in code generation and/or the production of metadata for use by an interpretive engine. Schema-based externalization usually has long-term schema reuse characteristics. A schema-based externalization is relying on long-term redundancy. This is compatible with some programming and lifecycle models, but can conflict with some application needs.

When the externalization method relies in a generalized way on representing differences from a template, parent object, or earlier message, it is called a delta. Delta mechanisms can be implemented in a high level, logical operations level, or as a low level byte or slot difference representation. Deltas can be produced by a computational differencing operation or by recording the location of changes as they happen. Deltas take advantage of both long term and short term redundancy.

In many cases, compression benefits from processing as much data as possible at the same time rather than considering individual fragments in isolation. This leads to processing models where a bulk compression or decompression step is performed. Generally, this leads to the data being inaccessible to application logic until all of the data is decompressed.

There are numerous methods of compression which rely on different methods of detecting redundancy and representing data. These methods sometimes have data access pattern needs and are generally good at compressing some data while having limited use on other data. Some popular methods include:

• Stream compression
• Block sorting compression
• Run length coding
• Linear quantization
• Dictionary coding
• Key compression
• Huffman coding
• Token tables
• Arithmetic coding
• Lempel-Ziv variants
• Quadtree and similar subdivision methods
• Frequency domain
• Wavelet coding
• Fractal coding

See the Compression FAQ for more information on these methods.

7.1.2 Type & range

For a given input document, this property is measured as a set of values [X, Lossy, Schema, Delta]. X represents the percent smaller the encoded version of the document is from the original. Lossy is a True or False with a True indicating the format uses a lossy compression scheme and a False indicates a lossless scheme. (Lossy and Lossless are defined by the Round Trip Support Measurement.) Schema is also a True or False with a True indicating the format achieves its compression via a schema-based encoding, and a False indicates a schema-based encoding is not used. Delta is also a True or False with a True indicating the format achieves its compression via a delta-based encoding, and a False indicates a delta-based encoding is not used.

XML 1.1 would measure as follows: [0%, False, False, False].

7.1.3 Methodology

When measuring the Compactness property, the encoder is not permitted to use prior knowledge about the semantics of information items used in the input document. For example, the encoder is not permitted to use specialized codecs to encode the contents of a specific element or attribute in the given instance document based on the name or location or that element or attribute.

A format that achieves compression without losing data and without the requirement to process the schema or reference document would be represented as [x%, False, False, False] where x is an integer value representing the amount of compression achieved. This enables formats that have higher compression numbers to be compared objectively with other formats, assuming the remaining three values are the same.

7.1.4 Dependencies

Compactness tends to have an inverse dependency relationship with Processing Efficiency, Small Footprint, and Space Efficiency.

7.1.5 Known Tradeoffs

High scores for this property may be at odds with higher scores in the following properties (An example is given why each is listed):

• Accelerated Sequential Access: An index is present to allow skipping over content.
• Fragmentable: Additional context is required for decoder.
• Human Readable and Editable: Additional information required in the format.
• Random Access: An Index table is required in the format.
• Robustness: Dedicated redundancy added to the format.
• Roundtrip Support: Lossless equivalence can mean a larger representation.
• Self Contained: Relevant information retained in the encoding.
• Specialized Codecs: The format may include references to predefined extensions.
• Support for Error Correction: Requires redundancy be contained in the representation.
• Processing Efficiency: Additional information may be provided in a format to elicit faster processing speeds.

7.2.1 Description

Processing Efficiency is a measure of the efficiency, and effectively the speed, of processing an instance of a format. Determining the relative speed of different formats in a complete and valid way is difficult. This is because there are many variables that affect actual speed, including processing library implementation details that are not fundamentally required by the format. Ideally, different formats could be compared based on determination of their best reachable performance levels in all needed situations. In practice, this cannot be done with absolute accuracy. As a result, comparative evaluation must be accomplished by a combination of complexity analysis, processing characterization estimation, format characteristic analysis, fitness for all needed abstract scenarios, and actual empirical testing. It is important to stress that while empirical testing provides proof of obtaining at least a certain level of performance, by itself it proves little about whether better performance can be obtained for a particular format and abstract scenario. Complexity analysis tends to be able to provide better proof of the theoretical limits of performance, although this is not infallible in the face of unexpected algorithms. Additionally, in some cases complexity for multiple candidates may be, for example, linear and relative performance differences may be dominated by format or method details that affect overhead such as an extra level of indirection. As an example of a subtle but possibly dominant detail, one format may tend to allow better locality of reference in processing than another. With cache memory in modern systems running 25 or more times faster than main memory, a large subset of processing scenarios could perform better for the former format.

The amount of increase in processing speed is dependent on the input documents used for testing. Therefore, to objectively compare formats for their inherent processing speed, competing measurements using the same set of input documents must be taken. These documents should vary is size and complexity to generate a set of results. In addition, normal performance profiling steps need to be followed. These include, but are not limited to, constructing a proper test environment with stable machines and software, utilizing a private network, and providing proper "warm-up" for adaptively compiled systems like Java. This requires the use of an appropriate set of Abstract Scenarios, Property Profiles, and Test Data.

Any algorithm used for this measurement should have a theoretical runtime of no more than O(n). However, this measurement alone cannot be used to effectively determine the speed of the algorithm. It is possible that two algorithms with O(n) runtimes could have vastly different performance characteristics if, for example, one algorithm used 100 cycles per byte processed, while the other used 500 cycles per byte processed. Both algorithms would be O(n), but result in vastly different performance measurements.

7.2.2 Type & range

For a given Abstract Scenario, Property Profile, and Test Data test scenario, this property is measured in several different ways:

1. Serialization - The time it takes to generate the alternate format.
2. Format parsing - The time it takes to parse the alternate format.
3. Data binding - The time it takes to create the application data model from the data contained in the alternate format.
4. Abstract processing steps - application operations such as creation, access, read, insertion, deletion, etc. This measurement aspect will only be relevant for certain Abstract Scenarios. In some scenarios, this aspect is controlling of the others and of other properties. For instance, when testing random access with incremental overhead, it is important to determine the minimum, incremental parsing and data binding required.

Each measurement is recorded as a percentage faster than a standard text-based alternative. Therefore, for a particular format, the measurement results might be: 73%, 250%, 48%, 5%, representing the speedup for serialization, format parsing, data binding, and processing steps, respectively.

7.2.3 Methodology

Measurements must be taken as follows:

1. Use a specific set of input documents and a text-based XML implementation to generate a baseline.
2. Using the same input documents, generate the alternate format and compare the results of the four tests when using an implementation of the alternate format.

This will allow a fair comparison between various alternate formats to determine their processing efficiency differences.

7.2.4 Dependencies

Processing Efficiency has a correlated relationship with Small Footprint and Space Efficiency and an inverse relationship with Compactness. Additionally, this property can be considered a measurement of the processing efficiency for most other properties.

7.2.5 Known Tradeoffs

High scores for this property may be at odds with higher scores in the following properties:

• Compactness: Compact encodings can cost extra cycles to interpret and expand compared to simpler formats.
• Human Readable and Editable: Precise structural information needed for efficiency, even if represented in text, tends to make a format less human readable and editable.
• Support for Error Correction: Requires processor to potentially detect and correct errors, therefore reducing processing speed.

7.3.1 Description

The objective of Accelerated Sequential Access to reduce the amount of time required to access XML infoset items in a document. The fundamental measurement is therefore the average time needed to access an XML infoset item. This time can be compared to a baseline measurement of the average time needed to access an XML infoset item using an unaccelerated sequential access method like that used to implement SAX.

T(ix) - time to create a sequential index, if used (fixed) T(sk) - time to seek an infoset item (average) T(am) - total time for all accesses over the document. This time amortizes the cost of T(ix) over the average number of total seeks (ns).

Not all accelerated sequential access methods use a sequential index and incur T(ix). In this case it is only necessary to compare T(sk) average for the unaccelerated case against the accelerated one.

If accelerated sequential access supports update of the sequential index we should also take this cost into account.

T(up) - time to update the sequential index.

T(up) should also be added to T(am) for the average number of total updates (nu).

T(am) = T(ix) + ns ( T(sk) ) + nu ( T(up) )

For the baseline, unaccelerated sequential access case we consider only T(sk) for the average total number of seeks (ns).

T(am) = ns ( T(sk) )

Example:

For an implementation of accelerated sequential access to XML:

  T(ix)  5.00ms
  T(sk)  3.50ms
  T(up)  3.00ms
  ns  1000
  nu    50
  
  T(am) = 5 + 1000 ( 3.5 ) + 50 ( 3.0 ) = 3655

For unaccelerated sequential access:

  T(sk)  4.00ms
  
  T(am) = 1000( 4 ) = 4000

Accelerated sequential access may have resource costs which can impact system performance. A more comprehensive model would be needed to take these into account in a full assessment of the comparative benefit of a accelerated sequential access implementation. As an approximation, an implementation which produces lower number for the following resource costs will be better in performance than an implementation with the same T(am) but with higher resource costs:

1. Memory consumption for sequential index structure
2. Cost in bandwidth utilization for I/O and transport of the sequential index if persisted
3. Cost of persistent store, if the sequential index structure is persisted

7.3.2 Type & range

7.3.3 Methodology

7.3.4 Dependencies

7.3.5 Known Tradeoffs

7.4.1 Description

The Efficient Update property is concerned with whether a format instance can be modified efficiently without being completely rebuilt. When a format is designed with efficient update as a constraint, it will tend to be apparent that this is possible. When this was not planned for, it is still possible that a processor could implement an efficient update capability. In the latter case, an evaluation of the format must determine if there are features that prevent or assist such implementation. As the property description notes, this property is somewhat related to support for Deltas.

There are three aspects under which this property should be evaluated:

1. Efficiency of update: This is the time and complexity required to apply the changes, starting from the original serialization up until the updated serialization is produced.
2. Efficiency of retrieval: This is the time required to retrieve a (possibly) modified value.
3. Compactness: This is the additional space required for the application of an update or the typical overhead of supporting different kinds of changes to a format instance. In the existence proof example, inserting a new element might be efficient because it might just result in an append to the file while inserting characters in a large text might cause a new chunk to be allocated at the end of the file and the old chunk to become an unused block. While the block could be reused just like with malloc, mitigating the cost, it is still a potential inefficiency.

7.4.2 Type & range

Evaluations of candidate formats that implement this property will produce three percentage values and a standard deviation. For update and retrieval, these are positive or negative percentages of improvement relative to comparison XML 1.1 solution. For compactness, this percentage is overhead over a linear creation of an instance with the same data in the candidate format, along with an estimated (for analytical) or actual (for empirical) standard deviation.

7.4.3 Methodology

The measurement for this property is by inspection of format specification, logical analysis, and empirical testing of test scenarios based on Abstract Scenarios that call for Efficient Update.

7.4.4 Dependencies

This property doesn't depend on other properties. It does have a weak relationship with Deltas based on solving similar problems.

7.4.5 Known Tradeoffs

The ability to support efficient updates in the direct, complete sense tends to imply compactness measures that are not monolithic and a mechanism for growing or shrinking data without requiring repositioning for all data following the change. Solutions for these tradeoffs will likely focus on differing granularity and may be tunable.

7.5.1 Description

Measures the degree to which a format supports embedding of files of arbitrary type within serialized content.

7.5.2 Type & range

This property is measured along an integer scale from [0,6], where zero indicates no embedding support and six indicates the greatest possible degree of embedding support.

7.5.3 Methodology

This property is measured by considering which of the following statements is true, based on that format's specification:

1. Provides structures or elements in which data of arbitrary type and reasonable size can be stored by virtue of the flexibility of the format.
2. Provides well-known points at which data of arbitrary type can be embedded.
3. Provides for the existence and management of metadata about embedded files.
4. Provides the ability to include or exclude embedded files from signatures over the file.
5. Provides the ability to include or exclude embedded files when (partially) encrypting the file.
6. Provides the ability to compress the contents of the embedded file.

The measurement levels resulting from this analysis are:

1. Doesn't support
2. Supports to some extent
3. Supports well

7.5.4 Dependencies

Support for (d) signing and (e) encryption are dependent on an underlying format which supports the Signable and Encryptable properties.

7.5.5 Known Tradeoffs

A format which supports embedding must make weaker guarantees regarding the humanly readable and editable property, since it forgoes control over the contents of the embedded files.

7.6.1 Description

The degree that the format supports no inherent limits is characterized as: No inherent limits, few limits (i.e. unreasonably large names), and many limits (fixed lengths, small tables).

Experience has shown that arbitrary limits in the design of reusable systems must be carefully scrutinized for the probability of future conflicts. As computing limitations have repeatedly been surpassed in short order and technology has been put to innovative uses, decisions that turned out to be short-sighted have led to painful migration. This property provides a rough measure with which to compare different approaches.

7.6.2 Type & range

The range of this measurement is membership in a category. These categories are: "no inherent limits", "few limits", and "many limits".

7.6.3 Methodology

The measurement for this property is by inspection of format specification and logical analysis.

7.6.4 Dependencies

This property does not depend on other properties.

7.6.5 Known Tradeoffs

Each type of flexibility in a data format can be a tradeoff between efficiency in the expected typical case and the ability to handle cases that are not expected to be encountered. In many cases in the past, seemingly sensible choices have not aged well with increases in computing capacity and new uses of technology.

7.7.1 Description

Measures the degree to which a format is competitive with alternatives across a diverse range of data, applications and use cases.

Generality is, in part, a function of the formats ability to optimize for application specific criteria and use cases. For example, some applications need to maximize compactness and are willing to give up some speed and processing resources to achieve it. While others need to maximize speed and are willing to give up some compactness to achieve it. Similarly, some applications require all the information contained in a document and are willing to give up some compactness to preserve it. Other applications are willing to discard certain information items in a document to achieve higher compactness.

Generality is also a function of the optimizations the format includes for efficiently representing documents of varying size and structure. For small, highly structured documents, a format informed by schema analysis will generally produce more compact encodings than a format informed solely by document analysis (e.g. generic compression software). For larger, more loosely structured documents, a format informed by document analysis techniques will generally produce more compact encodings than a format solely informed by schema analysis. A format informed by both schema analysis and document analysis will generally produce more compact encodings across a broader range of documents than a format that only includes one of these techniques.

7.7.2 Type & range

This property is measured along an integer scale in the range [0, 20], where a zero indicates a very specialized format that applies narrowly to a small set of data, applications, and use cases and 16 indicates a very general format that applies to a wide range of data, applications, and use cases.

7.7.3 Methodology

This property is measured by counting the number of statements below that are true of the format, based on inspection of the format specification and objective analysis of compactness results over a wide range of XML documents with varying size and structure. Statements designated as [optional] will broaden the applicability of a binary XML file format, but are not required for that format to be considered sufficiently general. The statements are organized into sections for readability.

Flexible schema analysis optimizations

• Can represent documents without a schema
• Can represent documents that include elements and attributes not defined in the associated schema (i.e., open content)
• Can represent any schema-invalid document
• Can leverage available schema information to improve compactness, processing speed, and resource utilization
• Can leverage available schema information to improve compactness, processing speed, and resource utilization even when documents contain elements and attributes not defined in the schema
• Can leverage available schema information to improve compactness, processing speed, and resource utilization for any schema-invalid document.

Flexible document analysis optimizations

• Can leverage document analysis to improve compactness
• Can suppress document analysis to increase speed and reduce resource utilization
• [optional] Can adjust document analysis to meet application performance and resource utilization criteria
• Can structure the binary XML stream to increase net compactness when off-the-shelf compression software is built in to the communications infrastructure

Flexible fidelity optimizations

• [optional] Supports high fidelity XML representations that preserve an exact copy of the original XML document, including all whitespace and formatting
• Supports reduced fidelity XML representations that preserve all infoset items, but discard whitespace and formatting to improve compactness
• Supports reduced fidelity XML representations that preserve all information needed by a particular application, but discard specified information items that are not needed (e.g., comments and processing instructions) to improve compactness
• Supports reduced fidelity XML representations that preserve the logical structures and values of an XML document, but discard lexical and syntactic constructs to improve compactness

Competes with frequency based compression

• Can consistently produce XML representations that are close to the same size or smaller than XML documents compressed using gzip
• Can consistently produce more compact XML representations than XML documents compressed using gzip
• Can consistently produce more compact XML representations than binary XML documents created with document analysis suppressed, then compressed using gzip

Competes with schema based encodings and hand optimized formats

• Can consistently produce XML representations that are close to the same size or smaller than the equivalent ASN.1 PER encoding
• Can consistently produce XML representations that are more compact than the equivalent ASN.1 PER encoding
• [optional] Can consistently produce XML representations that are more compact than the equivalent ASN.1 PER encoding compressed using gzip

7.7.4 Dependencies

7.7.5 Known Tradeoffs

High scores for this property may be at odds with high scores for the Small Footprint property. Some implementation approaches for supporting a broad range of data, applications, and use cases may require larger amounts of code.

7.8.1 Description

Measures the degree to which a format is or must be humanly readable and editable.

7.8.2 Type & range

This measurement is a pair of integers <m,n>, each on the scale [0,5]. The first number indicates the degree to which a file in a format may be humanly readable and editable; the second number indicates the degree to which a file in a format must be so. Thus, the greater the difference between the two numbers the greater the degrees of freedom given to the file's creator with respect to this property.

7.8.3 Methodology

Each item in the following list of statements is evaluated to determine if it is never true, may be true, or is always true of file created according to the file's specification.

1. If the statement is never true of this format no points are assigned;
2. If the statement may be true then one point is added to the first number of the score;
3. If the statement is always true than one point is added to both numbers of the score.

(Note: the first number in the score is therefore always greater to or equal than the second number.)

1. Uses a regular and explicit structure.
2. Uses only text, avoiding the use of compression or magic numbers.
3. For any given type of information (i.e., specifying a character encoding) uses a unique encoding mechanism.
4. Is self-contained.
5. Maintains the locality of items per their relative positions in the data model.

7.8.4 Dependencies

Support for this property is dependent in part on how self contained it is.

7.8.5 Known Tradeoffs

High scores for this property may be at odds with higher scores in Compactness, Processing Efficiency, Efficient Update, Random Access, Accelerated Sequential Access, and Specialized Codecs, all of which typically use techniques at odds with the requirements of this property.

7.9.1 Description

Measures the degree to which a format specifies usable Content Type Management information.

7.9.2 Type & range

This measurement uses a simple range of options from worst to best integration.

7.9.3 Methodology

Degrees of support:

1. provides no media type or encoding specification
2. provides a media type but not a content coding
3. provides a media type suffix akin to "+xml"
4. provides a content coding

7.9.4 Dependencies

None.

7.9.5 Known Tradeoffs

Note that there currently is dissent as to whether a binary XML format should be considered to be a content coding (like gzip) or not. Here are the options:

• It's just a content coding. In this case it may have a media type (like application/gzip) but the proper way of using it is to keep the original media type of the XML content and simply change the content coding. The upside is that the current dispatch system is untouched, that the media type information is far more useful that way, and that the content coding infrastructure is put to good use. The downside is that there is philotechnical dissent that binary XML is an encoding in the way that gzip is, and that there can be friction with the charset parameter to XML media types. With this content negotiation is fully possible. The behavior of fragment identifiers does not need to be re-specified.
• It's not a content coding but a media type, two sub-options:
  • There's just the media type. Any content sent using the format must have the media type of the format. The upside is that it's simple. The downside is that you lose all media type information so that you must then move to another system to provide that information (some Web systems - e.g. browsers - don't work without it), or define new media types for all content (application/binxhtml, image/binsvg, etc.). With this content negotiation is entirely impossible (or rather, totally useless) unless new media types are defined for all things XML. The behavior of fragment identifiers becomes impossible to specify, or has to be re-specified for all the new media types.
  • A new suffix, in the "+xml" style, is defined (say "+bix"). The upside is that it's simple and that the diversity of media types is maintained. The downside is that it requires more intrusive modifications to systems that rely on existing media types. The latter may be fine if there is one and only one binary XML encoding out there (or at least a set list so that the intrusive modifications are performed only once), but given an open-ended set of binary XML formats it becomes quite impractical. With this content negotiation is possible, but with lesser power. The behavior of fragment identifiers has to be re-specified to map back to the one in +xml types.

7.10.1 Description

Measures the ease with which a given format integrates with the rest of the XML Family of recommendations, based on its orthogonality in specification and the way in which it supports the core assumptions common to XML specifications. Many relevant considerations are presented in the Architecture of the WWW.

7.10.2 Type & range

This property is measured using a scale that reuses the measurement performed on Data Model Versatility for its middle point.

7.10.3 Methodology

The following scale (from lowest to highest support) is used:

1. optimized for a data model from outside the core XML Family
2. scores well on Data Model Versatility
3. uses the XML 1.x syntax

7.10.4 Dependencies

This measurement has a strong dependency on the Data Model Versatility measurement, even though it includes options outside the range of the latter.

7.10.5 Known Tradeoffs

The simplest way of integrating well into the XML Family is obviously to use an XML-compatible. This however does not mean that the given format shall be XML 1.x itself, for instance it could be a subset allowing only certain tokens or requiring a certain form and encoding (for instance a canonical version of the SOAP profile of XML). While this would enable normally impossible optimization to XML parsers, it would also close the door to a great number of other possible optimizations.

It must also be noted that some core XML technologies such as signatures and encryption rely directly on the XML syntax. There is therefore a tradeoff in which a format could integrate perfectly well with the XML Family minus these two members.

7.11.1 Description

Measures the degree to which a format is platform neutral as opposed to being optimized for a given platform.

7.11.2 Type & range

Measures the degree to which a format is platform neutral as opposed to being optimized for a given platform.

7.11.3 Methodology

This property is measured along an axis of values that rate its platform neutrality from none to optimal:

1. not platform-neutral at all (for instance, may be the native serialization of a given programming platform)
2. defined in a platform-neutral manner, but with fixed values for certain parameters that may advantage a platform over another (for instance, only a single Unicode encoding is supported)
3. defined in a platform-neutral manner, and multiple options (word-length, float format, etc.) can be set so that users may choose locally optimal encodings when the platforms involved in a given interchange are known.

7.11.4 Dependencies

This property has a weak link to Implementation Complexity in that if it is supported at its optimal level it will lead to require multiple encoding options that could be costly in implementation terms.

7.11.5 Known Tradeoffs

While allowing a format to support a large range of options to enable optimal processing between similar platforms, the added complexity may in fact have a generally negative impact as it complicates the format. While an assessment of this tradeoff can only be made on a format by format basis, it must be noted that allowing too many hooks for optimization may in fact prove to be a pessimisation.

7.12.1 Description

The objective of Random Access is to reduce the amount of time required to access XML infoset items in a document. The fundamental measurement is therefore the average time needed to access an XML infoset item. This time can be compared to a baseline measurement of the average time needed to access an XML infoset item using a sequential access method like that used to implement SAX.

This performance metric does not take into account what may be accessed with random access method and what operations may be supported on what is looked up (for example, can the looked-up item be treated as a sub-document or fragment).

T(ra) - time to create an access table (fixed) T(lu) - time to lookup an infoset item (fixed) T(sk) - time to seek an infoset item (average) T(am) - total time for all accesses over the life of the document This time amortizes the cost of T(ra) over the average number of total seeks (ns).

T(am) = T(ra) + ns ( T(lu) + T(sk) )

If random update of the access table is supported we should also take into account this cost.

T(up) - time to update an access table (fixed)

T(up) should also be added to T(am) for the average number of total updates (nu).

T(am) = T(ra) + ns ( T(lu) + T(sk) ) + nu ( T(up) )

For the baseline, sequential access case we consider only T(sk) for the average total number of seeks (ns).

T(am) = ns ( T(sk) )

Example:

For an implementation of random access to XML:

T(ra) 10.00ms
T(lu)   .05ms
T(sk)  1.00ms
T(up)  1.00ms
ns  1000
nu    50
                        

T(am) = 10 + 1000( .05 + 1.00 ) + 50 ( 1.00 ) = 1110

For sequential access:

T(sk)  4.00ms

T(am) = 1000 ( 4 ) = 4000

In this example, random access is advantageous if the average total number of seeks is over 3. For ns = 3, nu = 0 the random access T(am) is 13.15 and the sequential T(am) is 12 while at ns = 4, nu = 0 it is 14.20 versus 16.

Random access has resource costs which can impact system performance. A more comprehensive model would be needed to take these into account in a full assessment of the comparative benefit of a random access implementation. As an approximation, an implementation which produces lower numbers for the following resource costs will be better in performance than an implementation with the same T(am) but with higher resource costs.

1. Memory consumption for access table
2. Cost in bandwidth utilization for I/O and transport of the access table if persisted
3. Cost of persistent store, if the access table is persisted

The random access implementation can be categorized by the embedding or non-embedding of the access table:

1. No access table and not indexable - no random access
2. No access table but indexable
3. Access table defined part of format, but separate from XML document
4. Access table optionally embedded in the document
5. Access table always embedded in the document

Another simplification made in comparing T(am) for random access and sequential access is the assumption made that the random access implementation is able to provide access to the infoset items the user wants. If this is not the case, either the implementation of random access will not be useful to that user, its performance notwithstanding, or alternate methods of access would have to be provided and accounted for in the T(am). The access coverage to the infoset provided by the random access implementation can be categorized as follows:

1. Complete: addressing information for all infoset items
2. Selective: for certain infoset items
3. On-Demand: for infoset items which have been requested
4. Heuristic: for infoset items which have been predicated to be needed

It should also be specified whether the implementation does or does not provide alternative access methods to obtain all infoset items.

The random access implementation can also be categorized by its support for fragmentation:

1. Full Context (the random access implementation can provide full context information for the accessed infoset item's subtree)
2. Complete Subdocument (namespaces are propagated so that the accessed infoset item's subtree can be handled as a complete document)
3. No support for fragmentation

7.12.2 Type & range

The measurement for this property is by inspection of format specification and logical analysis.

7.12.3 Methodology

7.12.4 Dependencies

7.12.5 Known Tradeoffs

7.13.1 Description

Measures the degree to which a format supports round-tripping and round-tripping via XML.

7.13.2 Type & range

These two properties are measured along the same enumerated scale consisting of the following values:

1. "Exact equivalence": If round-tripping produces a byte-per-byte duplicate of the original
2. "Lossless equivalence": If exact equivalent is not achieved but round tripping produces a lossless equivalent to the original input
3. "Does not round trip": If round tripping is not supported.

7.13.3 Methodology

This property is measured by comparing the set of data models which can be represented in XML with those that can be represented in the alternative format.

With regards to Roundtrip Support (XML to binary to XML):

1. If the set of models supported by XML is a proper superset of those supported by the format, the measurement is - "Does Not Roundtrip."
2. If the transformations to and from the other format are byte preserving, the measurement is - "Exact Equivalence."
3. Otherwise, the measurement is - "Lossless Equivalence."

With regards to Roundtripping via XML (binary to XML to binary):

1. If the set of models supported by XML is a proper subset of those supported by the format, the measurement is - "Does Not Roundtrip."
2. If the transformations to and from the other format are byte preserving, the measurement is - "Exact Equivalence."
3. Otherwise, the measurement is - "Lossless Equivalence."

7.13.4 Dependencies

There are no known dependencies of this property on other properties.

7.13.5 Known Tradeoffs

Formats supporting both roundtrip and roundtrip via XML will tend to have the same data model versatility measurement as XML, as that is a measure of the set of data models which they support. Formats with greater data model versatility are more likely to support round-tripping but less likely to support round-tripping via XML, and vice versa.

7.14.1 Description

Measures the degree to which a format supports the creation and inclusion of digital signatures.

7.14.2 Type & range

This property is measured along an integer scale from [0,6], where zero indicates no support for digital signatures six indicates the greatest possible degree of support. (Note that a format with a score of zero is still signable, in that a file consists of a sequence of bytes and any sequence of bytes can be signed.)

7.14.3 Methodology

This property is measured by assigning the indicated number of points for each of the following statements which is true of the format, based on that format's specification:

1. Defines unique serializations for each possible data model instance (avoids canonicalization): 2 points
2. Permit multiple serializations for each data model instance, but defines one serialization as canonical: 1 point
3. Always serializes subtrees in a contiguous manner: 2 points
4. Permits, but does not require, the serialization of subtrees in a contiguous manner: 1 point
5. Defines a syntax for signature (i.e., recording certificates, signed ranges, etc.): 2 points

7.14.4 Dependencies

There are no known dependencies of this property on other properties.

7.14.5 Known Tradeoffs

Implementation of this property may be at odds with Compactness, Random Access, and Efficient Update, as support for these properties may be at odds with maintaining contiguous subtrees.

7.15.1 Description

A candidate format should be able to be processed by diverse platforms. Many of these platforms have very limited resources for program storage. A format that requires little actual code and data tables (aka initialized or BCC data) is attractive more widely. Inspection of specifications can be a useful form of analysis. Analysis of actual implementations can also be enlightening when those implementations are optimized by skilled developers.

7.15.2 Type & range

The detailed measurement for this property will consist of code and initialized data measured, estimated, or projected to a series of platforms that relate to key architectures including 64K StrongARM, Java bytecode, and Intel/AMD Pentium/64bit.

7.15.3 Methodology

The measurement for this property is by inspection of format specification, logical analysis, survey of implementations and implementers, and projections from one architecture to the others.

7.15.4 Dependencies

7.15.5 Known Tradeoffs

There is likely to be a tradeoff with Generality, Compactness, and general support of many features.

7.16.1 Description

Space Efficiency is the measurement of dynamic memory needed to decode, process, and encode a candidate format. In this case, processing doesn't include any application processing or needs, but may include any format-induced processing or bookkeeping that must be done to adhere to the format. Special consideration must be given to separate and discount overhead that a format requires that is accomplishing something that an application would likely need to perform anyway.

7.16.2 Type & range

This is a percentage measurement relative to the expected dynamic memory costs of popular and theoretical XML 1.1 processing systems. This may include both DOM and parser event (SAX et al) style processing. Due to the nature of applications in memory-constrained environments, it is the DOM-style measurement that is ranked for this property.

7.16.3 Methodology

The measurement for this property is by inspection of format specification, logical analysis, and empirical testing on test scenarios.

7.16.4 Dependencies

This property is related to Compactness and Processing Efficiency and may be affected by Generality.

7.16.5 Known Tradeoffs

Some Compactness methods tend to increase memory usage, sometimes dramatically. Reducing Processing Efficiency may also affect dynamic memory needed.