Previous section.

Systems Management: Topology Service

Systems Management: Topology Service
Copyright © 1997 The Open Group

Topology Query


Queries are expressed textually using a Topology Query Language (TQL).

Topology supports generally topology queries on the set of all defined Aggregate Entities (AEs). Each query specifies one or more meta_AEs which are matched against the known AEs. A meta-AE is essentially a template for matching AEs.

Queries also specify navigation paths through Topology, which dictate which associations are to be followed between AEs in evaluating a query. Navigation paths are expressed in terms of meta-associations, which are templates for matching associations in Topology.

The result of a topology query consists of two parts. The first part is a boolean value that indicates whether the propositional expression posed by the query evaluates to TRUE or FALSE. This part of the result is always returned. The second part of the result is a sub-graph, or sub-graphs, that match the navigation paths specified by the query. The construction and existence of this part of the result depends on the type of result requested by the client.

The process is illustrated in A Process for Performing Navigation Queries .

Figure: A Process for Performing Navigation Queries

Topology Data Store

The Topology data store can be viewed as a graph of associated AEs. A topology graph is a set of nodes and a set of edges connecting the nodes. Nodes are AEs, and edges simply indicate the existence of an association between the two AEs.

Figure: Topology Graph Structure

Type Matching

Topological types are organized into inheritance type hierarchies.

An entity is matched against a topological type if it has the same topological type as that specified, or it has a topological type which is a specialization of that specified.

For example, in Example of a Topological Type Inheritance Hierarchy , if a meta-AE specified topological type RT-3, all AEs with topological type RT-3, RT-6, RT-7 and RT-9 will match the meta-AE.

Figure: Example of a Topological Type Inheritance Hierarchy

Meta-AE (Meta-Aggregate Entity)

A meta-AE is a template for matching AEs in topology. A meta-AE can be:

Simple Navigation Paths

A simple navigation path contains one or more meta-AEs connected by meta-associations.

The presence of a meta-association in evaluating a query means that an association in the Topology data store must be traversed.

A meta-association can optionally specify a role for each of the meta-AEs that it connects. If specified, these roles limit the matching AEs to those that take the specified role in the corresponding association. The specification for a role may include an index, if cardinality is greater than 1.

A simple navigation path can be viewed as a proposition on topology that will return TRUE or FALSE, but not both. Each topology query must consist of at least one simple navigation path.

A simple navigation path is a recipe for matching paths through the Topology data store. A path in topology will match a simple navigation path if each AE in the topology path matches the corresponding meta-AE in the navigation path and adjacent AEs in the topology path are associated (in the correct roles) with each other; that is, the associations match the meta-associations. AE matching starts with the root meta-AE of the path and progresses sequentially to the leaf meta-AE of the navigation path. Several paths through topology may match a simple navigation path.

Some examples of simple topology queries using a simple navigation path (see TQL Overview for syntax specifications):

Figure: Graphical Representation of the Queries

Both example queries start AE matching at the root meta-AE of their simple navigation paths. Ex 1 will only find, at most, one matching path in topology as it specifies a specific AE at every meta-AE. Ex2 may find several paths in topology that match the root meta-AE as it specifies topological types at every meta-AE. A query will return TRUE if it can find at least one matching path in topology.

Query Trees

Simple navigation paths can be combined, using logical connectives, to pose more advanced queries on the topology graph structure. The logical AND, OR, and NOT are used to produce compound propositional expressions on topology. They are expressed as query trees. A simple navigation path is the simplest form of query tree. Evaluation of the connectives is in accordance with the rules of logic. These are:

Nodes in query trees are either meta-AEs or logical connectives. Branches only occur at the logical AND and OR connectives which each have two branches. Complex navigation paths are paths within query trees.

If a null sub-query tree is a child of an AND or OR logical connective, that null query sub-tree is assumed to return the result TRUE. In other words, the tree is equivalent to one where the AND or OR node (with the null sub-query tree) is removed; that is, the node that was its child becomes the child of the parent of the AND or OR.

