Hatena::ブログ(Diary)

Ynishi Bussiness Logs このページをアンテナに追加 RSSフィード

2013-04-26 SQLアンチパターン1

SQLアンチパターンを読んだ感想を書きたいと思う。全体の感想は別として、まず各論のパターンについての感想を書く。

SQLアンチパターン

SQLアンチパターン

ジェイウォーク(信号無視)

|  ジェイウォーク(信号無視)を含むブックマーク  ジェイウォーク(信号無視)のブックマークコメント

ひとつの属性に複数の値を入れてしまうというもの。例えば、一人の社員が複数の部署に属するからといって、社員のテーブルの部署という項目にカンマ区切りで属する部署を入れてしまうといった設計である。問い合わせが難しくなったり、参照整合性制約が設定できない、長さに制約があるなどの理由から、アンチパターンであるとしている。はじめからこんな設計をする人はいないと思うが、変更するときにテーブルを作るのが面倒、または極端にテーブルの結合を忌避する人たちがこのような設計を選択するのかもしれない。COBOLのデータ定義にはこのような繰り返し項目が存在するらしいが、RDBでは第一正規形に違反しているともいえ、扱いに困る。

さすがに、こういう設計はあまりみない。ただし、私がよく見るのは固定長で異なる意味を持たせたコードを定義している設計である。例えば、10桁の社員コードの1−3桁が事業部で4−7桁が課、8−10桁が連番といったような体系を、そのまま社員コードとして属性(列)に定義する。事業部や課を取り出すのはSUBSTRING等の文字列の一部きりだして使用する。これもCOBOLでは構造化された項目として定義が可能なのだが、RDBでは存在しないため、大変扱いにくい。

設計する上では、内部的な格納構造と外部的な表示を分けるべきである。つまり、コードは確かに桁で意味を持たせた方が人間にとってはわかりやすいので、外部的な表示はこれでよい。しかし、DBに格納する場合は分割したそれぞれの列として保持すべきである。理由はこのアンチパターンとほぼ同じである。このパターンでは長さに制約があるという理由になっているが、このような固定長の構成になっている場合は、例えば連番がつきて桁が足りない場合はプログラム自体から作り直しが入るなど悲惨なことになってしまう。

なお、一桁目が分類でそれ以降の分割はその分類毎に異なるような設計も見られる。例えば、地方の事業部だけは、4桁目がどこの地方かを表し、5桁目から8桁目が課を示すなどである。いずれにせよ、このような設計アンチパターンだと言えよう。

ナイーブツリー(素朴な木)

|  ナイーブツリー(素朴な木)を含むブックマーク  ナイーブツリー(素朴な木)のブックマークコメント

木構造を隣接リストで表現すると、n階層の検索をすることができなくなったり、ノード全体を削除するのが複雑になるという主張である。隣接リストとは、親への参照を作成するだけである。自分自身と親への参照を持っているに過ぎない設計なので、ある非葉ノードを削除する場合は、下層から削除しないと、参照整合性制約でエラーに成ってしまう。A-B-C-Dという構造があり、C以下を削除しようとした場合にCを先に削除するとDがもつCへの参照が切れてしまうという問題である。

一方、このアンチパターンを使用しても良い場合の一つとして、階層問い合わせが紹介されている。一部のDBMS再帰的なクエリを記述することができるためn階層の検索が(やや複雑ではあるが)可能になる。

さて、このパターンではとても気になる記述があった。

例えば、ノードの数(スレッドのコメント数)をCOUNTで数えたり、ノードの値(例:製造業の各部品のコスト)をSUMで合計する場合などにはすべての子孫を対象にする必要があります。(p 16)

このうち、前の方の記述は良い。メールのスレッド木構造である。ただ、後ろは多くの場合は正しくない。製造業の各部品のコストということは、部品表を想定しているようだが、部品表は多くの場合は木構造ではない。DAG(非循環有向グラフまたは無閉路有向グラフ)である。違いは一つの部品の親は複数であるということだ。共通して使われる部品は多数ある。こういう場合は、木構造にはならない。そして、そうした場合は、殆どの場合、隣接リストによる表現が一般的な設計となる。先ほど話したように、リレーショナルモデルは配列を持てないので、一般的には「親部品コード・子部品コード」を主キーにした「部品表テーブル」という設計が一般的である。この設計ではA-B-C-Dの構造でC以下を削除する際に、B-C、C-Dの順番で消しても参照整合性制約の違反にはならない。

