放送大学全科目感想 017 データベース(’17)

  • 情報コース
  • テレビ科目
  • 辻靖彦先生(放送大学准教授)
  • 柴﨑順二先生(放送大学教授)
  • 難易度 ★★★☆☆
  • おすすめ度 ★★★★☆

AccesなどでSQLを実際に使っていく、という講義ではない。データベースがなぜ使われるのか、数学的な定義は何かというところから掘り下げていくので、特に辻先生担当の所は難解な部分もあるが、データベースが有利な点についてかなり具体的に学ぶことができる。リレーショナルデータベースを中心とした講義で、後半はRDB以外のデータベースについても学ぶ。

第1回

イントロ、辻先生。

データを体系的に収集・加工、効率的に管理・運用するのがデータベースで、中核的な要素であるとのこと。例えばWAKABA。個人情報や成績・履修情報を管理できる。他にも銀行システム、ネット通販システム、顧客管理システムなど。いずれも業務に密接にかかわるデータの塊を持っている。目的を満たすための必要なデータ、実世界で必要な規則を取り扱うことが望まれる。実世界に沿ってデータベースの構造も変わっていく。

データベースとは、この授業では、目的を持った一定のデータの集まりと定義する。

ユーザーには誰がいるか。データベース管理者とアプリ開発者、それからユーザーがいる。普通は管理者と開発者が同一のことが多いような。

データモデル作成について。実世界→概念データモデル→論理データモデル→物理データモデルの3段階がある。いずれも別々に設計が必要(物理の方はあんまやらないかな)。論理データモデルの例としてリレーショナルデータモデルがある。いわゆるRDBMS。

データの整合性の維持。これはデータモデルで実装できる。例えば、学生の学籍番号の一意性とか、学生が必ず学籍番号を持たなければいけないとかは、データモデル自体に制約が内包されている。これが重要な機能の1つ。

データベース言語には、データ定義(DDL)、データ操作(DML)、データ制御(DCL)がある。データ操作に相当するのがSQLかな。

データ格納方式は木構造、ハッシングなど。検索は効率的に、高速に行われないといけない。

機密保護について。アクセス制限、権限の付与を行うことができる。

同時実行制御。処理単位をトランザクションと呼び、並列処理が可能になる。ロック機能も必要。

三層スキーマ構造。外部スキーマ(見え方、ビュー)、概念スキーマ(テーブルの設計)、内部スキーマ(物理的格納方法)の3つ。それぞれ独立性をもって、どれか1つを変更しても他に影響がないようにしている。

データベースを使う利点。データの整合性の保持が最も重要。副次的な要素として、効率の向上や機密保持、同時アクセスへの耐久性なども挙げられる。

最近登場したNOSQL(Not Only SQL)について。ビッグデータなど膨大で複雑な構造のデータを高速処理する時に使われる。

ここまで駆け足のイントロだったが、この後は講義全体の構成。技術的な話も押さえつつ、実際のデータベースの適用の様子をかなり見せてくれる講義のようだ。

第2回

身の回りのデータベースについて。柴﨑先生。声が大きい。

裏方として働くデータベース。経済活動自体がデータベースに依存しているという。電子カルテが例になってる。確かに私の開発してる電子カルテもデータベース操作がほとんどっす。座席情報は昔は手作業だったのでダブルブッキングがあったが今はほとんどないらしい。ATMは昔からデータベースだよね。絶対に間違いあっちゃいけないし。

WIndows95によってインターネットが開始され、ここから予約サービスのデータベースの役割が大きくなった。2000年以降ブロードバンド回線が普及し、一気にデータ量が増えてデータセンターなどもいっぱいできた。ポータブルデバイスが発達して、データはネットワークの向こう側に置くようになってきた。これらもデータベースで管理されている。

個人の生活とデータベース。まず検索エンジン。私たちが検索しているのはwebページそのものではなく、検索ロボット(クローラ)が巡回して作成したデータベースによるものである。大きなサイトだと数百万台のサーバーを抱えているそうだ。データベースはオンラインショッピングの土台にもなっている。商品情報、在庫情報、顧客情報、発注情報を全部管理しているので何度もデータベースへのアクセスが発生している。

ヤマトシステム開発のデータセンターに取材してる。クロネコヤマトやね。サーバーは3000台、データベースは270台。メンバーズの管理とか問い合わせ、大和グループの基幹システムで使ってる。一日4600万件(!)。問い合わせも700万回。インタビュイーのおじさん、技術者じゃないなー。広報って感じ。ふわっとした解答がおおい。もはや社会インフラなんで、ガス発電装置とか災害時にもばっちり対応しているらしい(データベースとあんま関係ない)。リアルタイムがどうとか伝票レスがどうとかしか言ってないのでデータベースの技術的なことに触れられてないっす。。なぜこのおじさんに高給を払うのだ。。

あっ先生技術的なこと他の人に聞いてるじゃん!!さすが!!

