ポリモーフィック関連の解消 - 直和による表現

# はじめに

ポリモーフィック関連は、「SQLアンチパターン[^anti]」でも例示されているように、よほどの理由がなければ使うべきでないものである。

[^anti]: https://www.oreilly.co.jp/books/9784873115894/

「SQLアンチパターン」では、ポリモーフィック関連の解消策として交差テーブル(中間テーブル)を使った方法を紹介しているが、本稿では、関連先のテーブルの数があまり多くない場合に使える方法として、筆者が「直和表現」と呼んでいる方法(すでに他の名前がついているものだったら教えてください)とその考え方を紹介する。

# 結論

記事が長くなったので、先に結論を書く。

* ポリモーフィック関連の代わりに「関連先候補のテーブルの外部キーを全て保持し、1つ以外はNULLにする」方法がある。
* これは集合論における内部直和の表現形式という数学的背景がある。
* また、これは「SQLアンチパターン」の解消策として紹介されている交差テーブルを用いた方法をあらかじめ外部結合したものと捉えることもできる。
* 関連先のテーブルの数が10個程度であれば現実的な選択肢となりうる。


# なぜポリモーフィック関連を使いたくなるのか

そもそも、なぜポリモーフィック関連を使いたくなるのだろうか。

例として、次のような状況を考える。

* あるウェブサービスにおいて、ユーザーは`記事`と`質問`を投稿することができる。
* `記事`や`質問`に対して他のユーザーが`コメント`をつけることができるようにしたい。
* `記事`に対する`コメント`と、`質問`に対する`コメント`は1つのテーブルで管理したい事情がある。

つまり、次のような Comment 型を関連データベース上で表現したい。

```typescript
class Comment{
    target: Article | Question;
    commented_user: User;
    comment_text: string;
}
```

ポリモーフィック関連では、`target`表現するために `target_type` と `target_id` という2つのカラムを用いる。

図: ポリモーフィック関連
![スクリーンショット 2023-01-08 22.01.48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309088/da359195-c194-a8b8-9451-b1f13117c54b.png)


`target_type`にはQuestionやArticleなどの関連先テーブルを表す文字列(またはenum)が入り、`target_id`には関連先テーブルにおける主キーが入る。
このような設計は一見合理的に見えるが、`Comment.target_id`は`Question.question_id`と`Article.article_id`のいずれを表しているかが不明なため、外部キー制約を張ることができない。
これは、`Articl.article_id`と`Question.question_id`は、同じ整数型ではあるものの、それぞれ「Articleの主キー」「Questionの主キー」全く別の「型」を表しており、これを静的に解決することができない問題であると考えることもできる。

では、なぜこのようなポリモーフィック関連による設計が合理的に見えてしまうのだろうか？
「Article または Question への関連」を考えるとき、「関連先が他にもあるかもしれない」と考える人は多いだろう。このように「関連先が増える(可変である)」ことを念頭に入れると、「関連先のテーブル」と「関連先テーブルの主キー」の「掛け算」として考えることが自然に思えるかもしれない。


```math
\mathrm{Type} = \{\mathrm{Article}, \mathrm{Question}, \cdots \}, \\
\mathrm{ID} = \{1, 2, 3, \cdots \}, \\
\mathrm{target} = (t, i) \in \mathrm{Type} \times \mathrm{ID}
```

いきなり数式を出してしまったが、これはつまり、`target`を選択する際に、横軸にType、縦軸にIDを並べた以下のような表の中から1マスを選択することに相当する。

図: ポリモーフィック関連の「掛け算」のイメージ
![](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309088/321bf5f0-2ac0-6228-9645-4cf78481cef7.png)


この表現はTypeの数が増えても2つのカラムだけで表現することができるので効率的に思えるが、本当に合理的な表現方法と言えるだろうか？
ポリモーフィック関連の問題点として、「Articleの主キー」「Questionの主キー」全く別の「型」を1つの`target_id`というカラムに押し込めてしまっているため、静的に型を解決できない点であると述べた。
ここでいえば、`(Article, 1)` と `(Question, 1)` は同じ `ID=1` という値を共有しているが、本来は全く関係無いものである。

関係無いものを関係無いものとして正しく表現するためにはどうすれば良いだろうか。
そのためには、「TypeとIDの掛け算」ではなく、「全く異なる複数のIDの足し算」として捉えることである。
図で表すと以下のようなイメージである。

図: 「足し算」のイメージ
![スクリーンショット 2023-01-08 20.49.28.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309088/2bf853d0-36b0-3bcd-6675-d1c1a33395ff.png)

以下では、ポリモーフィックな関連を「足し算」で表現するためにはどうすべきかについて考えていく。

# 直積と直和

上記で「掛け算」「足し算」と言っていたものは、数学的にはそれぞれ集合の **直積** および **(内部)直和** のことである。
ここでは、集合論において直積と直和をどのような形式で表現しているかを簡単に解説する。

### 直積

