Database

CS专业课学习笔记

Database紹介

データベース(database)とは複数のデータを多様な用途に利用できるよう組織化したうえで一元的に管理されたデータの集合

DBMS

データベース管理システム(DataBase Management System)とはデータを組織化し管理するための仕組みを提供するソフトウェア

• データベースシステム = DBMS + データベース

Webアプリケーションのシステム構成

DBMSの必要性

• 検索の高速性・容易性
• 異なるアプリケーション間でのデータ共有
• アクセス権限の管理(機密保護)
• 同時アクセス制御
• 障害時データ保護

DBMSの特徴

• 検索や更新を高速に行うためにデータを組織化して格納する
• 複数のアプリケーションからデータにアクセスしても整合性が担保される
• データにウィルスが含まれるかチェックする機能は一般的にはない
• ユーザの権限によるデータのアクセス可否をチェックする
• 障害に備えてデータをバックアップしたり，バックアップからデータを復元したりする
• データスキーマは設計時に確定してデータベース管理システムに設定する．自動的に選択するわけではない

Data modelとDatabaseの種類

データモデルとはデータの種別や組織化方法，操作方法の体系を定めたもの

例:

• ネットワーク型DB(networked)
• 階層型DB(hierarchical)
• リレーショナルDB(relational)
• オブジェクト指向DB(object oriented)
• 半構造DB(semistructured)
• NoSQL DB(Not Only SQL)

ネットワーク型DB(networked)

• 米国の情報技術標準か団体のCODASYLにより標準化(1971)
• データ構造：1組のデータをレコードにより表現し，複数のレコード間をポインタにより紐付ける
• Webのようにネットワークをたどることで目的のデータにアクセスできる（ただし，集中管理）

階層型DB(hierarchical)

• セグメント（レコードと同義）をノードとし，ノード間の親子関係に基づいて，木構造を構成
  • eg.Windowsのレジストリ(データベース)
• 1対Nの親子関係により整理が可能なものは扱い易い(N対Mの関係は定義できない場合も多い)

リレーショナルDB(relational)

• IBMサンノゼ研究所のE. F. Coddにより提唱された
• リレーショナルモデル(relational model) = 関係モデル
• すべてのデータは数学の集合論に基づいた表(テーブル)で表現できるという考え方

まとめ

• NoSQLとは、関係データベース管理システム (RDBMS) 以外のデータベース管理システムを指す大まかな分類語である
• 半構造データベースとは，データベースに保存するデータのデータ構造を予め規定せず，保存しようとしているデータに応じてデータ構造を定義するデータベースである．扱うデータ形式の例としてXMLやJSONがある
• キーバリュー型データベースは識別子（キー）とデータの組み合わせによるシンプルなデータの問い合わせを可能にするもので，インターネット上の大量データを効率的な扱う仕組みとして注目されている

database基礎理論

集合

• 集合(set)：「もの」の集まり．数，文字，記号など
• 要素(element)：集合に属する「もの」のこと．元とも呼ぶ．
  • $a \in A$
• 空集合(empty set)：何も要素を含まない集合
  • $A = \varnothing$

集合演算

• 和集合 $\quad A \cup B = \lbrace x \ |\ x \in A \lor x \in B \rbrace$
• 共通集合(積集合) $\quad A \cap B = \lbrace x \ |\ x \in A \land x \in B \rbrace$
• 差集合 $\quad A - B = \lbrace x \ |\ x \in A \land x \notin B \rbrace$
• べき集合 $\quad 2^A = \lbrace X \ |\ X \subset A \rbrace$
  • 部分集合全体からなる集合
• 直積集合 $\quad A \times B \lbrace (a, b) \ |\ a \in A \land b \in B \rbrace$

Relational data model

実世界のモノ・概念を表（=リレーション）として表現

• 属性(attribute)：データの種類
• タプル(tuple)：データの組
• リレーション(relation)：タプルの集合，インスタンス

注意:

• 同じタプル（行）が重複して，リレーション（表）の中に現れることはない（リレーションはタプルの「集合」だから）
• タプル（行）の順序に意味がない
• 属性（列）の順序には意味がない

リレーションと第1正規形

• 単純な値でできている表
  • 表の中に表やリストがない（入れ子型リレーションではない）
  • 各行の構造が共通している
• リレーショナルデータモデルで扱うリレーション

例:

• 名前が直積であるので非第1正規形

• 第1正規形

• 趣味が集合値なので非第1正規形

• 第1正規形

数学的な定義

• リレーション名: $\quad R$
• 属性名: $\quad A_1, A_2, \cdots, A_n$(n:次数degree)
• リレーションスキーマ: $\quad R(A_1, A_2, \cdots, A_n)$
• ドメイン(定義域): $\quad D_1, D_2, \cdots, D_n$
• 直積集合: $\quad D_1 \times D_2 \times \cdots \times D_n$
• タプル: $\quad t \in D_1 \times \cdots \times D_n$
• リレーション(インスタンス): $\quad R \subset D_1 \times \cdots \times D_n$

リレーションスキーマ

• 次数(degree)=列数
• 濃度(cardinality)=行数

例題:

リレーションスキーマ$R(A, B)$の属性$A, B$のドメインをそれぞれ$D_A = \lbrace 1,2,3 \rbrace, D_B = \lbrace a, b \rbrace$とする

(1) 直積集合$D_A \times D_B$を求めなさい．

$$D_A \times D_B = \lbrace (1,a), (1, b), (2, a), (2, b), (3, a), (3, b) \rbrace$$

(2)リレーションスキーマ$R(A, B)$の次数はいくつか？リレーションスキーマ$R(A, B)$に従うリレーション$R$の濃度の最大数はいくつか

• 次数：2
• 濃度の最大数: 6

リレーションと整合性制約

データベースとして矛盾なく健全である状態を保つための条件や制約

ドメイン制約

属性値が，その属性のドメインに含まれる（データ型が一致）

• 年：正の整数，月：1～12，日：1～31
• 氏名：文字列

キー制約 | 一意性制約

属性または属性の集合において，同じ属性値がリレーションの中で重複して現れることがない

• eg. 学籍番号は重複しない(キー制約)

キー (key)

• スーパーキー(super key)：タプルを一意的に特定できる属性や属性の集合
  • 学籍号可以特定这个表中的一行，所以学籍号是super key。当然跟学籍号组合的集合也能特定（学籍号+名字），这也是super key
  • $\lbrace a, c \rbrace$はスーパーキーであるが、候補キーではない
• 候補キー(candidate key)：他のスーパーキーを含まない極小の属性集合
  • 由于学籍号本身就是super key了，所以学籍号+名字不是candidate key
  • $\lbrace a \rbrace$は候補キー
• 主キー(primary key) ：候補キーから任意に選択した一つ（NULLを含まない）
• 複合主キー：主キーを構成する属性集合（主キーが２個以上の属性から構成される場合）

実体整合性制約

参照整合性制約

まとめ

商品

• リレーション名: 商品
• 属性名（すべて）: {商品番号，商品名，値段}
• 次数 (arity, degree): 3
• 濃度 (cardinality): 5
• リレーションスキーマ: 商品(商品番号，商品名，値段)
• タプル（複数あるうちの一つ）: (R001, プリンタ1, 49800)

リレーショナルモデルについて:

• リレーションはタプルの集合である
• リレーションのことをインスタンスとよぶ場合がある
• 同じタプルが重複して一つのリレーションに表れることはない

リレーションスキーマについて:

商品（商品ID, 商品名，型番）

