Recursive query in GRAQL?

Question

Is there a way to define a recursive query in GRAQL, i.e. to match a pattern where an exact predicate path between entities is unknown (for example, how many of them)?

SPARQL added support for these in 1.1 version. Example from the Apache Jena Documentation:

# Find the types of :x, following subClassOf
SELECT *
{
   :x  rdf:type/rdfs:subClassOf*  ?t
}

CYPHER also allows them from its inception. Example:

MATCH (alice:Person { name:"Alice" })-[:friend *1..2]->(friend:Person)
RETURN friend.name;

Is it possible to do something similar in GRAQL?

Answer 1

It is possible to achieve this in Graql, using Grakn's reasoning engine.

Graql match queries don't support a looping query syntax (yet, but it is planned), but you can define recursive logic in Grakn using a rule. To achieve recursion there should be a rule which contains in its when something of the same type as is inferred in a rule's then.

In Graql this exact friend example goes as follows. This example doesn't use recursion as we are only looking for 1 or 2-hop looping.

First you need a schema:

define

name sub attribute, value string;

person sub entity,
  has name,
  plays friend;

friend sub relation,
  relates friend;

If this is your starting schema you'll need to extend it as follows to add recursion in a new n-degree-friendship relation:

define

friend-of-a-friend isa relation,
  relates connected-friend;

person sub entity,
  plays connected-friend;

infer-friend-of-a-friend sub rule,
when {
  (friend: $p1, friend: $p2) isa friendship;
  (friend: $p2, friend: $p3) isa friendship;
}, then {
  (connected-friend: $p1, connected-friend: $p3) isa friend-of-a-friend;
};

Then you can query for friends connected by any number of friendship relations as:

match $p1 isa person, has name "John"; 
$p2 isa person, has name $n;
{ (connected-friend: $p1, connected-friend: $p2) isa friend-of-a-friend; } 
or { (friend: $p1, friend: $p2) isa friendship; };
get $n;

This friend example isn't recursive, but it can be extended to be recursive. What Grakn cannot currently support is the number of times to loop.

We can see a great example of recursion in the subClassOf example though:

define

class sub entity,
  plays subclass,
  plays superclass;

class-hierarchy sub relation,
  relates subclass,
  relates superclass;

class-hierarchy-is-recursive sub rule,
when {
  (subclass: $c1, superclass: $c2) isa class-hierarchy;
  (subclass: $c2, superclass: $c3) isa class-hierarchy;
}, then {
  (subclass: $c1, superclass: $c3) isa class-hierarchy;
};

Then match to find all subclasses of x:

match $x isa class; 
$y isa class; 
(superclass: $x, subclass: $x) isa subclass;
get $y;