# TMQL (Topic Map Query Language)

Ann Wrightson, Ontopia, BSI (<annw@ontopia.net>)

7 Nov 2000 (corrected 28 Nov 2000)

## Abstract

This is a (corrected) second preliminary draft of TMQL, a query language
for Topic Maps.

## Scope

A preliminary draft for discussion; intended as a substantive discussion
paper to table alongside a NWI proposal for ISO/IEC JTC1 SC34 at
Washington, December 2000.

All of it is provisional -- the parts in italics are more "straw-man"
than others, and are just intended to indicate that something of that
kind is needed.

## Introduction

The Topic Maps standard - "ISO 13250" below in this draft - describes an
interchange syntax for Topic Maps, intended to facilitate accurate
exchange of information between applications conforming to that
standard. However, many foreseen practical uses of Topic Maps will
require operations to be performed on Topic Maps. TMQL fulfils a known
industry requirement, for a standardized language for specifying these
operations on Topic Maps.

The TM concerned will not necessarily, or usually, be manipulated in the
ISO 13250 interchange syntax for this purpose -- but the functionality
of TMQL must nevertheless be appropriately related to ISO 13250.

The initial suggestion made here, is to describe the requisite
repertoire of Topic Map operations - TMQL - in a way which is not
inherently bound to a specific interchange syntax, and also to provide a
specific and detailed way of relating that functionality to the syntax
in ISO 13250, by way of a semi-formal data model and associated
operations.

(Another possibility is to provide detailed conformance specifications
grounded in TM interchange syntax, including a normative specification
for ISO 13250, and an informative specification for XTM 1.0. These
detailed conformance specifications could be written as if for each TMQL
operation, a TM in a specific interchange syntax is read by a TMQL
processor, processed, then output again in that syntax. It will not be
necessary for a conforming TMQL processor to actually do this, but what
it does must be equivalent.

> *This approach is motivated by wanting to ensure that conformance to
> TMQL is properly co-ordinated with the current medium of Topic Map
> standardization, whilst also respecting the realities of practical TM
> application development.*
>
> *However, it is probably more realistic in line with actual emerging
> uses of Topic Maps to ground everything in a semi-formal data model,
> whose development can be expected to give rise to corrigenda for
> 13250.)*

## Conformance

*Suggestion:*

> *Detailed conformance specifications are provided in Appendix B
> (normative) for topic maps derived from ISO 13250, and Appendix C
> (informative) for XTM 1.0. Further informative conformance
> specifications may be added in due course, as & if TM are formally
> adopted in other domains which publish their own distinctive
> interchange syntax.*

(Both to follow once the data model and transaction model are stable.)

Question: It is desirable to integrate XTM like this, but is it
possible?

## Acknowledgements