In query trees that are simple navigation paths, the edges always join nodes that are meta-AEs and always represent meta-associations. In contrast, in more general query trees, edges join nodes that may be meta-AEs or logical connectives. Edges in the tree are therefore not always meta-associations. Meta-associations exist between each pair of meta-AEs in the query tree where one meta-AE in the pair is the closest ancestor node of the other that is also a meta-AE.

Example Queries

Some example topology queries using the logical connectives are:

These examples show that the queries can be posed to Topology can be complex (and difficult to unambiguously describe in natural language).

Figure: Graphical Representation of Example Queries
All four queries start AE matching at the root meta-AE (E1). Queries Ex1 and Ex2 contains two complex navigation paths rooted at E1, whereas query Ex3 contains a single complex navigation path rooted at E1. Query Ex4 shows an example of nested logical connectives, with a total of three complex navigation paths that are rooted at E1.

The logical connectives AND and OR can also be used as root nodes in query trees. Examples of these types of queries are:

Figure: Graphical Representation of Queries: Logical Connectives


A simple navigation path, can be repeated a number of times as part of the query. A repetition statement is bounded by a lower limit. An optional upper limit may also be specified. These limits indicate the minimum and maximum number of times the repetition can occur in a topology path.

Here is an example of specifying repetition in a query:

Figure: Graphical Representation of Query Repetition

Queries containing repetition constructs where the upper bound is specified can always be expressed by an equivalent to a query without repetition. Equivalent Query without Repetition shows the equivalent query for a query shown in Graphical Representation of Query Repetition ' where an upper bound of 2 is specified.

Figure: Equivalent Query without Repetition

For the purposes of specifying the requirements for matching queries it is not necessary to consider the repetition construct given that equivalent queries can be constructed without them (for these purposes, queries containing repetition constructs where the upper bound is not specified can be considered as having a very large upper bound).

References to Registered Queries

At any point in a query where a meta-AE can be specified, it is also possible to specify a reference to a registered query. A registered query is a query that has been named. When a query that contains references to registered queries is evaluated, Topology replaces the references with the query tree that represents the registered query.

AE Matching Constraint

There are two things that are matched in a query. AEs match meta-AEs and associations match meta-associations.

The Topology Service supports the ability for the client to define constraints between pairs of meta-AEs that either require or forbit the same AE from matching both meta-AEs.

These constraints are specified for any pair of meta-AEs as:

If any pair of meta-AEs does not have a constraint specified, then the same AE may or may not match both meta-AEs; that is, "don't care" is the default.

There is similar support for expressing constraints for meta-associations.

Query Result

There are two parts to a query result:

Result Construction Rules

The result construction rules specify the number of sub-graphs to be returned from a query. A query can only return sub-graphs if the boolean result of the query was true. There are three result construction rules:

A query can only specify one result construction rule at a time.

User Tags

The Topology query service allows user tags to be specified on the meta-AEs of the query. While user tags are semantically irrelevant to the query evaluation process, the provide a means for the client to identify which topology AEs matched which meta-AE(s) in the query.

Each sub-graph returned in the result of a query will copy all user tags from the meta-AEs to their corresponding matched topology AEs. If the result construction rule of the query specifies the graph option, and the topology AE in the query result represents more than one meta-AE, the AE will copy all user tags from each meta-AE it matched.

The client can then extract AEs from the query result by specifying the tags of interest.

Topology Query System

The Topology Query System consists of the components as shown in Topology Query System .

Figure: Topology Query System

Query Language Definition

The query language definition consists of the language grammar (syntax) with corresponding semantics (see sections that follow on TQL: Topology Query Language). The language definition is a precise specification from which users can construct query programs for subsequent compilation and execution:

query program

A query program is a textual expression of a query.

compiled query

A compiled query is produced by the QueryExecutionFactory, which calls the TQL compiler, when a valid query program is processed.

parameterized query

A parameterized query is a query where named parameters are used as placeholders that are substituted when the query is evaluated. There are three kinds of values that can be substituted for a parameter: a tag, a specific AE or a compiled sub-query.

