Closure Tableを用いてRDBで木構造を扱う

はじめに

rdbで木構造を扱うための，最もシンプルな方法としてNaive Trees(素朴な木)がある．しかし，Naive Treesには様々な欠点があるためアンチパターンとされている．
アンチパターンを回避するための方法は様々あるが，ここではその1つであるClosure Table(閉包表)という方法を説明する．
以下，対象とする木構造は次のようなものを想定する．

A
├ B
│ ├ D
│ ├ E
│ └ F
│   └ I
└ C
  ├ G
  └ H

ここでは，SQLAlchemyを用いてテーブル定義などを行っていく．

Naive Trees

まずは，Naive Treesについて説明する．

テーブル定義

「自分の親のidだけをもつ」というのがNaive Treesである．つまり，以下のようなテーブル定義をすればよい．

class NaiveTree(Base):
    __tablename__="naive_trees"
    __table_args__=({"mysql_charset": "utf8mb4"})
    id=Column(Integer(unsigned=True), nullable=False, autoincrement=True, primary_key=True)
    name=Column(String(255), nullable=False)
    parent_id=Column(Integer(unsigned=True), ForeignKey("naive_trees.id", name="fk_naive_trees_00"), nullable=True)

実行されるsqlは以下．

CREATE TABLE naive_trees (
    id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, 
    name VARCHAR(255) NOT NULL, 
    parent_id INTEGER UNSIGNED, 
    PRIMARY KEY (id), 
    CONSTRAINT fk_naive_trees_00 FOREIGN KEY(parent_id) REFERENCES naive_trees (id)
)CHARSET=utf8mb4

例えば，上で出した木構造は，以下のようにテーブルに保存すればよい．

id	name	parent_id
1	A	NULL
2	B	1
3	C	1
4	D	2
5	E	2
6	F	2
7	G	3
8	H	3
9	I	6

欠点

欠点は多くあるが，その1つとして，あるノードの子孫，先祖を取ってくることが難しいということがある．
例えば，Bの子孫を全て取ってこようと思うと，4回JOINする必要がある．

Closure Table

次にClosure Tableについて説明する．

テーブル定義

Closure Tableでは，ノードの情報を持つテーブルと，木構造の情報を持つテーブルの計2つのテーブルを用いる．
ノードの情報を持つテーブルでは，木構造のことは考えずに，ノードの情報だけを入れていく．
木構造の情報を持つテーブルでは，「あるノード」と「その子孫ノード」の全ての組み合わせを「深さ(距離)」と共に入れていく．
ただし，「あるノード」と，「そのノード自身」の組み合わせも深さを0として入れる．

class Node(Base): #ノードの情報
    __tablename__="nodes"
    __table_args__=({"mysql_charset": "utf8mb4"})
    id=Column(Integer(unsigned=True), nullable=False, autoincrement=True, primary_key=True)
    name=Column(String(255), nullable=False)

class TreePath(Base): #木構造の情報
    __tablename__="tree_paths"
    __table_args__=({"mysql_charset": "utf8mb4"})
    descendant_node_id=Column(Integer(unsigned=True), ForeignKey("nodes.id", onupdate="CASCADE", ondelete="CASCADE", name="fk_tree_paths_00"), nullable=False, primary_key=True) #先祖
    ancestor_node_id=Column(Integer(unsigned=True), ForeignKey("nodes.id", onupdate="CASCADE", ondelete="CASCADE", name="fk_tree_paths_01"), nullable=False, primary_key=True) #子孫
    depth=Column(Integer(unsigned=True), nullable=False)

実行されるsqlは以下．

CREATE TABLE nodes (
    id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT, 
    name VARCHAR(255) NOT NULL, 
    PRIMARY KEY (id)
)CHARSET=utf8mb4

CREATE TABLE tree_paths (
    descendant_node_id INTEGER UNSIGNED NOT NULL, 
    ancestor_node_id INTEGER UNSIGNED NOT NULL, 
    depth INTEGER UNSIGNED NOT NULL, 
    PRIMARY KEY (ancestor_node_id, descendant_node_id), 
    CONSTRAINT fk_tree_paths_00 FOREIGN KEY(ancestor_node_id) REFERENCES nodes (id) ON DELETE CASCADE ON UPDATE CASCADE, 
    CONSTRAINT fk_tree_paths_01 FOREIGN KEY(descendant_node_id) REFERENCES nodes (id) ON DELETE CASCADE ON UPDATE CASCADE
)CHARSET=utf8mb4

