木を植える者
希望を植えます。
木を植える by Lucy Larcom ?
イントロ
この投稿では、ツリー データ構造として表される階層データを管理するためのオプションをいくつか紹介します。これは、次のようなものを実装する必要がある場合の自然なアプローチです。
- ファイルシステムのパス
- 組織図
- ディスカッションフォーラムのコメント
- より現代的なトピック: RAG アプリケーションの small2big 取得
グラフが何であるかをすでに知っている場合、ツリーは基本的に サイクルのないグラフです。このように視覚的に表現できます。
リレーショナル データベースにツリーを保存する方法は複数あります。以下のセクションでは、そのうちの 3 つを紹介します:
このブログ投稿は 2 つの部分に分かれています。この最初のバージョンでは、代替手段が紹介され、データのロードと保存の基本的な方法がわかります。それはさておき、第 2 部では、それらの比較とトレードオフに焦点を当てます。たとえば、データ量が増加した場合に何が起こるか、および適切なインデックス付け戦略は何かについて見ていきたいと思います。
以下のセクションに表示されるすべてのコードは、興味がある場合はここで確認できます。
実行中のユースケースは、従業員とそのマネージャーのユースケースであり、それぞれの ID は、上で示したツリーの視覚化で確認したものとまったく同じになります。
地域環境
私は最近リリースされた Postgres 17 を Testcontainers で使用しています。これにより、繰り返し可能なセットアップで作業できるようになります。たとえば、初期化 SQL スクリプトを使用して、必要なテーブルを備えた Postgres データベースの作成を自動化し、テスト データを追加できます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | @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" );
}
}
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
早速、最初のアプローチを見てみましょう。
1. 隣接リストモデル
これは階層データを管理するための最初のソリューションであったため、コードベースにまだ広く存在していることが予想されるため、いつか遭遇する可能性があります。考え方としては、マネージャーの (より一般的に言えば) 親 ID を同じ行に保存するということです。テーブル構造を見ればすぐにわかります。
スキーマ
隣接リスト オプションに対応するテーブルは次のようになります:
1 2 3 4 5 6 | create table employees
(
id bigserial primary key,
manager_id bigint references employees
name text,
);
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
上記に加えて、データの整合性を確保するには、少なくとも次のことを保証する制約チェックも記述する必要があります。
テストデータの生成
特にこのシリーズのパート 2 では、スキーマにデータを設定するために必要なだけのデータを生成する方法が必要です。わかりやすくするために、最初は段階的に実行し、その後再帰的に実行してみましょう。
一歩ずつ
まず、階層に 3 つのレベルの従業員を明示的に挿入することから始めます。
Postgres の CTE についてはすでにご存じかもしれません。CTE は、メイン クエリのコンテキスト内で実行される補助的な名前付きクエリです。以下に、前のレベルに基づいて各レベルをどのように構築するかを示します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | @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" );
}
}
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
これまでのところ期待どおりに動作することを確認してみましょう。この目的のために、挿入された要素の数を確認するためにカウントを実行します。この投稿の冒頭で示したツリー視覚化のノード数と比較できます。
1 2 3 4 5 6 | create table employees
(
id bigserial primary key,
manager_id bigint references employees
name text,
);
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
大丈夫そうですね! 3 つのレベルで、合計 15 個のノードが得られます。
再帰的アプローチに移りましょう。
再帰的
再帰クエリの作成は標準的な手順に従います。基本ステップと再帰ステップを定義し、union all を使用してそれらを相互に「接続」します。実行時に Postgres はこのレシピに従い、すべての結果を生成します。ぜひご覧ください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | 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;
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
実行後、もう一度カウントして、同じ数の要素が挿入されているかどうかを確認してみましょう。
1 2 3 4 5 | postgres=# select count (*) from employees;
count
-------
15
(1 row)
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
かっこいい!私たちはビジネスをしています。これで、必要な数のレベルと要素をスキーマに追加できるようになり、挿入されたボリュームを完全に制御できるようになりました。現時点では再帰クエリがまだ少し難しそうに見えても心配する必要はありません。実際には、少し後で、データを取得するクエリを作成する機会に再考します。
ここでは、テーブルを Java クラスにマップするために使用できる Hibernate エンティティを見てみましょう。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 クエリは次のとおりです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | @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 を記述することができます。
1 2 3 4 5 6 | create table employees
(
id bigserial primary key,
manager_id bigint references employees
name text,
);
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
生成されたクエリの確認
これは機能しますが、Hibernate が生成したものを詳しく見てみましょう。内部で何が起こっているのかを理解することは常に良いことです。そうでないと、ユーザーのリクエストごとに非効率が発生し、それが積み重なってしまう可能性があります。
次の設定で Spring Boot アプリを起動する必要があります:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | 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 によって生成された子孫のクエリは次のとおりです。
1 2 3 4 5 | postgres=# select count (*) from employees;
count
-------
15
(1 row)
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
うーん、予想より少し複雑ですね!ベース ステップとベース ステップにリンクされた再帰ステップについて前に示した図を念頭に置き、これを少し単純化できるかどうかを見てみましょう。それ以上のことをする必要はないはずです。以下についてどう思うか見てください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 が追加するテーブル名を人間が読みやすい名前に置き換えましょう。
1 2 3 4 5 | postgres=# select count (*) from employees;
count
-------
15
(1 row)
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
さて、ツリーをどのように「登る」か見てみましょう。
祖先
チェーン上のすべてのマネージャー
まず、ID = 14 の従業員のマネージャーを取得するための概念的な手順を書き留めてみましょう。
子孫の場合と非常によく似ていますが、基本ステップと再帰ステップの間の接続が逆になっているだけです。
JPQL クエリは次のように記述できます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | @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 に進みます。
2. 実体化されたパス
ltree は、(ツリーの最上部から始まる) 実体化されたパスとして階層ツリー構造を操作するために使用できる Postgres 拡張機能です。たとえば、リーフ ノード 8 のパス 1.2.4.8 を記録する方法は次のとおりです。いくつかの便利な機能が搭載されています。これをテーブルの列として使用できます:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 コマンドを使用して、前に見た隣接リストに使用されたテーブルから生成されたデータを移行することです。これもまた、各ステップで要素をアキュムレータに収集する再帰的クエリです。
1 2 3 4 5 6 7 8 9 10 11 12 | public class ClassImportIntegratorProvider implements IntegratorProvider {
@Override
public List<Integrator> getIntegrators() {
return List.of(
new ClassImportIntegrator(
singletonList(
Employee. class
)
)
);
}
}
|
ログイン後にコピー
ログイン後にコピー
上記のコマンドで生成されたエントリは次のとおりです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | @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):
でマッピングできます。
1 2 3 4 5 6 | create table employees
(
id bigserial primary key,
manager_id bigint references employees
name text,
);
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
いくつかのクエリを作成する準備ができました。ネイティブ SQL では、次のようになります:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | 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 ネイティブ オペレーターの置換を定義できるようになります。
1 2 3 4 5 | postgres=# select count (*) from employees;
count
-------
15
(1 row)
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
次に、次のように FunctionContributor として登録する必要があります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 行追加します。
わかりました、クールです!ついに次のクエリを作成できるようになりました:
1 2 3 4 5 | postgres=# select count (*) from employees;
count
-------
15
(1 row)
|
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
たとえば、このメソッドを次のように呼び出して、ID = 2 を含むすべてのパスを取得できます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | @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 を操作するための幅広い関数セットを提供します。それらは公式ドキュメントページで見つけることができます。便利なチートシートもあります。
データの一貫性を確保するには、スキーマに制約を追加することが重要です。このトピックに関して見つけた優れたリソースは次のとおりです。
3. ネストされたセット
直感を示す画像を使用するのが最も簡単です。ツリーの各ノードには、ID のほかに追加の「左」列と「右」列があります。ルールは、すべての子の左と右が親の左と右の値の間にあることです。
上記のツリーを表すテーブル構造は次のとおりです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 構文に変換しました。それは次のとおりです:
1 2 3 4 5 6 7 8 9 10 11 12 | public class ClassImportIntegratorProvider implements IntegratorProvider {
@Override
public List<Integrator> getIntegrators() {
return List.of(
new ClassImportIntegrator(
singletonList(
Employee. class
)
)
);
}
}
|
ログイン後にコピー
ログイン後にコピー
わかりました。いくつかのクエリを実行する準備ができました。祖先を取得する方法は次のとおりです。
1 2 3 4 | @DynamicPropertySource
static void registerPgProperties(DynamicPropertyRegistry registry) {
registry.add( "spring.jpa.show_sql" , () -> true);
}
|
ログイン後にコピー
子孫の場合は、まず左側と右側を取得する必要があり、その後、以下のクエリを使用できます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | 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 つのアプローチすべてについて、ツリーを上り下りする方法を確認しました。旅を楽しんでいただけて、お役に立てば幸いです。
Postgres とドキュメント/グラフ データベースの比較
上記の例で使用したデータベースは 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 サイトの他の関連記事を参照してください。