Spanner Graph におけるグラフ要素の同一性について

Spanner Graph においては、 CREATE PROPERTY GRAPH で明示的もしくは暗黙的にキーはノード、エッジのスキーマの一部として扱われます。
これらのキーはグラフ要素を一意に識別するために使用され、グラフ要素の同一性判定の基盤となります。
この記事では Spanner Graph におけるグラフ要素の同一性判定について、具体的な例を交えながら解説します。

全てのグラフ要素はアイデンティティが保証される

Spanner Graph における CREATE PROPERTY GRAPH 文の要素の定義は次のようなものになっています。

https://cloud.google.com/spanner/docs/reference/standard-sql/graph-schema-statements#element_definition

element:
  element_name
  [ AS element_alias ]
  [ element_keys ]
  [ { label_and_properties_list | element_properties } ]

element_keys:
  { node_element_key | edge_element_keys }

node_element_key:
  element_key

edge_element_keys:
  element_key
  source_key
  destination_key

element_keys: The key for a graph element. This uniquely identifies a graph element.

• By default, the element key is the primary key of the input table.
• Element keys can be explicitly defined with the KEY clause.
• Columns with uniqueness constraints can be used as element keys.

Spanner ではプライマリキーは全ての SQL テーブルに必須であるため、 Spanner Graph のグラフ要素のアイデンティティはプライマリキーかユニークキー制約のどちらかで常に保証されるとわかります。

一方、プライマリキーでもユニークキーでもない列をキーに指定しようとすると Troubleshoot Spanner Graph に書かれているように次のようなエラーになります。

spanner> CREATE OR REPLACE PROPERTY GRAPH FinGraph
           NODE TABLES (
             Person KEY (name)
           );
ERROR: rpc error: code = FailedPrecondition desc = Neither the primary keys nor any unique index defined on the property graph element source table `Person` provides the uniqueness guarantee for graph element `Person` belonging to the graph `FinGraph`. You want to redefine the element key columns (`name`) based on the source table's primary keys, or create a unique index on the element's key columns.

リレーショナルモデルではリレーションは重複したタプルは存在しない集合であるため必ずタプルを識別する候補キーは一つ以上存在するはずでしたが、
SQL は多重集合（バッグ）でありキーの存在を前提としてはいません。

SQL ではプライマリキーやユニークキー制約が重複を防ぐためにオプションとして存在するのみです。

ちなみにインターリーブや外部キー制約による参照整合性の保証は必須ではありません。下記のインターリーブと外部キー制約を削除した FinGraph スキーマのサブセットは正当であり、この DDL 文の実行は成功します。

CREATE TABLE AccountNoFK (
  id               INT64 NOT NULL,
  create_time      TIMESTAMP,
  is_blocked       BOOL,
  nick_name        STRING(MAX),
) PRIMARY KEY (id);

CREATE TABLE AccountTransferAccountNoFK (
  id               INT64 NOT NULL,
  to_id            INT64 NOT NULL,
  amount           FLOAT64,
  create_time      TIMESTAMP NOT NULL,
  order_number     STRING(MAX),
) PRIMARY KEY (id, to_id, create_time);

CREATE OR REPLACE PROPERTY GRAPH FinGraphNoFK
  NODE TABLES (AccountNoFK LABEL Account)
  EDGE TABLES (
    AccountTransferAccountNoFK
      SOURCE KEY (id) REFERENCES AccountNoFK (id)
      DESTINATION KEY (to_id) REFERENCES AccountNoFK (id)
      LABEL Transfers
  );

グラフ要素がスキーマで定義されたユニークなキーを持つことの保証は、 GQL においてキー列を意識せずにグラフ要素の同一性を扱うことが可能なことに直接関わっています。
ここからはグラフ要素の同一性の GQL における扱いについて見ていきます。

GRAPH_ELEMENT 型の値は = で同一性検査可能

ノードやエッジにマッチしたグラフパターン変数に束縛された GRAPH_ELEMENT 型の値はキーのカラム(プロパティ)名を使わなくても = による同一性の検査が可能です。

GRAPH FinGraph
MATCH (a:Account), (b {id: 7})
FILTER a = b
RETURN LABELS(a) AS labels, a.id AS a_id, b.id AS b_id
/*--------------+-------+-------+
| labels        | a_id  | b_id  |
| ARRAY<STRING> | INT64 | INT64 |
+---------------+-------+-------+
| [Account]     | 7     | 7     |
+---------------+-------+-------+
1 rows in set (9.97 msecs)
*/

