SQLと関係代数 正規化・クエリ最適化編

佐久間 正樹

前回「SQLと関係代数 基本演算編」に引き続き、データベースの数学的表現とその応用について考えます。今回はリレーションの正規化とクエリ最適化についてです。

1 正規化の数学的表現

表（テーブル、リレーション）の名前と属性集合の組による抽象化をリレーションスキーマ、リレーションスキーマに従う実際のデータが入ったリレーションをそのリレーションスキーマのインスタンスと言って区別することもありますが、同一視することもあります。また、属性自体とその属性の値を同じ記号で表すことがあります（通常の数学で変数の値を変数名と同じ記号で表すのと同様）。

\(X\)や\(Y\)が一つの属性からなるときは、その属性と一元集合を混同します。

アームストロングの公理系は、以下の3つの公理からなります。

• \(X\subset Y\Longrightarrow X\to Y\)（自明な関数従属性、反射律）

• \((X\to Y)\land (Y\to Z)\Longrightarrow X\to Z\)（推移律）

• \((X\to Y)\land (Z\subset W)\Longrightarrow X\cup W\to Y\cup Z\)（添加律、増加律）

自明な関数従属性の公理は狭義の反射律\(X\to X\) (\(\forall X\))を含意します。これらの公理を繰り返し適用することで、\(F\)から論理的に従う全ての関数従属性を過不足なく挙げることができます。

例えば、\(\Omega_R=\{A, B, C, D, E\}\)で、関数従属が\(\{A, B\}\to C, \{B, C\}\to D, D\to \{A, E\}\)のとき、候補キーは\(\{A, B\}, \{B, C\}, \{B, D\}\)の3つあります（データベーススペシャリスト試験平成29年春期過去問題問4より）。

なお、候補キーに非NULL制約（それを構成する全ての属性がNULLを許容しないという条件）をつけるかどうかについては流派が分かれています。「任意に選んだ候補キーを主キーとする」という立場では非NULL制約が付きますが、ここでは非NULL制約については考えません。

関数従属性集合\(F\)が与えられた関係\(R\)に対し、\(K\)が\(R\)のスーパーキーであることは\(K\in 2^{\Omega_R},(K\to \Omega_{R})\in F^{+}\)と同値です。

関係\(R\)に対して、関数従属の集合\(F\)が与えられているとします。このとき、正規形は主に\((R,F)\)の分解の構成要素に対して考える性質です。正規形のテーブルに分解することを正規化と言います。正規化することで重複や冗長性を削減すると同時に、データの一貫性を担保することができます。

1.1 第2正規形 (2NF)

第2正規形は、部分関数従属性の排除とよく言われますが、第1正規形（全ての属性値がスカラ値）であって、かつ、任意の非キー属性がどんな候補キーの真部分集合にも関数従属していない（任意の候補キーに完全関数従属する）という制約です。

分解後の任意のリレーション\(R'\)が第2正規形であるとは形式的には次を意味します。 \[\forall K\in\mathcal{K},\forall A \in \Omega_{R'}\setminus \bigcup \mathcal{K}; [X\subseteq K,(X \rightarrow A) \in F^{+}[\Omega_{R'}] \Rightarrow X=K].\] ここで、\(\mathcal{K}=\{\text{候補キー}\}\subseteq 2^{\Omega_{R'}}\)です。

1.2 第3正規形 (3NF)

第3正規形は、推移的関数従属性の排除とよく言われますが、第2正規形であって、かつ、任意の非キー属性が任意の候補キーに非推移的に（直接的に）関数従属していることを要求するものです。

形式的には \[\forall A \in \Omega_{R'}\setminus \bigcup \mathcal{K}; \forall (X \rightarrow A) \in F^{+}[\Omega_{R'}]; A \notin X \Rightarrow \exists K\in \mathcal{K};X\supseteq K\] ということです。

1.3 3NFへの無損失分解定理

