親子情報を持つテーブルとSQLの共通テーブル式(CTE)を使って、曽祖父母までの祖先を取得する

Drizzle SQL

以前、SQLのCTEを使って階層構造を持つデータから、祖先のデータを取得してみました。
django-cteと共通テーブル式(CTE)を用いた再帰クエリにより、階層構造を持つテーブルからデータを取得する - メモ的な思考的な

このときは django-cte の利用がメインだったため、祖先は1つ (りんごの種子親) だけを扱いました。

　

ただ、現実のりんごの祖先は単一ではなく、

  • 花粉親 (父)
  • 種子親 (母)

がそれぞれ存在します。また、当然ながら、それ以前の代のりんごも存在します。

例えば、シナノリップの場合、祖先をたどると以下のような感じになります。

  • シナノリップ
    • (父) シナノレッド
      • (父) ビスタベラ
        • (父) 不明
        • (母) 不明
      • (母) つがる
        • (父) 紅玉
        • (母) ゴールデンデリシャス
    • (母) 千秋
      • (父) ふじ
        • (父) デリシャス
        • (母) 国光
      • (母) 東光
        • (父) 印度
        • (母) ゴールデンデリシャス

　

そこで今回、「1つのりんごを指定したときに、曽祖父母までのりんご名をすべて取得して横持ちにする」を実装してみます。

例えば、シナノリップを指定した場合は、以下のような形で取得します。

りんご 父 父父 父父父 父父母 ... 母母母
シナノリップ シナノレッド ビスタベラ 不明 不明 ... ゴールデンデリシャス

　
目次

　

環境

まず、データの保管先とその取得方法ですが、今回は

  • 曽祖父母までの親子情報を持つRDB・テーブルを用意
  • そのテーブルからSQLでデータを取得する

とします。

なお、テーブルの主キーに意味を持たせたほうがわかりやすそうと感じたため、テーブルの主キーは自然キーとします。

　
次に、動作確認を容易にしたいため、何かしらのORMを用意します。 　
そこで、自然キーを主キーにできるORMを調べてみたところ、 drizzle-orm が自然キーを主キーにできそうでした。
Drizzle ORM - Indexes & Constraints

そこで、ORMは drizzle-orm を使うことにします。

　
ところで、drizzle-ormを使うときには何かしらのdriverが必要になります。

ただ、実行環境としてBunを選択すると、driverを追加することなくSQLiteを扱えます。
https://orm.drizzle.team/docs/get-started-sqlite#bun-sqlite

そこで、今回は実行環境としてBunを選択します。

　
以上を踏まえた、今回の環境は次の通りです。

  • Windows11 WSL2
  • SQLite
  • drizzle-orm 0.33.0
  • drizzle-kit 0.24.2
  • Bun 1.1.27

　

drizzle-ormまわりのセットアップ

SQLを試す前に、必要な環境をセットアップします。

# Bunのバージョンを確認
$ bun -v
1.1.27


# Bunプロジェクトを作成
$ bun init
bun init helps you get started with a minimal project and tries to guess sensible defaults. Press ^C anytime to quit

package name (ringo_genealogies_with_drizzle): ringo_genealogies_with_drizzle
entry point (index.ts):

Done! A package.json file was saved in the current directory.
 + index.ts
 + .gitignore
 + tsconfig.json (for editor auto-complete)
 + README.md

To get started, run:
  bun run index.ts


# drizzle-ormをインストール
$ bun add drizzle-orm
bun add v1.1.27 (267afa29)

installed drizzle-orm@0.33.0

1 package installed [342.00ms]


# マイグレーションコマンドが使えるようになる、drizzle-kitもインストール
$ bun add -D drizzle-kit
bun add v1.1.27 (267afa29)

installed drizzle-kit@0.24.2 with binaries:
 - drizzle-kit

16 packages installed [1.88s]

　
次に、drizzle-orm のSQLite向け設定ファイルを drizzle.config.ts として作成します。

import { defineConfig } from "drizzle-kit"

export default defineConfig({
  dialect: "sqlite",
  schema: "./src/schema/*",
  out: "./drizzle",
})

　
続いて、Bun用の設定ファイルを作成します。というのも、drizzle-orm の migrate コマンドについてはBunでそのまま使えないためです。

