連結型パターンマッチング（ベータバージョン）

連結型パターンマッチングとは？

ここまで、FROM句にある1つのパスのパターンをマッチングすることについて説明してきました。このセクションでは、1つのFROM句にある複数のパターンのマッチングが可能なGSQLの機能について説明します。この拡張機能は、クエリがパターンの連結（論理積AND）を求めるので、連結型パターンマッチング（CPM）と呼ばれます。CPMでは、すべてのパターンが一致するときにマッチが成立し、パターン相互に関係性がある場合もあります。パターンは互いに交差しあう線によって形成されていると視覚的にイメージできます。TigerGraph 3.0のベータ機能として導入されたCPMは、複雑なパターンを単独のクエリブロックで簡潔に表現できる手法です。

一般的に、CPMのクエリブロックは、複数のパターンのあるFROM句によって構成されていて、次のような構成になります。

# 連結型パターンマッチングの構文

SelectBlock := SELECT alias
               FROM pattern
               [sampleClause]
               [whereClause]
               [ [perClause] accumClause]
               [postAccumClause]*
                    ...

pattern := vertexPattern | edgePattern | (pathPattern ["," pathPattern])
# vertexPattern と edgePattern は従来のGSQLを使っています

以下、句の種類別に説明します。

SELECT句

SELECT句は、FROM句にあるすべてのパターンから、ただ1つの頂点エイリアスを選択します。

FROM句 - 連結型マッチング

連結型マッチングの式はFROM句に記述します。FROM句には、パスのパターンがカンマで区切られたリストとして記述されていますが、各パターンが下地にあるグラフデータに照合されてマッチテーブルが生成されます。2つのパターンに共通の頂点エイリアスがある場合、双方のマッチテーブルが自然に結合されます。

例えば、次のCPMの場合、

FROM X:x - (E1:e1) - Y:y - (E2>:e2) - Z:z,
     Z:z - (E3:e3) - U:u - (E4>:e4) - V:v

最初のパターンの変数はx、e1、y、e2、zです。2つ目のパターンの変数はz、e3、u、e4、vです。この2つのパターンを別々に考慮すると、次のマッチテーブルのスキーマが生成されます。

#1番目のマッチテーブル
(x, e1, y, e2, z)
#2番目のマッチテーブル
(z, e3, u, e4, v)

マッチテーブルの自然結合

マッチテーブルの自然結合では、双方のテーブルのすべての共有頂点エイリアスを比較します。その結果得られた結合テーブルには、すべての非共有変数が含まれ、さらに共有されている頂点変数が1回ずつ含まれています。次が上のCPMのマッチテーブルです。

#自然結合の結果、共有されている頂点のエイリアスzは1回表示されています
(x, e1, y, e2, z, e3, u, e4, v)

有効な連結型パターン

連結型パターンマッチングのマッチテーブルは、すべてのパターンのマッチテーブルを自然結合したものです。CPMマッチテーブルの行は、同時にすべてのマッチテーブルと一致しなければならないように設計されています。

FROM句に記述されているパターンのマッチテーブルが1つの表に自然結合できる場合、FROM句に入力されている内容はCPMに有効です。できない場合には、FROM句に入力されているパターンのリストは無効です。

例えば、次に有効なCPMのための入力の例を2つと、無効な例を1つ示します。

# 2つのパターンが:tgtで自然結合するので、CPM有効
SELECT
FROM Person:p - (KNOWS) - :tgt,
     Post:s -(<LIKES) - :tgt

# f2つのパターンが:fで自然結合するので、CPM有効
SELECT
FROM Person:p - (KNOWS) - :f - (LIKES>) - Post:tgt,
     :f - (LIKES>) - Comment:c

# 2つのパターンには頂点変数を共有していないので、CPM無効
# これらは自然結合できません
# 片方のパターンには (p, tgt) があり、もう片方には (s, t) があります
SELECT
FROM Person:p - (KNOWS) - :tgt,
     Post:s - (<LIKES) - Person:t

WHERE句

WHERE節の述部は、あらゆるパターンのあらゆる頂点エイリアス、エッジエイリアスを使うことができ、パターンを構成するパスの変数を組み合わせる述部を使うこともできます。CPMクエリは、WHERE述部に対して特別の制限を設けていません。しかし、パフォーマンスの観点から言えば、距離が影響要因となります。ローカルな条件は、パス横断またはパス内で近距離の場合、より早く解決できるのでスピードも速くなります。

次の例にある x2.age > x4.age は、パスを横断する述部で、 e1.timestamp < e3.timestamp もパスを横断する述部です。一方、 x1.gender == x4.gender は2つ目のパターンのローカルな述部です。

FROM X1:x1-(E1:e1)-X2:x2-(E2:e2)-X3:x3,
     X1:x1-(E3:e3)-X4:x4
WHERE x2.age > x4.age AND e1.timestamp < e3.timestamp AND x1.gender == x4.gender

ACCUM句

CPMブロック内のすべての頂点変数にACCUMを使うことができます。

ACCUM節は、CPMマッチテーブルで（マッチする）行数の回数だけ実行されることがデフォルト設定です。実行は、マッチテーブルの1行毎に行われます。