まずヤマトのDBはメンバーズのサービスは完全に別個扱いで、独立。あとはトレーシングDBとダウンロードDBの2つ。ダウンロードDBが大事で、現場で使うデータが全部入ってる。トレーシングDBは現場の状態を随時上げていくDBで、これは問い合わせのときに使う。不在率は20%もあって大変なので、DBを使ってこれを下げていきたいらしい(どうやって?)。

POSシステムって顧客の見た目のデータも入れてるんですね。これそのうちビデオカメラで自動でできるようになるんちゃうのかな。

第3回

データベースの仕組み。

データと情報との違いから。データはただの客観的な真実(今日は雨)で、情報はデータを役立つように加工したもの(今日の降水確率は80%だから傘を持っていこう)という違いがある。情報は正確・整合性・スピードなどいろいろな価値がある。これらを踏まえるとデータベースとは、「データに情報としての価値を持たせ、データを有効に活用できるようにする目的のために、共有性や再利用性を意図して、一定の規則に基づいてコンピュータ上に格納されたデータの集まり」である。

データは昔は紙集計だった。一部がファイル形式のデータになったのち、データ処理の高度化に対応するためデータベースが利用されるようになったといえる。ファイルシステムだと専用プログラムが必要になるし、汎用性がない。一意性もないし不整合も起きる。メンテが大変。データアクセスも煩雑。これをデータベースにすると管理も楽になるし、ほかのプログラムでデータベースにアクセスして再利用すること(マッピング)や複数ユーザー間の共有も可能になる。データベースは無駄のないデータ集合体である。おお、データベース使うメリット大きすぎじゃん!

データベースの概念について。過不足なくデータを蓄積して、適切な規則を作っておかなくてはならない。たとえば図書館の書誌情報。すべて同じ規則(ISBNコードがあるとか、同じ書籍を重複して登録しないとか)に従って入力されているので、データの増減があっても問題なくなる。データベースを図書館に例えると、データベース自体は書棚、DBMSは司書さん、アプリケーションはカウンターである。データベース管理システムが挟まってるところが便利なところなんだろな。

データベース管理システムはエンジンみたいなもん。データベース自体はただのデータの塊なので、実際に問い合わせる管理システムが重要。実際やることは、データモデルの提供や、整合性の維持、排他制御、障害対応。。いろいろある。

データモデルとモデリングについて。モデリングとは現実をデータに定義しなおすことをいう。概念データモデルの代表はE-Rモデル(実体-関連モデル)という。実体・関連・属性で表す。例えば、実体が商品・取引先、関連に発注、属性が商品コードとか価格とか。論理データモデルは前出のリレーショナルデータモデルとか。

3層スキーマアーキテクチャについて。データベース構造を外部スキーマ、概念スキーマ、内部スキーマに分ける。外部スキーマがビュー、概念スキーマがさっきのE-R図、内部スキーマが容量設計とかメモリ設計とかに対応する。それぞれが独立で他に影響しない。独立性ってのがコンピュータ系ではほんと大事な概念なんだね。

第4回

データベースの歴史。先生の声が小さくなった気がする。速度も落ちた。

データベースの起源は、1950年アメリカから始まる。軍の基地の中で分散していた情報を統合して一か所にまとめたところからデータベース(base)という言葉ができた。1957年スプートニクショックで、データの分散化と、分散されたデータの収集・処理・管理が望まれるようになった。

学術的には1959年のマギー氏、源泉ファイル(Source File)という言葉が初めて。データを階層的に管理し、蓄積する仕組み。重複回避や拡張性、機密保持などの必要性を唱え、現在のDBMSに通じる概念を作った。

商用DBは1960年のGE社のIDSがはじめて。社内生産管理システムを電算化したとき、索引部を介して情報をDB化した。まだまだコンピュータが高価な時代。国家機関しか利用できてない。COBOLにIDSを組み込んだのがCODASYLというグループらしい。聞いたことある気がする。1965年発足。1969年ごろからDBの仕様が一般的にできてきたそうだ。

初期のデータベースで採用されていたのが階層データモデル。データを階層木構造で表現する。常に親と子が1対nとなる。データへのパスは1つなので重複が発生してしまう。複数の親を持てないことが欠点。データ構造に変更があるとプログラム変更が必要なのも欠点。もう一つの流派であるネットワークデータモデルだと、データに達するパスは複数になるから、重複はなくなる。ただプログラム変更は複雑で、毎回変更が必要なことも同じ。

新しいデータモデル。リレーショナルモデルはIBMのコッドさんが作った。1970年代。幹や枝の考え方をやめて、表にする。数学の関係代数、集合理論に基づいているらしい。データベースは集合だったのか!!!なんつっても表とSQLとDBMSがあればオッケー。負荷はかかるが、ハードウェアの進歩とともに負荷は相対的にかからなくなっていった。

