SQLで集約関数と集合計算
基本的なSQL命令のための集約関数などの追加を説明のうえ、演習課題に取り組んでもらう。
来週も後半を演習時間とする予定。
特殊な条件演算子
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の実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。
さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。
考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。
SQLと結合
SQLの基礎
前回の講義で、データベースでは、記録されているデータの読み書きは、SQL で行われ、射影・結合・選択を表す処理で構成されることを示した。SQL の機能を理解するために、同じ処理を C 言語で書いたらどうなるのかを示す。
SELECT S.業者番号 -- 必要とされるデータを抽出する射影 -- FROM S -- 複数のテーブルを組合せる結合 -- WHERE S.優良度 >= 20 ; -- 対象となるデータを選び出す選択 -- // 配列の個数を求める #define 文 #define sizeofarray(ARY) (sizeof(ARY) / sizeof(ARY[0])) // C言語なら... S のデータを構造体宣言で書いてみる。 struct Table_S { char 業者番号[ 6 ] ; char 業者名[ 22 ] ; int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; // 結合 for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // 選択 if ( S[i].優良度 >= 20 ) // 射影 printf( "%d¥n" , S[i].業者番号 ) ; }
Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。
SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;
WHERE 節で記述できる条件式では、= , <>(not equal) , < , > , <= , >= の比較演算子が使える。
直積と結合処理
ここで、SQLの最も便利な機能は、直積による結合処理。複数の表を組み合わせる処理。単純な表形式の関係データベースで、複雑なデータを表現できる基本機能となっている。
SELECT SG.商品番号 , S.所在 FROM S , SG WHERE SG.業者番号 = S.業者番号
- 実験環境で直積と結合処理(学内のみ)
上記の様に FROM 節に複数のテーブルを書くと、それぞれのテーブルの直積(要素の全ての組み合わせ)を生成する処理が行われる。この機能が結合となる。しかし、これだけでは意味がないので、通常は外部キーが一致するレコードでのみ処理を行うように、WHERE SG.業者番号 = S.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。
// C言語なら struct Table_S { char 業者番号[ 6 ] ; char 業者名[ 22 ] ; int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; struct Table_SG { char 業者番号[ 6 ] ; char 商品番号[ 6 ] ; int 在庫量 ; } = SG[] { { "S1" , "G1" , 300 } , : } ; // FROM S for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM SG for( int j = 0 ; j < sizeofarray( SG ) ; j++ ) { // WHERE S.業者番号 = SG.業者番号 if ( strcmp( S[i].業者番号 , SG[j].業者番号 ) == 0 ) { // SELECT SG.商品番号 , S.所在 printf( "%s %s¥n" , SG[j].商品番号 , S[i].所在 ) ; } } }
(1) i,jの2重forループが、FROM節の結合に相当し、(2) ループ内のif文がWHERE節の選択に相当し、(3) printfの表示内容が射影に相当している。
射影の処理では、データの一部分を抽出することから、1件の抽出レコードが同じになることもある。この際の重複したデータを1つにまとめる場合には、DISTINCT を指定する。
SELECT DISTINCT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ;
- 実験環境で結合/重複削除(学内のみ)
上記のプログラムでは、データの検索は単純 for ループで記載しているが、内部で HASH などが使われていると、昇順に処理が行われない場合も多い。出力されるデータの順序を指定したい場合には、ORDER BY … ASC (or DESC) を用いる
SELECT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ORDER BY S.所在 ASC ; -- ASC:昇順 , DESC:降順 --
- 実験環境で結合/並び替え(学内のみ)
表型のデータと串刺し
FROM に記載する直積のための結合では、2つ以上のテーブルを指定しても良い。
SELECT S.業者名, G.商品名, SG.在庫量 FROM S, G, SG WHERE S.業者番号 = SG.業者番号 -- 外部キー業者番号の対応付け -- AND SG.商品番号 = G.商品番号 -- 外部キー商品番号の対応付け -- // 上記の処理をC言語で書いたら struct Table_G { char 商品番号[ 6 ] ; char 商品名[ 22 ] ; char 色[ 4 ] ; int 価格 ; char 所在[ 12 ] ; } = G[] = { { "G1" , "赤鉛筆" , "青" , 120 , "福井" } , : } ; // FROM S (結合) for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM G (結合) for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { // FROM SG (結合) for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // WHERE S.業者番号 = SG.業者番号 // AND SG.商品番号 = G.商品番号 (選択) if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 && strcmp( SG[k].商品番号 , G[j].商品番号 ) == 0 ) { // 使用するフィールドを出力 (射影) printf( "%s %s %d\n" , S[i].業者名 , G[j].商品名 , SG[k].在庫量 ) ; } } } }
- 実験環境で結合/3つのTABLEの串刺し(学内のみ)
ここで結合と選択で実行している内容は、外部キーである業者番号を S から探す、商品番号を G から探している。この、外部キー対応しているものを探すという視点で、上記 C 言語のプログラムを書き換えると、以下のように表せる。
// FROM SG for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // 外部キー SG.業者番号に対応するものを S から探す for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 ) { // 外部キー SG.商品番号に対応するものを G から探す for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { if ( strcmp(SG[k].商品番号,G[j].商品番号) == 0 ) { printf( "%s %s %d\n" , S[i].業者名,G[j].商品名,SG[k].在庫量 ) ; } } } } }
このような、複数の表の実体と関係を対応付けた検索を、データベースの専門の人は「データを串刺しにする」という言い方をすることも多い。
また、SQL では、このようなイメージの繰り返し処理を、数行で分かりやすく記述できている。このプログラム例では、キーに対応するものを単純 for ループで説明しているが、SQL ではプライマリキーなら、B木やハッシュなどを用いた検索が行われるが、SQLの記述するときにはあまり考えなくて良い。
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の説明。
キー
表形式のテーブルの中の各レコードを一意的に指定できるカラムはキーと呼ばれる。
キーは単独であるとは限らず、成績の評価結果であれば、学生と科目をキーとして成績というカラムが1つに絞られる場合もある。
キーのうち、データを一意に識別するためのキーは、プライマリーキーと呼ばれる。以下の例であれば、uID,sID がプライマリーキーである。一方、成績のテーブルでは、uID, sID は、学生,科目のキーとなっている。このようなキーは外部キーと呼ばれる。点数pointは、uID, sID により一意に決まるが、例えば成績の uID に、学生のテーブルに存在しないものが指定されてはいけない。こういった制約は外部キー制約と呼ばれる。
SQLの命令
SQL で使われる命令は、以下のものに分類される。
- データ定義言語 – CREATE, DROP, ALTER 等
- データ操作言語 – INSERT, UPDATE, DELETE, SELECT 等
- データ制御言語 – GRANT, REVOKE 等 (その他トランザクション制御命令など)
create user
データベースを扱う際の create user 文は、DDL(Data Definition Language)で行う。
CREATE USER ユーザ名 IDENTIFIED BY "パスワード"
grant
テーブルに対する権限を与える命令。
GRANT システム権限 TO ユーザ名 データベースシステム全体に関わる権限をユーザに与える。 (例) GRANT execute ON admin.my_package TO saitoh GRANT オブジェクト権限 ON オブジェクト名 TO ユーザ名 作られたテーブルなどのオブジェクトに関する権限を与える。 (例) GRANT select,update,delete,insert ON admin.my_table TO saitoh REVOKE オブジェクト権限 ON オブジェクト名 TO ユーザ名 オブジェクトへの権限を剥奪する。
create table
実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。
CREATE TABLE テーブル名 ( 要素名1 型 , 要素名2 型 ... ) ; PRIMARY KEY 制約 型の後ろに"PRIMARY KEY"をつける、 もしくは、要素列の最後に、PRIMARY KEY(要素名,...)をつける。 これによりKEYに指定した物は、重複した値を格納できない。 型には、以下の様なものがある。(Oracle) CHAR( size) : 固定長文字列 / NCHAR国際文字 VARCHAR2( size ) : 可変長文字列 / NVARCHAR2... NUMBER(桁) :指定 桁数を扱える数 BINARY_FLOAT / BINARY_DOUBLE : 浮動小数点(float / double) DATE : 日付(年月日時分秒) SQLiteでの型 INTEGER : int型 REAL : float/double型 TEXT : 可変長文字列型 BLOB : 大きいバイナリデータ DROP TABLE テーブル名 テーブルを削除する命令
insert,update,delete
指定したテーブルに新しいデータを登録,更新,削除する命令
INSERT INTO テーブル名 ( 要素名,... ) VALUES ( 値,... ) ; 要素に対応する値をそれぞれ代入する。 UPDATE テーブル名 SET 要素名=値 WHERE 条件 指定した条件の列の値を更新する。 DELETE FROM テーブル名 WHERE 条件 指定した条件の列を削除する。
select
データ問い合わせは、select文を用いる、 select文は、(1)必要なカラムを指定する射影、(2)指定条件にあうレコードを指定する選択、 (3)複数のテーブルの直積を処理する結合から構成される。
SELECT 射影 FROM 結合 WHERE 選択 (例) SELECT S.業者番号 FROM S WHERE S.優良度 > 30 ;
理解確認
- キー・プライマリキー・外部キーについて説明せよ。
- 上記説明中の、科目テーブルにふさわしい create table 文を示せ。
- select文における、射影,結合,選択について説明せよ。
データベースの用語など
データベースの機能
データベースを考える時、利用者の視点で分類すると、(1) データベースの管理者(データベース全体の管理)、(2) 応用プログラマ(SQLなどを使って目的のアプリケーションに合わせた処理を行う)、(3) エンドユーザ(データベース処理の専門家でなく、DBシステムのGUIを使ってデータベースを操作する)となる。
データベース管理システム(DBMS)では、データとプログラムを分離してプログラムを書けるように、データ操作言語(SQL)で記述する。
また、データは独立して扱えるようにすることで、データへの物理的なアクセス方法があっても、プログラムの変更が不要となるようにします。
データベースは、利用者から頻繁に不定期にアクセスされる。このため、データの一貫性が重要となる。これらを満たすためには、(a) データの正当性の確認、(b) 同時実行制御(排他制御)、(c) 障害回復の機能が重要となる。
これ以外にも、データベースからデータを高速に扱えるためには、検索キーに応じてインデックスファイルを管理してくれる機能や、データベースをネットワーク越しに使える機能などが求められる。
データベースに対する視点
実体のデータをそれぞれの利用者からデータベースを記述したものはスキーマと呼ばれる。そのスキーマも3つに分けられ、これを3層スキーマアーキテクチャと呼ぶ。
- 外部スキーマ – エンドユーザからどんなデータに見えるのか
- 概念スキーマ – 応用プログラマからは、どんな表の組み合わせで見えるのか、表の中身はどんなものなのか。
- 内部スキーマ – データベース管理者から、どんなファイル名でどんな形式でどう保存されているのか
データモデル
データを表現するモデルには、いくつかのモデルがある。
- 階層モデル – 木構造で枝葉に行くにつれて細かい内容
- ネットワークモデル – データの一部が他のデータ構造と関係している。
- 関係モデル – すべてを表形式で表す
データベースの基礎
データベースは、1970年頃に、E.F.コッド博士によりデータベースのための数学的な理論が確立された。
- 集合 A, B – 様々なデータ
- 直積 A✕B = { (x,y) | x∈A , y∈B } 集合A,Bのすべての組み合わせ
- 関係 R(A,B) すべての組み合わせのうち、関係があるもの。直積A,Bの部分集合
例えば、A={ s,t,u } , B={ p,q } (定義域) なら、
A✕B = { (s,p) , (s,q) , (t,p) , (t,q) , (u,p) , (u,q) }
このうち、Aが名前(sさん,tさん,uさん)、Bが性別(p=男性,q=女性)を表すなら、
R(A,B) = { (s,p) , (t,q) , (u,p) } (例)
(例):(sさん,男性) , (tさん,女性) , (uさん,男性)
理解確認
- データベースにおける3層スキーマアーキテクチャについて説明せよ
- 集合A,Bが与えられた時、関係R(A,B) はどのようなものか、数学定義や実例をあげて説明せよ。
2019データベース・ガイダンス
インターネットの情報量
インターネット上の情報量の話として、2010年度に281EB(エクサバイト)=281✕1018B(参考:kMGTPEZY)で、今日改めて探したら、2013年度で、1.2 ZB(ゼタバイト)=1.2✕1021B という情報があった。ムーアの法則2年で2倍の概算にも、それなりに近い。 では、今年2019年であれば、どのくらいであろうか?
そして、これらの情報を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万になるかもしれない。
さらに、コンピュータといってもハードディスクの故障などは発生する。 障害が発生してもデータの一貫性を保つためには、バックアップや 障害対応が重要となる。
授業アンケート結果(ぷちブルーな気分)
情報ネットワーク基礎(3EI/後期)
楽しんで受講してくれた人からの意見があり、ポイントでも85ポイントと高評価であった。内容理解やシラバスについてポイントが若干低いようであるが、誤差の範疇と思われる。理解把握のポイントが最も低く、理解度確認のための質問などをもう少し増やしても良かったかと思う。
情報制御基礎(3年学際科目/前期)
学際科目ということで、初めて実施した科目であり、他学科からも受講生がある内容で、ポイントも70ポイントと低い評価であった。
プログラムを授業でやっていない学科の学生から、内容が理解できないとの意見が多かった。今年度は、他学科の学生にもわかるように、プログラムの説明を増やしたり、プログラムよりも基本的な内容を増やしたいと考えている。
情報構造論(4EI/通年)
意見の欄には、例年になく辛辣な意見もあった。他の同クラスのアンケートでも、全般的に厳しい意見が多くみられ、ポイントは74.8と例年よりも低くいが、このクラスのオフセットとも考えられる。
昨年から講義資料のWeb掲載などを行い、それを使った授業を中心としているが、ノート作成ができていない学生から、ノートをとる時間を十分にとってほしいとの意見があった。もう少し、授業の時間の作り方などを考えたいが、一方で不まじめな学生がノートもも一切とらないで受講する姿は、理解する意欲に欠けていることもあり、どのような対処とすべきか、時間をかけて考えていきたい。
データベース(5EI/後期)
ポイントでは78.6と、若干低めの評価であった。演習量や試験についての評価が他に比べて若干低く、意見でも図や表といった具体例を交えた例での説明を増やしたほうが理解が進むとの建設的な意見もあった。資料などもWebでの公開などを進めているが、今後も実例などを増やし解りやすい資料を目指したい。
オブジェクト指向プログラミング(PS2/前期)
他学科出身の受講者も含まれるため、例年進度に注意しながら授業を進めているが、ポイントでは80ポイントで、例年並みの評価であった。
もう少し、演習などをタイムリーに行いながら授業を進めたいと考えているが、演習環境などの準備も必要で自主学習などの課題を検討したいと思う。
B木とB+木とハッシュ法
B木
データベースのデータを扱う場合には、B木を用いることが多い。
複数のデータを格納するノードは、位数Nであれば、2✕N個のデータと、その間のデータを持つノードへの2N+1個のポインタで構成される。
ノードにデータを加える場合は、頻繁にノードのポインタの付け替えが発生しないように、データがN個を下回った時や、2N個を超える場合とする。ノード内のデータ数が2Nを超える場合は、均等に木構造が成長するように、中央値を上のノードに移動し、ノードを2分割する。
B+木とシーケンスセット
再帰的な木構造のB木では、特定のデータを探す場合には、O(log N)で検索が可能である。
しかしながら、直積のようなすべてのデータを対象とする処理を行う場合、単純なB木では再帰呼出しをしながらの処理を必要とすることから、複雑な処理が発生する。そこで、データ列を横方向にアクセスするための単純リストであるシーケンスセットをB木と並行して管理するデータ構造がB+木である。
データを検索する場合は、B木構造部を用い、全データ処理は、シーケンスセットを用いる。
ハッシュ法
ハッシュ表は、データの一部をとりだしてハッシュ値を求め、そのハッシュ値を番地とする場所にデータを保存する方法である。しかし、データの一部を取り出すため、異なるデータに対して同じハッシュ値となる場合がある。これをハッシュ衝突とよぶ。この際のデータの保存の方法から、2つの方式がある。
- オープンハッシュ法
ハッシュ表がすでに埋まっていたら、別の保存場所を探す方式。 - チェイン法
同じハッシュ値となるデータをリスト構造で保存する方法。
(2019-01-29) 図が見にくかったので差し替え
トランザクション処理
トランザクション処理
トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。
例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。
上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。
同時実行制御
複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。
- ロッキング方式(悲観的制御)
先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。- ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
- ロックの種類
ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
- 2相ロッキングプロトコル
トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
- 時刻印処理(楽観的制御)
データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。
デッドロック
複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。
このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する。
データベースの物理設計
データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。
ディスク容量の見積もり
データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。
実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。
そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。
また、データベースへのデータの削除を行う場合、データが1つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。
このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。
一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。
また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。