【DB入門】従属性保存分解の定義

2023年9月20日

北川博之著「データベースシステム（オーム社）」を参考に，データベースシステムの知識をまとめます。

データベース記事一覧

従属性保存分解の定義

リレーションスキーマ$RS$，$RS$の分解$\rho=\{RS_{1},\ldots,RS_{m}\}$，$RS$に関する関数従属性集合$F$が与えられたとします。もし，任意の関数従属性$X\rarr Y\in F$に対して

\begin{align}
\pi_{RS_{1}}(F)\cup\cdots\cup\pi_{RS_{m}}(F) &\models X~\rarr~Y
\end{align}

が成立するならば，分解$\rho$は$F$に関する従属性保存分解であるといいます。ただし，$G\models H$は関数従属性集合$G$が関数従属性集合$H$を論理的に含意していることを表し，$\pi$は関数従属性集合の射影を表します。

補足

日本語で噛み砕くと「分解後の関数従属性集合の射影を全て合わせると元の従属性を論理的に含意しているとき，その分解は従属性保存分解となる」という定義です。イメージとしては，リレーションを分解するときに関数従属性の矢印をブチっと切らないような分解のことを指しています。

例

$RS=\{A,B,C\}$と$F=\{A\rarr B, B\rarr C, C\rarr B\}$に対し，関数従属性集合の定義で考えたように，

$AB$に対する関数従属性の射影$\pi_{AB}(F)$は$\{A\rarr B\}$
$AC$に対する関数従属性の射影$\pi_{AC}(F)$は$\{A\rarr C\}$
$BC$に対する関数従属性の射影$\pi_{BC}(F)$は$\{B\rarr C, C\rarr B\}$

となります。いま，$\{\{A,B\},\{B,C\}\}$という分解を考えたときに，射影の和集合は

\begin{align}
\pi_{AB}(F)\cup\pi_{BC}(F) &= \{A\rarr B, B\rarr C, C\rarr B\}\label{AB_BC}
\end{align}

となります。このとき，式($\ref{AB_BC}$)が$F$の任意の関数従属性集合を論理的に含意しているため，$\{\{A,B\},\{B,C\}\}$は従属性保存分解となります。ちなみに，論理的に含意に言及せずとも，射影の和集合が$F$そのものになっていることからも，$\{\{A,B\},\{B,C\}\}$が従属性保存分解であることは明らかともいえます。一方，$\{\{A,B\},\{A,C\}\}$という分解を考えたときに，射影の和集合は

\begin{align}
\pi_{AB}(F)\cup\pi_{AC}(F) &= \{A\rarr B, A\rarr C\}\label{AB_AC}
\end{align}

となります。このとき，式($\ref{AB_AC}$)が$F$の任意の関数従属性集合を論理的に含意していないため，$\{\{A,B\},\{A,C\}\}$は従属性保存分解となりません。具体的には，$C\rarr B$の関数従属性が抜け落ちてしまっています。