リレーショナルモデルはすぐには実用化されなかった。原因は既に以前のモデルに基づいて投資がされていたこと、コンピュータのパワー不足、実装の困難さなどがあった。RDBMSは70-80年代にだんだんと発展してきた。80年代になるとワークステーションが発展して、Oracleなんかも成長してきた。LANも発展してクラサバ型サービスができてきたので、需要が高まった。90年代はAccessやMySQLなども登場した。

オブジェクト指向データベース。バイナリやマルチメディアファイルを扱うのに適している。スキーマ不要で複雑な構造を表現できる。オブジェクト指向型プログラミング言語で扱うデータ(インスタンス?)をそのまんまDBに入れちゃうらしい。リレーショナルデータベースと組み合わせたPostgreSQLが代表。

NoSQL。データを分散して保管するためのニーズで生まれた。Microsoft Azure DocumentDBとか、Amazon RDSとか。キーバリュー型のAmazon DynamoDBというのもあるらしい。

第5回

データベースの動作環境。プラットフォームとしてのコンピュータがどのような変化をしてきたか。大型コンピュータ→ミニコン→Unix→ワークステーション→PC→クラサバという流れ。C言語って移植性が優れていたから発展したのか。おおまかには、データベースの動作環境はWindowsやUnixなど汎用化し、コンピュータも安くなって簡単に環境が構築できるようになった。

クラサバで主に使われているのはweb-データベース連携システムという。webブラウザ使えば特殊な端末も必要なく利用できる。近年はweb化が進んでいるのでwebアプリケーションサーバーをつけて、負荷を少なくする仕組みが確立している。webサーバ、アプリケーションサーバ、データベースサーバと負荷を3階層に分散することで、セキュリティも向上する。3階層システムという。

クラウド型データベース。手元にDBを持たなくていいのでコストがかからない。AWSとかね。

分散型データベース。データベースを分割し、複数のデータベース管理システム同士が通信を行う。ユーザーは通信を意識する必要はない。危険分散と負荷分散ができる。

webとXMLデータベース。XMLデータベースはXMLスキーマ自体をデータベースの定義として使うというもの。XMLは階層性を持ち、拡張性が容易な特徴がある。そしてデータ自体も書ける。これをそのまんま蓄積すればXMLデータベースになる。巨大なXMLデータをいかに効率よく管理するか、というのがXMLデータベースの必要性を生んだ。XMLだから別にテーブルじゃなくてもいい。XMLデータベースは基本的には単に蓄積するだけ。タグ情報をインデックス化することで高速アクセスを可能にする。データ定義の変更が頻繁にあるようなデータに向いている。汎用性も高いしマルチメディア情報も格納できる。

xpassとSQLの相互変換は可能なので、その意味ではRDBMSと共存ができる。XMLはDOMに読ませてしまえばオブジェクト指向DBとも連携できる。

オープンソースソフトウェアを組み合わせて構築できる環境としてLAMPがある。Linux Apache MySQL Python/PHP/Perl の略らしい。安価で高性能な環境が構築できる。

データベース言語について。ネットワークデータベースの規格がNDL(1987年)、リレーショナルデータベース言語のSQLも同年。SQLは2016年の定義まであるらしい。標準化は様々なメリットがある(略)。

第6回

概念設計の話。データモデルを作成すること。既出のように概念、論理、物理データモデルの3つ。まずは実世界からE-Rモデルを使って概念データモデルを作成する。概念データモデルを基に論理データモデルを設計する。また既出のように階層、ネットワーク、リレーショナル、オブジェクト指向モデルがある。最後は物理モデルだが、これはDBMSが勝手にやってくれる。

概念設計について。実体関連モデルは計算機科学者のピーター・チェンって人が作ったらしい。E-R図も別名はピーター・チェン記法という。

実体とは。実世界の個々の対象物のこと。一人一人の学生、教員、科目など。「学生」のようなカテゴリは実体型という。クラスのことかな?実体型は属性 attributeを持てる。例えば学生には氏名、住所、学籍番号などを持っている。学籍番号のような一意なキーを主キーという。

関連とは。2つ以上の実体同士の相互関係のこと。関連も関連型としてとらえることが多い。例えば学生→(履修)←科目のような関係。関連型に主キーなんてあるんかいな。人→結婚←人みたいな、同一の実体型の結びつきを表す関係もある。こういう場合関係性(ロール)が与えられる。結婚なら、夫や妻があるね。

1対1の対応関係は、考えやすい。教員→所属←研究室みたいな場合を考えることができる。このとき多重度は1対1という。主キーは教員でも研究室でもいい。

1対多の対応関係の場合は、多の方が主キーになる。例えば部活動と学生。学生の方が多いので、主キーは学生。多対多、例えば学生と科目の関係の場合は、主キーは両側の実体型の主キーの和集合(全組み合わせ)となる。主キーってのは一意性を満たす関係のことね。

実際の図を見て考える。図にするとどうやってモデルを作ればいいかわかりやすいね。昔、電車がリアルタイムで走るモデルを作ったことがあるけど、こんな風にモデルを作っておけばもっと楽だったな。