query language compiler

The TQL compiler, called by the QueryExeuctionFactory, takes as input a textual program (string) and performs syntactic and semantic checking on the input. If no errors are detected by this checking the query can be executed.


A TQL query string may contain references to other queries which are defined as a separate string with a particular name. These references to other queries are called sub-queries. They could have been directly written into the query but because of the semantics defined for the relationships they find it makes the query more understandable to write them as a short reusable query.

For example, a query to find grandparents of an entity can most easily be written as a query to find the parents of the parents of the entity. Thus, a query to find parents is a very suitable candidate to write as a sub-query.

A potential implementation could allow these sub-queries to be registered and stored for retrieval and sharing between various applications.

TQL Overview

TQL Language

TQL is a textual language designed to facilitate the use of the Topology Service navigation query functions, by allowing navigation queries to be expressed textually.

The language maps directly onto the query trees that are supported by Topology. No additional functionality is supplied by the language and none is denied.

The scope of the language is restricted to providing a syntax for the expression of any allowable query tree and the conversion of the expression into the physical tree data structure. Minimal semantic checking is done by the compiler; this is deferred untiqa():-l query execution.

TQL Compiler

The TQL compiler methods are defined by the QueryCompiler interface. Every Topology server instantiates one object that supports the Query Compiler interface. There is, therefore, a TQL compiler on every host on which the Topology Server is running.

Clients access the compiler by initializing a Query object with a TQL string.

TQL Grammar

The YACC specification of the TQL grammar is as follows. A discussion of the TQL grammar also follows:
query: query_head '\{'  clause_expr '\}' ;

query_head: IDENTIFIER | IDENTIFIER '(' ')' | IDENTIFIER '(' argument_list ')' ; clause_expr: sequence_clause | clause_member ; sequence_clause: sequence_clause clause_member | clause_member clause_member ; clause_member: clause | repetition_clause | meta_association | ABSENT_TOKEN clause_member | clause_member AND_TOKEN clause_member | clause_member OR_TOKEN clause_member | '('clause_expr')' ; meta_association: labeled_meta_association | role labeled_meta_association | labeled_meta_association role | role labeled_meta_association role ; labeled_meta_association: '-' | '-' label '-' ; clause: clause_item | clause_item clause_qualifier ; clause_item: topology_type_expression | query_reference | ARGUMENT | AENAME_TOKEN xfn ; /* where xfn is an agregate entity name */ clause_qualifier: HEAD_TOKEN | TAIL_TOKEN | label | tag | clause_qualifier HEAD_TOKEN | clause_qualifier TAIL_TOKEN | clause_qualifier label | clause_qualifier tag ; repetition_clause: '[' range clause_expr ']' ; topology_type_expression: topology_type | topology_type_expression TOPOLOGY_TYPE_AND topology_type_expression | topology_type_expression TOPOLOGY_TYPE_OR topology_type_expression | TOPOLOGY_TYPE_NOT topology_type_expression | '(' topology_type_expression ')' ; topology_type: xfn | ANY_TOKEN ; tag: TAGGED_TOKEN STRING ; /* * tags are used for marking parts of the query so that when the * results of the query are returned you can tell what actual data * matched which parts of the query */ label: LABELED_TOKEN IDENTIFIER ; /* labels are used for setting constraints */ role: '<' IDENTIFIER '>' | '<' IDENTIFIER INTEGER '>' ; range: /* nothing */ | INTEGER RANGE_TOKEN | RANGE_TOKEN INTEGER | INTEGER RANGE_TOKEN INTEGER ; query_reference: SUBQUERY_TOKEN xfn '(' ')' | SUBQUERY_TOKEN xfn '('query_actual_list')' ; query_actual_list: clause_item | query_actual_list ',' clause_item ; argument_list: IDENTIFIER | argument_list ',' IDENTIFIER ; xfn: IDENTIFIER | STRING ; ABSENT_TOKEN: 'ABSENT' AENAME_TOKEN: 'AENAME' AND_TOKEN: 'AND' ANY_TOKEN: 'ANY' HEAD_TOKEN: 'HEAD' LABELED_TOKEN: 'LABELED' OR_TOKEN: 'OR' RANGE_TOKEN: '..' SUBQUERY_TOKEN: 'SUBQUERY' TAGGED_TOKEN: 'TAGGED' TAIL_TOKEN: 'TAIL' TOPOLOGY_TYPE_AND: '&' TOPOLOGY_TYPE_NOT: '!' TOPOLOGY_TYPE_OR: '|'