ここで、商品リレーションは、商品のデータを格納するためのもので、商品毎に商品ID、商品名、型番を属性値としてもつ。ここで、商品IDはデータ登録時に払い出される商品固有の番号である。同じ商品名でも、仕様が異なれば異なる商品として管理する必要がある。例えば、商品名が同じ"USBキー"でも、容量が異なれば、別商品として扱い、異なる型番が付与される。

• 候補キー: 商品ID, 型番

• キー制約: ある属性（または属性の集合）において，同じ属性値がリレーションの中で重複して表れることはない
• ドメイン制約: 属性値が，予め指定したデータ型（属性値の定義域）に含まれる値である必要がある
• 実体整合性制約: 属性（または属性の集合）が空値をとってはならない
• 参照整合性制約: 外部キーの属性値は，空値の場合を除いて参照先の主キーの値である必要がある

Relational algebra

リレーショナル代数とは単一または複数のリレーションに対して定義された演算の体系

• 集合演算
• 関係演算(リレーショナル演算)

集合演算

• 和集合 $\quad R \cup S = \lbrace t \ |\ t \in R \lor t \in S \rbrace$
• 共通集合(積集合) $\quad R \cap S = \lbrace t \ |\ t \in R \land t \in S \rbrace$

和両立(union compatible)

リレーションスキーマ$R(A_1, A_2, \cdots, A_n)$と$S(B_1, B_2, \cdots, B_m)$が次の二つの条件を満たすとき，リレーション$R$と$S$は和両立である

1. $R$と$S$の次元が等しい(つまり$n = m$)
2. 各$i(1 \leq i \leq n)$に対して，属性$A_i$と$B_i$のドメインが等しい(つまりdom($A_i$) = dom($B_i$))

必ずしも属性名は同じでなくてもよい

例

次のリレーションの$R,S$は，和両立か否か？（ドメインは常識的に考えて答えなさい．）

• R(学籍番号, 氏名)，S（学籍番号，名前）
  • 「氏名」と「名前」のドメインは「文字列」と考えれば和両立
• R(学籍番号，氏名), S（教員番号，氏名，役職）
  • RとSの次数（列の数）が一致しないので和両立ではない

直積演算

• 直積，デカルト積 (Cartesian product): $\quad R \times S = \lbrace (u, c) \ |\ u \in R \land v \in S \rbrace$

関係演算

選択演算(selection)

リレーション$R$の中から条件式$F$を満たすタプルを抽出する演算

$$\sigma_f(R) = \lbrace t \ |\ t \in R \land P_F(t) = true \rbrace$$

タプル$t$が条件式$F$を満たせばtrue,満たさなければfalseを返す関数

射影演算(projection)

リレーション$R$から，指定した属性集合$\beta$のみを持つリレーションを抽出する演算

$$\pi_{\beta}(R) = \lbrace t[\beta] \ |\ t \in R \rbrace$$

リレーションはタプルの「集合」重複するタプルは削除

結合演算(join)

二つのリレーション$R$と$S$を条件$F$に従って一つのリレーションに統合する．内部結合(inner join)ともよぶ

$$R \bowtie_F S = \lbrace (u, v) \ |\ u \in R \land v \in S \land P_F((u, v)) = true \rbrace$$

等結合(equi-join)

結合演算の条件$F$として，2つのリレーションの対応する属性が等しいことを用いるもの

自然結合演算(natural join)

等結合で得られるリレーションから重複する属性を射影により取り除いたもの

• 交換法則と結合法則が成り立つ

$$R \bowtie S = S \bowtie R \quad (R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)$$

外部結合演算(outer join)

一方のリレーション$R$のタプルのうち，もう一方のリレーション$S$に対応するタプルがないものは，対応する$S$の属性値をNULLにする

• 左外部結合(left outer join)
• 右外部結合(right outer join)
• 完全外部結合(complete outer join)

左外部結合

右外部結合

完全外部結合

商演算(division)

$$R \div S = \lbrace t \ |\ t \in \pi_{X-Y}(R) \land \forall u \in S: (t, u) \in R \rbrace$$

1. $S$の各タプルに対して同じ値を持つ$R$のタプルを選択
2. $R$の属性集合$X$から$S$の属性集合$Y$を除いた上で同じ値を持つタプルを集約
3. $S$のすべてのタプルを含んでいる場合に対応するタプルを選択

商演算は直積演算の逆演算

整数などの商演算と同じように$(R \times S) \div S = R$が成立

課題4.1(集合演算)

(1) 下記に示すリレーション$R_a$と$R_b$に対して，和集合，共通集合，差集合の各演算結果を求めよ

• 和集合$R_a \cup R_b$

• 共通集合$R_a \cap R_b$

• 差集合$R_a - R_b$

(2) 下記に示すリレーション$R_1, R_2$に対して直積集合$R_1 \times R_2$を求めなさい

• 直積集合$R_1 \times R_2$

課題4.2(関係演算)

(1) 下記に示すリレーション$R$と$S$に対して，結合条件を両リレーションにおける属性$B$が等しいとした場合の内部結合，自然結合，左外部結合，右外部結合，完全外部結合の各演算結果を求めよ

• 内部結合(結合演算)$R \bowtie_F S$

• 自然結合$R \bowtie S$

• 左外部結合

• 右外部結合

• 完全外部結合

(2) 以下のリレーションＲについて，$\pi$日付，商品名($\sigma$日付=2013/10/3($R$))を求めよ．

課題4.3(商演算)

次のリレーション、サークル活動，サークルに対してサークル活動$\div$サークルを求めなさい．

SQL

SQLの概要

リレーショナルデータベースを操作するための標準言語

IBMのE.F.Coddが提案したDBMSであるSystem Dで使われていたSEQUEL(Structured English Query Language)が元祖

• データ定義言語(DDL)
  • eg. CREATE TABLE
• データ操作言語(DML)
  • eg. SELECT … FROM … WHERE, INSERT, UPDATE, DELETE
• データ制御言語(DCL)
  • eg. 権限の制御 CREATE USER…, GRANT

databseへの接続

• 専用コマンドラインインターフェース(mysql)による接続

1
2

# passwordを送信
mysql -u {ユーザ名} -p -h {ホスト名} -p {ポート番号} {データベース名}

• アプリケーション(ホスト言語)からの接続

1
2
3
4
5
6

$dsn = 'mysql:dbname = データベース名; host = ホスト名;'
$pdo = new PDO($dsn, ユーザ名, パスワード, $driver_options);
foreach ($dbh -> query('select * from shouhin') as $row) {
  print($row['id']);
  print($row['name'].'<br>');
}

SQLite

• 軽量・コンパクトなリレーショナルデータベース
• 単独アプリケーション、ライブラリとして動作
• 組み込み用途や小規模システムのデータストアとして利用される
• マルチプラットフォーム

テーブル

SQLとリレーショナルモデル

• 共通点
  • テーブル、行、列 $\Leftrightarrow$ リレーション、ダブル、属性
• リレーショナルモデルとの違い
  • 行と列の順序に意味がある(ソートした場合)
  • 同じ内容を持つ重複した行を持つことができる

データ型

• NULL
  • NULL値
• INTEGER
  • 符号付き整数
• REAL
  • 浮動小数点数. 8バイトで格納
• TEXT
  • 文字列
  • char(文字数), varchar(文字数)型はSQLiteには存在しないのでTEXT型に変換される
• BLOB
  • 入力値をそのまま格納(Binary Large Object)

create文

create: テーブルの定義

1
2
3
4
5
6
7

create table テーブル名(
  列名d1 データ型d1 [not null]
  [, 列名d2 データ型d2[not null] ...] -- 実体整合性制約
  [, primary key (列名d1 [, 列名p2 ...])] -- キー制約
  [, foreign key (列名f2) references 参照テーブル名f2(参照列名f2) ...] -- 参照整合性制約
  [, check(条件)] -- 検査制約
)

