ISO/IEC JTC1/SC34

ISO/IEC

ISO/IEC JTC1/SC34

Information Technology —

Document Description and Processing Languages

Title: Topic Maps — Canonicalization
Source: Jaeho Lee, Lars Marius Garshol, Motomu Naito, JTC1 / SC34
Project: ISO 13250: Topic Maps
Project editor: Jaeho Lee, Lars Marius Garshol, Motomu Naito
Status: Final Committee Draft
Action: For review
Date: 2008-04-14
Summary:
Distribution: SC34 and Liaisons
Refer to: http://www.isotopicmaps.org/cxtm/2008-04-14/
Supercedes: http://www.isotopicmaps.org/cxtm/2004-11-01/
Reply to: Dr. James David Mason
(ISO/IEC JTC1/SC34 Chairman)
Y-12 National Security Complex
Information Technology Services
Bldg. 9113 M.S. 8208
Oak Ridge, TN 37831-8208 U.S.A.
Telephone: +1 865 574-6973
Facsimile: +1 865 574-1896
E-mail: mailto:mxm@y12.doe.gov
http://www.y12.doe.gov/sgml/sc34/sc34oldhome.htm

Mr. G. Ken Holman
(ISO/IEC JTC 1/SC 34 Secretariat - Standards Council of Canada)
Crane Softwrights Ltd.
Box 266,
Kars, ON K0A-2E0 CANADA
Telephone: +1 613 489-0999
Facsimile: +1 613 489-0995
Network: jtc1sc34@scc.ca

Topic Maps — Canonicalization

Contents

1 Scope
2 Normative references
3 Terms and definitions
3   Canonicalization
3.1   Introduction
3.2   Notational conventions
3.3   CXTM Document Information Item
3.4   Constructing a representation of a topic map item
3.5   Constructing a representation of a topic item
3.6   Constructing a representation of the topic name item
3.7   Constructing a representation of a variant item
3.8   Constructing a representation of an occurrence item
3.9   Constructing a representation of an association item
3.10   Constructing a representation of the association role item
3.11   Constructing a representation of the [reifier] property
3.12   Constructing a representation of the [reified] property
3.13   Constructing a representation of the [scope] property
3.14   Constructing a representation of the [item identifiers] property
3.15   Constructing a representation of the [datatype] property
3.16   Constructing a representation of the [type] property
3.17   Constructing a representation of the [value] property
3.18   Constructing a representation of locator values
3.19   Normalizing locator values
3.20   Constructing the number attribute
3.21   Encoding of string properties
3.22   Encoding of positional values
3.23   Default property values for element information items
3.24   Default property values for attribute information items
4   Canonical Sort Order
4.1   Introduction
4.2   Information Type and Basic Type Sort Order
4.3   Comparison of Strings
4.4   Comparison of Sets
4.5   Comparison Order for Locators
4.6   Canonical Sort Order for Topic Items
4.7   Canonical Sort Order for Topic Name Items
4.8   Canonical Sort Order for Variant Items
4.9   Canonical Sort Order for Occurrence Items
4.10   Canonical Sort Order for Association Items
4.11   Canonical Sort Order for Association Role Items
A   RELAX-NG Schema for CXTM

Foreword

ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.

International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.

ISO/IEC 13250-4 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information Technology, Subcommittee SC 34, Document Description and Processing Languages.

ISO/IEC 13250 consists of the following parts, under the general title Topic Maps:

Introduction

This part of ISO/IEC13250 defines a format known as Canonical XTM, or CXTM for short. The format is an XML format, and has the property that it guarantees that two equivalent Topic Maps Data Model instances [ISO/IEC 13250-2] will always produce byte-by-byte identical serializations, and that non-equivalent instances will always produce different serializations. CXTM thus enables direct comparison of two topic maps to determine equality by comparison of their canonical serializations.

The purpose of CXTM is to allow the creation of test suites for various Topic Maps-related technologies that are easily portable between different Topic Maps implementations, so long as these support CXTM.

CXTM is not intended to be used for the interchange of topic maps, although this is possible. The standard format for interchange of topic maps is XTM [ISO/IEC 13250-3].

Topic Maps — Canonicalization

1 Scope

This part of ISO/IEC13250 defines the CXTM format, and specifies how CXTM files are produces from topic maps by means of a transformation from the Topic Maps Data Model [ISO/IEC 13250-2] to the XML Infoset [XML Infoset].

2 Normative references

