ISO/IEC JTC1/SC34

ISO/IEC JTC1/SC34

Information Technology —

Document Description and Processing Languages

Topic Maps Query Language

Contents

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 18048 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information Technology, Subcommittee SC 34, Document Description and Processing Languages.

Introduction

This International Standard defines a query language for Topic Maps known as TMQL (Topic Maps Query Language). This draft was informed by TMQLuc[2] and TMQLreq[1] and is for review for interested parties.

Topic Maps Query Language

1 Scope

This International Standard defines a formal language by providing a syntax to form query expressions. The document also defines an informal and a formal semantics for every syntactic form, including rules for the reporting of error conditions.

To constrain the interaction with query processors, this International Standard also describes an abstract processing environment. In this part the passing of parameters into the query process and the exchange of result values is loosely defined. This environment also includes predefined functions and predicates every conformant processor must provide.

This International Standard does not define an API (application programming interface) nor does it define an extension mechanism for extending the predefined environment can be while, but it does provide means for importing external ontologies and functionality. This International Standard also remains silent on potential optimization techniques, leaving these for implementors and researchers to define.

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.

Unicode, The Unicode Standard, Version 3.0, The Unicode Consortium, Reading, Massachusetts, USA, Addison-Wesley Developer's Press, 2000, ISBN 0-201-61633-5

TMDM, ISO 13250-2 Topic Maps — Data Model, ISO, 2005, http://www.isotopicmaps.org/sam/sam-model/

XML 1.0, Extensible Markup Language (XML) 1.0, W3C, Third Edition, W3C Recommendation, 04 February 2004, http://www.w3.org/TR/REC-xml/

RFC2396, RFC 2396 - Uniform Resource Identifiers (URI): Generic Syntax, The Internet Society, 1998, http://www.ietf.org/rfc/rfc2396.txt

3 Notation and Conventions

3.1 Notation and Syntax

The syntax of TMQL is defined using the EBNF formalism defined in [XML 1.0].

Additional convenience notations to extend the (minimal) grammar core are introduced via term equivalences. Variable parts in these terms are symbolized by variables which are implicitely all-quantified. These equations may be supported by additional prose.

For productions yet to be done the following pseudo nonterminal is used.

3.2 Informal and Formal Semantics

The semantics of TMQL are fully defined in prose. As this may result in ambiguities, the prose is supported by several layers of formal and semi-formal mappings. SELECT expressions are completely mapped into FLWR expressions (Annex A). In Annex C TMQL FLWR expressions are mapped to TMQL path expressions (excluding the content constructor in RETURN clauses). TMQL path expressions are mapped to τ path expressions (Annex D). The latter is then mathematically formalized in Annex E. Annex F describes the relationship between the Τ model and TMDM.

4 Query Environment

Every implementation has to provide a query environment which allows applications to interact with the query processor.

TMQL query expressions are executed in an environment that contains information used by the query processor. When executing begins the environment may be empty, or it may contain initial values set by means outside the scope of this International Standard. The query environment provides the following input:

Base URI (optional)

An optional URI against which relative URIs in the query are resolved, if provided.

Variable bindings

A set of variable bindings, each of these being a name/value pair. A mechanism must exist to associate values to variables (or parameters) inside the compiled query. One such can be the default topic map which—if it is defined—must be a topic map item as defined in [TMDM]. The set is empty by default.

Prefix bindings

A set of (prefix, type, uri) tuples. The prefix is a string matching the 'ident' production, and it is an error if there are duplicate prefixes. The type is one of the strings 'indicator', 'source', 'subject', or 'module'. The uri is an absolute URI. The set is empty by default.

Ed. Note:

drrho: Not exactly sure, what it does, but I assume this includes all not-predefined functions, predicates, ontologies.....?.

larsbot: No, it's the prefixes used in foo:bar qnames, and only that.

Predicate bindings

A set of (name, predicate) tuples. The name is a string matching the 'ident' production, and it is an error if there are duplicate names. The set initially contains the predicates defined in 10.2.

Ed. Note:

rho: If we can merge 'using' and 'rules', so this can be merged too.

larsbot: They serve different syntactical functions, so that seems difficult.

Ed. Note:

rho: I also have concerns in hardcoding _tolog_ rules. What if TMCL can be used here? Or maybe we find a way to include OWL ontologies?

larsbot: Now that it's just "predicates" that should be possible, since in the environment one can find ways to turn TMCL/OWL constructs into TMQL predicates and get them into the initial environment. How does that sound?

This context must be provided by the query infrastructure and the application using it. How the context is generated or managed is outside the scope of this International Standard.

5 Types and Values

5.1 Content

The language supports various types of content; simple content such as numbers and strings or XML content, but also composite content like sequences of (tuples of) values, or Topic Map content.

The constant NULL represents the undefined value. It is typeless per se and is used for situations when no particular value should or can be used.

Additional Notation: As an alternative we also allow undef to be used instead of NULL.

