Download Φ License Φ Forum Φ Team Φ Home

Model Analysis with ConceptBase

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