情報無損失分解であるためには\(\bigcup_{i=1}^n\Omega_{R_i}=\Omega_R\)が必要ですが、十分ではありません。また、属性名の組み合わせが同じ分解の仕方であっても、関数従属性の内容によって情報無損失かどうかは変わります。例えば、\(R(A,B,C)\)を\(R_1(A,B)\), \(R_2(B,C)\)に分解するとき、関数従属性が\(FD=\{B\to A\}\)や\(FD=\{B\to A,B\to C\}\)であればこの分解は情報無損失である一方、関数従属性が\(FD=\{A\to B\}\)の場合は一般には情報無損失ではありません。十分条件の一つとして、共通属性が分解後の少なくとも一方の候補キーであれば情報無損失です。

\(\bigcup_{i=1}^n\Omega_{R_i}=\Omega_R\)の下では、\(\Join_{i=1}^n R_i\supseteq R\)は常に成り立つため、この逆向きの包含が成り立つ、つまり自然結合で余計な行が新たに現れないことが情報無損失性の必要十分条件です。実は関数従属性より弱い多値従属性という概念を用いて同値条件が記述できます。

要するに、\(X\)のみで\(Y\)の取り得る値の集合が決まる（\(X\)でも\(Y\)でもない属性の影響を受けない）ということは、言い換えれば、\(X\)への射影が等しければ\(X\)でも\(Y\)でもない属性をお互いに交換したものもタプルになっているということと同義だということです。この同値条件を多値従属性の定義とする流儀もあります。

2NFから3NFへの無損失分解は必ずしも従属性保存ではありませんが、3NF Synthesis Algorithmと呼ばれる無損失分解アルゴリズムの結果は従属性保存なので上の定理が成立します。

ボイスコッド標準形は自動的に第3正規形になります。複数の属性からなる候補キーが複数存在しない場合は第3正規形はボイスコッド標準形に一致します。また、任意の第3正規形はボイスコッド標準形へ、ボイスコッド標準形は第4正規形へ無損失分解できます。ただし、第3正規形からボイスコッド標準形へ、ボイスコッド標準形から第4正規形へは、従属性を保存したまま変換する方法が存在しない場合があります。

2 関係代数とクエリ最適化

2.1 クエリを木構造で表現することによるクエリ最適化

関係代数において、SQLのクエリは抽象構文木（abstract syntax tree; AST）として表現することができます。この木構造では、各ノードが関係代数の演算（射影\(\pi\)、選択\(\sigma\)、直積\(\times\)、結合\(\bowtie\)、集合演算など）に対応し、葉ノードが基底関係（テーブル）となります。部分木は部分関係代数式に対応します。

例えば、次のようなSQL文を考えます。

SELECT name
FROM Employee, Department
WHERE Employee.dept_id = Department.id
  AND Department.location = 'Tokyo';

このクエリを素朴に関係代数で記述すると次のようになります：

\[\pi_{\text{name}} \left( \sigma_{\text{location} = 'Tokyo'} (\text{Employee} \bowtie_{\text{Employee.dept\_id = Department.id}} \text{Department}) \right)\]

この関係代数式を構文木として表現すると、次のような階層になります：

• \(\pi_{\text{name}}\)（射影） ← ルート

  • \(\sigma_{\text{location} = 'Tokyo'}\)（選択）

    • \(\bowtie_{\text{Employee.dept\_id = Department.id}}\)（等値結合）

      • Employee（基底関係）

      • Department（基底関係）

木構造にすると、行数や列数を減らす制限演算や射影演算をより下層（葉に近い早い段階）に「押し込む（push down）」ことでクエリ処理における中間結果のサイズを削減したり、共通の部分関係代数式を再利用したりするクエリ最適化が可能となることが可視化されます。

例えば、選択\(\sigma_{\text{location} = 'Tokyo'}\)は、結合の前にDepartment関係に適用することで、不要なタプルの結合を回避できます。つまり次のような式に変換することで、処理コストを削減できます：

\[\pi_{\text{name}} \left( \text{Employee} \bowtie_{\text{dept\_id = id}} \sigma_{\text{location} = 'Tokyo'}(\text{Department}) \right)\]