5.2 Booleans

Boolean content consists only of the two constants FALSE and TRUE:

FALSE is equivalent to NULL, but is different from TRUE.

5.3 Numbers

The language supports constants denoting decimal numbers:

The character _ (underscore) can be used to structure longer numbers and is otherwise ignored.

The language does not discern between decimal and integer numbers.

Together with numbers, the unary operator - and the binary operators +, -, * and / are defined as usual, also with the usual precedence. The language also adopts the usual meaning for comparing numbers using =, !=, <, <=, > and >=.

5.4 Strings

Strings are character sequences terminated by ":

Where the following constraints hold:

1. the string value does not contain the terminating quotes,

2. any occurrence of the character " has to be escaped as \", and

3. the string value has every substring matching \u[0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f][0-9A-Fa-f]([0-9A-Fa-f][0-9A-Fa-f])? replaced with the Unicode character whose code point is given in the substring in hexadecimal.

If a string contains substrings terminated with { and }, then these substrings are interpreted as TMQL value expressions (6.5). When strings are evaluated, first all these value expressions are evaluated. The results are then stringified according to the following rules:

1. Number content is converted into is textual representation.

2. String content is used as is.

3. XML content is serialized to a string representation.

4. Topic Map content is serialized into XTM.

5. Tuple sequence content is the concatenation of all tuple content. Tuple content is the concatenation of all serializations of tuple components.

If strings should contain the characters { and } verbatim, they have to be escaped as \{ and \}. For a string to contain the character " it must be escaped as \", and \ itself must be escaped as \\.

Together with strings, a concatenation operator + is defined. Also the comparison operators <, <=, > and >= with the usual meanings are defined.

5.5 Tuples

Tuples are ordered collections of heterogeneous components. The objects inside a tuple are the components and may only be of a simple type. The types of the tuple components can be organized also into a tuple, the tuple profile.

A tuple without a single component is called an empty tuple; it is equivalent with the constant NULL. Tuples with only a single component are called singletons. Any value of simple content can be interpreted as singleton.

The length of the tuple is called the arity of the tuple. The individual components of a tuple are ordered, the first component has assigned the index 0, the next 1, etc. The indices can be used to extract a component from a given tuple. If an index larger or equal the arity of a tuple is used the extraction will result in the value NULL.

When tuples are to be compared with each others, this is always done in the context of a ordering tuple. That tuple can only have components with values ASCENDING or DESCENDING. If that ordering tuple is missing, a tuple containing only ASCENDING is assumed.

Two tuples can then be compared with each other using the following rules:

1. The empty tuple is smaller than any other tuple.

2. The comparison of non-empty tuples is done component-wise by starting with index 0 moving by one to the next higher index at a draw.

   If the order tuple has ASCENDING as value on a given index, that tuple with the smaller component on that index is also the smaller tuple. If the order tuple has DESCENDING as value on a given index, that tuple with the bigger component on that index is the smaller tuple.

3. The components at a given index are compared. If the components at this index are equivalent, then the components with the next higher index are investigated. In the latter case the tuple with the smaller arity is also the smaller tuple.

It is not possible to denote individual tuples.

5.6 Tuple Sequence

Tuple sequences are sequences of tuples where all tuples have identical profiles. They can be denoted as follows:

Tuple sequences can be combined using the infix operator ||. For this, the tuple profiles of both tuple sequences must be identical, otherwise the compilation will fail with an type violation error.

The operator || will combine the two operands by interleaving any tuples into one result tuple sequence. Regardless of any ordering of the two operands, the resulting tuple sequence will be unordered.

The empty tuple sequence is equivalent with NULL. When compared, it is smaller than any other tuple sequence.

When a tuple is evaluated all components of the tuple are evaluated in no predefined order. The evaluation result of components denoting simple content will be interpreted as a sequence of length 1 with a singleton tuple containing this content. The evaluation of components denoted by path expressions may result in general tuple sequences. Only tuple sequences of singletons are valid, the evaluation will terminate with an evaluation exception if any of these sequences contain tuples which are not singletons.

The intermediary result of this tuple evaluation is then a tuple of sequences of singletons. This will be flattened out by building the cartesian product of all singleton sequences. The result sequence will only contain tuples with simple content.

Sequences can be ordered or unordered. If no order direction was provided in any of the tuple components, the result tuple sequence will be unordered. Otherwise the ordering information in the tuple will be used to construct the order tuple as follows:

1. If the order direction on a particular index is defined, this value will be used for the same index in the order tuple.

2. If no order direction was specified on a particular index, the default ASCENDING will be used as value for the same index in the order tuple.

That order tuple will be used for comparison according to 5.5.

5.7 XML Content

XML content follows exactly the syntactic rules given in the XML specification [XML 1.0] with one notable exception: XML content can contain value expressions (6.5) to generate more dynamic output. These subexpressions must be properly nested using a balanced pair of brackets { and } and can only occur in specific places:

• within an element tag,

• within an attribute value or as part of an attribute name,

• as part of element text.

Equivalently, if all occurrences of subexpressions (including the {} bracket pair) are replaced with the empty string, then the XML content must be well-formed.

If the characters { and } are used as-is, they have to be escaped as \{ and \}.

When XML content is evaluated, first all subexpressions are evaluated in no predefined order. The content generated by these subexpressions is then embedded into the XML content, replacing the text of the subquery (including the {} bracket pair) according to the following embedding rules:

• Number content is converted into its string representation.

• String content is used as-is whereby special characters &, ", <, >, ' are automatically encoded to the predefined entities &amp;, &quot;, &lt;, &gt;, &apos;.

• XML content is used as-is.

• Tuple content is stringified by concatenating the textual representation of all tuple components.

• TM content is serialized using XTM.

LET $s := "Portishead"
      LET $x := <some>XML code</some>
      LET $m := <message>{$s} has no idea about {$x}.</message>

5.8 Topic Map Content

The language supports to address whole topic maps or fragments thereof. It is also possible to directly denote topic map content:

Topic Map content can be either referenced or directly denoted. The operator + symbolizes the merge operations as defined in [TMDM]. URIs are defined as strings following the syntax in [RFC2396]. Finally, Topic Map content can also be computed using path expressions.

References can be interpreted as subject identifiers, subject indicators or source locators. For this purpose, it is optionally possible to qualify references with i, s or l:

If a reference is not qualified, it is assumed that the reference is a subject identifier. References can be either absolute (as URIs) or relative using an optional prefix and an identifier.

The prefix is supposed to be associated with a namespace (see 6.2.1), the URI of which will be used to resolve the identifier to an absolute URI. If a prefix is provided but not associated, a URI resolution error is flagged. During evaluation all URIs are resolved against the URI of the current context map. If this resolution does not result in an absolute URI, then an URI resolution error is flagged. The resulting URI will be resolved at evaluation time. The result of this evaluation is a Topic Map item, whereby implementations are allowed to postpone the actual loading of the data.

LET %opera := http://server/opera/
      LET %all   := http://server/opera/ + http://server2/librettos/

Apart from complete maps, also Topic Map items can be referred to, be they relative to the current context map or be they from some other, external map. Assuming that such topics can also reify functions and predicates, this mechanism can also be used to refer to these.

If other references are used, those references which are already absolute URIs will be used as is. References with a prefix identifier are translated by replacing the prefix (together with the colon :) with the value of the prefix. If the resulting URI is relative, it will be resolved against the URI of the context map. This also applies to references which consist of an identifier only. The resulting URI is use either as subject identifier, subject indicator or source locator to address a topic map item.

Additional Notation: To address all topic and association items of a particular class inside a map we allow the following notation:

TM content can also be constructed:

6 Query Expressions

6.1 Structure

A query can take one of three forms: a SELECT expression, a FLWR expression, or a path expression:

Any number of declarations can be put at the front of a query. These declarations apply through the whole query. Declarations are used to define functions, predicates, and name prefixes to be used in the query, and also to import modules containing functions and predicates.

SELECT and FLWR expressions both make use of path expressions as a sub-language. It is also possible to nest queries and mix the different styles.

6.2 Declarations

6.2.1 Prefix Declarations

The using declaration creates a URI prefix that can be used to create short and simple references to topic map objects using qualified URIs. It has the following syntax:

Each using production causes a new tuple (prefix, type, uri) to be added to the prefix bindings in the query environment, where prefix is the string matching the 'ident' production; type being the i, s, or l in the referenced-tm-content; and uri the string matching the 'uri' production. It is an error if the prefix already exists in the prefix bindings.

using xtm for i"http://www.topicmaps.org/xtm/1.0/core.xtm#"

The import declaration imports an external resource containing function and predicate definitions and makes it available through the given prefix.

Each import production causes a new tuple (prefix, 'module', uri) to be added to the prefix bindings in the query environment, where prefix is the string matching the 'ident' production, and uri the string matching the 'uri' production.

import "opera.tmql" as opera

using string for i"http://tmql.org/strings/1.0/#"
SELECT string:uppercase ("rumsti") FROM ...
# or
using adhoc for
   function rumsti (....) {
   }

   function romsti (...) {
   }

SELECT adhoc:rumsti($a) FROM ...
# or
using myrules for
  predicate influenced-by($A, $B) :- {
      pupil-of($A : pupil, $B : teacher) |
....
}.
# or whatever constraint language will come along
	

6.2.2 Predicate Declarations

In addition to the predefined predicates it is possible for users to define their own predicates in TMQL, to be used for inferencing, or simply as shorthands for common subqueries. The syntax is as shown below.

The 'rule' production adds a tuple to the rule bindings in the query environment. It is an error if the rule bindings already contain a tuple whose first element is the same as the string matching the 'ident' production. For examples, see 10.2.