制約について。部活動と学生は1対多だけど、部活に所属していない学生や、だれも所属していない部活動があってもいいのかは明らかではなかった。これを認めるか認めないかを、参加制約という。関連図に最小値や最大値を書くことで参加制約が明確になる。

ある実体に依存して初めて存在できる実体型のことを弱実体型という。例えば科目に対するレポート。単体で存在できるのは強実体型という。弱実体型は、対応する強実体型の主キーに対して、部分キーを持つことができる。強キーと必ずペアで用いられる。

3項関連型。例えば履修を複数年度にしたい場合。学生、科目だけではなく年度(時期)も関連として採用してやればいい。

Is-A関連。社員に対する営業部員・製造部員のような関係。社員がスーパータイプ、営業部員・製造部員はサブタイプという。継承ともいってるし、クラスに近い考え方だ。

UML。統一モデリング言語の略。今使われてるのかな。ここまでの概念は全部表現できるみたいだよ。属性を実体型に含めて書けるので見やすい。

第7回

リレーショナルDBモデル。論理データモデルの1つ。リレーションは数学的に定義できる。情報の単位自体をリレーションと呼んでる。スキーマとインスタンスがある。構造、操作、制約が3つの要素である(?)

リレーションインスタンスというのは、表1個のこと。リレーション名とは、いわゆるテーブル名のこと。行はタプルという(いろんなデータの集合だからかな)。

主キーはスーパーキー(一意なキー)かつ候補キー(スーパーキーかつ極小単位)であるキーの中で、設計者が選んだもののこと。NULLを取らないという制約がある。

リレーションの定義は、全リレーションの直積集合のこと。いくらでもあるね。

リレーションは同一要素を持ってはならない。タイムスタンプとか通し番号とか持ってないとダメね。順番にも意味はない。

正規形。入れ子型を禁止すること。入れ子のものは別のテーブルに分けてやれば正規化できる。

リレーショナル代数。和集合とかの集合演算のこと。同じ属性とドメイン(テーブルのことかな?)をもっていないとだめ。商演算は難しいな。直積演算の逆。選択(select?)や射影もある。射影は要素の重複ができてしまうので、重複は排する。

整合性制約。ドメイン制約(変数の範囲の制約)、一意性制約(同じ値の排除)、非NULL制約(空データはダメ)、主キー制約(=一意性制約+非NULL制約)、参照整合性制約(外部キーは必ず外部リレーション内にある)がある。

概念データモデル→論理データモデルの変換について。実体-関連図を使えばそのまんま変換できる。っていうかこの図自体がほぼ論理データモデルなんだな。ID関連型(弱実体型への関連)の関連はリレーションに入れる必要がない(どうせ1対1になるしってことかな)。弱実体型に所有実体型の主キーを持たせとけばいい。関連は、やろうと思えばリレーションに併合してしまうこともできるみたい。その場合、1対1関連ならどちらでも、n対1型ならn側に併合できる。n対mの場合は無理。

第8回

データ操作について。ユーザーの要求は主に、問い合わせと更新である。今回は問い合わせについての学習。

リレーショナル代数→集合論に基づく問い合わせの体系。リレーショナル論理→論理式を用いてデータを表現。代数と論理は等価らしい(ほんとか?)

リレーショナル代数はコッドさんが作った。演算は8種類。和集合とか差集合とか。8種類のうち3つはほかの5つで表現可能だから実質5つ。和、差、直積、選択、射影。

和集合演算。同一ドメインの表を合算して重複するものは排除したもの。論理式だと、または(∨)で表現可能。

差集合演算。論理式だとA∧¬Bで表現可能。

共通集合演算。かつ∧と同義。和、差、共通集合演算は同一ドメインで同一属性じゃないとダメ。和両立という。共通集合は R – (R – S) でも表現できる(図を書いてみよ)。

直積演算。全タプルの組み合わせで結合する演算のこと。膨大な数になるね。別ドメインに同一の属性があっても、リレーション-属性を一組にして区別し、問答無用で組み合わせを考える。

選択演算。これが一番重要。選択条件を使って絞り込む。選択はσで表す。

射影演算。指定した属性だけ残す。減らした結果重複が生じたら、重複は削除。

商演算。R/Sなら、Sの属性値が全部含まれているRの属性値だけを残すことに相当する。例えば「S:アメとガムとカップ麺」で「R:コンビニ」を割れば、アメとガムとカップ麺を持っているコンビニが残ることになる。商はめっちゃ頑張れば射影、直積、差を組み合わせまくって表現できる(詳細は略)。

自然結合演算。2つのリレーションに共通の属性があるとき、同じ属性を持つタプルを結合すること。直積+選択+射影で表現可能。共通の属性がないタプルをダングリングタプルという。

θ結合演算(または単に結合演算)。共通の属性がなくても、結合条件を与えて結合させることで一般の場合に拡張したもの。これも直積+選択で表現可能。