TQL Semantics

This section describes the grammar and semantics of TQL.
Query Structure
A TQL query has the following structure:
name(parameters) \{body bgcolor="#FFFFFF"\}

Name and Parameters
A TQL query has a name and optionally a list of parameters. This has the form:
name(parameter, parameter,parameter)

The name uniquely identifies the query. Parameters define placeholders for external queries to be used in the query body bgcolor="#FFFFFF". A placeholder defines where in the query body the value for the parameter is used; for example:

q(p)  \{TypeA-p-TypeC\}

When the query is called, a value must be supplied for each parameter and this value is bound into the query where the corresponding placeholder is used.

Query Body
The query body bgcolor="#FFFFFF" specifies the declarative logic of the query. When reference is made to a "query", what it usually means is the query body bgcolor="#FFFFFF".

The query body bgcolor="#FFFFFF" is an expression of clauses.

Clause Expressions
The body bgcolor="#FFFFFF" of the query is a clauseexpression. A clause expression consists of clause expressions (recursive definition) separated by the binary operators AND, OR, the unary operator ABSENT (equivalent to "NOT"), and the binary meta-association operator (DASH, or "-"). A clause expression can be a clause or a repetition expression.

Clause expressions are evaluated as per normal expression syntax, that is, a left associative infix expression of a binary tree with brackets for explicit grouping. Clause operators in order of precedence are: ABSENT , AND , OR , DASH.

For instance, the expression:

q() \{ clause OR clause AND clause or ABSENT clause \}

which is equivalent to the following, with brackets explicitly shown:

q() \{ ((clause OR (clause AND clause)) OR (ABSENT clause)) \}

An example of explicit precedence follows:

q() \{ (clause OR clause) AND (clause OR ABSENT clause) \}

A clause expression can be a list of clause expressions separated by meta-associations denoted by dashes.

q() \{ clause-clause-clause \}

We can then have the following expression:

q() \{ clause-clause-clause AND clause-clause \}

Brackets may be used for grouping clause epxressions so that they can be associated:

q() \{ (clause)-(clause)\}
q() \{ (clause AND clause)-(clause OR clause)-clause \}

A clause can be a meta-AE, a query reference or a placeholder.
A meta-AE expression is a template for matching AEs in topology. There are three forms:

A topological type consists of a valid name for a topological type, for example:

query() \{ Computer\}

This defines a query that will match all AEs of type Computer.

A meta-AE may be an expression of topological type identifiers. A topological type identifier is the name of a valid topological type. The binary operators "&" (and) "|" (or) and the unary operator "!" (not) are used as type operators, with brackets for explicit grouping (as with clause expressions). The precedence of the operators from highest to lowest is ! & |. All of the type operators have a higher precedence than the clause expression operators, so they will bind more tightly to type identifiers, avoiding ambiguities.

For instance:

(Computer & Workstation) | MiniComputer & !Mainframe

This specifies a single AE matching this expression for typological types.

The following example shows that the type expression operators have a higher precedence. The expression:

Type1 AND Type2 & Type3

is evaluated as:

(Type1 AND (Type2 & Type3))

Note that meta-associations are not applied to topological type identifiers in the type expression but to the entire expression (meta-AE).

A wildcard match can be defined using the keyword any. This specifies that an AE of any type may match the meta-AE.

Constraints, tags, roles and binding points may be specified on meta-AEs.