例えば，上で出した木構造は，以下のようにテーブルに保存すればよい．

id	name
1	A
2	B
3	C
4	D
5	E
6	F
7	G
8	H
9	I

descendant_node_id	ancestor_node_id	depth
1	1	0
1	2	1
1	3	1
1	4	2
1	5	2
1	6	2
1	7	2
1	8	2
1	9	3
2	2	0
2	4	1
2	5	1
2	6	1
2	9	2
3	3	0
3	7	1
3	8	1
4	4	0
5	5	0
6	6	0
6	9	1
7	7	0
8	8	0
9	9	0

クエリ操作

ここからは，上のテーブル定義にmethodやrelationshipを追加したものを用いて，様々な操作を行う．

models.py

class Node(Base): #ノードの情報
    __tablename__="nodes"
    __table_args__=({"mysql_charset": "utf8mb4"})
    id=Column(Integer(unsigned=True), nullable=False, autoincrement=True, primary_key=True)
    name=Column(String(255), nullable=False)
    def to_dict(self):
        return {"id": self.id, "name": self.name}

class TreePath(Base): #木構造の情報
    __tablename__="tree_paths"
    __table_args__=({"mysql_charset": "utf8mb4"})
    descendant_node_id=Column(Integer(unsigned=True), ForeignKey("nodes.id", onupdate="CASCADE", ondelete="CASCADE", name="fk_tree_paths_00"), nullable=False, primary_key=True) #先祖
    ancestor_node_id=Column(Integer(unsigned=True), ForeignKey("nodes.id", onupdate="CASCADE", ondelete="CASCADE", name="fk_tree_paths_01"), nullable=False, primary_key=True) #子孫
    depth=Column(Integer(unsigned=True), nullable=False)
    #relationship定義
    descendant_node=relationship("Node", foreign_keys=[descendant_node_id], uselist=False, lazy="joined")
    ancestor_node=relationship("Node", foreign_keys=[ancestor_node_id], uselist=False, lazy="joined")

指定したノードの子孫を全て取ってくる

指定したノードのidをtree_pathsテーブルのdescendant_node_id(祖先のid)に指定してfilterをかければよい．

import models

class DBOperation(object):
    def get_ancestor_node(self, target_node_id, session):
        tree_path_list=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==target_node_id).all()
        for tree_path in tree_path_list:
            print(tree_path.ancestor_node.to_dict())

実行例

>>> DBOperation().get_ancestor_node(1, session)
{'id': 1, 'name': 'A'}
{'id': 2, 'name': 'B'}
{'id': 3, 'name': 'C'}
{'id': 4, 'name': 'D'}
{'id': 5, 'name': 'E'}
{'id': 6, 'name': 'F'}
{'id': 7, 'name': 'G'}
{'id': 8, 'name': 'H'}
{'id': 9, 'name': 'I'}

>>> DBOperation().get_ancestor_node(3, session)
{'id': 3, 'name': 'C'}
{'id': 7, 'name': 'G'}
{'id': 8, 'name': 'H'}

>>> DBOperation().get_ancestor_node(4, session)
{'id': 4, 'name': 'D'}

指定したノードを含みたくなければ，depth!=0という条件をつけてfilterをかければよい．

指定したノードの先祖を全て取ってくる

指定したノードのidをtree_pathsテーブルのancestor_node_id(子孫のid)に指定してfilterをかければよい．

import models

class DBOperation(object):
    def get_descendant_node(self, target_node_id, session):
        tree_path_list=session.query(models.TreePath).filter(models.TreePath.ancestor_node_id==target_node_id).all()
        for tree_path in tree_path_list:
            print(tree_path.descendant_node.to_dict())

実行例

>>> DBOperation().get_descendant_node(1, session)
{'id': 1, 'name': 'A'}

>>> DBOperation().get_descendant_node(3, session)
{'id': 1, 'name': 'A'}
{'id': 3, 'name': 'C'}

>>> DBOperation().get_descendant_node(4, session)
{'id': 1, 'name': 'A'}
{'id': 2, 'name': 'B'}
{'id': 4, 'name': 'D'}

指定したノードを含みたくなければ，depth!=0という条件をつけてfilterをかければよい．

参考文献

この記事は以下の情報を参考にして執筆しました．
・閉包テーブル（Closure Table）を試してみた
・SQL: ナイーブツリーと閉包テーブルモデル