Repeating a 1-Hop Pattern

A common pattern is the two-step "Friend of a Friend".

This is related to the question "Do I know any famous people?" Even if you aren’t friends with any famous people, at least one of your friends' friends might be famous. That’s a one-hop pattern, repeated twice.

In terms of data throughput on a network, you can also ask "If everyone who receives a message passes it along to everyone else they know, how many entities will receive it?"

GSQL pattern matching makes it easy to express such variable-length patterns which repeat a single hop. Everything else stays the same as introduced in the previous section, except we append an asterisk (or Kleene star) and an optional min..max range to an edge pattern.

  • (E*) means edge type E repeats any number of times (including zero)

  • (E*1..3) means edge type E occurs one to three times.

Below are more illustrative examples:

  • 1-hop star pattern — repetition of an edge pattern 0 or more times

    1. FROM X:x -(E*)- Y:y

    2. FROM X:x -(F>*)- Y:y

    3. FROM X:x -(<G*)- Y:y

    4. FROM X:x -(_*)- Y:y

      • Any undirected edge can be chosen at each repetition.

    5. FROM X:x -(_>*)- Y:y

      • Any right-directed edge can be chosen at each repetition.

    6. FROM X:x -(<_*)- Y:y

      • Any left-directed edge can be chosen at each repetition.

    7. FROM X:x -((E|F>|<G)*)- Y:y

      • Either E, F> or <G can be chosen at each repetition.

  • 1-hop star pattern with bounds

    1. FROM X:x -(E*2..)- Y:y

      • Lower bounds only. There is a chain of at least 2 E edges.

    2. FROM X:x -(F>*..3)- Y:y

      • Upper bounds only. There is a chain of between 0 and 3 F edges.

    3. FROM X:x -(<G*3..5)- Y:y

      • Both Lower and Upper bounds. There is a chain of 3 to 5 G edges.

    4. FROM X:x -((E|F>|<G)*3)- Y:y

      • Exact bound. There is a chain of exactly 3 edges, where each edge is either E, F>, or <G.

Remarks

No alias allowed for edge with Kleene star

An edge alias may not be used when a Kleene star is used. The reason is that when there are a variable number of edges, we cannot associate or bind the alias to a specific edge in the pattern.

Shortest path semantics

When an edge is repeated with a Kleene star, only the shortest matching occurrences are selected. See the example below:

Figure 2 Shortest Path Illustration.

In Figure 2, or Pattern 1 -(E>*)- 4, any of the following paths reach 4 from 1.

  • 1→2→3→4

  • 1→2→3→5→6→2→3→4

  • any path that goes through the cycle 2→3→5→6→2 two or more times and jumps out at 3.

The first path is shorter than the rest; it is considered the only match.

Examples of Variable Hop Queries

In this tutorial, we will use the Interpreted Mode for GSQL so that we can skip the INSTALL step and run a query as soon as we create it. These one-step interpreted queries are unnamed (anonymous) and parameterless.

You can copy any of the shown GSQL scripts to a file with the file extension .gsql and invoke it in a Linux shell to see the results.

Linux Bash
gsql example.gsql

Example 1

Find the direct or indirect superclass (including the self class) of the tag_class whose name is "TennisPlayer".

Example 1. Directed Edge Pattern Unconstrained Repetition
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  tag_class1 =  SELECT t
               FROM Tag_Class:s - (Is_Subclass_Of>*) - Tag_Class:t
               WHERE s.name == "TennisPlayer";

    PRINT  tag_class1;
}

Note below that the starting vertex s, whose name is TennisPlayer, is also a match, using a path with zero hops.

Output of Example 1
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"tag_class1": [
    {
      "v_id": "211",
      "attributes": {
        "name": "Person",
        "id": 211,
        "url": "http://dbpedia.org/ontology/Person"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "239",
      "attributes": {
        "name": "Agent",
        "id": 239,
        "url": "http://dbpedia.org/ontology/Agent"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "0",
      "attributes": {
        "name": "Thing",
        "id": 0,
        "url": "http://www.w3.org/2002/07/owl#Thing"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "149",
      "attributes": {
        "name": "Athlete",
        "id": 149,
        "url": "http://dbpedia.org/ontology/Athlete"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "59",
      "attributes": {
        "name": "TennisPlayer",
        "id": 59,
        "url": "http://dbpedia.org/ontology/TennisPlayer"
      },
      "v_type": "Tag_Class"
    }
  ]}]
}

Example 2

Find the immediate superclass of the tag_class whose name is "tennis_player". (This is equivalent to a 1-hop non-repeating pattern.)

Example 2. Exactly 1 Repetition of A Directed Edge
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

    tag_class1 =  SELECT t
        FROM Tag_Class:s - (Is_Subclass_Of>*1) - Tag_Class:t
        WHERE s.name == "TennisPlayer";

    PRINT tag_class1;
}
Output of Example 2
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"tag_class1": [{
    "v_id": "149",
    "attributes": {
      "name": "Athlete",
      "id": 149,
      "url": "http://dbpedia.org/ontology/Athlete"
    },
    "v_type": "Tag_Class"
  }]}]
}