例:

1
2
3
4
5
6

create table 商品)
  商品番号 char(3) not null,
  商品名 varchar(20),
  価格 int,
  primary key(商品番号)
);

drop,alter文

drop: テーブルの削除
alter: テーブルの変更

1
2
3

drop table テーブル名

drop table if exists テーブル名;

1
2

alter table テーブル名
  add 列名d1 データ型d1 [not null]

INSERT文

insert: 行(ダブル)の挿入

1

insert into デーブル名[(列名1, ..., 列名m)] values (値1, ..., 値m)

例:

1
2
3
4
5

insert into 商品 values('A01', 'オフィス用紙A4', 2000);
insert into 商品(商品番号, 商品名) values('A03', 'オフィス用紙A4');
insert into 顧客 values(101, 'A社', '北海道札幌中央区');
insert into 注文 values(1, 101, 'A01', 10);
insert into 注文 values(1, 101, 'A01', 10), (2, 201, 'A02', 20);

データ操作

SELECT文

1
2
3

select [distinct] 列名1, ..., 列名m 　-- *(アスタリスク)もケ可
from テーブル名  -- ,(カンマ)でテーブルを並べる
[where 条件]

例:

1
2
3
4
5

select * from 商品;
select 商品番号, 商品名 from 商品;

select * from 注文 where 顧客番号=1301;
select 注文番号, 商品番号 from 注文 where 顧客番号=1301;

検索条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

select * from 商品 where 商品番号 <> 'A01';
select 1>2;
select “壱”<“弐”;

select * from 商品 where 価格>=1000 and 価格 <=10000;

select * from 商品 where 価格 between 1000 and 10000;
select * from 商品 where 価格 not between 1000 and 10000;

select * from 商品 where 商品名 like 'オフィス用紙%';

select * from 商品 where 商品名 like '%A_';
select * from 商品 where 商品名 not like '%A_';

select * from 商品 where 商品番号 in ('A01', 'A02');

select * from 商品 where 価格 is null;
select * from 商品 where 価格 is not null;

UPDATE文

update: 行(タプル)の更新

1

UPDATE テーブル名 SET 列名1=値1 [, 列名2 = 値2, ...] [WHERE条件]

例:

1
2
3

update 商品 set 価格=1000 where 商品番号='A01';

update 商品 set 価格=価格*0.9 where 商品番号='A01';

DELETE文

delete: 行(タプル)の削除

1

delete from テーブル名 [where 条件]

例:

1
2
3

select * from 商品;

delete from 商品 where 商品番号='C01';

ビュー

create view文

ビュー(view): 仮想的なテーブル(保存されているわけではなく、問い合わせ度にテーブルを作成)

1

create view ビュー名 [(列名1, ..., 列名m)] as select 文;

例:

1
2
3
4
5
6
7
8

create view 商品一覧(商品番号, 商品名)
  as select 商品番号, 商品名 from 商品;

create view 低価格商品
  as select * from 商品 where 価格 <= 2000;

create view 注文一覧1301
  as select 注文番号, 商品番号 from 注文 where 顧客番号=1301;

データベースのユーザとアクセス権限

• ユーザ登録

1

create user u1301 identified by 'password';

• 権限の付与と取消

1
2
3
4
5
6
7

grant 権限p [列名p1 [, 列名p2 ...]]
  [, 権限q [(列名q1 [, 列名q2 ...])]...] on テーブル名
  to ユーザ名u1 [, ユーザ名u2 ...]

revoke 権限p [列名p1 [, 列名p2 ...]]
  [, 権限q [(列名q1 [, 列名q2 ...])]...] on テーブル名
  from ユーザ名u1 [, ユーザ名u2 ...]

SQLによる高度な問合せ

distinct句とorder by句

distinct: 行の重複削除

1

select distinct 列名1, ..., 列名n from テール名;

order by: 行の並べ替え

1

select * from テーブル名 order by 列名 [desc];

• desc: 降順(descending)
• asc: 昇順(ascending)

例:

1
2
3
4
5
6
7
8

-- 科目名のデータから重複を取り除いて，科目名の一覧を表示
select distinct 科目名 from 履修;

-- 重複を取り除いた科目名を昇順に並べ替える
select distinct 科目名 from 履修 order by 科目名;

-- 降順に並べ替えるには？
select distinct 科目名 from 履修 order by 科目名 desc;

複数テーブルからのデータ抽出

テーブルの和(union), 積(intersect), 差(except)

• テーブルの和(union)

1
2
3
4

-- 学生IDが'701'か'702'の学生が履修している科目名を抽出
select 科目名 from 履修 where 学生ID='701'
union
select 科目名 from 履修 where 学生ID='702';

• テーブルの積(intersect)

1

select * from R intersect select * from S

• テーブルの差(except)

1

select * from R except select * from S

テーブルの結合

• 内部結合・等結合

1
2
3
4
5
6
7
8
9
10
11
12
13

-- 直積集合を求めてG.学生ID = S.学生IDの条件で行を選択
-- G, Sは表の別名
select * from 学生 as G, 修得単位 as S where G.学生ID = S.学生ID;

-- 内部結合を求める
-- inner joinでもOK
select * from 学生 as G join 修得単位 as S on G.学生ID = S.学生ID;

-- 内部結合を求める
select * from 学生 join 修得単位 using(学生ID);

select * from 学生 as G, 修得単位 as S, 履修 as R
  where G.学生ID = R.学生ID and G.学生ID = S.学生ID;

• 外部結合

1
2
3
4
5

-- 左外部結合を求める
select * from 学生 as G left outer join 履修 as R on G.学生ID=R.学生ID;

-- 右外部結合を求める(SQLiteには実装されていないためエラーになる)
select * from 学生 as G right outer join 履修 as R on G.学生ID=R.学生ID;

SQLとリレーショナル代数

副問合せ(sub query)

select文中にselect文を入れ子に記述することができる. 入れ子の内側の問合せを副問合せと呼ぶ.

1

select [列の指定に使用] from [from句に使用] where [where句で使用]

• where句で使用
  • 比較演算子
  • in と not in 演算子
  • exist と not exist 演算子
  • any(some) 演算子
  • all 演算子
• from句に使用
  • 仮想的なテーブルとして扱うことができる
• 列の指定に使用

where句で使用

• 比較演算子を使って主問合せと連携

1
2

select 学生ID, 修得単位数 from 修得単位
 where 修得単位数 >= (select avg(修得単位数) from 修得単位);

• in と not in 演算子

1
2

select 学生ID, 氏名 from 学生
  where 学生ID in (select 学生ID from 履修 where 科目名 = 'Webデザイン');

• exist と not exist 演算子

1
2
3
4
5

select 学生ID, 氏名 from 学生 as G
  where exists (select * from 履修 as R where G.学生ID = R.学生ID);

select 学生ID, 氏名 from 学生 as G
  where not exists (select * from 履修 as R where G.学生ID=R.学生ID);

• any(some) 演算子(sqlite未実装)

1

select 学生ID, 氏名 from 学生 where 学生ID = any(select 学生ID from 履修);

• all 演算子(sqlite未実装)

1
2

select 学生ID, 氏名 from 学生
  where 学生ID != all ( select 学生ID from 履修 );

from句に使用

• select文の結果を仮想的なテーブルとして扱うことができる

1
2
3
4
5
6
7
8

-- 修得単位数が44以上の学生を検索
select * from 修得単位 where 修得単位数>=44;