さて、次に解決策を1つずつ見ていく。

経路列挙

これは、先のジェイウォークのアンチパターンを使って一つ上の親だけでなく祖先全体をもつというやり方である。たとえばパスをスラッシュで区切る例を出している。例えば、コメントの階層を1/4/6/7というように表現し、このままの形で保存する。1/4の下を検索したい場合はLike '1/4/%'とすればよい*1

さて、アンチパターンを使わないようにするなら、テーブルはやはり分けるべきであろう。ただし、そうすると順序がわからなくなる。この時は木のレベル(深さ)をデータとして持てば良い。上記であればこのようなテーブルを別に作る。

レベル祖先コメントID子コメントID
017
147
267

とすると、1/4の下を検索するSQLは以下のとおりである。

select

 *

from

 コメントデータ

 inner join

 祖先コメントテーブル on

コメントデータ.コメントID = 祖先コメントテーブル.子コメントID

where

 祖先コメントテーブル.祖先コメントID = 4

;

ちなみにこの解決策は「閉包テーブル」という名前でこの本のおすすめの解決策の一つとして記述されている。なお、木構造なので、1/4の下は4の下と同じ意味である。DAGで、親が複数あったとしても親に応じて子が変わるわけではないので、同じパターンの検索で良い。

ただし、この本にもあるように、経路列挙は経路列挙値をソートすると階層全体を深さ優先探索の並び順で表示できるが、閉包テーブルは実現が難しい。閉包テーブルは自分の祖先や子供に何がいるかを検索するのには便利だが、階層構造全体を表現する際に一般的な深さ優先探索の並び順で検索することが簡単にはできない。

入れ子集合

1の子に2と3、3の子に4と5があるとする。このとき、親をX、子をYとZとした時にX(Y Z)と表現すると、下記のようになる。

1(2() 3(4() 5()))

この括弧の位置を保存する。例えば1であれば、1と10。2であれば、2と3となる。そうすると、子孫はこの位置の間に常にある。祖先は逆に自分の括弧の位置を含む値を取得すれば良い。ただし、直近の親をとるには、自身と親の間にノードがないことを検索する必要が有るため、複雑になる(外部結合して、NULLのものをとるというやりかた)。ただ、自分の祖先のうち、開始カッコが最も大きいものを取ればいいので、SQLだけで頑張らなければ比較的やさしい。一方で、括弧の位置を再構築するのにコストがかかるのが厳しい。ちなみに、再構築を減らすという入れ子区間モデルとは、実数を使って間に割り込ませるという素晴らしい方法である。

また、階層構造の深さ優先探索の検索も左側のカッコの順番で検索すれば簡単だ。

私の結論

この本に真っ向から対立するようだが、私は隣接リスト+階層問い合わせを最優先に考えるべきだと思う。素朴な構造であるがゆえに、更新処理に対する影響が最も出にくい。とにかく一番怖いのは、バグなどによりデータの整合性が壊れることである。それが最も起きにくい。ただし、先に述べたように親と子のペアのテーブルを別に作るという前提であり、この本の例のような1つのテーブルの中に親への参照だけをひとつ持っているという設計はかなりまずい。DAGにも応用できない。

木構造であれば、私は入れ子集合も検討すべきだと思う。この本では全くおすすめされていないが、実数を使うという入れ子区間モデルのアイデアはやはり素晴らしい。洗い替えが必要な点だけが問題だが、経路列挙の順番(深さ優先探索の順番)で簡単に検索もでき、ジェイウォークのアンチパターンにもはまらない。

*1:厳密にはLIKE '%/4/%'でもよい。ただし、前方一致ではないため、索引を設定しても使用されないという問題がある。索引は通常昇順で格納されているため、前方一致なら範囲検索ができる。

トラックバック - http://d.hatena.ne.jp/yuuntim/20130426