Example 3

Find the 1 to 2 hops direct and indirect superclasses of the tag_class whose name is "TennisPlayer".

Example 3. 1 to 2 Repetition Of A Directed Edge.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  tag_class1 =  SELECT t
               FROM Tag_Class:s - (Is_Subclass_Of>*1..2) - Tag_Class:t
               WHERE s.name == "TennisPlayer";

    PRINT  tag_class1;
}
Output of Example 3
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"tag_class1": [
    {
      "v_id": "211",
      "attributes": {
        "name": "Person",
        "id": 211,
        "url": "http://dbpedia.org/ontology/Person"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "149",
      "attributes": {
        "name": "Athlete",
        "id": 149,
        "url": "http://dbpedia.org/ontology/Athlete"
      },
      "v_type": "Tag_Class"
    }
  ]}]
}

Example 4

Find the superclasses within 2 hops of the tag_class whose name is "TennisPlayer".

Example 4. Up-to 2 Repetition Of A Directed Edge.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  tag_class1 =  SELECT t
               FROM Tag_Class:s - (Is_Subclass_Of>*..2) - Tag_Class:t
               WHERE s.name == "TennisPlayer";

    PRINT  tag_class1;
}
Output of Example 4
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"tag_class1": [
    {
      "v_id": "211",
      "attributes": {
        "name": "Person",
        "id": 211,
        "url": "http://dbpedia.org/ontology/Person"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "149",
      "attributes": {
        "name": "Athlete",
        "id": 149,
        "url": "http://dbpedia.org/ontology/Athlete"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "59",
      "attributes": {
        "name": "TennisPlayer",
        "id": 59,
        "url": "http://dbpedia.org/ontology/TennisPlayer"
      },
      "v_type": "Tag_Class"
    }
  ]}]
}

Example 5

Find the superclasses at least one hop from the tag_class whose name is "TennisPlayer".

Example 5. At Least 1 Repetition Of A Directed Edge.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  tag_class1 =  SELECT t
               FROM Tag_Class:s - (Is_Subclass_Of>*1..) - Tag_Class:t
               WHERE s.name == "TennisPlayer";

    PRINT  tag_class1;
}
Output of Example 5
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"tag_class1": [
    {
      "v_id": "211",
      "attributes": {
        "name": "Person",
        "id": 211,
        "url": "http://dbpedia.org/ontology/Person"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "239",
      "attributes": {
        "name": "Agent",
        "id": 239,
        "url": "http://dbpedia.org/ontology/Agent"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "0",
      "attributes": {
        "name": "Thing",
        "id": 0,
        "url": "http://www.w3.org/2002/07/owl#Thing"
      },
      "v_type": "Tag_Class"
    },
    {
      "v_id": "149",
      "attributes": {
        "name": "Athlete",
        "id": 149,
        "url": "http://dbpedia.org/ontology/Athlete"
      },
      "v_type": "Tag_Class"
    }
  ]}]
}

Example 6

Find the 3 most recent comments that are liked or created by Viktor Akhiezer and the total number of comments liked or created by the same person.

Example 6. Disjunctive 1-Repetition Directed Edge.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2{
  SumAccum<INT> @@comment_cnt = 0;

  // find top 3 latest comments that is liked or created by Viktor Akhiezer
  // and the total number of comments related to Viktor Akhiezer
  top_3_comments = SELECT p
                 FROM Person:s - ((<Has_Creator|Likes>)*1) - Comment:p
                 WHERE s.first_name == "Viktor" AND s.last_name == "Akhiezer"
                 ACCUM @@comment_cnt += 1
                 ORDER BY p.creation_date DESC
                 LIMIT 3;

  PRINT top_3_comments;
  // total number of comments related to Viktor Akhiezer
  PRINT  @@comment_cnt;
}
Output of Example 6
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [
    {"top_3_comments": [
      {
        "v_id": "2061584720640",
        "attributes": {
          "browser_used": "Chrome",
          "length": 4,
          "location_ip": "194.62.64.117",
          "id": 2061584720640,
          "creation_date": "2012-09-06 06:46:31",
          "content": "fine"
        },
        "v_type": "Comment"
      },
      {
        "v_id": "2061590804929",
        "attributes": {
          "browser_used": "Chrome",
          "length": 83,
          "location_ip": "194.62.64.117",
          "id": 2061590804929,
          "creation_date": "2012-09-04 16:16:56",
          "content": "About Muttiah Muralitharan, mit by nine degrees, five degrees being thAbout Steve M"
        },
        "v_type": "Comment"
      },
      {
        "v_id": "2061586872389",
        "attributes": {
          "browser_used": "Chrome",
          "length": 90,
          "location_ip": "31.216.177.175",
          "id": 2061586872389,
          "creation_date": "2012-08-28 14:54:46",
          "content": "About Hector Berlioz, his compositions Symphonie fantastique and GraAbout Who Knew, the gu"
        },
        "v_type": "Comment"
      }
    ]},
    {"@@comment_cnt": 152}
  ]
}