The conceptual model of Topic Maps underlying TMQL owes much to the
abstract modelling of the concepts underlying ISO 13250 undertaken by
the XTM activity (these models are available at time of writing via
http://www.doctypes.org/xtm/home.html); the query syntax uses, for
embedded Topic Map descriptions, the LTM notation developed by Ontopia
AS (available at the time of writing on
[http://www.ontopia.net](http://www.ontopia.net/)).

## Approach

TMQL has two complementary aspects:

-   The TMQL language

-   The TMQL evaluation specification

The exposition below first gives an introduction to TMQL and TMQL
evaluation, then presents the full TMQL language, then gives a detailed
account of TMQL evaluation.

There are inevitably large gaps, and a number of issues outstanding at
this stage -- some issues are noted in this document. This document is
intended as a basis for further discussion, not as a finished work in
any sense or part.

## Introducing TMQL and TMQL Evaluation

TMQL is a transactional language, similar in principle to SQL (ISO
ref?). Each statement of TMQL is evaluated as a separate transaction on
a specified TM. Bearing in mind probable future requirements in large
TM-based systems, there is a requirement for a well-described concept of
"undo" or "rollback" for TMQL transactions, including partially
completed transactions.

In brief, the "rollback" yields a result equivalent to the state of the
TM before the transaction started, where the "state of the TM" is
equivalent to what would be written in the interchange syntax to
represent the TM.

### TMQL transactions

TMQL has three basic transactions:

-   Add

-   Remove

-   Select

Each TMQL transaction starts and ends with one or more topic maps (this
is why conformance can be specified in terms of pre- and post-conditions
on topic maps in ISO 13250 syntax).

Note: There may be other transactions. However, TMQL should refrain from
trying to do things which are not to do with providing basic access
operations to a TM. These belong in different documents, e.g. a
technical report on modelling (specific kinds of) inferential
relationships with Topic Maps.

A sequence of TMQL transactions can be represented as a sequence of
statements in the TMQL syntax given below. Alternatively, a collection
of TMQL transactions can be organized for more flexible use using a
Topic Map.

Each transaction performs an operation on an input TM (called the
source-topic-map or S-TM), and yields an output or result TM (called the
result-topic-map or R-TM). In the case of Add and Remove, the output TM
can be thought of as an amended form of the input TM; in the case of
Select, the output TM is better regarded as a constructed selective view
of the input TM (and this view is of course itself a TM).

TM application builders are free to make their own choices regarding all
aspects of their implementation of TMQL operations on their own internal
TM representations (e.g. whether the Selected TM is actually a separate
TM, or a scoped portion of an amended version of the original TM). The
conformance criteria imposed by this standard will ensure that the end
result of applying the same sequence of TMQL transactions to the same
Topic Map in different conforming Topic Map applications will be
functionally equivalent with respect to the changes made in the Topic
Map concerned.

These basic TMQL transactions use a number of component operations,
including

-   Constructing the Topic Map(s) whose description(s) are embedded in
    the TMQL statement (called the Q-TM, short for query-topic-map,
    below; where there are several in one TMQL transaction, they are
    called Q-TM1, Q-TM2 etc)

-   Matching a Q-TM against the S-TM, and ranking candidate matches
    where there is more than one matching fragment.

-   Constructing the R-TM

These component operations have parameters, in order to allow concise
and helpfully similar TMQL syntax to be used for closely related
operations.

There follows an outline of TMQL evaluation for these transactions and
component operations.

> General issue: Do TMQL transactions have scope, i.e. can they be
> restricted to take effect within a specified scope within the S-TM? --
> I say yes, but it needs debate. If yes, then there is a preliminary
> filter of the S-TM with respect to the transaction scope before
> anything else in the transaction takes place; and the effect of the
> transaction-within-scope on the TM as it appears in the
> default/universal scope needs careful description, e.g. removal of a
> TM component by a scoped-transaction is likely (only) a removal of
> that scope from the node in question.
>
> General issue: Integrity constraints on TM need describing (we need
> something which plays an analogous role to referential integrity in
> relational databases, e.g. to help judge between alternatives for the
> issue just above)

### Add

The Add transaction applies a single Q-TM to the S-TM. The Q-TM and S-TM
are merged to yield the R-TM.

Issue: Parameters to this merging need definition. Default is 13250
merge. *(Note: there is consensus amongst TM tool developers that this
merge concept needs more precision -- this is one of the matters
referred to above in the notes regarding the semi-formal model and
conformance.)*

### Remove

The Remove transaction applies a single Q-TM to the S-TM. The Q-TM is
matched against the S-TM; the highest ranking matched fragment of the
S-TM is removed to yield the R-TM.

Issue: Removal semantics need detailed specification, including
integrity constraints.

### Query

The basic Query transaction applies a single Q-TM to the S-TM. The Q-TM
is matched against the S-TM; some selected (how?) matched fragment of
the S-TM is replicated as the R-TM.

Other options available:

-   All the matching fragments are constructed into a single R-TM in
    some appropriate way

-   Parameters to the query (which could be pretty complex, e.g. logical
    expressions, or a TM specifying the behaviour) control the process
    according to which S-TM fragments matching the Q-TM are included in
    the R-TM

-   The R-TM is articulated with the S-TM in some standardized way, e.g.
    by means of a structure-respecting set of associations (which are
    possibly scoped by the topic representing this query, if the query
    was launched from a TM, and ) which are scoped by various public
    subjects denoting the kind of relationships which the R-TM
    components have to the S-TM components.

The query evaluation process needs careful definition, but will probably
be something like (for a basic query):

-   Build Q-TM

-   Match Q-TM to S-TM, and select best match

-   Construct R-TM by naming, scoping and "role"-ing its components
    appropriately and populating Q-TM occurrences from relevant S-TM
    occurrences.

There are a number of possible ways of usefully extending the simple
query, including:

-   Query gives several Q-TMs which are combined (by standard merge, or
    TMQL extended merging semantics) into a single Q-TM, then used as
    above.

### Parameters on merging, matching, and construction of R-TMs

These may be simple values, or TMs. Their nature and significance needs
careful analysis and specification. For example,:

-   May specify transitive closure on associations which have designated
    scope(s)

-   May specify transitive closure on
    occurrence-which-is-topic-which-has-occurrence-which-is-topic....
    (within a designated scope)

## TMQL Language

### Describing transactions

The general form of a transaction is the name of the transaction,
followed by a sufficient identification of the S-TM, and either a
similar identification for the Q-TM, e.g. a suitable identification
(what?) of a file containing the Q-TM in 13250 syntax, or a
specification of the Q-TM in the TMQL embedded notation (see below).

Issue: Can any of S-TM, Q-TM be in TMQL embedded notation, or only Q-TM?
Suggest any, but deprecate large ones. "S-TM" below is intended to
indicate any suitable way (repertoire to be defined) of naming or
identifying the Tm involved.

Examples:

ADD { (Q-TM) } TO { (S-TM) }

REMOVE {(Q-TM) } FROM { (S-TM) }

SELECT { (Q-TM) } IN { (S-TM) }

More complex examples (Note: these examples distinguish different
source, query and result TMs using numerical suffixes -- these suffixes
have no other intended meaning):

ADD { SELECT { (Q-TM) } IN { (S-TM1) } } TO { (S-TM2) }

REMOVE { (Q-TM1) } FROM { ADD { (Q-TM2) } TO { (S-TM) } }

The centre connective (TO, FROM, IN) is provided to enable easier
writing and reading of queries. For example, if there is an explicit TO
in the middle, then errors of braces matching will be easier to debug.

### Describing topic maps (usually Q-TM) in TMQL embedded notation

The TMQL embedded notation allows a topic map (using a useful working
subset of the full ISO 13250 concept) to be embedded in a TMQL query. If
there is a requirement in a TMQL Q-TM for topic map features that are
not reflected in the TMQL embedded notation, then that topic map can be
provided to the TMQL transaction as a separate TM.

TMQL embedded notation has the following limitations compared to the ISO
13250 interchange syntax:

-   Limited expressive power

-   No Facets.

-   No mnemonic string alternatives to types on various constructs.

-   No scoping on individual base names, sort names and display names.

-   No display names that are not strings.

-   No scoping of associations, occurrences and topics.

-   No added themes.

-   No multiple identities, or any identities other than very simple
    names.

The basis of the notation is the ability to describe topics, which is
done by writing what would be the SGML ID of the topic in the ISO 13250
interchange syntax, in square brackets. For example:

\[ltm\]

This represents a topic map consisting of a single topic that has the
SGML ID \'ltm\', but no other topic characteristics. If you want, you
can provide it with a base name and a sort name as well, as in the
example below. Note that the sort name is optional.

\[ltm = \"The linear topic map notation\";

\"linear topic map notation, the\"\]

You can also add a display name. If you have a display name the sort
name is optional, but you need two semicolons to tell the parser that
the second name is a display name and not a sort name. The example below
shows a topic with all three name types.

\[foo = \"basename\"; \"sortname\"; \"misname\"\]

The topic can also be typed, if so desired. The example below adds the
type \'format\' to the ltm topic. Multiple type IDs can be listed after
the colon if the topic has more than just one type.

\[ltm : format = \"The linear topic map notation\";

\"linear topic map notation, the\"\]

Note that even if no topic with the ID \'format\' is described anywhere
in the Embedded Q-TM this reference will cause the topic to be created
by the TMQL processor. The \'format\' topic will have an ID, but no
other characteristics. Note also that in TMQL you can add as much white
space as you want anywhere except inside strings without having any
effect on the resulting topic map.

TMQL also supports providing subject identifiers for topics, as shown
below. The subject identifier is quoted and preceded by an \'@\'
character.

\[ltm : format = \"The linear topic map notation\";

\"linear topic map notation, the\"

@\"http://www.ontopia.net/topicmaps/ltm-tech-report.html\"\]

The final construct supported by TMQL for topics is scoping of names.
This can be done for the basename, sortname, dispname-trinity as a
whole, by putting a topic ID preceded by a slash after the initial \'=\'
character, as shown below. Multiple topic IDs are allowed.

\[ltm : format = / norwegian

\"Den lineære topic map-notasjonen\";

\"lineær topic map-notasjon, den\"

@\"http://www.ontopia.net/topicmaps/ltm-tech-report.html\"\]

Note that if this example and the one above it were to appear in the
same Embedded Q-TM it would cause a single topic to be created with the
union of the characteristics of these two definitions. That means that
the topic would have the \'ltm\' ID, the format type, the two different
name sets and the given subject identifier.

Note also that there are no requirements on the order in which
constructs appear in the TQML embedded topic map description. A topic
type can be used before it is described, for example.

Describing associations

The TMQL notation also supports describing associations, which can be
done using the notation shown below. In the example below the ltm topic
described above is associated with a topic with the ID \'topic maps\' by
an association that has the format-for type. (\'format-for\' is of
course the ID of the topic that types that association.)

format-for(\[ltm\], \[topic-maps\])

Note the use of square brackets around the IDs. All the constructs used
when describing topics can be used here, which means that it is possible
to describe topics with their characteristics in the associations they
participate in without describing them anywhere else. The example could
therefore also have been written as below.

format-for(\[ltm\], \[topic-maps : standard = \"Topic maps\"\])

The meaning of this example is that TMQL is a serialization format for
topic maps. This should perhaps be made clearer by adding association
role types. The example below does this.

format-for(\[ltm\] : format, \[topic-maps\] : standard)

Describing occurrences

TMQL also supports describing occurrences. This is done using the
notation shown below, where the occurrence information is given in curly
braces. Three pieces of information, all of which are required, appear
inside the braces, separated by commas. The first is the ID of the topic
which has the occurrence, the second is the ID of the occurrence role
type and the third is the locator of the occurrence in double quotes.

{ltm, specification,
\"http://www.ontopia.net/topicmaps/ltm-tech-report.html\"}

A complete example

Below is given a more complete example of a topic map in TMQL embedded
notation. Note that text appearing between \'/\*\' and \'\*/\' is
comments.

/\* topic types \*/

\[format = \"Format\"\]

\[standard = \"Standard\"\]

\[organization = \"Organization\"\]

/\* association types \*/

\[format-for = \"Format for\"\]

\[described-by = \"Described by\"\]

/\* occurrence types \*/

\[specification = \"Specification\"\]

\[homepage = \"Home page\"\]

/\* topics, associations and occurrences \*/

\[topic-maps : standard = \"Topic maps\"

= / fullname \"ISO/IEC 13250 Topic Maps\"\]

{topic-maps, specification,

\"http://www.y12.doe.gov/sgml/sc34/document/0129.pdf\"}

\[xtm : format = \"XTM Syntax\"\]

\[ltm : format = \"The linear topic map notation\";

\"linear topic map notation, the\"

@\"http://www.ontopia.net/topicmaps/ltm-tech-report.html\"\]

{ltm, specification,
\"http://www.ontopia.net/topicmaps/ltm-tech-report.html\"}

format-for(\[ltm\], \[topic-maps\])

format-for(\[xtm\], \[topic-maps\])

described-by(\[ltm\], \[ontopia\])

described-by(\[xtm\], \[xtm-wg\])

\[ontopia : organization = \"Ontopia AS\"\]

{ontopia, homepage, \"http://www.ontopia.net\"}

\[xtm-wg : organization = \"XTM Working Group\"\]

{xtm-wg, homepage, \"http://www.egroups.com/group/xtm-wg\"}

Formal syntax definition

This section describes the syntax of the TMQL embedded notation using a
formal extended BNF grammar. Lexical tokens are given either as
single-quoted strings directly in the grammar, or as upper-case names of
token types. The token types are described separately further below.

topic-map ::= encoding? (topic \| assoc \| occur) +

encoding ::= \'@\' STRING

topic ::= \'\[\' NAME (WS \':\' NAME+)? (topname)\* psi? \'\]\'

psi ::= \'@\' STRING

topname ::= \'=\' scope? basename ((\';\' sortname) \|

(\';\' sortname? \';\' dispname))?

scope ::= \'/\' NAME+

basename ::= STRING

sortname ::= STRING

dispname ::= STRING

assoc ::= NAME \'(\' assoc-role (\',\' assoc-role)\* \')\'

assoc-role ::= topic (\':\' NAME )?

occur ::= \'{\' occ-topic \',\' occ-type \',\' STRING \'}\'

occ-topic ::= NAME

occ-type ::= NAME

The lexical token types described below use perl-style regular
expressions for their definitions. Note that while white space
(represented by the WS token type) is implicitly allowed between any two
tokens, it is explicitly required in the \'topic\' production in the
above grammar. This is to avoid problems caused by the fact that a colon
is allowed in topic IDs.

NAME = \[A-Za-z\_\]\[-A-Za-z_0-9.:\]\*

COMMENT = /\\\*(\[\^\*\]\|\\\*\[\^/\])\*\\\*/

STRING = \"\[\^\"\]\*\"

WS = \[\\r\\n\\t \]+

The NAME token type is slightly modified compared to the definition in
the XML recommendation. The colon is no longer allowed as a name start
character, since otherwise a single colon could be both a name and a
separator.

All tokens are case-sensitive.

Character encoding handling

All Embedded TMQL topic maps are to be processed as if they were
composed of Unicode characters. Files may be in any encoding, but if
that encoding is not ISO 8859-1 it should be declared using the encoding
production. If the encoding declaration appears in the file it must
appear at the very beginning.

Processing and references

Any topic referred to by its ID in an Embedded TQML topic map is
considered to exist, even if it is never described anywhere by an
explicit occurrence of the topic production with that topic. All
occurrences of the same topic ID are considered to be references to the
same topic.

Further detailed issues will no doubt be identified and require
resolution.

## Full definition of TMQL transaction processing (construction, matching and evaluation)

To follow

# (Possible) Appendices:

# Appendix A (normative): Topic Maps Data Model 

# Appendix B (normative): Conformance specification for TMQL transactions

# Appendix C (not normative) : Conformance specification for TMQL transactions, for Topic Maps expressed in XTM 1.0 interchange syntax

## End of draft.