NaaN日記

やったこと、覚えたことを発信する場

閉包テーブルに触れてみる

はじめに

これは、SLPアドベントカレンダー最終日の記事となっています。毎日異なる部員が執筆を行ってきました。私を含んだ、25人の記事をお楽しみください。

adventar.org


SQLアンチパターンを読み始めました。まだ読んでいる途中ですが、良い本です。
さて、この本の2章では、ナイーブツリーの話題が登場します。
そこでは、階層的なデータ設計が比較されます。

  • 隣接リスト
  • 再帰クエリ
  • 経路列挙
  • 入れ子集合
  • 閉包テーブル


今回、この中から閉包テーブルを選択して、コメント管理機能を作成しました。その中から部分的にプログラムを載せています。
閉包テーブルは、ツリー全体のパスを格納する方法です。特徴には、ノードが複数のツリーへ所属することが挙げられます。メインのテーブルとは別に、木構造のパスを記憶するテーブルを持ちます。

開発環境

  • ホストOS : Windows10 Pro 1909
  • ゲストOS : ArchLinux ( Kernel 4.19.88-1-lts x86_64)
  • Golang : 1.13.0
  • MySQL : 8.0.17
  • Echo 3.3.10 (Go web framework)
  • jmoiron/sqlx (database/sqlのラッパー)

テーブルの作成

CREATE TABLE comments (
    id BIGINT AUTO_INCREMENT NOT NULL PRIMARY KEY,
    body TEXT NOT NULL,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
    deleted_at TIMESTAMP DEFAULT NULL,
    user_id INT NOT NULL REFERENCES user(id),
    question_id INT NOT NULL REFERENCES question(id)
);

CREATE TABLE tree_paths (
    ancestor BIGINT UNSIGNED NOT NULL REFERENCES comments(id),
    descendant BIGINT UNSIGNED NOT NULL REFERENCES comments(id),
    PRIMARY KEY (ancestor, descendant)
);
comments
属性* 概要*
id コメントのid。コメントを投稿すると、1から自動的に割り振られる
body コメントの内容
created_at コメントの作成時間
updated_at コメントの編集時間
deleted_at コメントの削除時間
user_id コメントを投稿した人のid
question_id 質問した話題のid
tree_paths
属性* 概要*
ancestor そのコメントの先祖となるコメントid
descendant そのコメントの子孫となるコメントid

ancestorとdescendantは、組み合わせが主キーとなっています。
自分自身を示すためには、両方の属性が同じidを持ちます。

コメントの登録

コメントを登録するには、2つの手順が必要です。

  1. コメントの挿入
  2. コメントのパスの挿入

プログラム内で、構造体は下のように定義しました。

type Comment struct {
	ID        uint64     `db:"id"`
	Body      string     `db:"body"`
	CreatedAt *time.Time `db:"created_at"`
	UpdatedAt *time.Time `db:"updated_at"`
	DeletedAt *time.Time `db:"deleted_at"`
	UID       uint64     `db:"user_id"`
	QID       uint64     `db:"question_id"`
}

/questions/:id へPOSTリクエストが行われると、ハンドラが呼び出されます。

func (comment *commentHandler) PostCommentHandler(c echo.Context) error {
        uid := getUserID()
	id := c.QueryParam("cid")
	body := c.FormValue("comment")
	param := c.Param("id")
	qid, err := strconv.ParseUint(param, 10, 64)
	if err != nil {
		return err
	}
	
	cid, err := strconv.ParseUint(id, 10, 64)
	if err != nil {
		return err
	}

	message := model.Comment{Body: body, UID: uid, QID: qid}
	fmt.Println(uid, qid, cid, body)
	err = comment.commentModel.CreateComment(&message, cid)
	if err != nil {
		return err
	}

	route := "/questions/" + param
	fmt.Println(route)
	return c.Redirect(http.StatusSeeOther, route)
}

コメントは、CreateCommentで作成されます。
CreateCommentの引数のparent_idは、コメントの親のIDです。
先祖を持たないコメントのとき、parent_idは0としています。
SELECT LAST_INSERT_ID()は、MySQL情報関数です。
最後にINSERTされたコメントのIDを取得するために用いています。