The following referenced documents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies.

NOTE:

Each of the following documents has a unique identifier that is used to cite the document in the text. The unique identifier consists of the part of the reference up to the first comma.

ISO/IEC 10646-1, ISO/IEC 10646-1:2000: Information technology — Universal Multiple-Octet Coded Character Set (UCS) — Part 1: Architecture and Basic Multilingual Plane, ISO, 2000

ISO/IEC 10646-2, ISO/IEC 10646-2:2001 Information technology — Universal Multiple-Octet Coded Character Set (UCS) — Part 2: Supplementary Planes, ISO, 2001

Unicode, The Unicode Standard, Version 5.0.0, The Unicode Consortium, Reading, Massachusetts, USA, Addison-Wesley Developer's Press, 2007, ISBN 0-321-48091-0, http://www.unicode.org/versions/Unicode5.0.0/

RFC 3986, Uniform Resource Identifiers (URI): Generic Syntax, Internet Standards Track Specification, January 2005, http://www.ietf.org/rfc/rfc3986.txt

XML-C14N, Canonical XML, Version 1.0, World Wide Web Consortium, 15th March 2001, http://www.w3.org/TR/2001/REC-xml-c14n-20010315

XML Infoset, XML Information Set (Second Edition), World Wide Web Consortium, 4 February 2004, http://www.w3.org/TR/2004/REC-xml-infoset-20040204

ISO/IEC 13250-2, ISO/IEC 13250-2:2006 Information technology — Topic Maps — Data model

3 Canonicalization

3.1 Introduction

The canonicalization process takes two parameters: a topic map item (that is, an instance of the Topic Maps Data Model [ISO/IEC 13250-2]) and a base locator. The process produces a canonicalization of the topic map, with all locators in the topic map rewritten to be relative to the given base locator.

Canonicalization is performed in three steps:

  1. A document information item representing the CXTM document is produced from the topic map item as described in 3.3.

  2. For each element information item that is a descendant of the document information item from the previous step, the following operations are performed:

  3. The document information item is serialized to a Canonical XML representation as described in [XML-C14N].

3.2 Notational conventions

Information item properties from [W3C XML-Infoset] are referred to using [[property name]], in order to distinguish them from properties from [ISO/IEC 13250-2].

3.3 CXTM Document Information Item

There is exactly one CXTM document information item in the XML Infoset generated by the canonicalization of the topic map item.

The CXTM document information item has the following properties:

  1. [[children]] A list containing only the representation of the topic map item

  2. [[document element]] The element information item that represents the topic map item

  3. [[notations]] The empty set

  4. [[unparsed entities]] The empty set

  5. [[base URI]] No value

  6. [[standalone]] No value

  7. [[version]] No value

  8. [[all declarations processed]] False

3.4 Constructing a representation of a topic map item

A topic map item is represented by an element information item with the following properties:

  1. [[local name]] The string "topicMap"

  2. [[children]] A list of element information items in the following order:

    1. A representation of the [item identifiers] property, if any

    2. A representation of each topic item in the [topics] property of the topic map item in canonical sort order

    3. A representation of each association item in the [associations] property of the topic map item in canonical sort order

  3. [[attributes]] A representation of the [reifier] property

3.5 Constructing a representation of a topic item

A topic item is represented by an element information item with the following properties:

  1. [[local name]] The string "topic"

  2. [[children]] A list of element information items in the following order:

    1. If the value of [subject identifiers] property of the topic item is not the empty set, then an element information item with the following properties:

      1. [[local name]] The string "subjectIdentifiers"

      2. [[children]] A representation of each locator in the [subject identifiers] property in canonical sort order

      3. [[attributes]] The empty set

    2. If the value of the [subject locators] property of the topic item is not the empty set, then an element information item with the following properties:

      1. [[local name]] The string "subjectLocators"

      2. [[children]] A representation of each locator in the [subject locators] property in canonical sort order

      3. [[attributes]] The empty set

    3. A representation of the [item identifiers] property, if any

    4. A representation of each of the topic name items of the [topic names] property in canonical sort order

    5. A representation of each of the occurrence items of the [occurrences] property in canonical sort order

    6. For each of the association role items of the [roles played] property in canonical sort order, an element information item with the following properties

      1. [[local name]] set to the string "rolePlayed"

      2. [[children]] An empty list

      3. [[attributes]] A set containing one attribute information item as follows:

        1. [[local name]] set to the string "ref"

        2. [[normalized value]] A sequence of character information items representing a string value constructed by the concatenation of:

          1. The string "association."

          2. The position of the association item which is the value of the [parent] property of the association role item, in the canonically sorted [associations] property of the parent topic map item

          3. The string ".role."

          4. The position of the reified association role item in the canonically sorted [roles] property of the parent association item

  3. [[attributes]] The union of:

3.6 Constructing a representation of the topic name item

Each topic name item is represented by an element information item with the following properties:

  1. [[local name]] The string "topicName"

  2. [[children]] A list of element information items in the following order:

    1. A representation of the [value] property

    2. A representation of the [type] property

    3. A representation of the [scope] property

    4. A representation of each of the variant items in the [variants] property in canonical sort order

    5. A representation of the [item identifiers] property, if any

  3. [[attributes]] The union of:

3.7 Constructing a representation of a variant item

A variant item is represented by an element information item with the following properties:

  1. [[local name]] The string "variant"

  2. [[children]] A list of element information items in the following order:

    1. A representation of the [value] property

    2. A representation of the [datatype] property

    3. A representation of the [scope] property

    4. A representation of the [item identifiers] property, if any

  3. [[attributes]] The union of:

3.8 Constructing a representation of an occurrence item

An occurrence item is represented by an element information item with the following properties:

  1. [[local name]] The string "occurrence"

  2. [[children]] A list of element information items in the following order:

    1. A representation of the [value] property

    2. A representation of the the [datatype] property

    3. A representation of the [type] property

    4. A representation of the [scope] property

    5. A representation of the [item identifiers] property, if any

  3. [[attributes]] The union of:

3.9 Constructing a representation of an association item

An association item is represented by an element information item with the following properties:

  1. [[local name]] The string "association"

  2. [[children]] A list of element information items in the following order:

    1. A representation of the [type] property

    2. A representation of each of the items of the [roles] property in canonical sort order

    3. A representation of the [scope] property

    4. A representation of the [item identifiers] property, if any

  3. [[attributes]] The union of:

3.10 Constructing a representation of the association role item

An association role item is represented by an element information item with the following properties:

  1. [[local name]] The string "role"

  2. [[children]] A list of element information items in the following order:

    1. An element information item with the following properties:

      1. [[local name]] The string "player"

      2. [[children]] The empty list

      3. [[attributes]] A set of one attribute information item with the following properties:

        1. [[local name]] The string "topicref"

        2. [[normalized value]] The position of the topic item in the [player] property within the canonically sorted [topics] property of the parent topic map item

    2. A representation of the [type] property

    3. A representation of the [item identifiers] property, if any

  3. [[attributes]] The union of:

3.11 Constructing a representation of the [reifier] property

If the [reifier] property of an information item is null it is represented by the empty set. Otherwise it is represented as a set containing an attribute information item with the following properties:

  1. [[local name]] The string "reifier"

  2. [[normalized value]] The position of the topic item that is the value of the [reifier] property in the canonically sorted list of all topic items

3.12 Constructing a representation of the [reified] property

The [reified] property of a topic item is represented as an attribute information item with the following properties:

  1. [[local name]] The string "reified"

  2. [[normalized value]] A sequence of character information items representing a string value constructed as follows:

3.13 Constructing a representation of the [scope] property

If the [scope] property of an information item is the empty set, then it has no representation. Otherwise it is represented by an element information item with the following properties:

  1. [[local name]] The string "scope"

  2. [[children]] A list of one element information item for each topic item in the value of the [scope] property in canonical sort order. Each element information item has the following properties:

    1. [[local name]] The string "scopingTopic"

    2. [[children]] An empty list

    3. [[attributes]] A list containing a single attribute information item with the following properties:

      1. [[local name]] The string "topicref"

      2. [[normalized value]] The position of the topic item within the canonically sorted list of all topic items in the topic map item being canonicalized

  3. [[attributes]] The empty set

3.14 Constructing a representation of the [item identifiers] property

If the [item identifiers] property of an information item is empty it has no representation. Otherwise it is represented by an element information item with the following properties:

  1. [[local name]] The string "itemIdentifiers"

  2. [[children]] A representation of each locator in the [item identifiers] property in canonical sort order

  3. [[attributes]] The empty set

3.15 Constructing a representation of the [datatype] property

The [datatype] property of an information item is represented by an element information item with the following properties:

  1. [[local name]] The string "datatype"

  2. [[children]] A sequence of character information items representing the string value of the normalized locator in the [datatype] property

  3. [[attributes]] The empty set