-- from句に副問い合わせを含むselect文
select distinct G.学生ID, 氏名, 学年, 修得単位数
from 学生 as G,
 (select * from 修得単位 where 修得単位数 >= 44) as VTB
where G.学生ID = VTB.学生ID;

列の指定に使用

• select文の(1個の)列を指定

1
2
3

select 学生ID, 学年, 修得単位数, (select 氏名 from 学生 as G where G.学生ID=S.学生ID)
  from 修得単位 as S
  where 修得単位数 >= 44;

集約関数(aggregate functions)

• count関数

1
2
3
4
5
6
7
8

-- 履修テーブルの行数をカウント
select count(*) from 履修;

-- 集約結果に名前を付けている
select count(*) as 履修総数 from 履修;

-- ユニークな（互いに異なる）学生IDの数
select count(distinct 学生ID) as 履修学生数 from 履修;

• max, min関数

1
2

-- 取得単位数の最大値
select 学生ID, max(修得単位数) from 修得単位;

• avg, stddev, variance関数(stddev, varianceはSQLite未実装)

1
2

-- 平均
select 学生ID, avg(修得単位数) from 修得単位;

group by句とhaving句

• group by句：テーブルの特定の列で行をグループ化して，個々のグループに対して集約関数を適用

1
2

-- 科目名ごとにグループ化して集約関数を適用
select 科目名, count(*) as 履修学生数 from 履修 group by 科目名;

• having句：集約化された値に対する選択条件を指定

1
2

-- having句で集約化された値に対する選択条件を指定
select 科目名, count(*) as 履修学生数 from 履修 group by 科目名 having count(科目名) >=2;

例:

1
2
3
4

-- 80単位以上を修得した学生と修得単位数の合計を検索
select 学生ID, sum(修得単位数) as 総修得単位数 from 修得単位 group by 学生ID having sum(修得単位数)>=80;

select 学生ID, count(学生ID) + 1 as 学年 from 修得単位 group by 学生ID;

集約関数を含むビュー

ビューの定義に集約関数を含めることができる

1
2
3

create view 合計修得単位
  as select 学生ID, count(学生ID)+1 as 学年, sum(修得単位数) as 合計単位数
  from 修得単位 group by 学生ID;

トランザクション

• トランザクション(transaction)：データベースの状態を整合性のある状態から，別の整合性のある状態に変化させるデータ操作の並び（データ操作の順番の入れ替えはない）

• まとめて行わなくてはいけないワンセットの処理のこと

例: 口座aから口座bに10万円を送金する

• $R[b]$: 口座bの貯金額を読み出す操作
• $W[b:=b+10]$: 口座bの預金額に10万円を足す操作

トランザクションの状態遷移

• コミット(commit)：正常終了した場合に，すべての更新を確定したものとしてデータベースに反映する処理
• アボート(abort)：異常終了した場合に，すべてのデータ操作を取り消して元の状態に戻す処理（ロールバック）

• トランザクションの開始と正常終了(commit)

1
2
3
4

begin transaction;
  select * from 口座;
  update 口座 set 金額 = 金額 - 10000; select * from 口座;
commit transaction;

• トランザクションの中止(abort, rollback)

1
2
3
4
5

begin transaction;
  select * from 口座;
  update 口座 set 金額 = 金額 - 10000; select * from 口座;
  -- ATMで紙幣が詰まって出てこない！
rollback transaction;

正規化

更新時異常

属性間の依存関係を考慮しないでリレーションを適当に設計すると，更新時にどのような問題が発生するか？

更新操作:

• 挿入 (insert)
• 削除 (delete)
• 修正 or 更新 (update)

次の制約を持つ履修登録リレーションを考える

• 各科目は1人あるいは複数の教員が担当
• 1人の学生が同じ科目を複数履修することはない
• 教員は複数の科目を担当できる
• 学生は一つの学科に属し，各学科に学科長は2人

履修情報

• 複合主キー: 学生, 科目

挿入時異常(insertion anomaly)

• 新たな学生S4が学科設計に加わった場合

履修情報

キー制約違反: 履修する科目が決まるまで新規学生を追加できない

削除時異常(deletion anomaly)

• 学生S3が科目設計演習を取り消した場合

履修情報

タプルを削除すると学生 S3 がいないことになる

修正時異常(update anomaly)

• 学生S1の学科が情報から設計に変更になった場合

履修情報

学生S1所属している学科は矛盾!

更新時異常を回避

• リレーションを分解することで冗長性を取り除く

情報無損失分解

情報無損失分解：自然結合で復元可能な分解

結合の罠(connection trap)

どんな分解でも情報無損失分解になるわけではない

関数従属性(FD)

関数従属性の例:

関数従属性 {学生}$\rightarrow${学科}, {学生}$\rightarrow${学科長} が成り立つ

• 学生は一つの学科に所属するという制約があるから

{学生}$\rightarrow${教員}の関数従属性は成立しない

• 学生が決まっても，履修する科目によって教員が変わるから

関数従属性 {学生，科目}$\rightarrow${教員} が成り立つ

• {学生，科目}は主キー．同じ値を持つタプルは唯一．
• {学生，科目}$\rightarrow${学科}, {学生，科目}$\rightarrow${学科長}, {学生，科目}$\rightarrow${教員，学科}等も従属

アームストロングの公理系 (Armstrong’s axioms)

関数従属性では以下の公理系が成立

• 反射律：BがAの部分集合であるならば, $A \rightarrow B$
• 添加律：$A \rightarrow B$ ならば $A \cup C \rightarrow B \cup C$
• 推移律：$A \rightarrow B$かつ$B \rightarrow C$ならば，$A \rightarrow C$

自明な関数従属性(trivial functional dependency)

被決定項が決定項の部分集合である場合（必ず関数従属する）

推移的関数従属性 (transitive functional dependency)

$A \rightarrow B$かつ$B \rightarrow C$ならば，$A \rightarrow C$が成立すると，CはAに推移的に関数従属するという．

完全関数従属性(full functional dependency)

関数従属性$A \rightarrow B$で，Aの任意の真部分集合$A'$について，関数従属性$A' \rightarrow B$が成立しないとき，完全関数従属性$A \rightarrow B$が成り立つという

$A$の真部分集合$A'$について$A' \rightarrow B$ が成立するので，$A \rightarrow B$は完全関数従属ではない

例

• $A \rightarrow B1$ は関数従属性が成立するが，完全関数従属ではない
  • $A1 \rightarrow B1$だから
• $A \rightarrow B2$ は関数従属性が成立し，かつ，完全関数従属性が成立

注意: B2 = {教員}

第2正規形(second normal form, 2NF)

第二范式（2NF）：候选键完全决定每一个非主属性

第3正規形(third normal form, 3NF)

第三范式（3NF）：没有传递函数依赖

ボイス・コッド正規形(Boyce-Codd normal form, BCNF)

BCNF：没有不依赖于候选键的函数依赖存在

• （城市，街道，邮政编码）
  • （城市，街道）-> 邮政编码
  • 邮政编码 -> 城市

課題7.1

学生の履修登録に関するリレーションスキーマ 履修登録（学生，科目，教科書，出版社）があり，以下の制約があるものとする．このときに以下の問いに答えよ．

1. 学生は任意の科目を履修できる
2. 科目毎に1冊の教科書が指定されている．ただし，科目が異なっても教科書が異なるとは限らない
3. 教科書は出版社をもつ．ただし，教科書が異なっても出版社が異なるとは限らない

関数従属性

(1) リレーションスキーマ履修登録（学生，科目，教科書，出版社）の持つ関数従属性を示せ．ただし，自明な関数従属性は除くものとする．また，1つの決定項に対して被決定項が複数存在する場合には，1つの関数従属性としてよい．

