データベース

ポイント86.3

• データベースガイダンス2022
• データベースの用語など
• SQLの基本
• 集約関数と副問い合わせ
• GROUP BY HAVINGとビューテーブル
• ERモデル
• データべースの設計と正規形
• データベースの物理設計
• トランザクション処理
• B木とB+木とハッシュ法
• NoSQLと Google firestore

データベースシステムとして、最近は NoSQL (Not Only SQL) が注目されている。この中で、広く使われている物として、Google Firestore などが有名である。教科書以外の最近のデータベースの動向ということで、最後に NoSQL の説明を行う。

リレーショナルデータベースシステムの問題

リレーショナルデータベースのシステムでは、大量の問い合わせに対応する場合、データのマスターとなるプライマリサーバに、そのデータの複製を持つ複数のセカンダリサーバを接続させる方式がとられる。しかしながら、この方式ではセカンダリサーバへのデータ更新を速やかにプライマリサーバに反映させる、さらにその結果が他のセカンダリサーバに反映させる必要があることから、大量のデータに大量の問い合わせがあるようなシステムでは、これらのデータ同期の性能が求められる。しかも、プライマリサーバが故障した場合の復旧なども考えると、こういったプライマリ・セカンダリ・サーバ構成での運用・管理は大変である。

NoSQLの利点

NoSQLのデータベースでは、すべてのデータを複数のサーバ(別のデバイス,ネットワーク)に冗長化したうえで分散して保存する。この際に、どのサーバがプライマリサーバといった概念はない。もし1つのサーバが故障したとしても、分散して保存されたデータから元のデータを自動的に修復できるような構造となっている。

データの分散保存であれば、ハードディスクの RAID システムなども関連知識となるであろう。

• RAID0 – ストライピング(データを別デバイスに分散保存し、並行読み出しで高速化)
• RAID1 – ミラーリング(データを複数デバイスに同じものを書き込んで、データ故障耐性を実現)
• RAID5 – データを複数デバイスに分散保存する際に、データ誤り訂正のデータも分散保存し、高速化と故障耐性を実現
• RAID6 – データ誤り補正のデータを複数もたせて、分散保存

リレーショナルデータベースで大量のユーザからアクセスされる場合、データが安全に取り扱うことができたり、システムに障害が発生した時の対応や、システムのスケーラビリティ(利用状況に応じて処理するプロセッサなどを増やしたり減らしたりする機能)が重要となる。NoSQLのシステムでは、中心となるプライマリサーバを作るのではなく、データを複数のシステムに分散して保存し、障害が発生しても、分散したデータから自動的にデータを修復できるような構成とする。

NoSQLのシステムでは、データ格納形式から、キーバリューストア型、カラムストア型、ドキュメントデータベース、グラフデータベースに分類される。最も代表的なものは、保存するデータ(Value)に対し検索するためのキー(Key)だけの基本的なデータ検索だけを提供する キーバリューストア(Key-Value store)である。こういった構成ではSQLとは違い、複数のテーブルをまたがった検索などができない(サブコレクションなどを使えば代用可能)。

Google の Firestore

NoSQLのデータベースを構築したのは、Google が先駆けであった。現在、このGoogle の NoSQL のシステムは、Firestore として利用されている。(データベースはFireBase)

Firestore は、ドキュメントモデルデータベースの一種であり、すべてのデータはドキュメントとコレクションに保存される。ドキュメントは、データベースでのレコードに相当するが、属性名とそれに対応したデータの JSON オブジェクトである。コレクションは、キーにより対応するドキュメントを取り出せるデータ群である。ドキュメントの中に、サブコレクションを保存することもできる。

データベースでは、キーなどの値を高速に探し出すために、単純なデータが並んだだけのテーブルとは別に、検索専用のデータ構造を別に持たせることが多い。これらの検索用のデータは、インデックスファイルと呼ばれる。また、データベースのテーブルのデータも、高速に検索する機能とすべてのデータを順次取り扱うための機能が求められる。これらの機能を実現するための仕組みを以下に説明する。

B木

データベースのデータを扱う場合には、B木を用いることが多い。(4年の情報構造論で説明済み)

複数のデータを格納するノードは、位数Nであれば、2✕N個のデータと、その間のデータを持つノードへの2N+1個のポインタで構成される。

ノードにデータを加える場合(あるいは削除する場合)は、頻繁にノードのポインタの付け替えが発生しないように、データがN個を下回った時や、2N個を超える場合に以下のような処理を行う。ノード内のデータ数が2Nを超える場合は、均等に木構造が成長するように、中央値を上のノードに移動し、ノードを2分割する。

データを削除することでN個を下回る場合は、隣接するノードからデータを移動する。(上図の緑部分のように上位ノードの値を交えながら移動する)

このような処理を行うことで、極力不均一に成長した木構造が発生しないようにB木は管理されている。

B+木とシーケンスセット

再帰的な木構造のB木では、特定のデータを探す場合には、O(log N)で検索が可能である。

しかしながら、直積のようなすべてのデータを対象とする処理を行う場合、単純なB木では再帰呼出しをしながらの処理を必要とすることから、複雑な処理が発生する。そこで、データ列を横方向にアクセスするための単純リストであるシーケンスセットをB木と並行して管理するデータ構造がB+木である。