type CommentModel struct {
	db *sqlx.DB
}
// CreateComment -- Insert comment data
func (c *CommentModel) CreateComment(comment *model.Comment, parent_id uint64) error {
	var id uint64
	_, err := c.db.Exec(`INSERT INTO comments (body, user_id, question_id) VALUES (?, ?, ?)`, comment.Body, comment.UID, comment.QID)
	if err != nil {
		return err
	}
	err = c.db.Get(&id, "SELECT LAST_INSERT_ID()")
        if err != nil {
		return err
	}
	if parent_id == 0 {
		parent_id = id
	}
	_, err = c.db.Exec(`INSERT INTO tree_paths (ancestor, descendant) SELECT tree_paths.ancestor, ? FROM tree_paths WHERE tree_paths.descendant = ? UNION ALL SELECT ?, ?`, id, parent_id, id, id)
	return err
}

上のプログラムから、TreePathへのINSERT文を抽出しました。

INSERT INTO tree_paths (ancestor, descendant)
    SELECT tree_paths.ancestor, id FROM tree_paths
    WHERE tree_paths.descendant = parent_id
    UNION ALL SELECT id, id;

理解を深めるために、実際に挿入しながら考えていきます。


ここに、おすすめのテキストエディタを尋ねる質問があります。
CommentIDが7の人はVS Codeを、8の人はVimを勧めました。
ここで、8の人に対して学生R(CommentID: 9)がEmacsを勧めると、どうなるでしょうか。
図で書くと、このようになるはずです。

属性には、先祖となるコメントIDと、子孫となるコメントIDを持ちます。
そのため、tree_pathsには、(8, 9), (9. 9)の二つがINSERTされるはずです。

mysql> SELECT tree_paths.ancestor, 9 FROM tree_paths
    -> WHERE tree_paths.descendant = 8
    -> UNION ALL SELECT 9, 9;

+----------+---+
| ancestor | 9 |
+----------+---+
|        8 | 9 |
|        9 | 9 |
+----------+---+

> SELECT tree_paths.ancestor, 9
1列目にtree_paths.ancestor、2列目に9を射影
> FROM tree_paths WHERE tree_paths.descendant = 8
子孫のIDが、挿入するIDの親と等しいtree_pathsのテーブルを選択
> UNION ALL SELECT 9, 9;
自分自身を指す9, 9の行と結合

コメント情報の取得

質問に対しての全てのコメントをデータベースから取得するのなら、質問番号で選択すれば良いです。

func (c *CommentModel) All(question_id uint64) ([]model.Comment, error) {
	comments := []model.Comment{}
	err := c.db.Select(&comments, "SELECT * FROM comments WHERE question_id = ?", question_id)
	if err != nil {
		return nil, err
	}

	return comments, nil
}

次の関数では、指定されたコメントIDの子孫を全て取得します。tree_pathsで、指定されたコメントIDが先祖となっている行を選択します。

func (c *CommentModel) GetDescendant(id uint64) ([]model.Comment, error) {
	comments := []model.Comment{}
	err := c.db.Select(&comments, "SELECT comments.* FROM comments INNER JOIN tree_paths ON comments.id = tree_paths.descendant WHERE tree_paths.ancestor = ?", id)
	if err != nil {
		return nil, err
	}

	return comments, nil
}

先ほどのコメントに対し、学生Oと学生Sが参加しました。


学生Iの子孫を表示

学生Rの子孫を表示


おわりに

二つのテーブルを用いているため、どちらか一方のみを間違えないよう、一つのテーブルを用いるとき以上に気を使う必要があると感じました。コメントを登録するCreateComment関数では、データを二度INSERTします。しかし、現時点では、二番目のINSERTが失敗した際の、ロールバックを行う処理は未実装です。そのため、優先度高めで対応したいと思います。
また、tree_pathsに深さの属性を追加することで、直近の親子関係を簡潔に調べることができます。今回、その部分の設計は行わなかったので、今後、その部分の設計が必要かどうか、考えたいです。
今回、プログラムの全てをここに記述したわけではありません。またリファクタリングを行った際、記事にする予定です。