Download Φ License Φ Forum Φ Team Φ Home

* Query classes* are the facility to combine the class view of ConceptBase
with logical expressions for class membership. Such query classes can be used
to analyze models for finding errors but also to define new concepts from existing ones.
Consider for example networked organizations where units are communicating
with other units. A *hub unit* is then a unit that receives information from
at least two units and sends information to at least two other units. In ConceptBase,
one would define this concept as a query class:

HubUnit in QueryClass isA Unit with constraint c1 : $ (#ToUnit[this] >= 2) and (#FromUnit[this] >= 2) $ end

The hub unit query class is a subclass of unit. It has those units as instances that fulfill the membership constraint. The instances of hub unit are displayed in a user-definable graphical type. The classification of objects into the query classes is dynamic. For example, if object o1 would get one more incoming link, then it would also be classified as a hub unit (and change its graphical display).

As a second example, consider a network of nodes connected to each other, e.g. cities connected by flight connections or concepts connected in a diagram. A widely used metric for such networks is the length of the shortest path between two nodes. ConceptBase can compute the length of the shortest path as a recursive function definition:

sp in Function isA Integer with parameter x: Node; y: Node constraint csp: $ (x=y) and (this=0) or (x nexttrans y) and (x <> y) and (this = MIN(spSet[x,y])+1) $ end spSet in GenericQueryClass isA Integer with parameter x: Node; y: Node constraint csps: $ exists x1/Node (x next x1) and (this=sp(x1,y)) $ end

The first definition states that the shortest path between x and y is 0 if x=y. Otherwise, it is the minimum of the lengths of the shortest paths between successors of x and y plus 1, provided that x and y are connected to each other (nexttrans). The second definition returns the lengths of the shortest paths between successors of x and y.

The example screendump shows the application of the shortest path definition to flight connections. The start/end nodes are displayed by the blue nodes, nodes on the shortest path are displayed in yellow. The graphical type is derived by a rule formulated in terms of the concepts of shortest paths. In this case, there are three nodes that lie on a shortest path between Amsterdam and Wangerooge.

As third example, consider the NIM-Game. Two players can take 1, 2, or 3 matches from an initial set of 13 matches. The player confronted with zero matches looses. So, is 13 a win position? First, we define the class position as follows:

Position in Class isA Integer with attribute moveTo: Position rule r1: $ (0 in Position) $; r2: $ forall p/Position p1/Integer (p < 13) and (p1=p+1) ==> (p1 in Position) $; take1: $ forall p1,p2/Position (p2=p1-1) ==> (p1 moveTo p2) $; take2: $ forall p1,p2/Position (p2=p1-2) ==> (p1 moveTo p2) $; take3: $ forall p1,p2/Position (p2=p1-3) ==> (p1 moveTo p2) $ end

Hence, the numbers 0 to 13 are allowed positions. Each move takes 1, 2 or 3 matches. This completely defines the NIM game. But how can we compute the win positions? A recursive query 'Win' does the job:

Win in QueryClass isA Position with constraint c: $ exists y/Position (~this moveTo y) and not (y in Win) $ end Loose in QueryClass isA Position with constraint c : $ not (~this in Win) $ end

The query 'Loose' is the relative complement of 'Win'.
The query 'Win' uses negation over recursion. As a consequence, it is not statically
stratified. However, the graph of possible moves is acyclic. So, the
inner predicate `(y in Win)` is always having an argument y that is strictly
smaller than the argument `~this`.
The graph shows that 13 is indeed a win position. The loosing positions are exactly
0, 4, 8, and 12. This is computed with just the above generic definition
of Win.
The Telos sources are also available from the
CB-Forum.

Recursive queries like Win are very expressive. Formally, the use of numbers and arithmetics breaks the Datalog borders. One can however replace the numbers by 13 objects and code the possible moves by hand to return to the strict Datalog world.

http://conceptbase.cc --
Contact:
M. Jeusfeld,
University of Skövde, Box 408, S-54128 Skövde, Sweden

2017-09-29/M.Jeusfeld