今回はBunの公式ドキュメントに従い、Bun向けのマイグレーションコマンドファイルを作成します。
https://bun.sh/guides/ecosystem/drizzle

これでBunでもマイグレーションが実行できるようになります。

import { migrate } from "drizzle-orm/bun-sqlite/migrator";

import { drizzle } from "drizzle-orm/bun-sqlite";
import { Database } from "bun:sqlite";

const sqlite = new Database("sqlite.db");
const db = drizzle(sqlite);
await migrate(db, { migrationsFolder: "./drizzle" });

　

テーブル設計

今回は

  • りんご情報を持つ apples テーブル
  • 親子関係を階層構造として持つ genealogies テーブル

の2つを用意します。

　
続いて、 genealogies の構造ですが、父母情報を縦持ち・横持ちのどちらにするかを考えます。

縦持ちの場合はこんな感じです。relationに 父 か 母 的な値を入れ、1つの子りんごに対し、2レコードで父母情報を管理します。

sqliteTable("genealogies", {
  parent_name: text('parent_name').notNull().references(() => apples.name),
  child_name: text('child_name').notNull().references(() => apples.name),
  relation: text('relation').notNull()
}, (table) => {
  return {
    pk: primaryKey({ columns: [table.parent_name, table.child_name, table.relation] })
  }

　
一方、横持ちはこんな感じで、1レコードで父母情報を管理します。

sqliteTable("genealogies", {
  child_name: text('child_name').notNull().references(() => apples.name),
  pollen_name: text('pollen_name').notNull().references(() => apples.name),
  seed_name: text('seed_name').notNull().references(() => apples.name),
}, (table) => {
  return {
    pk: primaryKey({ columns: [table.child_name, table.pollen_name, table.seed_name] })
  }
})

　
では、どうするか考えます。

初期データを用意する際に、前者だとデータ量が多くなる & うっかり親子関係を間違えやすそうと感じました。

また、一度りんごの親子関係を作ってしまえば、基本的に親子関係は不変と考えました*1。

そこで、今回は後者の「1レコードで父母情報を管理」とするテーブル設計としました。

　
ちなみに、これは以下の記事にある 閉包テーブル のような感じになりました。
MySQLで階層構造を扱うための再帰的なクエリの実装方法と実用例

　

drizzle-ormでのschema定義

テーブル設計ができたので、次はdrizzle-ormのschemaとして実装します。

まずは apples テーブルを表す apples.ts をディレクトリ scr/schema の中に用意します。

import {sqliteTable, text} from "drizzle-orm/sqlite-core";

export const apples = sqliteTable("apples", {
  name: text('name').primaryKey(),
  display_name: text('display_name').unique().notNull(),
  color: text('color').notNull()
})

　

続いて、親子関係を持つ genealogies テーブルを表す genealogies.ts も用意します。

import {primaryKey, sqliteTable, text} from "drizzle-orm/sqlite-core";
import {apples} from "./apples.ts";

export const genealogies = sqliteTable("genealogies", {
  child_name: text('child_name').notNull().references(() => apples.name),
  pollen_name: text('pollen_name').notNull().references(() => apples.name),
  seed_name: text('seed_name').notNull().references(() => apples.name),
}, (table) => {
  return {
    pk: primaryKey({ columns: [table.child_name, table.pollen_name, table.seed_name] })
  }
})

　

マイグレーションファイルの生成と適用

schemaファイルができたので、マイグレーションファイルを生成します。

$ bun run generate

　
続いて、マイグレーションファイルを適用します。Bunの場合は先ほど作成した migrate.ts を使って適用します。

$ bun run migrate.ts

　

sqlite.db が生成されました。中を見てみるとテーブルができていました。

　

seedファイルの生成と実行

毎回データ投入を行うのは手間なので、seedファイル( seed.ts )を用意します。

内容は以下ですが、記事の都合上一部を省略しています。全体像は以下のファイルを参照してください。
https://github.com/thinkAmi-sandbox/ringo_genealogies_with_drizzle/blob/main/seed.ts

import { db } from "./db";
import {apples} from "./src/schema/apples.ts";
import {genealogies} from "./src/schema/genealogies.ts";


await db.insert(apples).values([
  {
    name: "unknown",
    display_name: "不明",
    color: "不明"
  },
  {
    name: "shinano_sweet",
    display_name: "シナノスイート",
    color: "黃"
  },
  // 略
]);

await db.insert(genealogies).values([
  {
    child_name: "unknown",
    pollen_name: "unknown",
    seed_name: "unknown"
  },
  {
    child_name: "shinano_sweet",
    pollen_name: "tsugaru",
    seed_name: "fuji"
  },
  {
    child_name: "tsugaru",
    pollen_name: "kougyoku",
    seed_name: "golden_delicious"
  },
  {
    child_name: "kougyoku",
    pollen_name: "unknown",
    seed_name: "unknown"
  },
  {
    child_name: "golden_delicious",
    pollen_name: "unknown",
    seed_name: "unknown"
  },
  // 略
])


console.log(`Seeding complete.`);

　
続いて、seedを投入します。

$ bun run seed.ts

　

生SQLを用いたdrizzle-ormでの実装

再掲となりますが、今回は「1つのりんごを指定したときに、曽祖父母までのりんご名をすべて取得して横持ちにする」を実現したいです。これはSQLのCTE (共通テーブル式) を使えば良さそうです。

　
ただ、drizzle-orm ではまだCTEをサポートしていません。

drizzle-ormでは sql テンプレートを使って生SQLも扱えます。
Drizzle ORM - Magic sql`` operator

そこで、まずは以下のような生SQLを用意します。

WITH RECURSIVE ancestry AS (
    -- 最初に、検索したいりんごの情報を取得
    SELECT
        g.child_name,
        a.display_name as child_display_name,
        g.pollen_name,
        g.seed_name,
        0 AS generation
    FROM genealogies g
    INNER JOIN apples a
      ON g.child_name = a.name
    WHERE child_name = ${targetName}

    UNION ALL

    -- 再帰的に父母や祖父母、曽祖父母を取得
    SELECT
        g.child_name as child_name,
        apples.display_name as child_display_name,
        g.pollen_name as pollen_name,
        g.seed_name as seed_name,
        a.generation + 1
    FROM genealogies g
        INNER JOIN ancestry a 
            ON g.child_name = a.pollen_name OR g.child_name = a.seed_name
        INNER JOIN apples
            ON g.child_name = apples.name
    WHERE a.generation < 3 -- 曽祖父母まで取得する
)

-- 結果を横持ちで表示(重複して取得できてしまうので、DISTINCTが必要)
SELECT DISTINCT
    a.child_display_name AS "Apple Name",
    p.child_display_name AS "Father",
    pp.child_display_name AS "Grandfather (Father's side)",
    ppp.child_display_name AS "Great-Grandfather (Father's Father's side)",
    pps.child_display_name AS "Great-Grandmother (Father'sFather's side)",
    ps.child_display_name AS "Grandmother (Father's side)",
    psp.child_display_name AS "Great-Grandfather (Father's Mother's side)",
    pss.child_display_name AS "Great-Grandmother (Father's Mother's side)",
    s.child_display_name AS "Mother",
    sp.child_display_name AS "Grandfather (Mother's side)",
    spp.child_display_name AS "Great-Grandfather (Mother's side)",
    sps.child_display_name AS "Great-Grandmother (Mother's Father's side)",
    ss.child_display_name AS "Grandmother (Mother's side)",
    ssf.child_display_name AS "Great-Grandfather (Mother's Mother's side)",
    sss.child_display_name AS "Great-Grandmother (Mother's Mother's side)"
FROM
    ancestry a
-- 父系
-- 父親を結合
        LEFT JOIN ancestry p 
            ON p.child_name = a.pollen_name AND p.generation = 1
-- 父親の父親（祖父）を結合
        LEFT JOIN ancestry pp 
            ON pp.child_name = p.pollen_name AND pp.generation = 2
-- 父親の母親（祖母）を結合
        LEFT JOIN ancestry ps 
            ON ps.child_name = p.seed_name AND ps.generation = 2
-- 父親の父親の父親（曽祖父）を結合
        LEFT JOIN ancestry ppp 
            ON ppp.child_name = pp.pollen_name AND ppp.generation = 3
-- 父親の父親の母親（曽祖母）を結合
        LEFT JOIN ancestry pps 
            ON pps.child_name = pp.seed_name AND pps.generation = 3
-- 父親の母親の父親（曽祖父）を結合
        LEFT JOIN ancestry psp 
            ON psp.child_name = ps.pollen_name AND psp.generation = 3
-- 父親の母親の母親（曽祖母）を結合
        LEFT JOIN ancestry pss 
            ON pss.child_name = ps.seed_name AND pss.generation = 3
-- 母系
-- 母親を結合
        LEFT JOIN ancestry s 
            ON s.child_name = a.seed_name AND s.generation = 1
-- 母親の父親（祖父）を結合
        LEFT JOIN ancestry sp 
            ON sp.child_name = s.pollen_name AND sp.generation = 2
-- 母親の母親（祖母）を結合
        LEFT JOIN ancestry ss 
            ON ss.child_name = s.seed_name AND ss.generation = 2
-- 母親の父親の父親（曽祖父）を結合
        LEFT JOIN ancestry spp 
            ON spp.child_name = sp.pollen_name AND spp.generation = 3
-- 母親の父親の母親（曽祖母）を結合
        LEFT JOIN ancestry sps 
            ON sps.child_name = sp.seed_name AND sps.generation = 3
-- 母親の母親の父親（曽祖父）を結合
        LEFT JOIN ancestry ssf 
            ON ssf.child_name = ss.pollen_name AND ssf.generation = 3
-- 母親の母親の母親（曽祖母）を結合
        LEFT JOIN ancestry sss 
            ON sss.child_name = ss.seed_name AND sss.generation = 3
WHERE
    a.generation = 0;

　

この生SQLをdrizzle-ormで実行するために、以下のような index.ts を用意します。

なお、 <上記のSQLをそのまま貼る> の記載など、全体を見たい場合は以下のソースコードを参照してください。
https://github.com/thinkAmi-sandbox/ringo_genealogies_with_drizzle/blob/main/index.ts

import {db} from "./db.ts";
import {sql} from "drizzle-orm";

# ここではシナノリップの系統データを取得する
const targetName = 'shinano_lip'

const result = await db.all(
  sql`<上記のSQLをそのまま貼る>`
)

console.log(result)

　

動作確認

先ほど実装した index.ts を実行したところ、シナノリップの祖先を取得できました。

$ bun run index.ts 

[
  {
    "Apple Name": "シナノリップ",
    Father: "シナノレッド",
    "Grandfather (Father's side)": "ビスタベラ",
    "Great-Grandfather (Father's Father's side)": "不明",
    "Great-Grandmother (Father'sFather's side)": "不明",
    "Grandmother (Father's side)": "つがる",
    "Great-Grandfather (Father's Mother's side)": "紅玉",
    "Great-Grandmother (Father's Mother's side)": "ゴールデンデリシャス",
    Mother: "千秋",
    "Grandfather (Mother's side)": "ふじ",
    "Great-Grandfather (Mother's side)": "デリシャス",
    "Great-Grandmother (Mother's Father's side)": "国光",
    "Grandmother (Mother's side)": "東光",
    "Great-Grandfather (Mother's Mother's side)": "印度",
    "Great-Grandmother (Mother's Mother's side)": "ゴールデンデリシャス",
  }
]

　
奥州ロマンの場合はこんな感じです。こちらも良さそうです。

[
  {
    "Apple Name": "奥州ロマン",
    Father: "つがる",
    "Grandfather (Father's side)": "紅玉",
    "Great-Grandfather (Father's Father's side)": "不明",
    "Great-Grandmother (Father'sFather's side)": "不明",
    "Grandmother (Father's side)": "ゴールデンデリシャス",
    "Great-Grandfather (Father's Mother's side)": "不明",
    "Great-Grandmother (Father's Mother's side)": "不明",
    Mother: "シナノゴールド",
    "Grandfather (Mother's side)": "千秋",
    "Great-Grandfather (Mother's side)": "ふじ",
    "Great-Grandmother (Mother's Father's side)": "東光",
    "Grandmother (Mother's side)": "ゴールデンデリシャス",
    "Great-Grandfather (Mother's Mother's side)": "不明",
    "Great-Grandmother (Mother's Mother's side)": "不明",
  }
]

　

ソースコード

GitHubに上げました。
https://github.com/thinkAmi-sandbox/ringo_genealogies_with_drizzle

　
今回のプルリクはこちら。
https://github.com/thinkAmi-sandbox/ringo_genealogies_with_drizzle/pull/1

*1:稀に、遺伝子の検査などで親子の見直しが発生することもあるようです