このように、関係代数の交換則や結合法則を用いて木構造の演算順序を変更することで、より効率的なクエリ処理が実現できます。以下の演算法則に基づく木構造の変換もクエリ最適化に有用です。上では非常に単純なクエリしか扱っていませんが、複雑になればなるほど、そしてデータが増えるほど効率化が図れます。

• \(\sigma_{A}\sigma_{B}(R)=\sigma_{A\land B}(R)=\sigma_{B}\sigma_{A}(R)\)

• \(\sigma_{A\land S_R\land S_P}(R\times P)=\sigma_A (\sigma_{S_R}(R)\times \sigma_{S_P}(P))\)（\(S_R\)は\(R\)の属性のみ、\(S_P\)は\(P\)の属性のみから構成される条件）

• \(\sigma_{A}(R\setminus P)=\sigma_{A}(R)\setminus \sigma_{A}(P) =\sigma_{A}(R)\setminus P\)

• \(\sigma_{A}(R\cup P)=\sigma_{A}(R)\cup\sigma_{A}(P)\)

• \(\sigma_{A}(R\cap P)=\sigma_{A}(R)\cap\sigma_{A}(P)=\sigma_{A}(R)\cap P=R\cap \sigma_{A}(P)\)

実際によく使われているクエリパフォーマンスの改善手法には以下のようなものがあり、関係代数的に表現できるものもあれば、インデックスの作成などのように関係代数の枠組みには収まりきらないものもあります。

• 相関サブクエリやサブクエリ内での関数演算を共通テーブル式やウィンドウ関数を使って事前集約する。関係代数では新たな関係変数(テーブルを表す変数)を定義して媒介させることに相当。

• 相関サブクエリを非相関サブクエリに変換する。

• LIMIT句を利用して不要な行を取得するのを避ける。

• 小さいテーブルを先にJOINする（Nested Loop Joinを想定）。関係代数では結合律\((R \Join S)\Join Q=R\Join (S\Join Q)\)の適用に当たる。

• 更新頻度が低く、特定のJOIN演算を頻繁に行う場合、非正規化する。

• CTEやサブクエリのマテリアライズを回避する。（コンピュータの問題なので関係代数は無関係）

• 事前にWHERE句、ORDER BY句の条件やJOIN句の結合条件として頻繁に使われる属性に対してB+木インデックスを作成しておく。

• インデックスが作成されている属性の値にはなるべく定数倍などの演算を適用しないなど、既存のインデックスが使用できるようにクエリを同値変形する。

MySQLやPostgreSQLなどの実際のリレーショナルデータベース管理システムでは裏で自動的にクエリパフォーマンスを向上させるための最適化を行なってくれているため、記述したSQL文を文字通りに関係代数式として解釈したような処理がそのまま実行されるとは限りません。この最適化には、フルスキャンするかインデックスを活用するかの判断のような関係代数とはあまり関係ない最適化も含まれますが、選択・射影の下方移動や結合順序の変更などの関係代数式の変換に対応する処理も含まれます。前述のSQL文も関係代数式の変形により効率化された形で実行されます。この様子はEXPLAIN（実行計画の表示）やEXPLAIN ANALYZE（実際に実行して様子を分析）を用いると、木構造として確認できます。RDBMSの内部では次のような流れでパフォーマンスを維持しています。

SQL → 関係代数的な論理計画（木構造） 
    → 論理的最適化（関係代数変形）
    → コスト推定に基づく物理計画 → 実行

もちろん、このような自動的な最適化には限界があるので、人間側、つまり、SQL文を記述する側がなるべく効率的なクエリを作成するように意識することも大切です。この場面でも関係代数式の変形公式が役立ちます。

3 まとめ

関係代数の基本演算は直感的でありながら強力であり、全てのSQL結合を代数構造や木構造を通して理論的に支える構成要素です。SQL文がどのように数学的操作に分解できるかを理解することで、クエリ最適化やデータベース設計においてより深い洞察を得ることができます。