6.2.3 Function Declarations

6.3 Order Clause

All sublanguages use the same mechanism to order tuple sequences. The order clause is optional and allows the resulting tuple sequence to be sorted according to one or more given criteria:

If there are no value expressions provided in the order clause, no ordering will occur. Any number of value expressions can be provided whereby the lexical ordering is significant.

Additional Notation: To keep path expressions concise the language allows the following abbreviations:

For every tuple in the incoming tuple sequence that tuple will be added to the current context. In this new context all value expressions in the provided tuple sequence specification are evaluated. From each result sequence one arbitrary value is taken. These are organized into an ordering tuple. At the end of this process every tuple of the incoming tuple sequence will be associated with exactly one order tuple.

The outgoing tuple sequence is built from the incoming tuple sequence by ordering the tuples according to the ordering tuple they are associated with.

6.4 Unique Clause

To filter out duplicate tuples in the incoming tuple sequence, the unique clause can be used:

All tuples of the incoming tuple sequence are compared according to the equality rules in section Clause 5. For identical copies of tuples only one is chosen.

Additional Notation: For further conciseness this can be abbreviated:

6.5 Value Expressions

Values are either those which have been handed in from the application into the querying process or those which are created during the execution of a query. In either case all values are immutable, i.e. once they exist, they cannot be changed within a TMQL expression.

Values created within a TMQL expression are ephemeral. After creation, values can be referred to inside a given scope which is determined by syntactic measures as outlined below. Outside that scope the value is inaccessible.

Value expressions are expressions which produce a value, usually as a parameter to a predicate or function. They are common to all sublanguages, and have the following syntax:

• By constant content according to the syntax given 5.1.

• By referencing a variable: The value is the value of the variable in the current context. If the variable is not yet bound to a value, NULL will be used.

  If the variable is indexed, the number inside the [] must be a non-negative integer and is used as index. If the variable is prefixed with $ and its value is a tuple, then the index indicates the position inside the tuple which should be extracted.

  If the variable is prefixed with @, then the index indicates the position of the tuple within the tuple sequence which should be extracted.

• By evaluating a function: This follows the rules in 6.2.3.

• By evaluating an operator expression.

• By evaluating a path expression: This follows the rules in Clause 7.

During the creation of an object, it will be associated with a value of one of the types listed in Clause 5. The type determines how the object can be used inside other expressions.

During the creation of an value object, it can optionally be associated with a variable:

Variables have to be prefixed with either a $ to signal an object of simple type, @ for a objects containing sequences and % for Topic Map content. Variables can optionally be postfixed by any number of primes; these are part of the variable name. There is no limit on the length of identifiers.

Some syntactic constructs allow to create nameless objects. To refer to these, the special names $_ and @_ can be used. %_ contains the current context map.

Additional Notation: The shorthand . means the same as $_[0] and is handy if a tuple has only a single component:

6.6 Comments

Comments are allowed anywhere whitespace is and follows a bracket approach:

Comments cannot be nested.

Comments are ignored.

7 Path Expressions

7.1 Structure

Path expressions allow to navigate through a given topic map from a given position on. With them, values can be extracted from the context map, be they map information items or strings. As such, path expressions can extract tuples of such values, the result being then an unordered or an ordered sequence of value tuples.

A path expression is specified by a starting position, the path base and any number (also zero) of path postfixes:

The path base defines a tuple sequence, mostly one consisting of topic map information items in the context map. Postfixes are then applied in lexical order in the context of that map. Association templates are high-level constructs allowing a concise notation for specific, but rather frequent path expression patterns.

Once the path base has been evaluated, the result will be a sequence of information items. As all postfixes operate on individual tuples or sequences of tuples of information items, the path base item sequence will be interpreted as a sequence of singletons, each containing one information item. This sequence is called the initial tuple sequence. Some postfixes operate on individual tuples and some on sequences of tuples. In case of an individual tuple, postfix applications produce an outgoing tuple sequence. In the case of tuple sequences, postfixes transform the incoming tuple sequence into the outgoing tuple sequence.

In many cases the actual order in the outgoing sequence is not relevant for the (final) result. In this case the outgoing sequence can remain unordered. Otherwise the sequence will be ordered. All postfix applications are stable operations, i.e. the evaluation of every postfix occurs in the order of the incoming tuple sequence if that itself happens to be ordered. For unordered incoming tuple sequences no particular evaluation order is guaranteed.

Postfixes themselves are also always evaluated in a particular variable context. Any variable references are treated normally in that during evaluation the variable references are substituted by the variable value(s) according to the current context. Postfixes also may contain function references. These are treated normally in that during evaluation functions inside the postfix are evaluated before the evaluation of the postfix itself.

In the following we provide the informal semantics of path expressions. Annex D contains a formal mapping of path expressions onto the Τ-model.

7.2 Postfix Chains

