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
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
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
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
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.
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.
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).
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.
A query can only specify one result construction rule at a time.
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.
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.
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.
Clients access the compiler by initializing a Query object with a TQL string.
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: '|'
name(parameters) \{body bgcolor="#FFFFFF"\}
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.
The query body bgcolor="#FFFFFF" is an expression of clauses.
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 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
Tags are indicated in the keyword TAGGED.
Roles
are explained in
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.
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.
TypeA-TypeB-TypeC
TypeA-(TypeB AND TypeC)
(TypeA AND TypeB)-(TypeC OR TypeD)
TypeA | TypeB-TypeC & TypeD
A meta-association is placed between clause expressions:
clausexpr-clausexpr
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 \}
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:
MetaAE<roletype>
<roletype>MetaAE
<roletype>MetaAE<roletype>
For instance, a query, "Clients and Servers in the NetWare relationship":
q() \{ Computer<client>-NetWare-<server>Computer \}
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.
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:
q(x) \{ parent(x)-Located \{ loc \} Location
AND grandparent(x)-Located- \{ loc \}Location \}
parent(x) \{ x<child>-Family-<parent>head,tail Person \}
grandparent(y)\{ parent(parent(x)) \}
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.
<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)) \}
Square brackets define the repetition unit:
q() \{ TypeA-TypeB[1..20, TypeC-TypeD-]TypeE \}
In a list of one or more clauses, such as:
clause-clause-clause-clause-clause
a repetition unit may be placed starting at a clause and ending at a meta-association:
clause-[clause-clause-]clause-clause
or starting at a meta-association and ending at a clause:
clause[-clause-clause]-clause-clause
The smallest repetition unit is one of the following:
[clause-]clausexpr
clausexpr[-clause]
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 specified as a list of strings immediately after the meta-AE type expression:
q() \{ TypeA TAGGED "tag1",TAGGED "tag2",TAGGED "tag3" \}
q() \{ TypeA TAGGED"tag1" \}
[??] Some characters or strings that appear in the printed document are not easily representable using HTML.
| Contents | Next section | Index |