外部結合。ダングリングタプルをNULLを用いて強引に結合してしまうこと。結合に使った全タプルが含まれることになるが、NULLがあるから扱いにくそう。

第9回

正規化。リレーションスキーマがよいものかどうかを判断する手掛かりになる。論理設計の一部。

関数従属性。Xの値が等しいすべてのタプルにおいて必ずYの値も等しいということ。X→Yの関係が成り立つことと同じ。学籍番号→氏名とか。リレーションRの出現しえるインスタンスの満たす性質のこと(リレーションを作るための必要条件ってことかな)。

関数従属性は実世界上の規約で決まる。例えば「受注番号が受注ごとに新しく発行される」という規約があれば、「受注番号→受注年月日、顧客番号」のような関数従属性が成り立つ。

関数従属性の表記方法。A1, A2, … Am → Y と表記する。カンマを省略することもある。A1A2…→Y 。X∨YはXYと書くこともある。

Kがスーパーキーであるとは、関数従属性K→A1A2…Anが成立することと定義することができる。Kが候補キーであるとは、Kの部分集合K’がスーパーキーにならないことともいえる。

A1A2…Am→B1B2…Bnという関数従属性が成り立っていたら、A1A2…→B1,A1A2…→B2のように分割できる。例えば、受注番号と項番が候補キーになっていれば、ここから受注年月日、顧客番号、単価などを一意に決定できるでしょ?ということ。受注番号単体では一位にならない。直感的にはそりゃそっかーって感じだけど式にして一般化も可能なんだね。

アームストロングの公理系。まず反射律。YがXの部分集合なら、X→Yが成り立つ。添加律。X→YならX∨Z→Y∨Zが成立。推移律。X→YかつY→ZならばX→Zが成立する。この3つが基本になる。

関数従属性の閉包。リレーションRにおける関数従属性集合Fが与えられたとき、①Fの要素と②Fの要素の任意の組の関数従属性が考えられ、①②をあわせてFの閉包という。F+と書く。なんのこっちゃって感じです。具体例が欲しい。

アームストロングの公理系は健全で完全であるという。健全→Fの各要素にアームストロングの規則を用いると、どれもF+の要素になる。完全→F+の関数従属性は、全部Fの各要素にアームストロングの公理系の各規則を適用すれば、導出できる。というわけで、関数従属性集合の閉包はアームストロングの公理系を使えば求められるってわけ(foon)。

閉包を求めるアルゴリズム。全然意味わからんが、「スーパーキーというのは数学的な手続きを踏めば必ず求められる」ということまでは理解できたので、そこまでにしておこう。

更新時異状。第一正規形では全部スカラー値になっているが、異状が起きることが3パターンある。

修正時異状。ある事実を表す情報が複数のタプルに存在する場合。例えばある商品番号の単価を更新したら、全部更新しないといけない。更新漏れがあるのが修正時異状。

挿入時異状。ある事実を表す値をデータベースに追加したいが、情報が足りなくて追加できない場合。

削除時異状。ある値を削除する時、意図しない形で別の事実を表す情報が失われること。受注情報を1行削除したら商品情報がなくなるとか。

これらをなくすために正規化が必要。まず第2正規形。Rの全ての非キー属性が、Rの候補キーに完全関数従属していること。完全関数従属性とは、Xの任意の真部分集合X’についてX´→Yが成立しないことをいう。成立してしまうことを部分関数従属という。部分関数従属をなくしていけばよい。

第三正規形。第二正規形かつ、Rの全ての非キー属性が、Rのいかなる候補キーにも推移的に関数従属しないこと。推移的関数従属性とは、関数従属性X→YかつY→ZのときX→Zが成り立つこと。推移的関数従属をなくしていくことになる。実質、全ての候補キーについて第二正規形と同じようなことを行えばよいということになる。

ボイス・コッド正規形。X→Yが自明な関数従属性であるかXがRのスーパーキーである、という条件を満たすこと。具体例を見せてくれたがよくわからんかった。

第10回

データベース言語。SQLについてくわしく。SQLはIBMが作ったSEQUELが原型。その後ベンダーごとに拡張が進み、ANSIやISOが標準化した。

リレーションとは属性の構成、ドメインの直積の部分集合のこと。リレーショナル代数とは、データ操作演算体系のこと。リレーションとSQLはデータの扱い方が少し違う。リレーションでは重複タプルは許されないが、SQLでは許される。また、リレーションでは順序が意味を持たないが、SQLでは順序があり、行や列の順序も支持できる。

SQLはDDL(データ定義)、DML(データ操作)、DCL(データ制御)で構成される。

DDLは具体的にはCREATE、ALTER、DROPの3つ。

表の種類。実表(実体)、ビュー(論理的な表??)、導入表(一時的な表)。

CREATE文。CREATE TABLE 表名+(列・データ・列制約)*n+表制約。表制約では、PRIMARY KEYで主キーを設定したり、CHECKで値の範囲を制限したりできる。