a と b 両方のフィルタが AND 条件、言い換えれば集合でいう積集合として適用されるので、 (a:Account {id: 7}) のように働きます。

GRAPH FinGraph
MATCH -[a:Transfers]->, -[b WHERE b.amount > 100]->
FILTER a = b
RETURN LABELS(a) AS labels, a.id AS a_id, b.id AS b_id, b.amount AS amount
/*--------------+-------+-------+------------+
| labels        | a_id  | b_id  | amount     |
| ARRAY<STRING> | INT64 | INT64 | FLOAT64    |
+---------------+-------+-------+------------+
| [Transfers]   | 7     | 7     | 300.000000 |
| [Transfers]   | 16    | 16    | 300.000000 |
| [Transfers]   | 20    | 20    | 500.000000 |
| [Transfers]   | 20    | 20    | 200.000000 |
+---------------+-------+-------+------------+
4 rows in set (18.66 msecs)
*/

こちらも a と b 双方へのフィルタが積集合として適用されるので -[a:Transfers WHERE b.amount > 100]-> のように働きます。

任意の数の GRAPH_ELEMENT の同一性を確かめる SAME 述語

= は2項演算ですが、3つ以上の GRAPH_ELEMENT の同一性比較には SAME 述語が使えます。

SAME (element, element[, ...])

GRAPH FinGraph
MATCH (:Account {id: 20})-[a:Transfers]->, -[b WHERE b.amount > 100]->, -[c]->(:Account {id: 7})
FILTER SAME(a, b, c)
RETURN LABELS(a) AS labels, a.id AS a_id, a.to_id AS to_id, a.amount AS amount;
/*---------------+-------+-------+------------+
 | labels        | a_id  | to_id | amount     |
 | ARRAY<STRING> | INT64 | INT64 | FLOAT64    |
 +---------------+-------+-------+------------+
 | [Transfers]   | 20    | 7     | 500.000000 |
 +---------------+-------+-------+------------+
1 rows in set (148.6 msecs)
*/

a, b, c 全てが同一のグラフ要素(このクエリではエッジ) を指すため、それぞれの変数に関するパターンは積として扱われます。
よって、 (:Account {id: 20})-[a:Transfers WHERE b.amount > 100]->(:Account {id: 7}) と同様にパターンマッチします。

Spanner Graph GQL の MATCH ステートメントについて: Part.1 基礎編 で書いたように、経路パターンにおけるノードとエッジの関係は一種の JOIN だと考えることができます。
OPTIONAL MATCH ではなくノード側にグラフパターン変数が使われていないこのパターンであれば EXISTS を使ったセミジョインだと考えても良いでしょう。

隣り合うノードパターンにも SAME が適用される

経路パターンは通常はエッジパターンとノードパターンが交互に書かれますが、ノードパターンが連続した場合はそれらには SAME 演算が適用されると明記されています。

If this results in two node patterns that are next to each other or a node pattern is next to a subpath, a SAME operation is performed on to the consecutive node patterns.

このルールにより、次のクエリの (a:Account) ({id: 7}) は (a:Account {id: 7}) と書かれているのと同様に解釈されます。

GRAPH FinGraph
MATCH (a:Account) ({id: 7})
RETURN LABELS(a) AS labels, a.id AS id;
/*---------------+-------+
 | labels        | id    |
 | ARRAY<STRING> | INT64 |
 +---------------+-------+
 | [Account]     | 7     |
 +---------------+-------+
1 rows in set (7.03 msecs)

何故このルールが必要なのかというと、部分経路(subpath)パターンでは必要に応じて暗黙的に空のノードパターンが挿入されるルールがあり連続するノードパターンについて定義する必要があるためだと考えられます。

Before	After
(node edge node)	(node edge node)
(edge node)	(empty_node edge node)
(node edge)	(node edge empty_node)
(edge)	(empty_node edge empty_node)

この2つのルールを適用するよって、下記のようにパターンを変更して解釈することが可能です。

(p:Person)(-[e:LocatedIn]->)(c:City)-[s:StudyAt]->(u:School)

-- エッジパターンの両側への空のノードパターンの挿入
(p:Person)(()-[e:LocatedIn]->())(c:City)-[s:StudyAt]->(u:School)

-- 単純化のため部分経路のカッコを外す
(p:Person) ()-[e:LocatedIn]->() (c:City)-[s:StudyAt]->(u:School)

-- 隣り合うノードパターンを SAME 述語で合成する
(p:Person)-[e:LocatedIn]->(c:City)-[s:StudyAt]->(u:School)

ID は STRING 値のスカラ値

GRAPH_ELEMENT は対応する要素 ID を持っているため、これを使って同一性の検査ができます。
要素 ID を得る最も簡単な方法は ELEMENT_ID 関数です。

ベースの SQL テーブルでは複合キーであっても常に ID を単一の STRING 値として比較できるので、次のクエリは結果としては今までのクエリで見てきたような結果となります。

GRAPH FinGraph
MATCH (a:Person), (b {id: 1})
FILTER ELEMENT_ID(a) = ELEMENT_ID(b)
RETURN LABELS(a) AS labels, a.id AS id, ELEMENT_ID(a) AS element_id;
/*---------------+-------+------------------------------+
 | labels        | id    | element_id                   |
 | ARRAY<STRING> | INT64 | STRING                       |
 +---------------+-------+------------------------------+
 | [Person]      | 1     | mUZpbkdyYXBoLlBlcnNvbgB4kQI= |
 +---------------+-------+------------------------------+
1 rows in set (8.78 msecs)
*/

