データベースと永続性

情報システム概論 I 

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/dsys-2005/2006-02-20
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■復習

• オペレーティング・システムのカーネルの役割
• ２種類の記憶のためのハードウェア
  • メインメモリ
  • ハードディスク
• ３種類の情報処理
  • 計算(computation)
  • 通信(communication)
  • 記憶(storage)

■目標

■記憶のためのハードウェア

メインメモリは、ＩＣ（Integrated Circuit、シリコンという元素による半導 体で作られた電気回路）でできている。その他に、ハードディスクやフロッピ・ ディスクも重要な記憶のための部品である。

メモリ(RAM(Random Access Memory))

実行中のプログラムを保持する。加工するデータを一時的に保持する。 非常に速い。容量は、ハードディスクよりは小さい。値段が高い。 (揮発的(電源を切ると消えてしまう)。)

ハード・ディスク (HD(Hard Disk), HDD(Hard Disk Drive))

プログラムやデータをデータを保持する。 容量は、メモリより大きい。値段が安い。 (永続的である(電源を切っても残っている)。)

メモリには、数字で番地（アドレス）が付いている。番地を指定して、データ を保存する。番地を指定すると、データが取り出せる。

◆アクセス時間で見た記憶階層

◆仮想記憶(仮想メモリ)

仮想記憶(仮想メモリ、virtual memory)とは、オペレーティングシステムの働きにより、実際に備えているメ モリ容量よりも大きなプログラムを動かすための仕組みである。

仮想記憶を使うと、メモリが１００Ｍバイトしかないコンピュータで、２００ Ｍバイトのメモリを使うプログラムを実行することができるようになる。

もともとは、１つのプログラムで実際のメモリ容量以上のものを使うための仕 組みである。最近では、複数のプログラムが使うメモリの総量で考えることも ある。

仮想記憶の基本的なアイディアは、すぐに使うところだけを速いメモリ（ＩＣ） に、当分使わない所を、遅いハードディスクに置き、ディスクとメモリの内容 を入れ替えながら仕事を進めることである。この時、速いメモリを主記憶 (main memory, primary storage)、遅いハードディスクを二次記憶(secondary storage)とう。

◆記憶の持続性からみた時の記憶ハードウェア分類

揮発的 (volatile)

電源を切ると消えてしまう。

永続的 (persistent)、不揮発的 (non volatile)

電源を切っても残っている。

永続的なメモリを仮想化して使いやすくしたものが、 ファイルやデータベース。

■ファイル

• バイト単位でデータを保存できる。
• 物理媒体に依存しない、統一的な扱いができる。
• 情報に名前がつけらる。
• 情報に対してアクセス制御が行える。

もしも、ファイルに名前がつけられなかったら・・・・。

◆ディレクトリの木構造

◆ファイルがどう見えるか

• シェルから。Unix ls コマンド、MacOSX Finder、Windows Explore
• プログラムから。ストリームとランダムアクセス。

◆ストリーム

• TCP層は、ストリーム転送サービスを提供する。
• 動画像のストリーミング転送では、データ全体の転送を 待たずに再生を開始できる。 データを保存させないで再生できる。

• Unix のシステムコール。read(), write() 。
• C 言語のライブラリ関数。fread(), fwrite(), fgets(), getchar(), fprintf().

FOPEN(3)                 BSD Library Functions Manual                 FOPEN(3)

NAME
     fopen, fdopen, freopen -- stream open functions

LIBRARY
     Standard C Library (libc, -lc)

SYNOPSIS
     #include <stdio.h>

     FILE *
     fopen(const char * restrict path, const char * restrict mode);

     FILE *
     fdopen(int fildes, const char *mode);

     FILE *
     freopen(const char *path, const char *mode, FILE *stream);

DESCRIPTION
     The fopen() function opens the file whose name is the string pointed to
     by path and associates a stream with it.

• 磁気テープ、紙テープのように、先頭から順にしかアクセスできない 記憶媒体があった。
• 人間（プログラムを書く人）にとって、わかりやすい。
• 通信との融合が可能。Unix のパイプとファイルを統一的に扱える。

◆ランダムアクセス

ハードディスク上に作られたファイルは、（テープ上に作られたファイルと違っ て）、先頭から順にアクセスだけでなく、メインメモリと同様に、任意の順番 に配列のようにアクセスすることができる。

API

• pread(), pwrite() システムコール
• mmap() システムコール
• (fseek() ライブラリ関数, lseek() システムコールを使う)

■プログラミング言語から見た永続性

◆変数

◆配列

◆連想配列(associative array)

例：Rubyの連想配列。

aa = {};
aa["apple"] = 100;
aa["orange"] = 120;
printf("%d\n", aa["apple"] );

キー (key)

表を検索する時に使うもの。配列の添字相当。

値 (value)

検索の結果得られるもの。

◆連想メモリ

• CPU のキャッシュ
• MMU のアドレス変換。(この講義では話をしていない。)

◆ファイルを連想配列として考える

◆人間を連想配列として考える

◆変数の寿命とスコープ

スコープ