ALTERは属性の変更・追加。DROPは表の削除。

DML。選択はSELECT *(よく使うので略)。射影はSELECT文で列名指定。重複除去はSELECT DISTINCT。和集合はUNION ALL、差集合はEXCEPT ALL、共通集合はINTERSECT ALLを使う。ALLを省略すると重複除去も兼ねる。副問い合わせは()の中にSELECT文を入れる。

第11回

DBMS1回目。データベースには大量のデータが蓄積されていることが前提。高速処理、データの整合性の保障、同時処理が必要になる。他にも障害復旧、セキュリティ、操作手段(言語の提供)も必要。

構成。問い合わせ処理部、トランザクション管理部、記憶管理部からなる。

前回のデータ定義、操作、制御はそれぞれメタデータ管理、問い合わせ処理、トランザクション処理として実装される。

メタデータ管理。メタデータとはデータのデータのことで、テーブルに関するデータや、列、索引、型構造のデータのこと。データ辞書に格納される。

データベースの格納方式。揮発性では困るので磁気ディスクに格納する。レコード、ファイルといった単位を使う。テーブルとファイルは1対1対応する。レコードは行、フィールドは列。論理的配置と物理的配置は違うことに注意。

代表的な格納方法に、ヒープ、索引編成、B+木、ハッシュがある。

ヒープ。効率的だが、順序はキー値の順にはならない。順次探索しかできないのでノロい。

索引検索。インデックスのことかな。主索引(主キーかな)と二次索引(主キー以外のフィールド)がある。二次索引を用いると検索が効率化できるが、レコードの格納位置が変わると、索引中の格納位置も変えないといけない。なので、ディレクトリ参照(どこにレコードがあるかの情報)をするようにする、ここでいうディレクトリはwindowsのファイルシステムとは違うようだ。レコード挿入は索引修正が必要になる。レコードをずらさなくていい工夫が必要。—バーフロー領域を使ったりしてなんとかする(よくわからん)。

索引を階層化して検索時間を減らすことを考える、これがB+木。木の高さをなるべく等しくするような木のこと。葉以外の節が索引(どうやってるの?)。B+木自体が探索木になる。キーの値を二分探索していくといずれ辿り着く。レコードの挿入は木構造の再編成をすることで実現する。

ハッシュ。ハッシュ関数を用いてキー値からレコードの格納位置を算出すること。高速。でも範囲指定とか全レコード読み出しが無理。

問い合わせ処理。コストをできるだけ小さくすることを最適化という。処理の流れは構文の判定→最適化と実行プランの生成→実行プログラムの生成→実行。

多様な実行プランの存在要因。代数演算処理には組み合わせに任意性がある(等価なものがいっぱいある)こと、代数演算処理がデータへのアクセス処理の仕方に影響を受けることなど。例えば選択と射影をする方法には、選択→射影でも、射影→選択の順でもいい。

テーブルの結合方法。まず入れ子ループ法。結合先から1行読んで、結合元の各行を読んで言って結合。これだと結合先(外部)に行数が少ない方を持ってくる方が速い。

マージ結合法。各テーブルを結合フィールドでソート後、フィールド値の小さい順に結合する。ソートにコストがかかるが、その後は速い。

ハッシュ結合法。ハッシュ表に両方とも行を読み込んで、同じハッシュ値になるものを結合。ハッシュ表が主記憶上に保持できれば高速処理が可能。

第12回

DBMSの第2回。トランザクション管理について。トランザクションは処理の単位のこと。例えば5000円の振り込み処理を考えると、出金と入金が両方同時に行われないといけない。片方では困る。

ACID特性。原子性、一貫性、隔離性、持続性。これが順守されていないといけない。原子性→全部完了 or 全く実行されないこと。一貫性→DBに矛盾が生じないこと。隔離性→各トランザクションは独立して実行できる。持続性→トランザクションが終了すれば、障害発生しても結果が消えないこと。

トランザクションが終わったら、コミット(終了)かアボート(障害発生、中止)のどっちかになる。

同時実行制御。口座の話だと、送金処理中に他人の入金があった場合どうなるか。制御がないと他人の入金が上書きされてなかったことになってしまうかもしれない。複数のトランザクションが同時実行されるとき、矛盾が起きないようにしないといけない。代表的なのはロック方式。排他制御する。1つのトランザクションだけがロックをかけられる。後のトランザクションはアンロックされるまで待つ。まあこれもプログラミングの実務でよくやるよね。

直列化可能性。複数のトランザクションを並列処理した結果、逐次処理と等価になること。これがうまくいけば並列処理可能になる。2相ロッキングプロトコルでこれを保障できる。複数のトランザクションで読み書きの対象データをロックし、処理終了までアンロックしないこと。ロックを解除したら再度ロックできないようにする。これでいいらしい(数学的に証明できるのかな?)。ただ、複数の資源を同時にロックせざるを得ないので、効率がちょっと悪い。