(2) 上記で列挙した関数従属性のうち，完全関数従属性が成立しないものを挙げなさい

正規化

(1) このリレーションを第2正規形に正規化したリレーションを示せ

(2) (1)で作成したリレーションが第3正規形になっているか確認し，なっていない場合には第3正規形に正規化せよ

以下の受注票リレーションを第３正規形まで正規化しなさい．

• 受注番号は受注毎に新たに発行される番号であり，
• 項番は１回の受注で商品コード別に連番で発行される番号である．
• なお，単価は商品コードによって一意に定まる

多値従属性(MVD)

リレーションスキーマ R(A, B, C)においてA, B, CをRの属性集合の部分集合とする．

1. Bの値がAの値のみに依存し
2. Cの値から独立しているとき

多値従属性 $A \twoheadrightarrow B$が成り立つという．

• 「候補キーのみ」からなるリレーションRが対象
• 関数従属性の一般化

多値従属性の性質

• 多値従属性$A \twoheadrightarrow B$が成り立つための必要十分条件は, $A \twoheadrightarrow C$が成り立つことである.
  • $A \twoheadrightarrow B \ |\ C$ と表記する.
• $R$ が射影 $R1(A, B), R2(A, C)$ に情報無損失分解されるための必要十分条件は, 多値従属性$A \twoheadrightarrow B$が存在することである.
• 関数従属性 $A \Rightarrow B$ が成り立つならば, 多値従属性 $A \twoheadrightarrow B$が成り立つ.

$A \twoheadrightarrow B \ |\ \Phi$ を自明な多値従属性という

第4正規形

2つのリレーションに情報無損失分解が可能:

課題7.2

多値従属性について以下の問いに答えよ

R

• 以下の制約を持つリレーションRに対応する3部グラフを作成しなさい
  • 製品は複数の部品から構成されている
  • 部品は複数の工場で製造されている
  • 製品と部品の工場は独立している
• リレーションRが第4正規形でないことを示しなさい
• リレーションRを第4正規形に正規化せよ

結合従属性(JD)

2つのリレーションに情報無損失分解できない例

2-分解による情報無損失分解が不可能な事例

多値従属性ではない理由：教員P1が決まっても、助手が違えば対応する学生が変わる！

リレーションスキーマ $R$ において, $A_1, \cdots, A_n$ を $R$ の属性集合の部分集合とする. $R$ のすべてのリレーションが $A_1, \cdots, A_n$ での射影の自然結合と等しい場合に限り, $R$ に結合従属性 *$(A_1, \cdots, A_n)$ が存在するという．

$n$ 個の射影に情報無損失分解できるリレーションスキーマをn-分解可能(n-decomposable)という．

結合従属性の性質

結合従属性は多値従属性の一般化である

• $R(A, B, C)$ が情報無損失分解可能 $\Leftrightarrow A \twoheadrightarrow B \ |\ C$
• ２つのリレーション($\lbrace A, B \rbrace, \lbrace A, C \rbrace$への射影)に2-分解可能

自明な結合従属性(trivial join dependency)：$\lbrace A_1, \cdots, A_n \rbrace$ の1つが $R$ の全属性集合と等しい場合

第5正規形

課題7.3

下記のリレーション $R$ は，学生が昼食に利用するメニューと食堂の関係を表す．学生とメニュー，メニューと食堂，食堂と学生の関係は多対多であるとする．ここで，多対多とは，例えば，学生とメニューの関係では，各学生は１つ以上のメニューを利用し，各メニューは１人以上の学生から利用されるものとする．また，学生が利用するメニューは，そのメニューを扱うすべての食堂で提供される．このリレーションについて以下の問いに答えなさい．

R

• このリレーションが第4正規形であるか否かを，理由を挙げて示せ
• このリレーションを第5正規形に正規化せよ
• 正規化したリレーションを自然結合し，情報無損失分解であることを示せ

正規化とリレーションスキーマの設計

関数従属性，多値従属性，結合従属性の順に一般化された従属性

正規化が常に良いわけではない. 従って. 更新時異常の回避，検索性能，制約の保存のトレードオフを考えて，正規化の有無を決定する必要がある．

まとめ

リレーションの更新時異常を解消するために正規化を行う

• 関数従属性の概念を理解
• 第2正規形：部分関数従属性を解消
• 第3正規形：推移的な関数従属性を解消
• ボイス・コッド正規形：自明でない関数従属性を解消
• 上位の正規形にすれば，必ずしも良いわけではない．検索性能を高めるために，正規形を崩すこともある．

总结

データモデリング(data modeling)

データモデリングとは

実社会の中でデータベース化したい対象からデータ項目を抽出・整理し，適切なデータ構造を決定すること

リレーショナルデータベースの場合であれば，以下を決めること

• データ項目：テーブル名，属性名
• データ構造：ドメイン，整合性制約，主キー・外部キー

情報システムの要求分析・定義工程，設計工程の一部

• 業務フローや顧客の要求を把握する必要がある

データベース設計と実体関連図

3層スキーマ