結果は同じになりますが、実行計画を確認すると要素 ID を明示的に使ったクエリは他の同一性判定とは異なり最適化されない傾向があるので注意してください。

まとめ

Spanner Graph においてはグラフ要素の元になっている SQL テーブルの行がユニークなことがスキーマレベルで保証されており、
同一性の概念がグラフクエリの基本的なセマンティクスの基盤になっていることを確認しました。

この知識はクエリの変換や見慣れない書き方のクエリを解読する場合に役に立つことでしょう。

余談 opaque な要素 ID の構造を調べる

ところで、 ELEMENT_ID の構造についてはドキュメンテーションされていません。

Gets a graph element's unique identifier. The unique identifier is only valid for the scope of the query where it's obtained.

と書かれており、クエリのスコープを外れて使用することはできないことになっている他は、単なる STRING 値として使用する必要があります。一言で言い換えると opaque な値であるといえるでしょう。

しかし、先ほどのクエリ結果の mUZpbkdyYXBoLlBlcnNvbgB4kQI= を見ると BASE64 された値であることが想像できます。
実際に、 ELEMENT_ID の値は次のように FROM_BASE64 関数でデコード可能です。

GRAPH FinGraph
MATCH (n)
RETURN LABELS(n) AS labels, n.id AS id, ELEMENT_ID(n) AS element_id,
       FORMAT("%T", FROM_BASE64(ELEMENT_ID(n))) AS element_id_dec;
/*---------------+-------+------------------------------+--------------------------------------+
 | labels        | id    | element_id                   | element_id_dec                       |
 | ARRAY<STRING> | INT64 | STRING                       | STRING                               |
 +---------------+-------+------------------------------+--------------------------------------+
 | [Account]     | 7     | mUZpbkdyYXBoLkFjY291bnQAeJEO | b"\x99FinGraph.Account\x00x\x91\x0e" |
 | [Account]     | 16    | mUZpbkdyYXBoLkFjY291bnQAeJEg | b"\x99FinGraph.Account\x00x\x91 "    |
 | [Account]     | 20    | mUZpbkdyYXBoLkFjY291bnQAeJEo | b"\x99FinGraph.Account\x00x\x91("    |
 | [Person]      | 1     | mUZpbkdyYXBoLlBlcnNvbgB4kQI= | b"\x99FinGraph.Person\x00x\x91\x02"  |
 | [Person]      | 2     | mUZpbkdyYXBoLlBlcnNvbgB4kQQ= | b"\x99FinGraph.Person\x00x\x91\x04"  |
 | [Person]      | 3     | mUZpbkdyYXBoLlBlcnNvbgB4kQY= | b"\x99FinGraph.Person\x00x\x91\x06"  |
 +---------------+-------+------------------------------+--------------------------------------+
6 rows in set (7.41 msecs)
*/

デコードした結果を見てわかることとして、次のようなものがあります。

• プロパティグラフ名(FinGraph)が入っている。
• テーブル名(Account, Person)が入っている。
  • （この結果だけだと曖昧なもののラベルとテーブル名が異なったり、ラベルが複数あるグラフ要素を見るとラベルではなくテーブル名であると判別可能）
• キーが入っている。
  • この例では id カラムの INT64 のみが Protocol Buffers wire format と同様の ZigZag encoding された varint 128 でエンコードされていると思われる(検証内容や複合キーでの例は割愛)

ELEMENT_ID はあくまで opaque な STRING 型の値として使う必要はありますが、グラフ要素の識別に必要十分な情報が入っていることがわかりました。

エッジはまた別の構造を持っていますが、そこを説明するのはこの記事のスコープから外れるので確かめてみてください。