【応用情報】用語集[せ]

線形探索法

　探索対象データの先頭から順に探索していく方法で、整列されていないデータ、特に使用頻度(探索の多い)順に格納されているデータを探索するのに有効。探索対象データがN個のとき、探索が終了するまでの最小比較回数は1回、最大比較数はN回なので、平均比較回数は(N+1)/2となる。なお、Nが十分大きい場合の平均比較回数はN/2と考えられる。

　線形探索法では、探索したいデータと同じデータを探索対象データの末尾に追加することで、探索の終了判定を単純化することができます。これを番兵法といいます。

正規化と非正規化

　正規化の目的は、データ操作にともなう更新時異常の発生を防ぐこと。正規化により属性間の関数従属を少なくし、かつ、データの重複を排除することで更新時異常の発生を防ぐことができる。しかし、正規化を進めると表がいくつにも分割されるため、そこから必要なデータを取り出すには、表の結合が必要となり処理時間がかかる。そのため、処理速度が厳密に要求されたり、更新時異常の発生が低い場合(たとえば、更新が少ない表に対して)は、あえて正規化を進めないか、あるいは正規化したものを元に戻す、非正規化を行う。なお、ここでいう非正規化とは、アクセスパターンを考慮したうえで、どの表を統合させるか、どの属性を表間に重複させるかを考えることをいう。