三層スキーマ：ANSI/X3(米国規格委員会情報処理部会)のSPARC(標準計画要件委員会）によって提案されたデータモデリングの基本的な概念

3層スキーマとデータベース設計手順の対応

実体関連図(ER図)

1976年にChenが提唱したエンティティとリレーションシップという二つの概念でデータ構造の分析を行い図に表現する手法．

• エンティティ（実体）：システムで関心対象となり得る「人・もの」や「概念」
  • eg. 社員，顧客，商品，部署
• リレーションシップ（関係）：実体間の関係
  • eg. 1対1関係，1対多関係，多対多関係

実体間のリレーションシップ：多重度(cardinality)

• 1対1関係，1対多関係，多対多関係

IE記法における多重度の表現

課題8.1

データモデリングの方法

データモデリングの手順

1. 実体の抽出
2. 実体間の関係の設定
3. 多対多の関係の分解
4. キーと属性の設定
5. 正規化
6. 実世界の要求の反映
7. リレーショナルデータモデルへの変換

手順1：実体を抽出

業務フロー，帳票，画面，ユースケースシナリオから名詞部分を抽出

ガイドライン：

• 管理対象である
  • eg. 「大学」は履修登録システムの管理対象外なので実体として扱わない
• 一つの実体には複数のインスタンスが発生しうる
  • 固有名詞ではなく，その総称を実体にする
  • 実体の持つ特徴や状態はエンティティの属性とする（例，生年月日）
• 一意識別子（キー）を持ちうる
  • 一意識別子の例：社員番号，商品コード，マイナンバー（個人番号），端末ID，など
  • eg. 「年齢」はキーを持たないので実体として扱わない．「年齢層」なら実体として扱うこともある

例：手順1：実体の抽出（履修管理システム）

• 要求（1）：履修管理システムは大学のすべての学生と開講科目を管理し，どの学生がどの科目をどのセメスタ（学期）で履修したかを検索表示できる
• 要求（2）：履修管理システムは学生の履修履歴を管理し，学生ごと，科目ごと，学科ごとに検索表示できる

手順2：実体間の関係の設定

実体間にどのような関係があるか検討する

• 1対1関係，1対多関係，多対多関係

手順3：多対多の関係の分解

実体間の関連に「多対多」がある場合には，複数の「1対多」の関連に分解する（リレーショナルデータモデルの場合）

手順4：キーと属性の設定

• 主キーを設定
  • 実体のインスタンス（リレーションにおけるタプル）を一意に特定できる属性
• 属性を設定
  • 実体を管理するために必要なデータ項目
• 外部キーを設定
  • 1対多の「多」の方の実体に１つ設定する

例：手順4：キーと属性の設定（履修管理システム）

実体として「学生」と「学科」しか抽出しなかった場合

手順5：正規化

リレーションを正規化する（第３正規形までで十分な場合が多い）

• 学生リレーションタプルを特定するために、学籍番号と履修科目名が必要（学生が複数科目履修可能）
• 担当教員名、教員所属学科、開講セメスタ、履修登録年月日は学籍番号と独立しているため、学生氏名、学科ID、性別を別のリレーションに分解する
• 部分関数従属性が残っているため（科目に関する属性）、別のテーブルに分解する

• 推移的関数従属性が残っているため、それを分解して第3正規形にする
• 関数従属性が残っていないため、第3正規形になる

手順6：実世界の要求の反映

構築するシステムへの要求を満たしているか検証

手順7：リレーショナルデータモデルへの変換

各属性のデータ型を決め整合性制約を設定

課題8.2

課題8.3

• 設問1：ER図を作成しなさい

• 設問2：新たな要求を考えて，要求を追加した場合に，どのようにER図を変更する必要があるか検討しなさい．

他のキャンパスの図書も扱えるように要求を追加する

データベース管理システムと外部記憶装置

データベース管理システムの基本構成と機能

SQL実行機能

• SQL文の解析(パーサ)：SQL文の構文解析
• 機密保持：ユーザの権限を確認しアクセス可能か判断
• SQL文の最適化(オプティマイザ)：効率化のためにSQL文の実行順序等を変更インデックスの利用可否の判断
• クエリ実行エンジン：クエリの実行
• 整合性維持：整合性制約を遵守しているか監視違反していたらロールバック（実行を取消）
• トランザクション制御：同時実行制御

テーブル／ビュー／インデックスの管理機能

• テーブルの管理
  • リレーション名，属性名，ドメイン，制約，インデックス名などを管理
  • テーブルのデータを外部記憶装置のどこに書き込むかを管理
• ビューの管理
  • ビューの属性と実テーブルの対応関係を管理
• インデックスの管理
  • データベースの検索性能を向上させるためのデータを管理（B-tree, B+tree, ハッシュなど）

データベースが管理するファイル群

• データファイル
  • テーブル内のデータを保持するファイル
• インデックスファイル
  • インデックスデータを保存しているファイル
• システムファイル（システムカタログ）
  • RDBMSの運用や内部処理のためのシステム情報を保持するファイル
  • テーブル名，列名，データ型，整合性制約なども格納される
• 一時ファイル
  • クエリを実行する際に一時的に生成されるファイル（group by句，distinctを実行した時のソートデータなど）
• ログファイル
  • データベースの変更情報が記録されたファイル

データベースの外部記憶装置への書き込み

外部記憶装置への書き込み

• ページ：固定サイズ（例えば，4, 8, 16, 32KB）の記憶領域
• エクステント：連続する複数ページのまとまり

ヒープファイル：ページへのレコードの格納

• リレーションのタプル（テーブルの１行）を内部レベルではレコード(record)として表現してHDDに格納
• ヘッダ，スロット（ディレクトリ），レコードから構成される．レコードサイズはページサイズより小さく設定する

レコードの構造

• 更新で可変長属性が大きくなった場合は，別ページに移動する必要がある

インデックス方式

インデックス(index)：書籍の巻末にある索引（インデックス）と同じように本体のデータに効率的にアクセスするための仕組み

インデックス方式:

• B-tree, B+treeインデックス
  • バランス木構造
  • B+treeが，RDBMSでは標準的に使われている (SQLiteにも実装されている）
• ハッシュインデックス
  • ハッシュ関数を利用

B-treeを用いたレコードの検索

• 各ノードにはキー値とコード所在を固定数まで格納可能
  • レコード：ページ番号とスロット番号
• キー値は整列している

B-treeへのレコード挿入

B-treeインデックス

B+ treeインデックス

B+treeインデックス：Leafノードにキーに対応したデータ所在を持たせる方式（B-treeインデックスでは，Root, Branchノードにも「キー値＋レコード所在」を保持する）

B-tree/B+treeの特徴

• 高速な一致検索が可能
  • eg. 学籍番号が469999の学生を検索
• 高速な範囲検索が可能
  • eg. 年齢が20未満の学生を検索
  • eg. 生年月日が2000/4/1～2001/3/31までの学生 (Between句)

ハッシュインデックス

ハッシュ関数：任意の長さのデータを固定長のデータに変換する関数

ハッシュ関数を用いて，パケット番号からパケットキーをレコード所在に変換

パケットに空きがなくなったらオーバーフロー処理が必要 $\Rightarrow$ 検索効率の悪化

• 動的ハッシング：キーのパケットへの割り当てを動的に決定
• 静的ハッシング：ハッシュ関数は固定

「B-tree,B+tree」と「ハッシュ」インデックスの比較:

2次インデックス

• 主キー以外の属性に対してインデックスを付与すること
• 検索キーに対して複数の行が抽出されるので，一つのキーに対して複数のレコード所在を格納する必要がある

SQLでのインデックスの作成

1

create [unique] index インデックス名 [using method] on テーブル名(属性1, …);

• MySQL,PostgreSQLではインデクスの種類を選べる(btree, index, …)

課題9.1

キー値 [25, 1, 15, 7, 24, 30, 2, 13, 5, …]をこの順にB-treeに挿入するとどのようになるか．ノードには４つまでのキー値を格納するものとする．

外部記憶装置の種類

記録メディアによる分類

• 磁気ディスク：HDD (Hard Disc Drive)
• 光学式ディスク：CD (Compact Disc), DVD (Digital Versatile Disc), BD(Blue-ray Disc)
• 半導体メモリ： SSD (Solid State Drive)

接続インタフェースによる分類

• DAS: Direct Attached Storage
• NAS: Network Attached Storage
• SAN: Storage Area Network

ハードディスク

• トラック：ディスク上のデータを書き込む円周部分
• セクタ：読み書きの単位 (512～4096バイト)
• ブロック：固定数の連続したセクタから構成される単位（初期化の際にサイズが決まり，通常は0.5, 1, 2, 4Kバイト)
• シリンダ：トラックを縦に並べたもの

HDDの平均アクセス時間

平均アクセス時間の計算

回転速度：5000rpm(=rotations per minute; 回転/分)，平均シーク時間=20ミリ秒, 1トラックあたりの記憶容量=16000バイト，1ブロック4000バイトのデータを転送するために必要な平均アクセス時間は？

平均回転待ち時間は、ディスクが半回転する時間である

1トラックあたりの記憶容量は16000バイト，ブロックの容量は4000バイトだから，１トラックは4(=16000 / 4000)ブロックから構成される

• ディスクが1回転する時間は12ミリ秒(60 / 5000)
• 平均回転待ち時間は6ミリ秒(60 / 5000 / 2)
• 1トラックあたりの（データ転送時間）は12ミリ秒
• 1ブロックあたりの（データ転送時間）は3ミリ秒

平均アクセス時間 = 平均シーク時間 + 平均回転待ち時間 + データ転送時間 = 20 + 6 + 3 = 29ms

課題9.2

回転速度：5000回転/分，平均シーク時間=20ミリ秒, １トラックあたりの記憶容量=16000バイト， 1ブロック4000バイトとする

• 連続する3ブロックのデータを転送するために必要な平均アクセス時間は？
  • 20+6+3*3=35ms
• 断片化した3ブロックのデータを転送するために必要な平均アクセス時間は？
  • (20+6+3)*3=87ms

断片化していると倍時間がかかる

transaction

トランザクション(transaction)：データベースの状態を整合性のある状態から，別の整合性のある状態に変化させるデータ操作の並び（データ操作の順番の入れ替えはない）

ACID特性

• 原子性(atomicity)：トランザクションがDBを更新後の状態に遷移させるか，あるいは全く処理を行わないかのいずれか
• 一貫性(consistency)：整合性のあるDBに対してトランザクションが実行された場合，完了後にも整合性が維持される
• 分離性(isolation)：あるトランザクションは他のトランザクションに影響を与えないように，分離された状態で実行される
• 持続性(durability)：一旦コミットされたトランザクションの更新は，その後の障害などで失われることがない

スケジュールと直列化可能性

同時実行制御(concurrency control)

同時実行(concurrent execution)：複数のユーザが同時にデータベースにアクセスすること

• 利点
  • CPUとI/Oは並列に実行できるので，ディスクとCPUが暇な(idle)時間の量を減らせる
  • 短いトランザクションと長いトランザクションを交互に実行すると，通常は短いトランザクションが早く終わり，長いトランザクションの後回しになることが少ない
• 欠点
  • 実行するタイミングによっては不整合が発生し，分離性が維持できなくなる

• 脏读(Dirty reads): 有俩事务T1,T2。如果T1读了一条数据，这条数据是T2更新的但是还没提交，突然T2觉得不合适进行事务回滚了，也就是不提交了。此时T1读的数据就是无效的数据
• 不可重复读(Non-repeatable reads): 有俩事务T1,T2。如果T1读了一条数据，之后T2更新了这条数据，T1再次读取就发现值变了
• 幻读(Phantom reads): 有俩事务T1,T2。如果T1读了一条数据，之后T2插入了一些新的数据，T1再次读取就会多出现一些数据

スケジュール

スケジュール：トランザクションのデータベースに対するデータ操作の順序

• データ操作(Read, Write, Commit, Abort)の順序
• トランザクション内で操作順序は入れ替えない

直列スケジュールと非直列スケジュール

直列スケジュール(serial schedule)：複数のトランザクションを直列に実行

如下图，按照顺序（T1 -> T2）执行的schedule是直列スケジュール

競合操作(conflict)

スケジュールの中の二つの操作について，次の場合に競合(conflict)があるという

• 二つの操作は別のトランザクションに属する
• 二つの操作は同じデータにアクセスする
• 二つの操作のうち少なくとも一方はデータを更新する

課題10.1

直列化可能スケジュール

直列化可能スケジュール(serializable schedule)：非直列スケジュールとしてトランザクションを同時実行しながら，直列スケジュールと実行結果が等価なもの

• ビュー等価(view equivalence)
• 競合等価(conflict equivalence)

ビュー等価

スケジュール $S$ （直列）と $S'$ （非直列）は次の条件が成り立つ場合，ビュー等価である

• $S$ において $Ri[a]$ が先行する $Wj[a]$ の結果（あるいは $a$ の初期値）を読み出すならば，$S'$ においても同様
• 各データ $a$ について，$S$ において最後の更新が $Wk[a]$ ならば $S'$ においても同様

どんな初期状態から始めても直列スケジュールと最終状態が等しくなるが, 与えられたスケジュールがビュー直列化可能か否かの判定はNP完全

競合等価(conflict equivalence)

競合等価：スケジュール $S$ （直列）と $S'$ （非直列）は競合するデータ操作の順番が同じ, 競合等価であればビュー等価

競合直列化可能スケジュール：直列スケジュールと競合等価なスケジュール

• 分别看冲突的次序是否一致即可

冲突可串行化调度：一个调度S在保证冲突操作的次序不变的情况下，通过交换两个事物不冲突操作的次序得到另一个调度S’，如果S’是串行的，称调度S为冲突可串行化的调度

競合直列化可能性の判定

先行グラフ(precedence graph):

1. すべてのトランザクションをグラフの頂点として記載する
2. トランザクションTjが，Tiによって更新Wされたデータを読み出すRならばTiからTjに有向辺を引く
3. トランザクションTjが，Tiによって読み出されたRデータに対して更新Wを行うならば， TiからTjに有向辺を引く
4. トランザクションTjが，Tiによって更新Wされたデータに対して更新Wを行うならば， TiからTjに有向辺を引く
5. スケジュールのすべての操作に対して，2から4を行った結果，グラフに閉路(cycle)がなければ競合直列化可能であり，閉路があれば競合直列化可能ではない

課題10.2

スケジュール $S$ と $S'$ は競合するデータ操作の順番が同じかどうか確認する

課題10.3

ロックによる同時実行制御

多くの場合はトランザクションを予測できないので，一般的には事前に実行スケジュールを作成できない．

• 動的に同時実行制御を行う必要がある
• ロック(lock)，アンロック(unlock)による同時実行制御

共有ロックと排他ロック

共有ロック(shared lock; SL)：データの読み出しを行うためのロック
排他ロック(exclusive lock; XL)：データの更新を行うためのロック

既にロックされたデータに対して，他のトランザクションがロックを要求した場合，両立性行列に従ってロックが許可される

• 両方が共有ロックかけているだけロックが許可される

ロックの変換

アップグレード：あるトランザクションが既にかけている共有ロック(SL)を排他ロック(XL)に変換．他のトランザクションが共有ロックをかけていない場合に限る

ダウングレード：あるトランザクションが既にかけている排他ロック(XL)を共有ロック(SL)に変換

ロックの粒度

粒度(granularity)：ロック対象となるデータの単位

ロックの粒度が大きいとロックの制御が容易（制御に要する間接的な処理量は小さい）になるが、ロックによる待ち時間が長くなる

２相ロッキングプロトコル

ロックをかけるだけでは不整合は防げない

それぞれの読み出し，更新操作の前後でロック，アンロックを行っても不整合が生じる

2相ロッキングプロトコル(two-phase locking protocol; 2PL)：

1. トランザクションはデータの操作を行う前に，対象のデータをロックしなければならない
2. ロックしたデータをアンロックした後で，さらにロックしようとしてはならない（必要なデータをすべてロックするまではアンロックしてはならない）

2PLに従うスケジュール

2PLとロック両立性行列に従うスケジュールは競合直列化可能になる

課題10.4

連鎖的アボート

• 共有ロック(SL)を排他ロック(XL)に変換するとデッドロックが生じる場合あり $\rightarrow$ 更新を前提とした読み出しの場合は排他ロックを使用 (select文のfor update句)
• アンロックのタイミングによっては，連鎖的アボート(cascading abort)が発生する(T1がアボートされるとT2もアボートする）

厳格な２相ロッキングプロトコル

厳格な２相ロッキングプロトコル(rigorous 2PL)：コミットあるいはアボートまでアンロック操作を保留すること

• 連鎖的アボートは回避できる
• デッドロックは回避できない

図にアボートと同時にアンロックをかけて、コミットと同時にアンロックをかけるという操作を行うと連鎖的アボートは回避できる

課題10.5

1. 三つのトランザクションを考える．厳格な2PLに従うようにロック操作，アンロック操作を挿入しなさい．
2. 適当な順序でデータ操作を実行した場合に生成されるスケジュールを示し，競合直列化可能スケジュールになっていること，連鎖的アボートが発生しないことを確認しなさい．

課題10.6

デッドロック

デッドロック(dead lock): 複数のトランザクションが相互に相手が必要とするデータをロックし合い，永遠に相手のアンロックを待つ状態

デッドロックに対する対処方法：

• デッドロックを検出し，一方のトランザクションをアボートした後で再試行する
• デッドロックを回避するために，一定の規約に従ってロック，アンロックを行う

デッドロックの検出

• タイムアウトによる方法
  • 待ち時間を監視し，待ち時間が設定された時間以上になった場合にデッドロックが発生したと判断
• 待ちグラフ(wait-for graph)による方法
  • 先行グラフと同じような有向グラフを用いて判定
  • デッドロックは３つ以上のトランザクションによっても構成される

デッドロックを回避

• 事前に必要なすべてのデータをロックする方法：１つでもロックできないデータがあれば，一定時間後に再試行
  • スループット低下
• 決まった順序に基づいてロックする方法：データに順序関係を設定しておき，その順にロックしていく
• 時刻印(time stamp)を用いる方法：トランザクションの開始時刻により一意の時刻印を与える

トランザクションT1がロックしようとしたときに，トランザクションT2が既にロックを獲得していたという状況を考える

• ウェイト・ダイ(wait-die)方式：T1の時刻印がT2よりも早い（T1の優先度が高い）場合はT1はT2のアンロックを待つ，遅い(T2の優先度が高い）場合にはT1をアボートする
• ワウンド・ウェイト(wound-wait)方式：T1の時刻印がT2よりも早い（T1の優先度が高い）場合にはT2をアボート（優先度の低い相手をアボートさせる），遅い場合にはT1はT2のアンロックを待つ

分離レベルと多版型同時実行制御

分離レベル

許容する不整合のレベルを分離レベル(isolation level)として設定可能

• デフォルトの分離レベル：MySQL(InnoDB) … REPEATABLE READ, PostgreSQL …READ COMMITTED

多版型同時実行制御

多版型同時実行制御(multi version concurrency control: MVCC): データベース更新前の過去の版(version)をスナップショット(snapshot)としてとっておき，読み出しはロックせずに実行する

• MVCCを採用しているRDBMS: Oracle, PostgreSQL, MySQLなど

NOSQL

NOSQL: 構築したいアプリケーションによっては必ずしもリレーショナルデータベースが適しているとは限らず，他に適したデータベースの選択肢がある

代表的なNOSQLデータベース:

• Google
  • 分散ファイルシステム GFS (Google File System)
  • データ格納方式 Bigtable
  • 並列データ処理技術 MapReduce
• Amazon
  • DynamoDB
• その他
  • Apache Cassandra (列指向型データベース; Facebook)
  • MongoDB (ドキュメント指向データベース)
  • Apache CouchDB (ドキュメント指向データベース)
  • Neo4j (グラフ型データベース)

NOSQLデータベースを用いる理由:

• 高い処理性能: 巨大なデータを対象に，大量のクエリを高速に処理する高い処理性能が必要
• 疎なデータ: 欠損値を多く含む疎なデータはRDBで効率的に扱うのが難しい
• 柔軟なスキーマの変更: データ構造が頻繁に変更される場合や，事前にデータ構造が分からない場合はデータ構造を柔軟に変更できるデータベースが望ましい
• データ構造の適性: SNSサイトにおけるユーザの関係はRDBで扱いにくい

インターネット検索の仕組み

インターネット検索エンジン

• クローラ(crawler)：Webページの自動巡回プログラム（ロボット）
• インデックス生成：高速・高精度なキーワード検索を実現するために，事前に転置インデックス(reverse index)を作成しておく
• ランキング (ranking)：重要度(relevance)に応じてWebページを順位づけ

高速化のための工夫:

• 検索インデックスをすべてメモリ上に置く
• ハードディスクの中でもより高速にデータを読み出すことができるディスクの外周部にすぐに読み出す必要のあるデータを配置
• Googleはノンパリティのメモリを使っているため、エラーから回復するためのプログラムを自作し、ディスクスケジューラも自作

ランキング（スコアリング）

• 単語ベースのスコア：検索語の組み合わせから算出
  • TF/IDF (1972), Okapi BM25 (1994)：他のページには滅多に出てこない単語は重要
  • タイトル：Webページのタイトルに含まれる単語は重要
  • アンカーテキスト：他ページからリンクするときにリンクに付けられた文字列に含まれる単語は重要
• ページのスコア：各ページ毎にまとめたスコアを予め算出
  • ページランク (page rank)：重要なページから参照があるページほどより重要
  • ログ解析：検索クリック数やユニークユーザ数が大きいページはより重要

複数のスコアを（非公開の）ランキング関数で統合してページのスコアを算出

スケールアップとスケールアウト

スケールアップ(scale up)：ハードウェアの性能を向上することで処理性能を上げること

スケールアウト(scale out) ：コンピュータを並列化することにより処理性能を上げること

シャーディングとレプリケーション

シャーディング(Sharding)：一定の単位でデータ全体を断片に分割して分散管理すること

レプリケーション(replication)：データ断片を複製して複数のコンピュータに保持すること

• 機器の故障時にデータを保全
• 同じデータ断片を持つコンピュータ間でクエリの負荷を分散

従来の転置インデックス

転置インデックス(inverted index)：単語をキーとして，単語が出現する”文書”とその”位置”を逆引きできるようにするデータ構造

Googleの転置インデックス

“文書分散方式”で転置インデックスを分散管理

転置インデックスの分散方式

CAP定理

CAP定理：整合性，可用性，分断耐性の特性のうち，同時には二つしか満たすことができない

• 整合性(Consistency)：更新クエリを実行した後に実行されるデータ読み出しでは最新のデータを返す特性
• 可用性(Availability)：いかなる時刻に到着したクエリでも実行できる特性．更新処理中や，障害で一部のコンピュータ間の通信が途絶した場合でもクエリが実行可能
• 分断耐性(Partition Tolerance)：障害によって分散データベースが複数のグループに分断され，互いに通信できない場合であっても，データベースとして動作できる特性．スケーラビリティがある

BASE特性

BASE特性：基本的にはどんなときでも動作し(Basically Available)，データの更新は断片の複製を持つノードすべてに徐々に反映されることで(Soft-state)，結果的に整合性がとれた状態に至る(Eventual Consistency)という特性

分散データベースのクエリはACID特性もしくはBASE特性のどちらかを満たすべき(Brewer, 2000)

• ACIDにおける整合性は完全な整合性
• BASEにおける整合性は結果整合性(Eventual Consistency)

データの分散管理方式

CP型データベースにおけるデータ分散管理方式

マスタ・スレーブ方式 (Master Slave):

1. 書き込みクエリ
   1. マスターに送られる
   2. 書き込んだデータは時間をかけてスレーブに反映させる（最新になるまでに時間がかかる）
2. 読み込みクエリ
   1. マスタを介さず最寄りのスレーブが返答

AP型データベースにおけるデータ分散管理方式

P2P方式(Peer to Peer):

• すべてのノードが対等であり，複数のノードで同時並行にクエリを処理する（障害時にも可用性が保証される）
• 同時に複数の書き込みが発生した場合は，データの競合解決が必要

NOSQLのデータモデル

列指向型データベース

Bigtableの2次元表形式のデータ構造を基にしたデータベース

• 列方向に大量のデータを集計する処理に向いている（例，キーワード検索）
• 列は複数の「列ファミリ」から構成される．列項目は自由に追加可能
• 行IDと列IDによって定まる値にはタイムスタンプを付与
• 原子オブジェクトは行

キーバリュー型データベース

キー項目とそれに対応する値のみを持つ2次元の表を管理

• 原子オブジェクトは行
• eg. Dynamo, Memcached

ドキュメント指向型データベース

ドキュメントを単位としてデータを管理

• キー・バリュー型データベースのバリエーション
• ドキュメントはXML, JSONなどの半構造データ
• ドキュメント内の各項目にインデックスが付く
• 原子オブジェクトはドキュメント

グラフ型データベース

データ間の関係をグラフ構造を用いて管理