Postfixes can be cascaded, so that every subsequent postfix operates on the tuple sequence which is the result of the previous postfix application. The language does not mandate specific valid combinations of postfixes. Any combination may be used whereby not all of these may make sense. A complete cascade of postfixes transforms the initial tuple sequence into a final tuple sequence.

A single postfix either selects topic characteristics, navigates along associations through the context map, filters specific tuples from the incoming tuple sequence or evaluates other path expressions in the context of individual tuples:

7.3 Navigation Postfix

To navigate inside a given map we have to move across associations and their roles. There are two kinds of movements, in-movements and out-movements:

Navigation postfixes operate on a tuple sequence. For every tuple in the sequence the specified postfix is applied to every item in a tuple. Every such application will result in a sequence of topic map items. The result then for one particular tuple will be a new tuple of sequences. As usual, this will be flattened by creating the cartesian product of these sequences, building a sequence of tuples of topic map items. All generated tuple sequences are concatenated into the outgoing tuple sequence.

The in-movement is supposed to lead from a topic item to those association items where the topic plays a given role (or any direct or indirect subclass thereof). In this case the movement will return all association items in which that topic plays the given role (or any direct or indirect subclass thereof). No particular order of the output is guaranteed.

The role is specified by another, nested path expression. Its evaluation will result in a sequence of tuples as well. An evaluation error is flagged if these tuples are not singletons. The single components in these singletons are interpreted as alternative roles.

The out-movement is supposed to lead from an association to all topics playing (one of) the given role(s).

Additional Notation: To retrieve the type, the scope or the reifier of an information item the following shorthand notations exists:

Additional Notation: For topic items we also allow to access to the topic characteristics using the following shorthand notations:

7.4 Predicate Postfix

With a predicate postfix conditions are used to filter particular tuples from the incoming tuple sequence:

When the predicate postfix is applied to an incoming tuple sequence the predicate condition will be evaluated for every tuple in this sequence. One by one, each of these tuples will be added to the variable context being accessible via $_ for the path expression(s) inside the predicate postfix.

Only tuples in the incoming tuple sequence where the evaluation returns a non-empty result will be part of the outgoing tuple sequence.

The language defines the following forms of conditions:

In the case of two path expressions connected via a positive compare operator the condition is then satisfied if - after evaluating both path expressions in the current context - there exists at least one identical pair of tuples in the two result tuple sequences, respectively.

Additional Notation: A condition can also be a single path expression:

As both path expressions, left and right to the = comparison operator, are identical, they also result in identical tuple sequences. If that is empty, then no tuples can be compared, making the overall predicate fail. If there is a single tuple in the result, then both result sequences are identical and the predicate succeeds.

In the case of two path expressions connected via a negative compare operator the condition is satisified when - after evaluating both path expressions - there exists not a single identical pair of tuples in the two respective tuple sequences.

Additional Notation: A single path expression inside a predicate can also be negated. Such predicates can be rewritten as

If the evaluation of the path expression results in a non-empty sequence, then the comparison != between the two identical sequences will fail. Only if there is not a single tuple in the result of that path expression, the comparison will succeed emptily.

Additional Notation: The connective AND (&) between conditions we define via the following syntactic equivalence:

The connective OR (|) between conditions we defined based on the combination operator on tuple sequences (see 5.6):

Additional Notation: To test whether a current information item has a particular value, the following shortcuts for conditions can be used conditions in predicates:

7.5 Projection Postfix

When operating on tuple sequences, it may sometimes be necessary to select particular columns out of the tuples in the incoming tuple sequence and to form with these new tuples for an outgoing tuple sequence. This can be achieved with a projection postfix:

This postfix is applied to every individual tuple in the incoming tuple sequence. The current tuple will be added to the current variable context, addressable via the name $_. Then all path expressions inside this list of path expressions are evaluated whereby the order is left undefined.

%m // opera < ./bn[@opus], . -> work [ * is-composed-by ] >

7.6 Association Templates

Association templates allow to define path expressions which look for associations of a certain type having particular role/player combinations. While association templates are a more concise notation for that purpose, they do not introduce new expressitivity or semantics as they can be transformed into path expressions (see Annex B). Nevertheless we will describe their informal semantics here.

Association templates can occur anywhere where a path expression postfix is allowed:

The tm-reference in the association template identifies an association type and the optional members are pairs of path expressions. The ellipsis ... can be used to indicate the fact that there may be other members in such associations which remain unmentioned.

The (potential) player(s) and role(s) for a particular member in the association template are computed by evaluating the path expressions for the association player and the association role, accordingly. This happens within the current context; the evaluation order itself is irrelevant. For each member there then exists a sequence of potential players and a sequence of potential roles. If one of the sequences does not result in a sequence of singletons, an evaluation error is flagged.

The evaluation result of an association template is a singleton sequence containing all associations in the context map which satisfy the following conditions:

1. The association must be an instance of the given type or of any of its subtypes.

