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:

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}
  ]
}