データを検索する場合は、B木構造部を用い、全データ処理は、シーケンスセットを用いる。

ハッシュ法

ハッシュ表は、データの一部をとりだしてハッシュ値を求め、そのハッシュ値を番地とする場所にデータを保存する方法である。しかし、データの一部を取り出すため、異なるデータに対して同じハッシュ値となる場合がある。これをハッシュ衝突とよぶ。この際のデータの保存の方法から、2つの方式がある。

1. オープンアドレス法
   ハッシュ表がすでに埋まっていたら、別の保存場所を探す方式。
2. チェイン法
   同じハッシュ値となるデータをリスト構造で保存する方法。

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

• C言語でのファイルロック(共有ロック,排他ロックの機能あり)

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

1. ロッキング方式(悲観的制御)
   先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。
   • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
     
   • ロックの種類
     ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
     この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
   • 2相ロッキングプロトコル
     トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
2. 時刻印処理(楽観的制御)
   データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ばれる。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼ばれ、始点(行)と終点(列)の経路がある所を1で表す。

最初にテストを返却した後、データベース物理設計の話を行う。来週はレポート課題作成日とすることから、課題を以下に示す。

データベース後半課題

データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。

情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。

レポートで記載する内容は、以下の通りとする。

• 卒業研究におけるデータベース化する対象の説明
• データベースをトップダウン設計する際の
  • 実体と関連を抽出するまでの説明
  • 正規化を行う経過の説明
  • 上記を踏まえたトップダウン設計でのER図
• データベースをボトムアップ設計する際の
  • 対象とする帳票に相当するデータの一例と説明
  • レベル分けや正規化を行う経過の説明
  • 上記を踏まえたボトムアップ設計でのER図
• 考察
  • トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
  • 両設計方法から分かったこと

データベースの物理設計

データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。

ディスク容量の見積もり

データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。

実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。

そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。

また、データベースへのデータの削除を行う場合、データが１つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。

このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。

一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。

また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。

補足：残り予定：トランザクション処理, 内部構造, テスト前レポート課題

特殊な条件演算子

WHERE 節の中で使える特殊な条件演算子を紹介する。

... AND ...
   WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ;
... OR ...
   WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ;
NOT ...
   WHERE NOT S.業者番号 >= 100 ;
... IN ...
   WHERE S.業者番号 IN ( 'S1' , 'S4' ) ;
... BETWEEN A AND B 
   WHERE S.優良度 BETWEEN 50 AND 100 ;
... LIKE ...
   WHERE S.業者名 LIKE 'A_C社' ;   _ は任意の1文字　ABC社 ADC社
   WHERE S.業者名 LIKE 'A%社' ;    % は任意の0～N文字 A社, AA社 ABC社
... IS NULL
   WHERE S.業者名 IS NULL
   WHERE S.業者名 IS NOT NULL

集約関数

集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。

COUNT() - 項目の数
SUM() -   項目の合計
AVG() -   項目の平均
MAX() -   項目の最大値
MIN() -   項目の最低値

SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;

• 実験環境で集約関数(学内のみ)

集合計算

複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。

... UNION ...  集合和
... EXPECT ... 集合差
... INTERSECT ... 集合積

SELECT S.業者名 FROM S WHERE S.所在 = '福井'
UNION
SELECT S.業者名 FROM S WHERE S.所在 = '東京'

• 実験環境で集合計算(学内のみ)

SQLの副問い合せ

前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。

SELECT S.業者名, S.所在
  FROM S
  WHERE S.業者番号 IN
     ( SELECT SG.業者番号
         FROM SG
         WHERE SG.商品番号 = 'G2'
           AND SG.在庫量 >= 200 ) ;

• 実験環境で副問い合わせ(学内のみ)

まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。

この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。

{(S1,G2,200),(S2,G2,400),(S3,G2,200),(S4,G2,200)}が該当し、その業者番号の{S1,S2,S3,S4}が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN {‘S1′,’S2′,’S3′,’S4’} を実行する。

相関副問い合わせ

SELECT G.商品名, G.色, G.価格
  FROM G
  WHERE 'S4' IN 
     ( SELECT SG.業者番号
         FROM SG
         WHERE SG.商品番号 = G.商品番号 ) ;

• 実験環境で相関副問い合わせ(学内のみ)

この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。

処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。

// 概念の説明用に、C言語風とSQL風を混在して記載する
for( int i = 0 ; i < sizeofarray( G ) ; i++ ) {
   SELECT SG.業者番号 FROM SG
    WHERE SG.商品番号 = G[i].商品番号 を実行
   if ( WHERE 'S4' IN 副query の結果が真なら ) {
      printf( ... ) ;
   }
}
// 全てのG 副queryの結果     WHERE 射影
// G1 ->  {S1,S2}
// G2 ->  {S1,S2,S3,S4} -> ◯ -> (ノート,青,170)
// G3 ->  {S1}
// G4 ->  {S1,S4}       -> ◯ -> (消しゴム,白,50)
// G5 ->  {S1,S4}       -> ◯ -> (筆箱,青,300)
// G6 ->  {S1}

演習課題

SQLの実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。

さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。

• サンプルプログラム

考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。