CPMパターンにある3つの頂点変数にACCUMを実行

#x1、x2、x4に対する積算処理
FROM X1:x1-(E1:e1)-X2:x2-(E2:e2)-X3:x3,
     X1:x1-(E3:e3)-X4:x4
ACCUM x1.@cnt +=1, x2.@cnt += x3.quantity, x4.@cnt += x3.quantity

POST-ACCUM句

CPMのPOST-ACCUMは、単独パスのパターンの場合と同じように動作します。つまり、各POST-ACCUM節は1つの頂点エイリアスを照会でき、その頂点セットに対して（例えば、マッチテーブル内の頂点列毎に）反復して実行されます。POST-ACCUMの命令文は、ACCUM句で計算された、集約されたアキュムレータの結果にアクセスすることができます。クエリには、作業の対象となる頂点エイリアス毎にPOST-ACCUM句を入れて、複数のPOST-ACCUM句を使うことができます。複数あるPOST-ACCUM句は並列に処理されるので、POST-ACCUM句の作成の順番はかまいません。（結合毎に、句内の命令文が順番に実行されていきます。）

次の例にはPOST-ACCUM句が3つあります。最初の句はx1内で反復されていくので、x1毎に、@@cnt += x1.@cntが実行されます。2つ目と3つ目のPOST-ACCUM句は、各々x2とx3内で反復され、そこで得られたアキュムレータ@cntの値が@@cntに積算されます。

CPMの頂点変数3つを使って、グローバルアキュムレータ@@cntにPOST-ACCUMを実行

FROM X1:x1-(E1:e1)-X2:x2-(E2:e2)-X3:x3,
     X1:x1-(E3:e3)-X4:x4
ACCUM x1.@cnt +=1, x2.@cnt += x3.quantity, x4.@cnt += x3.quantity
POST-ACCUM @@cnt += x1.@cnt
POST-ACCUM @@cnt += x2.@cnt
POST-ACCUm @@cnt += x3.@cnt;

例

例1. Viktor Akhiezerが好きな（100日以上前に作成された）メッセージの内、作者の姓がSで始まるものを求め、メッセージが投稿されたサイトを出力する。

USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  SumAccum<int> @@cnt;

  F  =  SELECT f
        FROM Person:s - (LIKES>:e1) - :msg - (HAS_CREATOR>) - Person:t,
             Forum:f - (CONTAINER_OF>:e2) - :msg
        WHERE s.firstName == "Viktor" AND s.lastName == "Akhiezer"
              AND t.lastName LIKE "S%"
              AND e1.creationDate >DATETIME_ADD(msg.creationDate, INTERVAL 100 DAY);

  PRINT F;
}

#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"F": [{
    "v_id": "962072688797",
    "attributes": {
      "id": 962072688797,
      "title": "Album 12 of Mario Santos",
      "creationDate": "2011-04-12 09:36:50"
    },
    "v_type": "Forum"
  }]}]
}

例2. Viktor Akhiezerが好きな投稿の作者の内、姓がSで始まる人を求める。そして各作者の国を求めて出力する。

USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {

  SumAccum<int> @@cnt;

  C  =  SELECT ctry
        FROM Person:s - (LIKES>:e1) - Post:msg - (HAS_CREATOR>) - Person:t,
             :t - (WORK_AT>:e2) - Company:c,
             :c - (IS_LOCATED_IN>) - Country:ctry
        WHERE s.firstName == "Viktor" AND s.lastName == "Akhiezer"
              AND t.lastName LIKE "S%" ;

  PRINT C;
}

#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"C": [{
    "v_id": "93",
    "attributes": {
      "name": "Portugal",
      "id": 93,
      "url": "http://dbpedia.org/resource/Portugal"
    },
    "v_type": "Country"
  }]}]
}

例3. TagClassと国を条件として入力し、その国で作られたすべてのサイトの中から、そのTagClassに直属するタグのある投稿が少なくとも1件あるサイトを求める。サイトの所在地は、サイトのモデレーターの所在地とする。

USE GRAPH ldbc_snb

DROP QUERY bi_4

CREATE QUERY bi_4(string tcName, string cName) for graph ldbc_snb syntax v2 {
  SetAccum<vertex<Post>> @postSet;
  SumAccum<int> @personId, @postCount;

  ForumSet =
    SELECT f
    FROM Forum:f -(HAS_MODERATOR>)- Person:a -(IS_LOCATED_IN>.IS_PART_OF>)- Country:c,
         :f -(CONTAINER_OF>)- Post:p -(HAS_TAG>.HAS_TYPE>)- TagClass:tc
    WHERE c.name == cName and tc.name == tcName
    ACCUM f.@personId = a.id, f.@postSet += p
    POST-ACCUM f.@postCount = f.@postSet.size(), f.@postSet.clear()
    ORDER BY f.@postCount DESC, f.id ASC
    LIMIT 3;

  PRINT ForumSet[ForumSet.id, ForumSet.title, ForumSet.creationDate,
                 ForumSet.@personId, ForumSet.@postCount];
}