集合の直積とは、各集合から要素を1つずつ取ってくるあらゆる組み合わせの集合のことである。
例えば、集合AとBの直積 A×Bは、Aの要素aとBの要素bのタプル(a,b)をの集合である。

A = {a1, a2}, B = {b1, b2, b3} とすれば、
A×B = {(a1, b1), (a1, b2), (a1, b3), (a2, b1), (a2, b2), (a2, b3)}
となる。
A×Bの要素数は、Aの要素数とBの要素数の積となる。

上述の例では、ポリモーフィック関連とは、Type = {Article, Question} と ID = {1, 2, 3, …} の直積によって関連先を表現したものであると理解される。

### (内部)直和

直和とは、簡単にいえば「交わりのない和集合」のことである。
ただし、集合Aと集合Bに同じ要素xが含まれていたとしても、AとBの直和集合 $A+B$ の中では、「A由来のx」と「B由来のx」を区別する必要がある。
上記の例で言えば、「ArticleのID=1」と「QuestionのID=1」を区別することに相当する。

数学の集合論で内部直和を表す際に一般的に用いられるエンコーディングは次のようなものである。

> A や B に属さない記号をたとえば * として、集合 A* ≔ A ∪ {\*}, B* ≔ {\*} ∪ B を考えてやると、二つの埋め込み
> ```math
> {\displaystyle A\hookrightarrow A^{*}\times B^{*};\;a\mapsto (a,*),} \\
> {\displaystyle B\hookrightarrow A^{*}\times B^{*};\;b\mapsto (*,b)} \\
> ```
> が得られ、この埋め込みによって A* × B* の部分集合と見なした A, B は交わりを持たない。この埋め込み像を記号の濫用で A*, B* と書けば A* × B* の部分集合としてとった和集合 A* ∪ B* を A と B の直和といい A ⊔ B などと書く[^plus]。
>
> *Wikipedia 日本語版 [直和#集合論的直和]((https://ja.wikipedia.org/wiki/%E7%9B%B4%E5%92%8C#%E9%9B%86%E5%90%88%E8%AB%96%E7%9A%84%E7%9B%B4%E5%92%8C)) より*

[^plus]: Wikipedia では集合の直和の記号として「⊔」を用いているが、本稿では「足し算」であることを強調するため、単に「+」と表記する。

数学的形式になじみがない人にとってはわかりづらいかもしれないので、エンジニアにわかりやすい言葉を使って説明すると以下のようになる。

- A や B に属さない記号「*」とは、「NULL」のようなものである。
- 「A*」 とは、Aの要素にNULLを加えたものである。
    - たとえば、 A = {1, 2, 3, ...} の場合、 A* = {NULL, 1, 2, 3, ...} である。
- 「A* × B*」 とは、 (a, b) の形(a, b は NULLもok)で表されるあらゆる組み合わせの集合である。
    - たとえば、 (1, 3), (2, NULL), (NULL, 4), (NULL, NULL) などは A* × B* の要素である。
- 「埋め込みによって A* × B* の部分集合と見なした A, B」 とは、「Aの要素を (a, NULL)、Bの要素を (NULL, b) として表現する」ことを意味する。
    - 例えば、 「A由来の1」は(1, NULL)、「B由来の4」は(NULL, 4)として表現される。


例えば、 A = {1, 2, 3}, B = {2, 4} とすると、
A + B = {(1, NULL), (2, NULL), (3, NULL), (NULL, 2), (NULL, 4)}
となる。


上述の「記事または質問」の例でいえば、Articleの集合 A = {a1, a2, a3} とQuestionの集合 Q={q1, q2, q3} の直和集合を取ると、
A + Q = {(a1, NULL), (a2, NULL), (a3, NULL), (NULL, q1), (NULL, q2), (NULL, q3)}
となる。

こうすることで何が嬉しいかというと、集合A+Qの要素 (a1, NULL), (NULL, q1) 等は、1要素目がAnswer (またはNULL), 2要素目がQuestion (またはNULL)といった具合に、静的に型が決まる。
これにより、AnswerとQuestionという全く異なる対象を区別して扱うことができる。

以上では2つの集合の直和を扱ったが、3つ以上の場合も同様に、「1つだけがNULLでないタプルの集合」として表すことができる。
例えば3つの集合の直和の場合、(a, b, c)の形のタプルでa,b,c のうち1つだけがNULLでないものの集合として表す。


# 内部直和による表現

上述の集合論における内部直和のエンコードによって、ポリモーフィックな関連を表現する。
最初の例に戻ると、「コメントの対象となる記事または質問」を直和によって表現すると次のようになる。

図: 直和表現を用いた設計
![スクリーンショット 2023-01-08 22.03.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309088/c0d049bb-f7dc-d221-99d3-f521321bb5f6.png)


Comment は単純に Nullable な `article_id` と `question_id` の両方のカラムを持つ。
ただし、`article_id`と`question_id`のうち**NULLでないのはどちらか一方のみ**である。
このように実装することで、


これは、「SQLアンチパターン」 6.5.2節「交差テーブル」の方法における、中間テーブルを外部結合したものみることもできる。
いま、交差テーブルを用いた実装の場合、次のようになる。

図: 交差テーブルを用いた設計
![スクリーンショット 2023-01-08 22.04.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/309088/ecfeb350-538f-b2dc-ceb4-fc9b1de4b610.png)

この場合において、以下のように交差テーブルを結合すると、直和表現が得られる。

```sql
SELECT
    Comment.comment_id,
    ArticleComment.article_id,
    QuestionComment.question_id,
    Comment.commented_user_id,
    Comment.commented_text
FROM
    Comment
LEFT OUTER JOIN
    ArticleComment USING comment_id
LEFT OUTER JOIN
    QuestionComment USING comment_id
```

一方で、直和表現の一部を取り出すことで交差テーブルを再現することもできる。
例えば、直和表現のCommentテーブルからArticleCommentテーブルを抽出する場合、単にarticle_idが非NULLなものを取り出すだけで良い。

```sql
SELECT
    article_id,
    comment_id
FROM
    Comment
WHERE
    article_id IS NOT NULL
```

このように、直和表現と交差テーブルを用いた方法は表裏一体の関係にあると言える。

交差テーブルを用いた方法と比べた際の直和表現のメリットは、以下の通りである。

- 構造が簡単である
    - 複数の交差テーブルを定義する必要がない。
    - 関連の深さも浅くなるため、参照速度の上でも有利である。
- Commentテーブルを見ただけで、何に対するコメントであるかを判断できる。
    - 交差テーブルを用いた方法の場合、あるCommentに対応するArticleまたはQuestionを探そうとした場合、ArticleCommentとQuestionCommentの両方を探す必要がある。
    - 特に、関連先テーブルが増えた場合、全てのテーブルを関連先候補として探さないといけないため、交差テーブルを用いた方法はこの方向の参照に不利である。
- CHECK制約をかけられる
    - 「article_idとquestion_idのどちらか一方のみが非NULLである」というのを、SQLのCHECK制約[^check]によって検証することができる。
    - 交差テーブルの場合、1つのCommentを参照するArticleCommentとQuestionCommentが両方作成されてしまうことをDB制約で禁止することができない。

[^check]: 例えばMySQLの場合 https://dev.mysql.com/doc/refman/8.0/ja/create-table-check-constraints.html

一方で、直和表現にはデメリットも存在する。

- テーブルがスパースになってしまう
    - `article_id` と `question_id` のいずれか一方は必ず NULL のため、交差テーブルを用いた方法に比べてデータ効率が悪い。
    - 関連先が2つの場合はまだ良いが、３つ４つと増えていったとき、1つ以外は全てNULLとなるため、この問題は深刻となる。
- 関連先を追加するたびに既存テーブルへのカラム追加が必要となる。
    - 交差テーブルの場合、新たなテーブルを作れば良いだけだが、直和表現の場合、Commentテーブルに新たなカラムを追加しなければならない。
    - 小さな違いだが、すでにレコードが存在するテーブルへのカラム追加は、テーブル追加に比べ、マイグレーションやそのロールバックが難しいという問題がある。

特に1つ目の問題は重要であり、関連先のテーブルが大量に存在する場合には直和表現を用いるのは難しい。
それでも、関連先候補のテーブル数が少ない(だいたい~10程度)場合には、直和表現は現実的な選択肢になるのではないかと考えている。

もっとも、交差テーブルを用いた場合についても、CommentからArticleやQuestionを引く方向に関連を辿る場合には、問い合わせの際に結局両方のテーブルを結合する必要があるため、直和表現のテーブルをその場で作成しているのと変わらない。関連先が増えるとその分結合すべきテーブルも増えていくので、交差テーブルを用いる方法も関連先のテーブルがあまりにも多い場合には現実的な手法とは言えない。
CommentからArticleとQuestionを引くのではなく、ArticleやQuestionからCommentを辿る方向にしか参照しなければ良いと考えるかもしれないが、そもそも、記事へのコメントと質問へのコメントをCommentという1つのテーブルにする必要があるのは、同じ「コメント」として同一視して検索したりすることができるようにするためであって、記事へのコメントと質問へのコメントを同一視する必要がないのであれば、これらを1つのテーブルにまとめるべきではない。
つまり、Commentを1つのテーブルにまとめたいという要件がある以上、Comment側からArticleやQuestionを辿る必要が生じ、そのため問い合わせの際にすべてのテーブルを結合する必要が生じ、それは直和表現のテーブルをその場で作成することに他ならない。

結局、直和表現は、交差テーブルを用いた方法の結合処理を高速化するため、データ容量(空間計算量)を犠牲に、あらかじめ交差テーブルを結合したものと位置付けられるものであると考えられる。

# まとめ

本稿では、ポリモーフィック関連の代替策として、「直和による表現」ともいうべき方法を紹介した。
1つ以外のカラムを全てnull にするなんて非効率でカッコ悪いと思うかもしれないが、静的に型を解決できたり、参照速度が高速であるなど何かと扱いやすい形式なので、関連先の種類が少ない場合には有効な手法であると考えている。