木を植える者
希望を植えます。
木を植える by Lucy Larcom ?
この投稿では、ツリー データ構造として表される階層データを管理するためのオプションをいくつか紹介します。これは、次のようなものを実装する必要がある場合の自然なアプローチです。
グラフが何であるかをすでに知っている場合、ツリーは基本的に サイクルのないグラフです。このように視覚的に表現できます。
リレーショナル データベースにツリーを保存する方法は複数あります。以下のセクションでは、そのうちの 3 つを紹介します:
このブログ投稿は 2 つの部分に分かれています。この最初のバージョンでは、代替手段が紹介され、データのロードと保存の基本的な方法がわかります。それはさておき、第 2 部では、それらの比較とトレードオフに焦点を当てます。たとえば、データ量が増加した場合に何が起こるか、および適切なインデックス付け戦略は何かについて見ていきたいと思います。
以下のセクションに表示されるすべてのコードは、興味がある場合はここで確認できます。
実行中のユースケースは、従業員とそのマネージャーのユースケースであり、それぞれの ID は、上で示したツリーの視覚化で確認したものとまったく同じになります。
私は最近リリースされた Postgres 17 を Testcontainers で使用しています。これにより、繰り返し可能なセットアップで作業できるようになります。たとえば、初期化 SQL スクリプトを使用して、必要なテーブルを備えた Postgres データベースの作成を自動化し、テスト データを追加できます。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
早速、最初のアプローチを見てみましょう。
これは階層データを管理するための最初のソリューションであったため、コードベースにまだ広く存在していることが予想されるため、いつか遭遇する可能性があります。考え方としては、マネージャーの (より一般的に言えば) 親 ID を同じ行に保存するということです。テーブル構造を見ればすぐにわかります。
隣接リスト オプションに対応するテーブルは次のようになります:
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
上記に加えて、データの整合性を確保するには、少なくとも次のことを保証する制約チェックも記述する必要があります。
特にこのシリーズのパート 2 では、スキーマにデータを設定するために必要なだけのデータを生成する方法が必要です。わかりやすくするために、最初は段階的に実行し、その後再帰的に実行してみましょう。
まず、階層に 3 つのレベルの従業員を明示的に挿入することから始めます。
Postgres の CTE についてはすでにご存じかもしれません。CTE は、メイン クエリのコンテキスト内で実行される補助的な名前付きクエリです。以下に、前のレベルに基づいて各レベルをどのように構築するかを示します。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
これまでのところ期待どおりに動作することを確認してみましょう。この目的のために、挿入された要素の数を確認するためにカウントを実行します。この投稿の冒頭で示したツリー視覚化のノード数と比較できます。
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
大丈夫そうですね! 3 つのレベルで、合計 15 個のノードが得られます。
再帰的アプローチに移りましょう。
再帰クエリの作成は標準的な手順に従います。基本ステップと再帰ステップを定義し、union all を使用してそれらを相互に「接続」します。実行時に Postgres はこのレシピに従い、すべての結果を生成します。ぜひご覧ください。
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
実行後、もう一度カウントして、同じ数の要素が挿入されているかどうかを確認してみましょう。
postgres=# select count(*) from employees; count ------- 15 (1 row)
かっこいい!私たちはビジネスをしています。これで、必要な数のレベルと要素をスキーマに追加できるようになり、挿入されたボリュームを完全に制御できるようになりました。現時点では再帰クエリがまだ少し難しそうに見えても心配する必要はありません。実際には、少し後で、データを取得するクエリを作成する機会に再考します。
ここでは、テーブルを Java クラスにマップするために使用できる Hibernate エンティティを見てみましょう。
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
特別なことは何もありません。マネージャーと従業員の間には 1 対多の関係があるだけです。あなたはこれが来るのを見ました。クエリを開始しましょう。
マネージャーのすべての部下
ID で参照される特定のマネージャーの部下であるすべての従業員を取得するには、再帰クエリを再度作成します。 ベース ステップと、ベース ステップにリンクされている再帰ステップが再度表示されます。 Postgres はこれを繰り返し、クエリに関連するすべての行を取得します。たとえば、ID = 2 の従業員を考えてみましょう。これは視覚的に表現したもので、今説明した内容を理解しやすくするものです。すべての結果を含めたわけではありません。最初のいくつかだけを示します。
子孫をクエリするための JPQL クエリは次のとおりです。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
上記のようなクエリでは、クエリをわかりやすくし、結果を書き込むレコードの完全修飾名を記述する必要を避けるために、hypersistence-utils ライブラリを使用して ClassImportIntegratorProvider を記述することができます。
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
これは機能しますが、Hibernate が生成したものを詳しく見てみましょう。内部で何が起こっているのかを理解することは常に良いことです。そうでないと、ユーザーのリクエストごとに非効率が発生し、それが積み重なってしまう可能性があります。
次の設定で Spring Boot アプリを起動する必要があります:
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
それでは、見てみましょう。 Hibernate によって生成された子孫のクエリは次のとおりです。
postgres=# select count(*) from employees; count ------- 15 (1 row)
うーん、予想より少し複雑ですね!ベース ステップとベース ステップにリンクされた再帰ステップについて前に示した図を念頭に置き、これを少し単純化できるかどうかを見てみましょう。それ以上のことをする必要はないはずです。以下についてどう思うか見てください。
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
ずっと良くなりました!いくつかの不要な結合を削除しました。これにより、実行する作業が減り、クエリが高速化されることが期待されます。
最後のステップとして、クエリをクリーンアップし、Hibernate が追加するテーブル名を人間が読みやすい名前に置き換えましょう。
postgres=# select count(*) from employees; count ------- 15 (1 row)
さて、ツリーをどのように「登る」か見てみましょう。
チェーン上のすべてのマネージャー
まず、ID = 14 の従業員のマネージャーを取得するための概念的な手順を書き留めてみましょう。
子孫の場合と非常によく似ていますが、基本ステップと再帰ステップの間の接続が逆になっているだけです。
JPQL クエリは次のように記述できます。
@Entity @Table(name = "employees") @Getter @Setter public class Employee { @Id private Long id; private String name; @ManyToOne(fetch = FetchType.LAZY) @JoinColumn(name = "manager_id") private Employee manager; @OneToMany( mappedBy = "parent", cascade = CascadeType.ALL, orphanRemoval = true ) private List<Employee> employees = new ArrayList<>(); }
それで終わりです!生成された SQL クエリを確認しましたが、削除できる余分なコマンドは見つかりませんでした。アプローチ 2 に進みます。
ltree は、(ツリーの最上部から始まる) 実体化されたパスとして階層ツリー構造を操作するために使用できる Postgres 拡張機能です。たとえば、リーフ ノード 8 のパス 1.2.4.8 を記録する方法は次のとおりです。いくつかの便利な機能が搭載されています。これをテーブルの列として使用できます:
return entityManager.createQuery(""" with employeeRoot as ( select employee.employees employee from Employee employee where employee.id = :employeeId union all select employee.employees employee from Employee employee join employeeRoot root ON employee = root.employee order by employee.id ) select new Employee( root.employee.id ) from employeeRoot root """, Employee.class ) .setParameter("employeeId", employeeId) .getResultList();
上記のテーブルにテスト データを設定するために私がとったアプローチは、基本的に、次の SQL コマンドを使用して、前に見た隣接リストに使用されたテーブルから生成されたデータを移行することです。これもまた、各ステップで要素をアキュムレータに収集する再帰的クエリです。
public class ClassImportIntegratorProvider implements IntegratorProvider { @Override public List<Integrator> getIntegrators() { return List.of( new ClassImportIntegrator( singletonList( Employee.class ) ) ); } }
上記のコマンドで生成されたエントリは次のとおりです。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
Hibernate エンティティの作成に進むことができます。 ltree 型の列をマップするために、UserType を実装しました。その後、パス フィールドを @Type(LTreeType.class):
でマッピングできます。
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
いくつかのクエリを作成する準備ができました。ネイティブ SQL では、次のようになります:
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
しかし、JPQL でクエリを書いてみましょう。このためには、まずカスタム StandardSQLFunction を作成する必要があります。これにより、Postgres ネイティブ オペレーターの置換を定義できるようになります。
postgres=# select count(*) from employees; count ------- 15 (1 row)
次に、次のように FunctionContributor として登録する必要があります。
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
最後のステップは、META-INF/services フォルダーに org.hibernate.boot.model.FunctionContributor というリソース ファイルを作成し、上記のクラスの完全修飾名を 1 行追加します。
わかりました、クールです!ついに次のクエリを作成できるようになりました:
postgres=# select count(*) from employees; count ------- 15 (1 row)
たとえば、このメソッドを次のように呼び出して、ID = 2 を含むすべてのパスを取得できます。
@Entity @Table(name = "employees") @Getter @Setter public class Employee { @Id private Long id; private String name; @ManyToOne(fetch = FetchType.LAZY) @JoinColumn(name = "manager_id") private Employee manager; @OneToMany( mappedBy = "parent", cascade = CascadeType.ALL, orphanRemoval = true ) private List<Employee> employees = new ArrayList<>(); }
Postgres は、ltree を操作するための幅広い関数セットを提供します。それらは公式ドキュメントページで見つけることができます。便利なチートシートもあります。
データの一貫性を確保するには、スキーマに制約を追加することが重要です。このトピックに関して見つけた優れたリソースは次のとおりです。
直感を示す画像を使用するのが最も簡単です。ツリーの各ノードには、ID のほかに追加の「左」列と「右」列があります。ルールは、すべての子の左と右が親の左と右の値の間にあることです。
上記のツリーを表すテーブル構造は次のとおりです。
return entityManager.createQuery(""" with employeeRoot as ( select employee.employees employee from Employee employee where employee.id = :employeeId union all select employee.employees employee from Employee employee join employeeRoot root ON employee = root.employee order by employee.id ) select new Employee( root.employee.id ) from employeeRoot root """, Employee.class ) .setParameter("employeeId", employeeId) .getResultList();
テーブルにデータを設定するために、Joe Celko の書籍「SQL for Smarties」のスクリプトを Postgres 構文に変換しました。それは次のとおりです:
public class ClassImportIntegratorProvider implements IntegratorProvider { @Override public List<Integrator> getIntegrators() { return List.of( new ClassImportIntegrator( singletonList( Employee.class ) ) ); } }
わかりました。いくつかのクエリを実行する準備ができました。祖先を取得する方法は次のとおりです。
@DynamicPropertySource static void registerPgProperties(DynamicPropertyRegistry registry) { registry.add("spring.jpa.show_sql", () -> true); }
子孫の場合は、まず左側と右側を取得する必要があり、その後、以下のクエリを使用できます。
with recursive employeeRoot (employee_id) as ( select e1_0.id from employees eal1_0 join employees e1_0 on eal1_0.id = e1_0.manager_id where eal1_0.id=? union all ( select e2_0.id from employees eal2_0 join employeeRoot root1_0 on eal2_0.id = root1_0.employee_id join employees e2_0 on eal2_0.id = e2_0.manager_id order by eal2_0.id ) ) select root2_0.employee_id from employeeRoot root2_0
それで終わりです! 3 つのアプローチすべてについて、ツリーを上り下りする方法を確認しました。旅を楽しんでいただけて、お役に立てば幸いです。
上記の例で使用したデータベースは PostgreSQL です。これが唯一の選択肢ではありません。たとえば、MongoDB のようなドキュメント データベースや Neo4j のようなグラフ データベースを選択しないのはなぜではないかと疑問に思うかもしれません。なぜなら、これらは実際にこの種のワークロードを念頭に置いて構築されているからです。
おそらく、トランザクション保証を活用したリレーショナル モデルの Postgres に、信頼できるデータのソースがすでに存在していると思われます。その場合、すべてを 1 か所にまとめておくために、まず Postgres 自体が補助的なユースケースをどのように適切に処理するかを確認する必要があります。こうすることで、新しい別個の専用データ ストアの立ち上げと保守/アップグレードに必要なコストと運用の複雑さの増加、およびそれに慣れる必要を回避できます。
データベース アプリケーションで階層データをモデル化するための興味深いオプションがいくつかあります。この記事では 3 つの方法を紹介しました。パート 2 では、それらを比較し、より大量のデータで何が起こるかを見ていきますので、ご期待ください。
https://dev.to/yugabyte/learn-how-to-write-sql-recursive-cte-in-5-steps-3n88
https://vladmihalcea.com/hibernate-with-recursive-query/
https://vladmihalcea.com/dto-projection-jpa-query/
https://tudborg.com/posts/2022-02-04-postgres-hierarchical-data-with-ltree/
https://aregal.tech/hibernate-6-custom-functions#Heading-implementing-a-custom-function
https://www.amazon.co.uk/Joe-Celkos-SQL-Smarties-Programming/dp/0128007613
https://madecurious.com/curiosities/trees-in-postgresql/
https://schinckel.net/2014/11/27/postgres-tree-shootout-part-2:-adjacency-list-using-ctes/
以上がPostgreSQL と Spring Data JPA による階層型データの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。