A constraint is simply a label associated with a meta-AE. However, for a given query, the labels constrain the query result in that any two meta-AEs that share the same label must result in the same matching AEs in every query result produced. Correspondingly, non-matching labels must result in non-matching AEs. Constraints can also be assigned to meta-associations to produce matching or non-matching associations in the query results. Constraint labels are identifiers specified with the Keyword LABELED.

Tags are explained in User Tags .

Tags are indicated in the keyword TAGGED.

Roles are explained in Topology Rules , and are specified at the start and end of the meta-AE expression to indicate the roles the AE plays in associations coming into it (the role specification at the start) or going out of it (the role specification at the end). A role specification is indicated by braces:

q() \{"AE-pattern" <role> "AE-pattern"\}

Binding points are used to process query references. There are binding points in each query referred to as head and tail binding points. Binding points are assigned to AEs to define the way that references to that query by other queries are resolved. When a referenced query is bound to its reference, a new bound query is produced by taking the referencing query and replacing the reference node with a referenced query. Replacement here means the head node of the referenced query will replace the reference node, and the subtree rooted at the reference node will be duplicated and attached to each tail of the referenced query.

A meta-AE can be labeled as both a head and a tail.

The following diagram depicts this:

Figure: Binding Points assigned to AEs

An example of a fully featured meta-AE expression is:

HEAD TAIL <client> (Computer&Workstation|PC) <server> TAGGED "box"

This matches an AE that is a Computer and a Workstation, or a PC. Furthermore, it has two tags: box and node. It has a constraint label "x" on it and is both the head and tail binding point. It will be a client role with any associated meta-AE on the left, and a server role with an associated meta-AE on the right.

A meta-association is specified using the binary "-" (dash) operator:
TypeA-(TypeB AND TypeC)
(TypeA AND TypeB)-(TypeC OR TypeD)
TypeA | TypeB-TypeC & TypeD

A meta-association is placed between clause expressions:


The expression is evaluated from left to right. Every clause expression on the left is associated with every clause expression on the right.

In the simple case, with clause expressions that are clauses, this could look like:

q() \{ clause-clause-clause-clause-clause \}

for example, "Vehicles belonging to people":

q() \{ Person-Owns-Vehicle \}

Slightly more complex clause expressions could be associated:

q() \{ clause-(ABSENT clause)-clause-(clause) \}

A clause expression could be even more complex, forming a tree, such as:

clause AND clause OR clause

For example, "all coconuts or lemons, as long as there are no guavas":

q() \{ (Coconuts OR Lemons) AND ABSENT Guavas \}

Meta-associations can be placed between clause expressions that are grouped by brackets, giving a mechanism to associate subtrees.

q() \{ (clause1 AND clause2)-(clause3 OR clause4) \}

The example above would be equivalent to:

q() \{ (clause1-clause3 OR clause1clause4) 
AND (clause2-clause3 OR clause2-clause4) \}

The subtree (clause3 OR clause4) is attached to both leaves of the tree (clause1 AND clause2).

If the subtree (clause expression) on the left has multiple leaf nodes, the subtree associated to the right will be placed at each of these leaves with equals constraints between the corresponding elements in the right subtree.

For example, "computers with both a modem and a printer that are located in the same location":

q() \{ Computer-(Modem AND Printer)-(Located-Location) \}

Meta-associations may have constraint labels attached to them.

Meta-associations can be established between repetition expressions, denoted by square brackets, for example:

q () \{ TypeA-TypeB-[1..20,TypeC-TypeD]-[2,TypeE-]TypeF \}

Meta-associations can be established between placeholders. The binding points in the external query determine how it is bound into the query.

q(x) :- TypeA-x-TypeB \}

Meta-associations can be made between query references. The binding points in the referenced query determine how it is bound into the query.

q(x) :- parent(x)-Owns-Vehicle \}

A meta-AE can be in different roles for different meta-associations. Roles are specified inside "<" and ">" symbols and using the role type name.

The role is specified on the side of the meta-AE adjacent to the associated meta-AE, as a particular meta-AE can be in a different role with an associated meta-AE on the other side in the query:


For instance, a query, "Clients and Servers in the NetWare relationship":

 q() \{ Computer<client>-NetWare-<server>Computer \}

Constraint Labels
Meta-AE and meta-association constraints are specified using labels. Labels are specified with LABELED.

A meta-AE constraint label is expressed after the meta-AE:

q() \{ TypeA LABELED x - TypeB - TypeC AND TypeD LABELED y;

A meta-association constraint label is expressed using two DASH operators with the label between them.

q() \{ TypeA-(LABELED x)-TypeB-(LABELED y)-TypeA;

There are three conditions for constraints:

Equals constraints are specified using the same label; not equals constraints with different labels; don't care conditions are the default, with no label.

Sub-queries and Query References
A query may be defined in terms of other sub-queries. Sub-queries can be passed in as parameters and referenced in a clause with a placeholder or called using a query reference.

An example of a query passed in as a parameter is:

p() :- TypeA-TypeB;
q(p) :- p;

In the example, "p" is a placeholder for an external query and is equivalent to the fully expanded form:

q() \{ TypeA-TypeB\}

A query can be called via a query reference which has the form:

SUBQUERY queryIdentifier(parameter)

Parameters in a query reference can be either a placeholder for a parameter passed into the calling query or another query reference. The previous example is also equivalent to:

q() \{ p() \}

Consider the following query:

parent(x) \{ x<child>-Family-<parent>head,tail Person \}
grandparent(y)\{ parent(parent(x)) \}

q(x) \{ parent(x)-Located \{ loc \} Location AND grandparent(x)-Located- \{ loc \}Location \}

It queries, "Are X's parents and grandparents located in the same location". It shows how parameters may be defined in terms of other query references.

Bindingpoints are used to control what is bound for a sub-query that is called from a query. If no binding points are specified, the entire query is bound by default.

Binding Points
Binding points are used to control how a sub-query is bound into a calling query. The keywords HEAD and TAIL are used for this purpose. These are specified before the meta-AE expression. They are put before the label, if one exists, and between the role specifiers:
<role>HEAD TAIL (x) Typexpr TAGGED "tags"<role>

One, all or none may be specified on a meta-AE.

The validity of binding points is not enforced by TQL but by the QueryExecutionFactory:

p()\{ HEAD TypeA-(TypeB-TypeC OR TypeD-TAIL TypeE)\}

The head and tail may be specified on a single meta-AE:

p() \{ TypeA-(TypeB-TypeC OR TypeD-(HEAD TAIL TypeE)) \}

Repetition is used to specify paths that may be repeated over and over within bounds. The path that may be repeated is called a repetition unit.

Square brackets define the repetition unit:

q() \{ TypeA-TypeB[1..20, TypeC-TypeD-]TypeE \}

In a list of one or more clauses, such as:


a repetition unit may be placed starting at a clause and ending at a meta-association:


or starting at a meta-association and ending at a clause:


The smallest repetition unit is one of the following:


An integer range can be placed on the repetition unit:

[1, TypeA-TypeB-]TypeC

This means repeat unit 1 to infinity times.

[1...20, TypeA-TypeB-]TypeC

This means repeat unit 1 to 20 times.

If no repetition range is specified, it defaults to "0...[??]" (zero to infinity).

The repetition unit consists of an expression that is similar to a clause expression, except that it cannot have clause expression operators AND, OR, ABSENT and cannot have a repetition statement (repetitions cannot be nested).

Tags are strings that are attached to sets of entities that match the meta-AE template in the query. This allows individual result sets to be extracted from the query result later on.

Tags are specified as a list of strings immediately after the meta-AE type expression:

q() \{ TypeA TAGGED"tag1" \}

q() \{ TypeA TAGGED "tag1",TAGGED "tag2",TAGGED "tag3" \}

[??] Some characters or strings that appear in the printed document are not easily representable using HTML.

Why not acquire a nicely bound hard copy?
Click here to return to the publication details or order a copy of this publication.

Contents Next section Index