グラフを使った部品数の数え上げ

![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/73cf9e76-db22-6f7d-8577-6f84096ab353.jpeg)

以前の記事[「トレーサビリティを実現する強力なグラフ検索」](https://qiita.com/ryotayamanaka/items/fb5f9feeb0d487aa0151)ではグラフデータベースを使うことで、部品表（BoM）やサプライチェーンのデータに対して高い性能のパス検索を実現できることを紹介しました。

今回は、以前と同様の部品表を用いて、必要な部品数の数え上げを効率的に計算する方法を考えてみます。このような数え上げは一見シンプルですが、設計に変更があった場合のコストや重量の差分の計算や、調達できる部品の個数に変更があった場合の影響の大きさなど、多くのケースで繰り返し実行する必要があります。

## 部品表の例

今回は次のような部品表を想定します。エッジ上に置かれている数字が親部品に必要とされる子部品の数を示しています。

![graph_20230523203428.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/410176/7822ad26-92de-ad8d-d7aa-0888d67b49fa.png)

このグラフをデータベースに表構造で格納すると次のようになります。

```:bom_node
ID         PRICE
----- ----------
X               
A               
B               
C               
D               
E               
F            200
G               
H            150
I            120
...
```
```:bom_edge
        ID PAREN CHILD        CNT
---------- ----- ----- ----------
         1 G     K              2
         2 X     A              1
         3 X     B              2
         4 X     C              4
         5 A     D              2
         6 A     E              2
         7 B     E              4
         8 C     F              2
         9 C     G              3
        10 D     H              1
...
```

この表データをロードするスクリプトは[こちら](https://github.com/ryotayamanaka/oracle-graph/tree/main/count-parts)を参照ください。

## 計算方法

例えば、パーツ E の個数を求める場合、パーツ A が 1 個に対して E が 2 個、パーツ B が 2 個に対して E が 2 * 4 = 8 個、が必要になるので、その合計が 2 + 8 = 10 個となります。

つまり、あるパーツの必要個数を求めるためには、ルートにあたるモデル X からの**パスをすべて取得**した上で、それぞれのパスごとにエッジの値を掛け合わせ、それらを足し合わせればよいことがわかります。

この手法を使うと、パーツ K の必要個数は以下のように求まります。

```
(1 * 2 * 4) + (2 * 4 * 4) + (4 * 3 * 2) = 64
```

ここで、グラフデータベースは未知の長さのパスを効率的に検索することができるため、上のように二点間のすべてのパスを取得する場合にも、その特長を活かすことができます。

## グラフの作成

では、先に示した表データ `bom_node` と `bom_edge` からグラフを作成します。グラフの名前は `bom_graph` としておきます。この構文は PGQL としてのみ Oracle Database 12.2 以上で利用可能でしたが、さらに 23c 以降では SQL 標準として利用できます。

```
CREATE PROPERTY GRAPH bom_graph
  VERTEX TABLES (
    bom_node
      KEY (id)
      LABEL part
      PROPERTIES (id, price)
  )
  EDGE TABLES (
    bom_edge
      KEY (id)
      SOURCE KEY(parent) REFERENCES bom_node (id)
      DESTINATION KEY(child) REFERENCES bom_node (id)
      LABEL has_part
      PROPERTIES (cnt)
  )
```

## PGQL クエリ

早速、PGQL クエリとその結果を見てみましょう。

```sql
SELECT
  p2.id AS id
, LISTAGG(LISTAGG(CAST(e.cnt AS INTEGER), '*'), ' + ')||' =' AS fomula
, SUM(my.product(LISTAGG(CAST(e.cnt AS INTEGER), ','))) AS total_cnt
FROM MATCH ALL (p1) -[e:has_part]->{1,100} (p2) ON bom_graph
WHERE p1.id = 'X'
GROUP BY p2.id
ORDER BY p2.id
```
```
+------------------------------------------+
| id | fomula                  | total_cnt |
+------------------------------------------+
| A  | 1 =                     | 1         |
| B  | 2 =                     | 2         |
| C  | 4 =                     | 4         |
| D  | 1*2 =                   | 2         |
| E  | 1*2 + 2*4 =             | 10        |
| F  | 4*2 =                   | 8         |
| G  | 4*3 =                   | 12        |
| H  | 1*2*1 =                 | 2         |
| I  | 1*2*4 =                 | 8         |
| J  | 1*2*2 + 2*4*2 =         | 20        |
| K  | 1*2*4 + 2*4*4 + 4*3*2 = | 64        |
| L  | 4*3*5 =                 | 60        |
| M  | 4*3*2 =                 | 24        |
+------------------------------------------+
```

簡単に解説しますと、まず次のパターンマッチ構文では、2 つのノード p1 (= X) と p2 の間の 1〜100 ホップのパスをすべて検索しています。すべてのパスを求める場合には（無限ループに入らないよう）上限を指定する必要があるため、これを 100 としています。

```sql
FROM MATCH ALL (p1) -[e:has_part]->{1,100} (p2) ON bom_graph
WHERE p1.id = 'X'
```

そして、それぞれのパスについて、エッジに振られている数のリストを一度カンマ区切りの文字列にして（`LISTAGG`）から、それらの積を計算（`my.product`）して、すべてのパス分を合計（`SUM`）します。

```sql
SUM(my.product(LISTAGG(CAST(e.num AS INTEGER), ','))) AS total_cnt
```

ここで用いている `my.product()` は「カンマ区切りの整数の文字列からそれらの積を求める」というユーザー定義関数です。Oracle Graph のグラフ分析エンジン PGX でユーザー定義関数を使う方法の詳細は[「Oracle Graph でユーザー定義関数を使う」](https://qiita.com/ryotayamanaka/items/cdc4205532647990b2d0)を参照してください。

末端の部品の単価をノードのプロパティとして持っていれば、それぞれの部品の合計金額を計算するといった使い方もできます。

```sql
SELECT
  p2.id AS id
, LISTAGG(LISTAGG(CAST(e.cnt AS INTEGER), '*'), ' + ')||' =' AS fomula
, SUM(my.product(LISTAGG(CAST(e.cnt AS INTEGER), ','))) AS total_cnt
, p2.price AS unit_price
, SUM(my.product(LISTAGG(CAST(e.cnt AS INTEGER), ','))) * p2.price AS total_price
FROM MATCH ALL (p1) -[e:has_part]->{1,100} (p2) ON bom_graph
WHERE p1.id = 'X'
GROUP BY p2.id, p2.price
ORDER BY p2.id
```
```
+---------------------------------------------------------------------+
| id | fomula                  | total_cnt | unit_price | total_price |
+---------------------------------------------------------------------+
| A  | 1 =                     | 1         | 0.0        | 0.0         |
| B  | 2 =                     | 2         | 0.0        | 0.0         |
| C  | 4 =                     | 4         | 0.0        | 0.0         |
| D  | 1*2 =                   | 2         | 0.0        | 0.0         |
| E  | 1*2 + 2*4 =             | 10        | 0.0        | 0.0         |
| F  | 4*2 =                   | 8         | 200.0      | 1600.0      |
| G  | 4*3 =                   | 12        | 0.0        | 0.0         |
| H  | 1*2*1 =                 | 2         | 150.0      | 300.0       |
| I  | 1*2*4 =                 | 8         | 120.0      | 960.0       |
| J  | 1*2*2 + 2*4*2 =         | 20        | 50.0       | 1000.0      |
| K  | 1*2*4 + 2*4*4 + 4*3*2 = | 64        | 20.0       | 1280.0      |
| L  | 4*3*5 =                 | 60        | 30.0       | 1800.0      |
| M  | 4*3*2 =                 | 24        | 70.0       | 1680.0      |
+---------------------------------------------------------------------+
```


以上、グラフを使った部品数の数え上げ、を試してみました。今後もさまざまなユースケースを想定してグラフ機能を活用していきます。ご興味のある方は、ぜひ [OracleGraph](https://qiita.com/tags/oraclegraph) の記事をフォローしてください。