INSTALL QUERY bi_4

RUN QUERY bi_4("MusicalArtist", "Burma")

#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"ForumSet": [
    {
      "v_id": "81903",
      "attributes": {
        "ForumSet.title": "Wall of Donald Steele-Perkins",
        "ForumSet.@personId": 5226,
        "ForumSet.id": 81903,
        "ForumSet.@postCount": 65,
        "ForumSet.creationDate": "2010-02-15 06:48:04"
      },
      "v_type": "Forum"
    },
    {
      "v_id": "137438953686",
      "attributes": {
        "ForumSet.title": "Wall of Eric Law-Yone",
        "ForumSet.@personId": 2199023262994,
        "ForumSet.id": 137438953686,
        "ForumSet.@postCount": 65,
        "ForumSet.creationDate": "2010-04-25 22:10:32"
      },
      "v_type": "Forum"
    },
    {
      "v_id": "687194810508",
      "attributes": {
        "ForumSet.title": "Wall of Hector Hugh Michie",
        "ForumSet.@personId": 10995116283784,
        "ForumSet.id": 687194810508,
        "ForumSet.@postCount": 39,
        "ForumSet.creationDate": "2010-12-19 15:33:30"
      },
      "v_type": "Forum"
    }
  ]}]
}

例4. 入力された国について、次のような3人組のセットを探し、一意化された個別のセット数を求める。

a は b の友人
b は c の友人
c は a の友人

「一意化された個別のセット」とは、ある3つの頂点が結果に1回でてきた場合、それ以上繰り返して結果に出力されず、1回しか表示されないということです。KNOWSは無向性の関係性なので、3つの頂点はどのような順番で並べてもかまいません。

USE GRAPH ldbc_snb

CREATE QUERY bi_17(string cName) FOR GRAPH ldbc_snb SYNTAX v2 {
  TYPEDEF TUPLE <uint a, uint b, uint c> triplet;
  SetAccum<triplet> @@tripletSet;
  SumAccum<int> @@tripletCount;

  C =
    SELECT c
    FROM Country:c -(<IS_PART_OF.<IS_LOCATED_IN)- Person:p1,
         :c -(<IS_PART_OF.<IS_LOCATED_IN)- Person:p2,
         :c -(<IS_PART_OF.<IS_LOCATED_IN)- Person:p3,
         :p1 -(KNOWS)- :p2 -(KNOWS)- :p3 -(KNOWS)- :p1
    WHERE c.name == cName AND p1.id < p2.id AND p2.id < p3.id
    ACCUM @@tripletSet += triplet(p1.id, p2.id, p3.id);

  @@tripletCount = @@tripletSet.size();
  @@tripletSet.clear();
  PRINT @@tripletCount;
}


INSTALL QUERY bi_17

RUN QUERY bi_17("Spain")

#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@tripletCount": 242}]
}

その他の例： LDBC-SNB のBIとICのクエリをCPMで解釈したものを、githubで共有しました。CPMのクエリはこちらからご覧ください。ほとんどのクエリは関数としてインストールされています。関数で使われているサンプルのパラメーターはこちらにあります。

ソース頂点セットの柔軟性

パターンマッチングの説明で最初に説明したように、 1ホップのパターンでは、ソースとなる（最も左に置く）頂点セットは、頂点タイプでも、タイプの交互指定でも有効で、また省略することもできます。

例1. Viktor Akhiezerが大好きな作者の内、姓がSで始まる人の数を求める。

USE GRAPH ldbc_snb

#頂点タイプ「Person」から始めます
INTERPRET QUERY () SYNTAX v2 {

  SumAccum<int> @@cnt;

  F  =  SELECT t
        FROM Person:s -(LIKES>:e1)- :msg -(HAS_CREATOR>)- Person:t
        WHERE s.firstName == "Viktor" AND s.lastName == "Akhiezer"
              AND t.lastName LIKE "S%"
        POST-ACCUM @@cnt+=1;

  PRINT  @@cnt;

}
#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@cnt": 8}]
}

例2. 例 1と同じクエリですが、頂点タイプで始めていません。GSQLのコンパイラーが:sのタイプを推測することができます。

USE GRAPH ldbc_snb

#始めと終わりのエンドポイントに頂点タイプのないパターン
INTERPRET QUERY () SYNTAX v2 {

  SumAccum<int> @@cnt;

  F  =  SELECT t
        FROM :s -(LIKES>:e1)- :msg -(HAS_CREATOR>)- :t
        WHERE s.firstName == "Viktor" AND s.lastName == "Akhiezer" AND t.lastName LIKE "S%"
        POST-ACCUM @@cnt+=1;

  PRINT  @@cnt;

}
#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@cnt": 8}]
}

例3. LIKESのエッジ数を求める。

USE GRAPH ldbc_snb

# 情報なしで始まるパターン
INTERPRET QUERY () SYNTAX v2 {

  SumAccum<int> @@cnt;

  F  =  SELECT msg
        FROM  -(LIKES>:e1)- :msg
        ACCUM @@cnt+=1;

  PRINT  @@cnt;

}
#結果
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@cnt": 2190095}]
}