共有ロックと占有ロック。共有ロックは読み込み用。参照を許可する。占有ロックは書き込みを行うのでアクセスも禁止する。これを使い分けて高速化を図る。

デッドロック。複数のトランザクションが互いに他のアンロックを待っている状態になること。T1がxをロック、T2がyをロック、T1がyを待ち、T2がxを待つとデッドロックが発生する。こういうときはDBMSが強制的アボートをして解消する。

隔離性レベル。未コミット読取り→コミット済み読取り→再読み込み可能読取り→直列化可能、の順でレベルが高い。

障害と回復。トランザクション障害。トランザクションの途中で異常が発生した場合のこと。システム障害。全トランザクションが停止すること。メディア障害。ディスククラッシュのこと。一番障害が大きい。

ロールバックとロールフォワード。ロールバックが実行開始前、ロールフォワードは実行完了にすること。アボートしたらロールバック、コミットしたら障害発生してもロールフォワードする。

メディア障害をに備えるためには、フルバックアップしたり差分バックアップしたりする。差分バックアップはトランザクションだけ記録して実装してる。

ログ。データベースの更新を記録したもので、更新前と更新後の状態とか、トランザクションそのものを記録する。ロールバックもロールフォワードもログを見て実行する。

ログを取るタイミングの問題。WALプロトコル。ログ先行書き出し(Write Ahead Log)のこと。データベース更新前に全部ログを記録してしまうこと。そうしないとロールフォワードが不可能になる。更新後ログも先に書いてしまう。

チェックポイント。一定間隔でバッファのデータをディスクに書き込むこと。ログはでかいので復旧には時間がかかる。チェックポイントがあれば、これ以降のログを用いて回復処理が行えるから、処理時間短縮になる。

第13回

データベースの発展技術1。データストアについて。

データベースの機能から。本質的な機能として、データの論理形式・格納と操作。選択的な機能は永続性・整合性・高速応答性・堅牢性。

データ操作の4要件、CRUD。Create, Read, Update, Delete。

キャッシュデータベース。応答性の優れたキャッシュデータベースを真ん中に挟んで高速化を図ること。これうちの実務でもやってるぞ!不整合が起きないようにする工夫が必要になる。

データストアとは何か。データベースの機能、性能を特徴づけるデータ集合の入れ物。データ取扱い単位の概念を含む。実装の詳細は含まない。論理的モデルと物理的モデルの中間あたりに位置する。

データストアの5分類。キーバリュー型、列指向型、リレーショナルデータベース、ドキュメント指向、グラフデータベース。

キーバリュー型。キーとバリューの組(タプル)のこと。大規模性、高速性が特徴で、演算機能はない。

列指向型。タプルを識別するキーと、属性:値の多数の組。タプルごとに異なる属性を持てる。キーバリュー型のもう一段階複雑なやつって感じ。リレーショナルデータベースと比べると、列単位の読み書きや列の追加が簡単なことが特徴。逆に、リレーショナルデータベースは行指向といえる。

ドキュメント型。XMLデータベースとか。柔軟なデータ形式が特徴で、入れ子構造も行ける。集計は無理。

グラフデータベース。次回に回す。

社会での様々なデータベース。IoTのことを聞くため、ソラコムのCTO安川さんにインタビュー。今私たちは時計とかカメラとかいろんなものからDBにデータを上げてる。で、こういうデータは消えない、消さない。データベースは大規模化してる。web、IoT時代だと24/365で稼働、高速応答が求められる。リレーショナルデータベースは何でも使えるのが利点。ただ、いつも使いやすいわけではない。アプリケーションによっては特定の機能に絞った方がよいこともある。そこでデータストアの選択が大事になる。

キーバリューストアを使う場合。ショッピングストアとか、可用性、高速性、分散処理が大事な分野で有利。性能の向上も簡単。線形でできる。一方でSQLだと大掛かりになってしまう、重い。スケーラビリティが厳しい。柔軟なクエリ、トランザクションが必要ならRDBを使えばいい。

オンライントランザクション型では、ランダムアクセス性能に強いSSDの方が有利らしい(!)。ハードディスクはランダムアクセスは苦手。なのでサーバーでもSSDが好まれるようになってきている。連続したデータならハードディスクでも強いので、今でも使われることがある。

Update、Deleteが実際ないようなデータベースもある。再配置とか面倒なんでやめて、リンクだけなくしてしまう。そうするとかなりコストを省くことができる。メッセージを削除してもデータベース中には残っているという話。デリートマークだけつけてるってことかな。

列指向データベースの使いどころ。RDBはオンライントランザクション型に強い。トランザクションが行と同じだから。一方でデータの分析には列指向が強い。ユーザープロファイルからデータを取りだして解析したいって時、RDBだと全部の表を読まないといけないけど、列指向だと速い。

第14回

グラフデータベースについて。グラフの基本についてはほかの講座でやったので略。