3.16 Constructing a representation of the [type] property

The [type] property of an information item is represented by an element information item with the following properties:

  1. [[local name]] The string "type"

  2. [[children]] An empty list

  3. [[attributes]] A set containing an attribute information item with the following properties:

    1. [[local name]] The string "topicref"

    2. [[normalized value]] The position of the topic item that is the value of the [type] property within the canonically sorted list of all topic items in the Topic Maps Data Model being encoded.

3.17 Constructing a representation of the [value] property

A [value] property of an information item is represented by an element information item with the following properties:

  1. [[local name]] The string "value"

  2. [[children]] A sequence of character information items representing the string value of the [value] property. If the information item has the property [datatype] set to "http://www.w3.org/2001/XMLSchema#anyURI" the value is a locator, and must be normalized accordingly.

  3. [[attributes]] The empty set

3.18 Constructing a representation of locator values

Locator values are represented by an element information item with the following properties:

  1. [[local name]] The string "locator"

  2. [[children]] A sequence of character information items representing the normalized string value of the locator

  3. [[attributes]] The empty set

3.19 Normalizing locator values

Locator values are normalized into strings using the process described below. This description uses the terms "fragment identifier", "query" and "path segment" as defined in [RFC 3986].

  1. Let the value P be the string value of the base locator with any fragment identifier and query removed and any trailing "/" character removed.

  2. If the string value of the locator starts with P, then the representation of the locator is the substring starting from, and including, the character immediately following the string that matches P, with any leading "/" character removed.

  3. If the string value of the locator does not start with P and P can be interpreted as a URI with at least one path segment, then remove the last path segment from P and any trailing "/" character and repeat from step (2).

  4. If the string value of the locator is not modified by the steps above, then the string value of the locator is the representation of the locator.

NOTE:

This process may result in a string value which is no longer a syntactically valid or resolvable IRI. This is by design, as this part of ISO/IEC13250 does not require a conforming implementation to dereference these addresses.

The resulting string must be normalized according to Unicode Normalization Form C.

3.20 Constructing the number attribute

The number attribute of an information item is an attribute information item with the following properties:

3.21 Encoding of string properties

