ホーム » 「データベース」タグがついた投稿

タグアーカイブ: データベース

2018年12月
« 11月    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT                             RESULT
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90

((SQLの例))
select STUDENT.name , RESULT.subject , RESULT.point --射影--
   from STUDENT , RESULT                            --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --     --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

Wikipedia B+木 より引用

2018データベース・ガイダンス

シラバス:2018年度データベースシラバス

インターネットの情報量

インターネット上の情報量の話として、2010年度に281EB(エクサバイト)=281✕1018B(参考:kMGTPEZY)で、今日改めて探したら、2013年度で、1.2 ZB(ゼタバイト)=1.2✕1021B という情報があった。ムーアの法則2年で2倍の概算にも、それなりに近い。 では、今年2018年であれば、どのくらいであろうか?

そして、これらの情報をGoogleなどで探す場合、すぐにそれなりに情報を みつけてくれる。これらは、どの様に実装されているのか?

Webシステムとデータベース

まず、指定したキーワードの情報を見つけてくれるものとして、 検索システムがあるが、このデータベースはどのようにできているのか?

Web創成期の頃であれば、Yahooがディレクトリ型の検索システムを構築 してくれている。(ページ作者がキーワードとURLを登録する方式) しかし、ディレクトリ型では、自分が考えたキーワードではページが 見つからないことが多い。

そこで、GoogleはWebロボット(クローラー)による検索システムを構築した。 Webロボットは、定期的に登録されているURLをアクセスし、 そのページ内の単語を分割しURLと共にデータベースに追加する。 さらに、ページ内にURLが含まれていると、そのURLの先で、 同様の処理を再帰的に繰り返す。

これにより、巨大なデータベースが構築されているが、これを少ない コンピュータで実現すると、処理速度が足りず、3秒ルール/5秒ルール (Web利用者は次のページ表示が3秒を越えると、次に閲覧してくれない) これを処理するには負荷分散が重要となる。

一般的に、Webシステムを構築する場合には、 1段:Webサーバ、2段:動的ページ言語、3段:データベースとなる場合も 多い。この場合、OS=Linux,Web=Apache,DB=MySQL,動的ページ生成言語=PHPの組合せで、 LAMP構成とする場合も多い。

一方で、大量のデータを処理するDBでは、フロントエンド,スレーブDB,マスタDBのWebシステムの3段スキーマ構成となることも多い。

データベースシステム

データベースには、ファイル内のデータを扱うためのライブラリの、 BerkleyDBといった場合もあるが、複雑なデータの問い合わせを実現する 場合には、リレーショナル・データベース(RDB)を用いる。 RDBでは、データをすべて表形式であらわし、SQLというデータベース 問い合わせ言語でデータを扱う。 また、問い合わせは、ネットワーク越しに実現可能であり、こういった RDBで有名なものとして、Oracle , MySQL , PostgreSQL などがある。 単一コンピュータ内でのデータベースには、SQLite などがある。

データベースシステムと呼ばれるには、ACID特性が重要となる。

  • A: 原子性 (Atomicity) – 処理はすべて実行するか / しない のどちらか。
  • C: 一貫性 (Consistency) – 整合性とも呼ばれ、与えられたデータのルールを常に満たすこと。
  • I: 独立性 (Isolation) – 処理順序が違っても結果が変わらない。それぞれの処理が独立している。
  • D: 永続性 (Durability) – データが失われることがない(故障でデータが無くならないとか)

しかし、RDBでは複雑なデータの問い合わせはできるが、 大量のデータ処理のシステムでは、フロントエンドDB,スレーブDB,マスタDB の同期が問題となる。この複雑さへの対応として、最近は NoSQL が 注目されている。

データベースが無かったら

これらのデータベースが無かったら、どのようなプログラムを作る 必要があるのか?

情報構造論ではC言語でデータベースっぽいことをしていたが、 大量のデータを永続的に扱うのであれば、ファイルへのデータの読み書き 修正ができるプログラムが必要となる。

こういったデータをファイルで扱う場合には、1件のデータ長が途中で 変化すると、N番目のデータは何処?といった現象が発生する。 このため、簡単なデータベースを自力で書くには、1件あたりのデータ量を 固定し、lseek() , fwrite() , fread() などの 関数でランダムアクセスのプログラムを書く必要がある。

また、データの読み書きが複数同時発生する場合には、排他処理も 重要となる。例えば、銀行での預け金10万の時、3万入金と、2万引落としが 同時に発生したらどうなるか? 最悪なケースでは、 (1)入金処理で、残金10万を読み出し、 (2)引落し処理で、残金10万を読み出し、 (3)入金処理で10万に+3万で、13万円を書き込み、 (4)引落し処理で、残金10万-2万で、8万円を書き込み。 で、本来なら11万になるべき結果が、8万になるかもしれない。

さらに、コンピュータといってもハードディスクの故障などは発生する。 障害が発生してもデータの一貫性を保つためには、バックアップや 障害対応が重要となる。

データベースのテスト返却

後期中間試験が終わり、あわてて採点していたデータベースの返却。
来週が不在となるので、課題を出すなら、12/1 17:00 までとアナウンス。

データベースの設計

返却を終え、残り時間は後半の説明。

データベース設計には、概念設計、論理設計、物理設計に分けられる。
概念設計では、データベースによって管理の対象とするものを現実の世界から抽出して設計を行う。一般的にはER図などを描きながら設計を行う。論理設計では、どのようなデータモデルで作成するのかを設計。通常であれば、リレーショナルモデルで概念設計に沿って設計を行う。物理設計では、データベースの効率を考えながら設計を行い、インデックスをどう作成するかなどを設計する。

ER図とは、データの対象で具体的な物や人といった実体(Entity)と、その実体の間の関連(Relation)であらわされるものを、図にして表現したもの。ER図では、実体を長方形、関連をひし形、属性を楕円であらわす。属性のなかでキーとなるものには、下線をつけて表す。ER図の表現には、色々な方式があるが、Peter Chen記法で説明を行う。

このような、プログラム開発での考えを表すための図には、UML(Uniformed Modeling Language)というものもある。ER図は、データ構造を表現するための構造図と、処理を表現する振る舞い図がある。

viewテーブルとデータベース設計

実テーブルとビューテーブル

データベースでの表の構造は、テーブルの集合で表され、これは概念スキーマに相当する。

しかし、プログラマーの視点では、複数の表から構成されているといった所を気にせずプログラムを作れると便利。こういう使い勝手のよいテーブルは、外部スキーマに相当する。この外部スキーマを定義するものが、create view 命令である。

-- 優良業者しか見えないテーブル --
create view 優良業者 ( 業者番号, 優良度, 所在 )
  as select S.業者番号, S.優良度, S.所在
        from S where S.優良度 > 15 ;

-- 串刺し結果で参照できるテーブル --
create view 業者在庫 ( 業者名, 在庫量 )
  as select S.業者名, SG.在庫量
        from S, SG
        where S.業者番号 = SG.業者番号 ;

-- 外部スキーマで参照 --
select 業者在庫.業者名, 業者在庫.在庫量 from 業者在庫 ;

このように外部スキーマを設けることで、SQLをシンプルに記述できたり、外部プログラマが余計な内容を見れないようにしたりすることができる。ただし、データベースシステムによっては読み出しだけだったり、ビューテーブルを更新する時に更新異常が発生する場合がある。 (さらに…)