プロパティグラフ。ノードには名前がついているほかに、プロパティも持っている。エッジにも名前やプロパティがついている。

グラフデータベースの構成。リレーショナルモデルなら、関係性をデータベースに保存することができる。JOINすればいろんな関係性がわかるが面倒。一方でグラフモデルなら、エッジをたどることで簡単に関係性が分かる。ネイティブ処理エンジンというのを使って、高速にエッジをたどる機能がある。

Cypherという言語を使う。SQLに似ている。

CREATE (alice{name: ‘Alice’}), (bob{name:{‘Bob’})

みたいにノードを生成できる。エッジを生成するときは

CREATE (alice{name: ‘Alice’}) – [:FRIEND] -> (bob{name:{‘Bob’}), (alice) <- [:FRIEND] – (bob)

みたいにやればよい。直感的だ。

RDBとの違い。例えば人テーブルに年齢という列を加える。RDBだと非常にコストがかかる。グラフデータベースなら、プロパティの追加で済む。列指向型と同じで簡単。また、1対多の関係も簡単。エッジを追加するだけ。

エッジの検索。

MATCH(p) WHERE p.name = ‘Alice’ RETURN p

で、Aliceというノードを検索できる。

MATCH文とCREATE文を組み合わせることもできる。MATCHした結果を使って、そこにCREATEでノードを追加できる。

MATCH (p{name:’Alice’}) – [:FRIEND*2] -> (friend_of_friend) RETURN DISTINCT friend_of_friend.name
にすれば、Aliceの友達の友達の結果を検索できる。グラフの特性を大いに使った問い合わせだ。これをRDBでやると、JOINを何度も使うことになり、非常にコストがかかってしまう。隣接性を使う場合はグラフの方がとても有利。友達の友達の友達の・・・ってやるときは数字を増やすだけでいいしね。

第15回

分散データベース。

検索高速応答性を考える。インデックスはある程度範囲を絞ったうえで線形探索するから、場合によっては遅い。B+木の計算量はO(logN)で速いし範囲検索も可能。ハッシュはO(1)でめちゃはやいが範囲検索は無理。

ストアドプロシージャ。データベース側に処理内容を保存しておいて、例えばSELECTとログのINSERTを同時に行うようにする。バッチ処理をDB側においておくようなもんかな。アプリケーション側との通信の削減と、処理の漏れが無くなる。

Map Reduce。入力した文章群をMap Stepでクラスターごとの文章にノード単位で分割、さらにReduce StepでShuffleしてwordに分割。出力でwordごとの回数の合計を得る。大量のデータを処理できるのが特徴で、分散処理もできる。ストアドプロシージャの分散DB版。

スケールアップとスケールアウト。スケールアップは高性能なハードウェアを使えばいい。が、金がかかる。スケールアウトでは、処理を分散させて全体としての性能を向上させること。金がかからない。協調動作が難しいのが欠点。

スケールアウトの手法。まずレプリケーション。データベースの複製を用意して、同期する。負荷は減るが、データの変更が大変。

シャーディング。データの一部分をドメインみたいな感じで分けて管理。北海道、青森県、岩手県で分けるとか。同期がいらない。ただ、ボトルネックが一番処理の集中するDBになる。東京ってDBを作ったらそいつが辛い処理になってしまうね。

分散データベース。まずCAP定理。C整合性、A可用性、P分断耐性。整合性はどのノードからも同一の値が読み出せること。可用性は、アクセスできればリクエストに応答できること。分断耐性は、システムが分断されても機能を継続できること。故障があってもこれを満たしてほしいが、全部は無理。2つはいけるが1つは諦めなければいけない。これがCAP定理。

CAだけ生きていて分断されてるときは、互いに通信をシャットアウトすればよい。CPだけ生きているときは、一つの断片だけ機能させる。すると整合性はなんとかなる。APだけのシステムにするなら、全断片を機能させるが、不整合は生じる。いずれかの組み合わせを選択しないといけない。だいたいはCPかAPを選択する。

BASE。Basically Avaliable Soft-state Eventual consistency。基本的に可用、データ状態は厳密でない、結果的に整合性をもつ。例えば分散DBで、住所データベースを実現するとして、新住所を更新したとする。これを他のDBに通知して、いずれは全ノードで新住所に更新されればいいやという考え方。一定時間内は不整合が発生する。障害があれば不整合の時間は長い。

決済への応用。決済は素早く行わなければいけないので、中央データベースに毎回アクセスしていられない。そこで少額の決済処理を店舗側データベースでも行えるようにする。で、処理は順次中央データベースに送られていくようなモデルにすれば、正確性と迅速性を確保する。一定金額以上は中央にアクセスしないといけないようにすればよい。

気象情報などのセンサネットワークはそもそも分散してデータが発生するし、逐次的に発生する。これも分散処理に向いている。

“放送大学全科目感想 017 データベース(’17)” への1件の返信

コメントを残す

メールアドレスが公開されることはありません。