NTT Tutorial

NTT is a lean, but expressive algebra that consists - besides the usual set operations - of five different operators only:

Extension
Relatives
Selection
Expansion
Tuples

The descriptions are followed by a few examples

In order to denote the syntax of the individual NTT operators we use the folowing EBNF: Non-terminals are written in italic letters, and terminals in bold face letters or as single `quoted' characters; the meta symbol `|' separates alternatives, `{x}' denotes 0, 1 or more occurrences of `x' and `[x]' denotes an optional `x'.

Set Operations

On the top level an NTT query consists of one or more objects sets which can be combined by the usual set operations:

  NttQuery ::= ObjSet `;'

  ObjSet ::= ObjSetTerm {SetOp ObjSetTerm}

  SetOp ::= union | `\'

  ObjSetTerm ::= ObjSetFactor {intersect ObjSetFactor} 

  ObjSetFactor ::= `(' ObjSet `)' 
                 | Operator 
                 | INPUT `[' NaturalConst `]' 
                 | `{' SingleObject `}' 

  SingleObject ::= `_' 
                 | `~' 
                 | Variable 
                 | SingleObject `/' ConcreteLinkname 
                 | Variable `@'

The expression `{' SingleObject `}' forms the set which consists only of the common root object (_), the home object(~) or the object denoted by Variable. To this end the variable Variable must be bound to the individual objects of a set in the query's outer part (see below). In addition the next case provides the possibility to navigate from such an object to another one via the following link (compare the relatives operator). The last case can be used to refer to the destination object of a link that is designated by Variable.
The expression INPUT[NaturalConst] indicates that an object set passed to NTT via the API is to be inserted at that position. Hence, the usage of this expression is not allowed via the interactive frontend.

Extension

By means of the operator Extension NTT computes all objects that have the indicated type or one of its subtypes:

  Operator ::= ext `(' TypeName `)'

Relatives

The purpose of the operator Relatives is the set-oriented navigation via so-called NTT link names. In contrast to the other NTT operators this operator is not denoted in the functional style `relatives(...)', but in a more comfortable infix-notation which is similar to UNIX path names. This notation is mere syntactic sugar to improve the readability of NTT expressions; it does not affect the algebraic character of the language:

  Operator ::= ObjSetFactor `/' Linkname [`^' Depth] 

  Depth ::= NaturalConst | `*'

The fact that the operator Relatives is not to be applied to a complex object set ObjSet but to an atomic object set ObjSetFactor means that the slash `/' has got a higher priority than the set operations have. To start navigation from a combination of sets, the corresponding complex set expression must be enclosed by parentheses. By means of the infix notation of the operator Relatives the writing of several navigations forms a UNIX-like path.
If the depth Depth is 1, the operator will deliver all objects which are reachable from at least one object of the input set via a link matching the NTT link name Linkname. The missing of the optional parameter Depth means a depth of 1. A depth of n means that the result objects are to be reachable by 1 to n navigations (via suitable links). The depth `*' does not limit the number of necessary navigations. So the operator fits for the search of iterative structures, e.g. lists.

An NTT link name is either a concrete link name - this corresponds to a PCTE link name - or a link name pattern:

  Linkname ::= ConcreteLinkname | LinknamePattern 

  ConcreteLinkname ::= [{ConcreteKey `.'} ConcreteKey] `.' TypeName

  LinknamePattern ::= {ArbitraryKey `.'} ArbitraryKey `.' TypeName
                    | `_.' TypeName

  ArbitraryKey ::= ConcreteKey | VagueKey

  ConcreteKey ::= NaturalConst | StringConst

  VagueKey ::= `['NaturalConst `..' [NaturalConst] `]' | RegularString

A link name pattern must contain at least one vague key attribute value! In the case of a key attribute of type natural this is a - probably unbounded - interval; in the case of a key attribute of type string this is a regular string, which contains at least one of the meta symbols `?' or `*'. The question mark represents exactly one character and the asterix represents any sequence of characters.

Selection

The operator Selection has the following syntax:

  Operator ::= select `(' Variable `:' ObjSet `,' Predicate `)'

The result of this operation is the set containing only those objects of ObjSet for which Predicate is true. Hence Predicate must be an expression which evaluates to a boolean value. In Predicate it is possible to refer to the corresponding object by Variable.

  Predicate ::=
              | Conjunction {or Conjunction} 

  Conjunction ::= Literal {and Literal} 

  Literal ::= SingleExpr 
            | not Literal 
            | QuantPred 
            | TypePred 
            | UserDefinedPred 

  SingleExpr ::= SingleValue
               | SingleValue SingleRelOp SingleValue
               | SingleValue in Collection
               | Collection CollectRelOp Collection

  SingleRelOp ::= `=' | `#' | `<' | `<=' | `>' | `>=' | like 

  CollectRelOp ::= `=' | `#' | subseteq

SingleValue has to evaluate to a boolean value itself in the first case, since there is no combination with any operator, according to the fact that the computation of Predicate within the select statement must result in a boolean value. The operands of the operator like must be of string type, the second one has to be a string constant containing meta symbols like in regular string keys for linkname patterns.

  SingleValue ::= Term {AddOp Term}

  AddOp ::= `+' | `-'

  Term ::= Factor {MulOp Factor}

  MulOp ::= `*' | `/'

  Factor ::= `(' Predicate `)' 
           | Const 
           | card `(' Collection `)' 
           | pick `(' Collection `)' 
           | FieldedVariable 
           | SingleAttrAccess 

  Const ::= NaturalConst | IntConst | FloatConst | StringConst  | BoolConst