Before encoding a string property as a sequence of character information items, the string must be normalised according to Unicode Normalization Form C (Unicode Standard Annex #15, Unicode Normalization Forms, [Unicode]). Each character information item must have the following properties:

  1. [[character code]] The ISO 10646 ([ISO/IEC 10646-1] and [ISO/IEC 10646-2]) character code for the character.

  2. [[element content whitespace]] False.

  3. [[parent]] The containing element or attribute information item.

3.22 Encoding of positional values

When the position of an item in a list is to be encoded, the encoded value is the index of that item in the list counting from 1 as the index of the first list item.

3.23 Default property values for element information items

All element information items created by the canonicalization process must have the following property values:

  1. [[namespace name]] No value

  2. [[prefix]] No value

  3. [[namespace attributes]] The empty set

  4. [[in-scope namespaces]] The empty set

  5. [[base URI]] No value

  6. [[parent]] The element information item or document information item of which the element is a direct child

3.24 Default property values for attribute information items

All attribute information items created by the canonicalization process must have the following property values:

  1. [[namespace name]] No value

  2. [[prefix]] No value

  3. [[attribute type]] Unknown

  4. [[references]] Unknown

  5. [[specified]] True

  6. [[owner element]] The element information item that this attribute information item belongs to

4 Canonical Sort Order

4.1 Introduction

When transforming an instance of the Topic Maps Data Model to an instance of the XML Infoset model, all properties in the Topic Maps Data Model which are sets of information items must be encoded in the XML Infoset model by encoding each set element in the canonical sort order for the set. The clauses 4.2 to 4.11 define the canonical sort order for each information item type.

4.2 Information Type and Basic Type Sort Order

The following sort order applies to all information items and all values of the types defined by the Topic Maps Data Model.

  1. Null

  2. string

  3. set

  4. locator

  5. topic map

  6. topic

  7. topic name

  8. variant

  9. occurrence

  10. association

  11. association role

4.3 Comparison of Strings

String values are compared on a character by character basis from the start of the string to the end. The comparison is performed on strings normalized to Unicode Normalization Form C. When the first pair of characters with different character codes are found, then the string containing the character with the lower code sorts lower than the string containing the character with the higher code. If all pairs compare equal, but one string is shorter than the other, the shortest string sorts lower than the longest string. If no differences are found the two strings are considered equal.

4.4 Comparison of Sets

  1. Sets sort in order of the number of elements in the collection. A set with fewer elements sorts lower than a set with more elements.

  2. For sets of equal size, first sort the elements of each set into their canonical ordering. Starting with the lowest element in each sorted set, perform a pair-wise comparison of element in each collection until a non-equal comparison is found. The collections then sort in the order of the two non-equal elements.

  3. Sets with exactly the same elements will be considered equal.

4.5 Comparison Order for Locators

Locators are compared in the same way as strings (see 4.3).

4.6 Canonical Sort Order for Topic Items

Topic items are compared by comparing their properties in the following order.

  1. [subject identifiers]

  2. [subject locators]

  3. [item identifiers]

NOTE:

A combination of these three properties are all that is required to compare two topics. Part 2 of this standard requires that all topic items have at least one value for one of these properties and should two topics match in any one of these three properties, they must be merged.

4.7 Canonical Sort Order for Topic Name Items

Topic name items are compared by comparing their properties in the following order.

  1. [value]

  2. [type]

  3. [scope]

  4. [parent]

4.8 Canonical Sort Order for Variant Items

Variant items are compared by comparing their properties in the following order.

  1. [value]

  2. [datatype]

  3. [scope]

  4. [parent]

4.9 Canonical Sort Order for Occurrence Items

Occurrence items are compared by comparing their properties in the following order.

  1. [value]

  2. [datatype]

  3. [type]

  4. [scope]

  5. [parent]

4.10 Canonical Sort Order for Association Items

Association items are compared by comparing their properties in the following order.

  1. [type]

  2. [roles]

  3. [scope]

  4. [parent]

4.11 Canonical Sort Order for Association Role Items

Association role items are compared by comparing their properties in the following order.

  1. [player]

  2. [type]

  3. [parent]

A RELAX-NG Schema for CXTM (informative)

topicMap = element topicMap {
  attribute reifier { xsd:integer }?, itemIdentifiers?, topic*, association*
}

attlist.reifier =
  attribute reifier { xsd:integer }?,
  attribute number { xsd:integer }

topic = element topic {
  attribute reified { reified.ref }?,
  attribute number { xsd:integer },
  subjectIdentifiers?, 
  subjectLocators?, 
  itemIdentifiers?, 
  topicName*, 
  occurrence*, 
  rolePlayed*
}

reified.ref = 
  xsd:token { pattern = "topicMap" } |
  xsd:token { pattern = "topic.[1-9][0-9]*.name.[1-9][0-9]*" } |
  xsd:token { pattern = "topic.[1-9][0-9]*.name.[1-9][0-9]*.variant.[1-9][0-9]*" } |
  xsd:token { pattern = "topic.[1-9][0-9]*.occurrence.[1-9][0-9]*" } |
  xsd:token { pattern = "association.[1-9][0-9]*" } |
  role.ref

role.ref = xsd:token { pattern = "association.[1-9][0-9]*.role.[1-9][0-9]*" }

subjectIdentifiers = element subjectIdentifiers {
  locator+
}

subjectLocators = element subjectLocators {
  locator+
}

itemIdentifiers = element itemIdentifiers {
  locator+
}

topicName = element topicName {
  attlist.reifier, value, type, scope?, variant*, itemIdentifiers?
}

variant = element variant {
  attlist.reifier, value, datatype, scope, itemIdentifiers?
}

occurrence = element occurrence {
  attlist.reifier, value, datatype, type, scope?, itemIdentifiers?
}

rolePlayed = element rolePlayed {
  attribute ref { role.ref }
}

association = element association {
  attlist.reifier, type?, role*, scope?, itemIdentifiers?
}

role = element role {
  attlist.reifier, player?, type?, itemIdentifiers?
}

attlist.topicref = attribute topicref {xsd:integer}

player   = element player { attlist.topicref }
type     = element type { attlist.topicref }
value    = element value { text }
locator  = element locator { text }
scope    = element scope { scopingTopic+ }
datatype = element datatype { xsd:anyURI }

scopingTopic = element scopingTopic { attlist.topicref }

start = topicMap

Bibliography

ISO/IEC 13250-3, ISO/IEC 13250-3: Information technology — Document Description and Processing Languages — Topic Maps — XML Syntax , ISO, 2007