2. For each of the members mentioned in the association template, the association must have a role out of the sequence of potential roles, together with a player out of the sequence of potential players.

3. If the ellipsis ... has not been used, there does not exist further members in the association which are not explicitely named in the association predicate.

is-located-in (%_//cities: location , $_: theatre)

8 SELECT Expressions

8.1 Structure

SELECT expressions use a pattern-matching approach for queries. They always produce sequences of tuples as their results. A query follows the syntax:

Full SELECT expressions are evaluated starting with the FROM clause, which produces the topic map which is queried. Then, the predicate list in the WHERE clause is evaluated, generating an initial tuple sequence. Finally, the SELECT clause is evaluated, producing the final tuple sequence.

If only a predicate list is given, this is equivalent to having a full SELECT with no SELECT or FROM clause.

In the following we provide the informal semantics for the individual clauses. A formal mapping to FLWR expressions is given in Annex A.

8.2 FROM Clause

The optional FROM clause may contain references to one or more maps which the query refers to, or an expression computing the map. If the FROM clause is omitted, this is equivalent to FROM %_.

8.3 SELECT Clause

SELECT clauses are used to define which values go into the final result set using references to variables defined in the query or expressions based on these.

The SELECT clause generates an output tuple for every input tuple in the tuple sequence, with one component in the output tuple for each value-expression in the SELECT clause in lexical order.

  select $COMPOSER
  where composed-by($COMPOSER : composer, $OPERA : work)
  

8.4 Predicate lists

8.4.1 General

The predicate list produces a tuple sequence, with one component for each variable occurring in the predicate list, and one tuple for each binding of values to the set of variables. Each tuple represents a set of values for the variables in which the statement represented by the query is true, according to the topic map(s) being queried.

Variables occurring within a predicate list are scoped for the whole predicate list. This implies that two occurrences of variables with the same name refer to one and the same variable binding.

The predicate expressions are evaluated one by one with the result set produced by the previous expression as input to the next. The initial result set used by the first expression has one column for each variable in the query and a single row where all values are null. The result set returned by the final expression is the result of evaluating the predicate list.

Predicate expressions have the following syntax:

8.4.2 Predicate application

The default form of predicate expression is the application of a predicate, which is done with the following syntax:

The type, number, and order of parameters is defined by the predicate that is applied. Some predicates are sensitive to the order of their parameters, while others are not.

8.4.3 Comparisons

Comparison expressions are used to compare values produced by means of path expressions, which often are simple variable references. Comparison expressions have the following syntax:

Comparison operations are mapped to predicate applications where the comparator is the predicate, and the value expression are parameters in the order given.

8.4.4 The instance-of predicate

The instance-of predicate has special syntax, as follows:

Any expression matching the production above can be transformed into an application of the predicate instance-of with the parameters in the same order.

8.4.5 OR Expressions

Or expressions are used in queries where a result is wanted when it is sufficient for one of several conditions to be met. The syntax is as follows:

The predicate lists in the OR expression are evaluated independently, all starting from the input result set. The result of the or expression is the concatenation of the output result set from all the predicate lists in the expression.

8.4.6 NOT Expressions

NOT expressions are used to remove from query results all matches where a certain condition is met, and the syntax is as follows:

The NOT expression is evaluated by evaluating the predicate list with the current input result set as the input result set. The output from the NOT expression is a result set containing all rows in the input result set that do not match a row in the output result set from the predicate list. A row matches another if for all columns where neither has a null value their values are equal.

8.4.7 Optional clause

The optional clause is used to include predicate expressions in the query that do not form part of the search criteria (ie, they do not remove matches), but which are included to produce values (ie, they bind variables). Optional clauses have the following syntax:

Queries using optional clauses can always be rewritten into a longer, but equivalent query that does not use the optional clause. An optional clause with predicate list X can be replaced by the following OR expression: { X | 0 = 0 }. That is, an OR expression where X is one branch, and the other branch is trivially true.

8.4.8 EVERY/SATISFIES Expressions

In general, predicate expressions generate as matches all cases where at least one piece of evidence can be found to support the match. EVERY/SATISFIES expressions do the opposite: they only return matches in cases where for all values in a certain set there is supporting evidence.

All EVERY/SATISFIES expressions can be translated into an equivalent (but rather harder to understand) nested NOT expression, as follows. The expression EVERY x SATISFIES y can always be replaced with not(x, not(y)), which will give the same result.

$CLUSTER : cluster,
EVERY part-of($MACHINE : part, $CLUSTER : whole)
SATISFIES is-down($MACHINE)?

9 FLWR Expressions

9.1 Structure

FLWR expressions have the same expressivity as path expressions; their syntactic structure, though, allows not only tuple sequences to be returned, but also the construction of content in XML and TM form:

Only the RETURN clause is obligatory; it allows the result content to be generated. All the other clauses are optional.

The conceptual processing model of FLWR expressions is that first the FOR clauses are evaluated in lexical order, if they exist. A value expression is used to generate a tuple sequence. One by one, each of these tuples will be bound to the loop variable which is named in the FOR clause. This variable binding will be added temporarily to the current context while the rest of the query is evaluated. This step is repeated for every tuple in the sequence. If there is more than one such FOR clause, these act consequently as nested loops.

The optional WHERE clause contexts to be tested for particular conditions; only those contexts for which the evaluation of the WHERE clause returns TRUE will be passed on into the next clause.

Note that a WHERE clause can contain references to variables that are not bound to values in the current context. Conceptually, for each such variable another FOR clause has to be created where the variable iterates over all items in the current context map.

Once the variable contexts have been filtered, all these remaining contexts are now organized into an unordered sequence.

The RETURN clause is then responsible for actually generating content, be it a number, a string, a tuple sequence, a single XML structure, or a TM instance.

If—due to enclosing FOR clauses—several results have been computed for every iteration, then these partial results are combined into a total result. For strings this combination is done via concatenation, for tuple sequences, the partial sequences are interleaved (unless they are ordered), for XML content the individual fragments are combined into a node list and for Topic Map content the fragments are merged.

In the following we informally describe the semantics of the individual clauses. A formal mapping of FLWR expressions to path expressions is given in Annex C.

9.2 FOR Clauses

A given FLWR expression can contain any number of FOR clauses. In each of these clauses a loop variable is declared:

The language allows several such variable associations to be listed in a single FOR clause. This is equivalent to using a dedicated FOR clause for every individual variable.

A variable association includes the evaluation of another query expression:

The introduced variable is visible until the end of the directly enclosing FLWR expression.

The provided value expression is evaluated in the current context, resulting in a tuple sequence. If the variable can only hold simple content, then - one by one - one tuple of this sequence is bound to the variable and this binding is added to the current context. For each of the tuples the rest of the FLWR expression is evaluated.

If the variable can hold composite content, then the whole tuple sequence is assigned and that binding is added to the current context. In that case, only a single iteration of the remained of the FLWR expression is evaluated.

9.3 LET Clauses

LET clauses are used to assign a value to a variable in the current context without looping over all alternatives. The syntax is as given below.

The value expression will be evaluated in the current context. If the variable is prefixed with @ the resulting tuple sequence will be bound as a whole to the named variable. If the variable is prefixed with $ only the first value out of this sequence will be bound to the variable. If the result tuple sequence is empty, then NULL will be used as value. That variable binding will be added to the current context.

A LET clause where the variable has a $ prefix is equivalent to a FOR clause with the same value-expression, except that it must have [0] appended. If the variable has a @ prefix it is equivalent to a FOR clause with the same value-expression.

9.4 WHERE Clause

9.4.1 Structure

The WHERE clause makes use of boolean expressions but expresses exists semantics:

Additional Notation: As convenience, it is possible to reduce the verboseness when dealing with path expressions:

All boolean expressions are evaluated in the current context.

For the evaluation, the operators AND, OR and NOT have the usual meaning (non-short-circuit, symmetric), the brackets () can be used to override the usual precedence, namely that AND binds stronger than OR and that NOT binds stronger than AND.

EVERY $opera IN %m // opera SATISFIES
      composed-by ($person: composer, $opera: opera)
      AND
      SOME ...	    
	  

EVERY $opera IN %m // opera SATISFIES
      composed-by ($person: composer, $opera: opera)
AND
SOME ...	    
	  

All subexpressions of a boolean expression are interpreted in the current context. They evaluate either to TRUE or FALSE.

If boolean expressions in a WHERE clause contain references to unbound variables, then the directly enclosing FLWR expression will be wrapped with an additional FOR clause which makes the variable iterate over all items in the current context map. With this process all unbound variables are eliminated.

The evaluation of boolean expression works under the following constraints. For any context which satisfies a boolean expression, it must hold that:

1. Any two occurrences of one and the same variable within the boolean expression must have equivalent values bound to them in that context.

2. Any two occurrences of two different variables within the boolean expression may have any values bound to them. They are regarded to be independent.

3. Any two occurrences of two different variables within the boolean expression where the names only differ in the number of primes, must not have equivalent values bound in that context.

The special variables $_ and @_ can be used as placeholders, but any bound values are not accessible outside the directly enclosing WHERE clause.

9.4.2 FORALL and EXISTS Clauses

These clauses allow to test whether a particular condition can be satisfied by at least one value out of a set of values or whether all these values satisfy a condition:

Any number of new variable associations can be introduced. These bindings will be added to the current context only for the evaluation of the boolean condition.

The forall clause evaluates to TRUE if for all variable bindings the boolean expression evaluates to TRUE. Otherwise it will evaluate to FALSE. The exists clause evaluates exactly then to TRUE if there exists at least one variable binding for which the evaluation of the boolean clause returns TRUE.

Additional Notation: If the boolean condition is not relevant, the following abridged forms can be used:

Additional Notation: In the special case that two path expressions are compared for equality, then we also introduce

9.5 RETURN Clause

In the RETURN clause the variable bindings in the current context can be used to generate output:

For every context generated by the previous clauses of the FLWR expression, the RETURN clause is evaluated. The aggregated result of this evaluation is the result for the directly enclosing FLWR expression.

10 Predefined Environment

10.1 General

for strings:

   - concat, length, the usual suspects
   - pattern match =~, !~
	Issue: how to fit in patterns for =~ qr{...} as shorthand for
	re:match (..., ...., 'i'), argh.

for sequences:

   - || interleave, ..., &, |

other topics

   - is-scoped-by

   - is-reified-by

   - has-uri-occurrence

   - has-data-occurrence

   - has-basename

-topic?

-thing?

dates:?

10.2 Predefined Predicates

The following predicates are predefined in TMQL.

using xtm for i"http://www.topicmaps.org/xtm/1.0/core.xtm#"

direct-instance-of($INSTANCE, $TYPE) :-
  xtm:class-instance($INSTANCE : xtm:instance, $TYPE : xtm:class).

is-subclass-of($SUB, $SUPER) :- {
  xtm:superclass-subclass($SUB : xtm:subclass, $SUPER : xtm:superclass) |
  xtm:superclass-subclass($SUB : xtm:subclass, $MID : xtm:superclass),
  is-subclass-of($MID, $SUPER)
}

instance-of($INSTANCE, $TYPE) :- {
  direct-instance-of($INSTANCE, $TYPE) |
  direct-instance-of($INSTANCE, $SUB),
  is-subclass-of($SUB, $TYPE)
}.

11 Conformance

A Mapping of SELECT Expressions to FLWR Expressions (normative)

SELECT expressions can be mapped to FLWR expressions. This is quite intuitive, since SELECT expressions solve the special case of generating tuples out of a particular map. Both use the same concept of a boolean expression for the condition and both use the same sorting mechanism:

If an ORDER clause exists, that would be copied verbatim, so would be a UNIQUE clause.

Tenative/Idea: The path expressions would be converted according to the following pattern:

• Every anonymous object in OD corresponds its path expression in OD'.

• Every typed object in OD corresponds to an additional LET clause in the FLWR expression of the form:

  LET variable := tau // tm-reference

  This, new, variable will appear in OD'.

• Every untyped object in OD corresponds to a LET clause in the FLWR expression of the form:

  LET variable := tau // *

  The variable will appear in OD'.

B Mapping Association Templates to Path Expressions (normative)

TBW

C Mapping of FLWR Expressions to Path Expressions (normative)

FLWR expressions consist of two parts. In the upstream-side variables will be bound to values to build contexts. These contexts are optionally sorted and finally filtered with the WHERE clause. The downstream-side of a FLWR expression is the RETURN clause which is concerned in translating the variable bindings into content, be it tabular, XML content or Topic Map content.

The upstream part of FLWR expressions can be mapped into path expressions as follows:

1. The τ expression for the queried map %m is used as absolute path base %m // *.

2. Then a projection postfix is built by including all path expressions (keeping the syntactic order):

   [AB]

   'FOR' f1 ':=' p1 'FOR' f2 ':=' p2 '...' 'LET' l1 ':=' q1 'LET' l2 ':=' q2 '...'

   :==

   '<' p1 ',' p2 ',' '...' ',' q1 ',' q2 ',' '...' '>'

   The variable names f1, f2, ..., l1, l2, ... are associated with an index in the projection tuple. f1 is associated to 0, f2 to 1, etc. These associations can be used in the RETURN clause to refer to individual values.

   Ed. Note:

   I have a problem with LET clauses and variables which store lists. I cannot hold lists in a tuple component.

3. The condition in the WHERE clause is converted into predicate postfixes as follows:

   1. All boolean subexpressions which are separated by AND are converted into a separate predicate postfix.

   2. All boolean subexpressions which are separated by OR are put into one predicate postfix.

   3. TODO: FORALL, EXISTS

   4. TODO: association-predicate becomes path expression

4. The ORDER clause is added as further postfix.

5. The UNIQUE clause is added as further postfix.

D Path to τ Expression Translation (normative)

E τ Model (informative)

TBW

F Relationship between Τ and TMDM (normative)

The Topic Map Data Model (TMDM) describes a data model for Topic Maps. In that it defines which objects exist in a given Topic Map instance and what properties these different objects have. In contrast, the Τ model sees a topic map instances as a set of assertions; all other features of a topic map are mapped into assertions.

In the following we will characterize how topic map instances according to TMDM can be thought as instances of a map according to Τ

need more time for typing....

G Syntax (informative)

Core Syntax

Shorthand Notations

Bibliography

TMQLreq, TMQL Requirements, ISO, 2003

TMQLuc, TMQL Use Cases, ISO, 2003