In this way all logical and arithmetical operations can be used to build complex predicates. The syntax of the constants follows the usual conventions. String constants must be included in double quotes. card computes the cardinality, and pick delivers one (i.e. usually the only) element of a collection(see below).

  QuantPred ::= for all Variable in Collection `[' Predicate `]'
              |  exists Variable in Collection `[' Predicate `]'

The meaning of the quantified predicates should be clear. Collections will be described below.

  TypePred ::= type is TypeName

There is a formal restriction for type predicates to achieve an efficient computation: They must be homogeneous, which means that they can only be logically combined with other type predicates. In this special case the Variable and the following `:' may be omitted in the corresponding select statement. Otherwise type predicates always refer to the Variable of the select statement.

  UserDefinedPred ::= PRED `[' NaturalConst `]' `(' VarList `)'

  VarList ::= Variable {Variable}

With user defined predicates NTT provides the very powerful possibilty to use self-programmed routines, which e.g. can compare multi media documents etc. The usage of user defined predicates is not possible via the interactive frontend.
The predicates have to be passed to NTT as an array of functions of the signature defined in the C-API/NTT's header file. So the index is used to access the different predicates. Furthermore it is possible to control the routine calls with a further parameter which can be passed to NTT in a second array, whose n-th entry is used as parameter when the n-th predicate function is called.
In NTT's Java Interface the functionality ist not supported yet.

  FieldedVariable ::= Variable [`:' Name]

A Factor can be simply a variable. If a variable designates a link, then an applied attribute can be accessed via `:' and the attribute name.

  SingleAttrAccess ::= SingleAttr `(' SingleSource `)'

  SingleAttr ::= Name
               | ConcreteLinkname [`!'] [`:' Name]

  SingleSource ::= SingleObject 
                 | pick `(' ObjSet `)'

A single attribute access is the access of an attribute at a certain object or at one of its outgoing or incoming links, resp. the link itself. An outgoing link is denoted as a concrete link; an incoming link is denoted by its reverse outgoing link and the symbol `!'. The attribute access is done like at FieldedVariable.

  Collection ::= ObjSet | SetAttrAccess 

  SetAttrAccess ::= SingleAttr `(' MultipleSource `)'
                  | SetAttr `(' SingleSource `)'
                  | SetAttr `(' MultipleSource `)'

  SetAttr ::= LinknamePattern [`!'] [`:' Name]

  MultipleSource ::= ObjSet

A collection is a set of objects or links, or it is a multiset if it consists of atomic values. A multiset is the result of a set attribute access which is similar to a single attribute access but has a set-valued result.

Expansion

By using the operator Expansion it is possible to attach virtual attributes or virtual links at objects.

  Operator ::= expand `(' Variable `:' ObjSet `,' Name `<-' SingleExpr `)'

The atomic value to which SingleExpr evaluates is applied as virtual attribute Name to each object in ObjSet. The respective object can be refered to in SingleExpr by Variable.

  Operator ::= expand `(' Variable `:' ObjSet `,' Name `<-' ObjSet `)'

In this way for each object in the first ObjSet a second ObjSet is computed and virtual links of type Name are drawn to all objects in those set. Such virtual links have no specified key attributes, hence only `_' can be used as key for them. Similarly to the first case it is possible to refer to the respective object by Variable.

Tuples

The operator Tuples is used to convert a set of objects into a tabular representation which can be shown on some output medium.

  Operator ::= tuples `('ObjSet {`,' Attribute} `)'

  Attribute ::= Name
              | ConcreteLinkname [`!'] `:' Name
              | LinknamePattern  [`!'] `:' Name

At least one attribute has to be given! The delivered table consists of one column for each Attribute, and one row for each object in ObjSet. If a simple name is given as Attribute, the attribute of the corresponding object is printed. If the attribute name is preceded by a concrete linkname and `:', it designates an attribute of the corresponding outgoing link, resp. of its reverse, if `!' is used. By analogy a linkname pattern produces a collection of attribute values instead of a single value.

Some Usage Examples

These example queries should be a little help to formulate queries with NTT. They are based on the standard SDS's of (H-)PCTE.

```
  ext(user_group);
```
Computes all existing user groups in the repository.

  select(P:ext(process), process_priority(P) < 2);

Computes all processes with a priority less than 2.

```
  select(P:ext(process), 
           exists CP in {P}/_.child_process
                  [ process_termination_status(CP) = 0 ]);
```
Computes all processes having a child process with termination status 0.
(Rem.: To use navigation with link patterns, P must be converted to a set by {P}.)

  tuples(expand(P:ext(process), 
                parent_start_time <- process_start_time(P/.parent_process)),
         process_start_time, parent_start_time);

Prints the start times of all processes together with the start time of their respective parent process.