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である．つまり，以下のようなテーブル定義をすればよい．

```python
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`は以下．

```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として入れる．

```python
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`は以下．

```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`を追加したものを用いて，様々な操作を行う．

```python: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`をかければよい．

```python
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())
```
実行例

```python
>>> 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`をかければよい．

```python
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())
```
実行例

```python
>>> 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`をかければよい．

<!-- 
\###ノードを挿入する
挿入するノードの`name`，挿入する位置を決めるために，そのノードの親ノードの`id`，子ノードの`id`を指定する．
作業は大きく分けて以下の5つある．
1. `nodes`テーブルに新しいノードを追加する(`:=self_node`)
2. 自分自身の`TreePath(descendant_node_id=self_node_id, ancestor_node_id=self_node_id, depth=0)`を追加する
3. 挿入位置よりも上のノード(`:=upper_node`)に対して，`TreePath(descendant_node_id=upper_node_id, ancestor_node_id=self_node_id, depth=depth)`を追加する．
4. 挿入位置よりも下のノード(`:= lower_node`)に対して，`TreePath(descendant_node_id=self_node_id, ancestor_node_id=lower_node_id, depth=depth)`を追加する．
5. すでに存在している`TreePath(upper_node_id, lower_node_id, depth)`の`depth=depth+1`

例えば，上で出した木構造のB(`id=2`)とF(`id=6`)の間に，J(`id=10`とする)を追加したければ，
1. nodesテーブルに`name="J"`のノードを追加する
2. `TreePath(descendant_node_id=10, ancestor_node_id=10, depth=0)`を追加する
3. `upper_node=["A", "B"]`であり，
   `TreePath(descendant_node_id=1, ancestor_node_id=10, depth=2)`と
   `TreePath(descendant_node_id=2, ancestor_node_id=10, depth=1)`を追加する
4.  `lower_node=["F", "I"]`であり，
   `TreePath(descendant_node_id=10, ancestor_node_id=6, depth=1)`と
   `TreePath(descendant_node_id=10, ancestor_node_id=9, depth=2)`を追加する
5. `(descendant_node, ancestor_node)=("A", "F"), ("A", "I"), ("B", "F"), ("B", "I")`の組み合わせのdepthを1だけ増やす
とすればよい．

```python
import models

class DBOperation(object):
    def insert_node(self, name, parent_node_id, child_node_id, session):
        """
        rootとして挿入したければparent_node_id=None
        leafとして挿入したければchild_node_id=Noneとする
        """
        #1
        node=models.Node(name=name)
        session.add(node)
        session.flush()
        self_node_id=node.id
        #2
        tree_path=models.TreePath(descendant_node_id=self_node_id, ancestor_node_id=self_node_id, depth=0)
        session.add(tree_path)
        #3
        upper_tree_path_list=session.query(models.TreePath).filter(models.TreePath.ancestor_node_id==parent_node_id).all()
        for upper_tree_path in upper_tree_path_list:
            tree_path=models.TreePath(descendant_node_id=upper_tree_path.descendant_node_id, ancestor_node_id=self_node_id, depth=upper_tree_path.depth+1)
            session.add(tree_path)
        #4
        lower_tree_path_list=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==child_node_id).all()
        for lower_tree_path in lower_tree_path_list:
            tree_path=models.TreePath(descendant_node_id=self_node_id, ancestor_node_id=lower_tree_path.ancestor_node_id, depth=lower_tree_path.depth+1)
            session.add(tree_path)
        #5
        for upper_tree_path in upper_tree_path_list:
            for lower_tree_path in lower_tree_path_list:
                tree_path=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==upper_tree_path.descendant_node_id).filter(models.TreePath.ancestor_node_id==lower_tree_path.ancestor_node_id).one()
                tree_path.depth=tree_path.depth+1
```
\###ノードを削除する
作業は大きく分けて2つある．
1. 削除するノードの`id`を`descendant_node_id`または`ancestor_node_id`に含む`TreePath`のレコードを削除する．
   (`Foreing Key制約`で`ondelete=CASCADE`としているので，`nodes`テーブルから削除したいノードを削除すればよい．)
2. 削除位置よりも上のノード(`:=upper_node`)，削除位置よりも下のノード(`:=lower_node`)に対して，
   `TreePath(upper_node_id, lower_node_id, depth)`の`depth=depth-1` 


```python
import models

class DBOperation(object):
    def delete_node(self, target_node_id, session):
        #1
        session.query(models.Node).filter(models.Node.id==target_node_id).delete()
        #2
        #削除位置より1つ上にあるnodeを探す
        parent_tree_path_list=session.query(models.TreePath).filter(models.TreePath.ancestor_node_id==target_node_id).filter(models.TreePath.depth==1).all()
        #削除位置より1つ下にあるnodeを探す
        child_tree_path_list=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==target_node_id).filter(models.TreePath.depth==1).all()
        if len(parent_tree_path_list)!=0 and len(child_tree_path_list)!=0: #もし削除位置がrootでもleafでもなければ
            for parent_tree_path in parent_tree_path_list:
                parent_node_id=parent_tree_path.descendant_node_id
                for child_tree_path in child_tree_path_list:
                    child_node_id=child_tree_path.ancestor_node_id
                    upper_tree_path_list=session.query(models.TreePath).filter(models.TreePath.ancestor_node_id==parent_node_id).all()
                    lower_tree_path_list=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==child_node_id).all()
                    for upper_tree_path in upper_tree_path_list:
                        for lower_tree_path in lower_tree_path_list:
                            tree_path=session.query(models.TreePath).filter(models.TreePath.descendant_node_id==upper_tree_path.descendant_node_id).filter(models.TreePath.ancestor_node_id==lower_tree_path.ancestor_node_id).one()
                            tree_path.depth=tree_path.depth-1
```
-->

#参考文献
この記事は以下の情報を参考にして執筆しました．
・[閉包テーブル（Closure Table）を試してみた](https://enomotodev.hatenablog.com/entry/2015/11/19/235300)
・[SQL: ナイーブツリーと閉包テーブルモデル](https://blog.amedama.jp/entry/2016/05/18/234343)