応用情報技術者の勉強をしています。

Question

応用情報技術者の勉強をしています。データベースの分野で、

データの正規化
完全関数従属、部分関数従属、推移関数従属の見分け方がいまいちわかりません。

データベースの方式
B-Treeインデックス、転置インデックス、ハッシュインデックス、ビットマップインデックスの説明と見分け方も教えてほしいです。

よろしくお願いします。

Answer 1

■完全関数従属 full functional dependency
Ｘ→Ｙで、かつ、ＹがＸのいかなる射影についても 関数従属が成り立たないこと。
たとえば、属性Ｘ＝(x1,x2,x3,x4) と、４つの要素からなる時、 この「要素の真部分集合」たとえば(x1,x2,x3)とか(x2,x4)から Ｙを一意に定めることが出来てしまったら、 Ｘ→Ｙは完全関数従属とは言えない （部分関数従属である)。 (x1,x2,x3)だけからＹが決まるなら、x4はＹを決めるには あっても無くても良い要素である。 主キーの中からレコードを一意に決めるのに 「あっても無くても無い要素」を除いた形式が 第二正規形となる。
具体例で示す。 [生徒番号・試験科目コード]という連結属性Ｘに対して、 [科目得点]Ｙ1は、[生徒番号]だけ、もしくは[試験科目コード]だけが決まっても、 一意には値が定まらない。つまり、
Ｙ1は、Ｘのどんな射影(要素の真部分集合)に対しても 関数従属が成りたたない、
逆に言えば、Ｙ1の値を定めるには、Ｘの全ての要素の値が 決まっている必要がある。
従って、[科目得点]Ｙ1は、[生徒番号・試験科目コード]Ｘに対して、 完全関数従属である。
一方、[生徒氏名]Ｙ2は、[生徒番号・試験科目コード]Ｘの射影である [生徒番号]だけが決まれば、一意に値が定まってしまう。つまり、
Ｙ2は、Ｘの射影に対して関数従属が成り立つ
逆に言えば、Ｙ2の値を定めるには、Ｘの一部の要素の値が 決まっていれば後は関係ない。(あっても無くてもいい。)
従って、[生徒氏名]Ｙ2は、[生徒番号・試験科目コード]Ｘに対して、 完全関数従属では無い。

■部分関数従属 partial functional dependency
属性Ｘの一部の要素にＹが従属するとき、ＹはＸに部分関数従属であると言う。
{Ｘ1,Ｘ2}→Ｙであり、Ｘ1→Ｙであれば、 Ｙは{Ｘ1,Ｘ2}に部分関数従属する。

■推移的関数従属 transitive functional dependency
既存の関数従属から、 新たな関数従属を得られる時、推移的関数従属がある、と言う。
例えば、[取引コード]Ｘ→[取引先会社コード・取引先会社名]Ｙという関数従属関係がある時、 よく見ると、Ｙの中で、[取引先会社名]Ｙ2は、 やはりＹの中の[取引先会社コード]Ｙ1に関数従属である。 つまり、Ｘ→Ｙという関数従属は、詳しく見ると Ｙ1→Ｙ2という関数従属を含んでいる。 （Ｘ→Ｙ1→Ｙ2、という関数従属関係の連鎖が見られる。）

データベースの構造
検索の条件により必要な索引構造は異なるため、異なる構造を持つ複数の索引を提供するデータベース製品も存在する。

●B-Tree
多くのデータベースは、索引に B-Tree (または B+Tree, B*Tree) 構造を採用している。
B-Treeは範囲検索にも利用できる。
B-Treeを使った索引では、索引定義の際の順序が重要である。
最初の列のみを条件とした検索であれば索引は利用できるが、2番目以降の列を指定するだけでは索引は利用できない。
索引のキーを (住所, 苗字, 名前) とする電話帳データベースを例に挙げると、住所が与えられればこの索引を使った検索ができるが、苗字だけではできない。

●ハッシュインデックス
ハッシュ関数に基づく索引は、一般にB-Treeよりも性能面およびサイズ面で有利であるが、範囲検索はできず、完全一致検索にのみ利用できる。

●ビットマップインデックス
ビットマップ索引はキーの濃度 (カーディナリティ; cardinality) が低い場合に適した索引である。
例えば、「性別」を表す列 (「男性」または「女性」の値のみを含む) に対して索引を作成する場合には、B木よりも効率が良い。
ビットマップ索引は、それぞれのキー値ごとにビットマップ (ビットの配列) を作成し、その各ビットはレコードがキーを含んでいるかを表す。
また、ビット演算を行うことにより複数のビットマップ索引を同時に利用することもできる。

●多次元索引
B-Treeに基づく索引はキーがスカラー値である場合にのみ適用できる。GIS (地理空間情報) データ型等の多次元空間上での位置や広がりを持つデータに対しては、kd木や汎用検索ツリーを用いた多次元索引が利用される。

●転置インデックス
一般的な索引は、1つの行は1つのキーのみを持つことを前提としている。一方、配列の各要素を検索する場合や、文書を全文検索する場合には、1つの行から複数のキーが抽出されうる。これらのデータに対しては転置インデックスが利用される。