空間的な概念。 プログラムの字面上、どの範囲から使えるか。 プログラムで、スコープにない変数をアクセスするとコンパイル時にエラーに なる。

寿命

時間的な概念。 「いつ」、その変数がアクセス可能になり、「いつ」、アクセスできなく なるのか。実行時のタイミング。 無効になった変数を無理やり使うと、何が起るかわからない。（Ｃ言語では、 ポインタを通じて、無効になった変数をアクセスできてしまうことがある。）

int x;

f()
{
    int y ;
    static int z ;
}

◆永続的な変数

プログラムの実行開始前にも有効で、終了後にも有効な変数を 考えてみる。これを永続的な変数という。

プログラミング言語で永続的な変数を支援しているものがある。

• オブジェクト指向データベースといっしょに使うオブジェクト指向言語
• Perl tie

一般の言語からは、ライブラリ関数で「永続的なハッシュ表（連想配列）」と して扱うことが多い。

◆永続的なハッシュ表を扱うライブラリ

• Berkeley DB (dbopen(3), btree(3), hash(3), recno(3) )
• DBM, NDBM, ODBM, GDBM, SDBM

◆永続的なハッシュ表を扱うライブラリ(Ruby DBM)

保存するプログラム [ruby-dbm-store.rb]

#!/usr/local3/bin/ruby

require 'dbm';
db = DBM::open("fruits",0666);
db["apple"] = 100;
db["orange"] = 120;
db.close();

#!/usr/local3/bin/ruby

require 'dbm';
db = DBM::open("fruits");
printf("%d\n", db["apple"] );
db.close();

% ls fruits.db 
ls: fruits.db: No such file or directory
% ./ruby-dbm-store.rb 
% ls fruits.db 
fruits.db
% file fruits.db 
fruits.db: Berkeley DB (Hash, version 7, native byte-order)
% ./ruby-dbm-print.rb  
100
% 

■データベース

ファイルと同様に、 永続的な記憶媒体を 仮想化して使いやすくしたもの。

ファイルと違い

• プログラムから独立している(データ独立性)
• 整合性(integrity)を保ったデータしか入っていない
• 複数のプログラムから同時アクセスにつよい機能がある(トランザクション)
• 障害回復の機能がある(トランザクション)

◆データモデル

• 関係データモデル
• 階層データモデル
• ネットワーク型データモデル

◆関係データベース

「関係」とは、２次元の表。 関係データモデルでは、表の集合としてデータベースを構築する。

サークル

サークル名	部屋番号	電話番号
テニス	101	1011
サッカー	203	4423

社員

社員番号	氏名	基本給与	住所
001	筑波太郎	400	つくば市×××
002	土浦次郎	450	土浦市△△△
003	水戸三郎	450	水戸市○○○

所属

サークル名	社員番号	役職
テニス	001	代表
テニス	002	会計
サッカー	001	一般部員
サッカー	003	幹事

◆関係データベースに対する操作

• 和 (Union)
• 差 (Diff). R-S=={t|t∈R ∧ ¬t∈S}
• 直積
• 射影
• 選択
• 結合
• 共通部分
• 商

◆問い合わせ言語

◆SQL

• 集合ではなくて、重複も許す（マルチ集合）
• データの順序に意味がある

CREATE TABLE サークル
(サークル名 CHAR(20) NOT NULL,
部屋番号 CHAR(3) NOT NULL,
電話番号 CHAR(4) NOT NULL)

SELECT 電話番号
FROM サークル
WHERE 部屋番号='101'

■並行プログラミング

• 複数のプロセスが同じファイルを開く
• 複数のプロセスが同じデータベースの表を操作する
• 複数のスレッドが同じ変数を操作する

◆相互排除

相互排除(mutual exclusion)

ある資源（ファイル、変数、表など）を アクセスできるプロセス（またはスレッド）の数を多くても１つにする。

際どい部分(critical section) (クリティカルセクション) プログラムの字面上、相互排除が必要な部分

◆ロック

lock();
  相互排除したい部分。
unlock();

◆デッドロック

◆トランザクションの目的

• データベースの整合性を保ちたい。
• 障害から回復させたい。
• 相互排除、デッドロックより高いレベルの抽象が欲しい。
• ロックよりも楽にプログラムを作りたい。

◆トランザクションの意味

歴史：１９６０年代、テープの時代。 失敗したら、巻き戻す(rollback)。

銀行口座間の預金の移動。

1. 口座１から出金
2. 口座２に入金

◆トランザクション・プリミティブ

• Begin_Transaction
• Commit (End Transaction)
• Abort
• Read
• Write

◆特性(ACID)

Atomic

外の世界からみると１つ。中間状態が見えない。不可分。

Consistency

不変量(invariant)を保つ。例：口座間の預金の移動。預金の総額は不変。

Isolated

並行するトランザクションは、孤立している。直列化可能(serializable)

Durable

Commit すると永続的。

◆直列化可能(serializable)

注意：Javaの serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。

◆トランザクションの例

Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-JFK");
Commit();

途中の reserve() が失敗したら、トランザクション全体を abort() する。