Dark

CMU Database Systems (Fall 2019) 受講録

カーネギーメロン大学 Database Group が公開している講座 "Database Systems" の勉強録です。

[Prof. Andy Pavlo - Carnegie Mellon University] [Homepage]

  1. Course introduction & Relational Data Model [YouTube] [Slide] [Note]
  2. Advanced SQL [YouTube] [Slide] [Note]
  3. Database Storage I [YouTube] [Slide] [Note]
  4. Database Storage II [YouTube] [Slide] [Note]
  5. Buffer Pools + Memory Management [YouTube] [Slide] [Note]
  6. Hash Tables [YouTube] [Slide] [Note]
  7. Tree Indexes I [YouTube] [Slide] [Note]
  8. Tree Indexes II [YouTube] [Slide] [Note]
  9. Multi-Threaded Index Concurrency Control [YouTube] [Slide] [Note]

Overview

This course is on the design and implementation
of disk-oriented database management systems.

Course Outline

  • Relational Databases
  • Storage
  • Execution: (クエリの)実行
  • Concurrency Control: 並行性制御
  • Recovery
  • Distributed Databases: 分散データベース
  • Potpourri: 雑録

Database

Database: 現実世界のある側面をモデル化した、相互に関連したデータのコレクション。ほとんどのアプリケーションのコアだぜ。

もしただのファイル (CSV)をDBにしたら

flat_file_strawman_example

(source: https://15445.courses.cs.cmu.edu/fall2019/slides/01-introduction.pdf)

「アーティスト」、「アルバム」を考える。

  • 読み書きのたびにファイルをパースしないといけない
  • データの構造を知らないといけない

例えば、データがこんな CSV だったら、'Ice Cube'のレコードにアクセスするためにこんなコードを書く。

"Wu Tang Clan",1992,"USA"
"Notorious BIG",1992,"USA"
"Ice Cube",1989,"USA"
for line in file:
    record = parse(line)
    if 'Ice Cube' == record[0]:
        print(int(record[1]))

(筆者コメント: これはいけてない。'Ice Cube'record[0] の列にあることを知らないといけない。record[1] も然り。物理層の情報 (データの構造。ファイルのどこにあるか)と論理層の情報 (例えば項目名)の両方を気にしないといけない。SQL なら後者を知ってるだけでいい。この話は後ほど出てくる。)

Data Integrity (整合性)

  • アルバムのエントリーごとにアーティストが同じであることを保証するにはどうする?
  • 誰かがアルバムの年号を無効な文字列で上書きしたらどうする?
  • 1枚のアルバムに複数のアーティストがいたらどうやって保存する?

Implementation

  • どうやって特定のレコードを見つける?
  • 同じデータベースを使用する新しいアプリケーションを作成したいとしたらどうする?
  • 2つのスレッドが同時に同じファイルに書き込もうとするとどうなる?

Durability (耐久性)

  • プログラムがレコードを更新している間にマシンがクラッシュしたらどうなる?
  • 高可用性のためにデータベースを複数のマシンに複製したい場合はどうすればいい?

Database Management System

DBMS: アプリケーションがデータベースに情報を保存たり分析したりできるようにするソフトウェア。汎用DBMSは、データベースの定義、作成、参照、更新、管理ができるように設計されてる。

初期のDBMS

  • 使うのも保守するのも大変だった
  • 論理層と物理層が密結合

Relational Model

(筆者コメント: 以下では「列」、「属性」を同じ意味で、「タプル」、「行」を同じ意味で使っている。)

Data Model: データベース内のデータを記述するための概念の集まり。 (筆者コメント: 雑に言えばデータを保存する形式だと理解した。RDB, Graph, NoSQL などいろいろある)

Schema: 与えられたデータモデルにおいて、特定のデータの集まりを記述したもの。 (筆者コメント: DB の構造だと理解している。構造とは、どんなテーブルがあって、それぞれがどの型のなんという列をもって、どんな関連をもつかなどのこと。)

tuple: 非負整数個の列の値の集合。行のこと。

relation (関係): 「各属性の定義域 (ドメイン)から取り出された対の値で作りうる組み合わせに、いくつか条件付けを行った結果として得られる部分集合」 [参考文献1]

primary keys (主キー): タプルを1つに特定できる値というか列。

foreign keys (外部キー): ある属性が別の関連テーブルのタプルにマッピングされなければならないことを指定する値。

Relational Algebra (リレーショナル代数)

リレーショナル代数 (関係代数): 「関係データベースの関係モデル (リレーショナルモデル)において、集合論と一階述語論理に基づいて、関係 (リレーション、表、テーブル)として表現されたデータを扱う、コンピュータ科学における代数的な演算の体系である。」 [参考文献2]

Select σ\sigma
SELECT句。行を表示する。

SELECT * FROM artists

Projection π\pi
WHERE句。特定の行だけに絞り込む。

SELECT * FROM artists WHERE name like 'A%'

Union \cup
和集合をとる。くっつける対象どうしは同じ列名にしないといけないので注意。

SELECT artist_id AS id FROM artists
UNION
SELECT album_id AS id FROM albums
;

Intersection \cap
積集合をとる。

SELECT artist_id AS id FROM artists
INTERSECT
SELECT album_id AS id FROM albums
;

Difference -
差集合をとる。

SELECT artist_id AS id FROM artists
EXCEPT
SELECT album_id AS id FROM albums
;

Product ×\times
直積、デカルト積というやつ。あるテーブルの全部の行に、他のテーブルの全部の行が結合される。

SELECT * FROM R CROSS JOIN S;
-- or
SELECT * FROM R, S;

Join \bowtie
複数のテーブルを結合する。内部結合、外部結合がある。
自然結合は、全てのテーブルにある同じ名前の列が使われるので、結合条件を書く必要がないらしい。


  • Rename
  • Assignment
  • Duplicate Elimination
  • Aggregation
  • Sorting
  • Division

最初のコードを SQL で書くとこうなるね。

for line in file:
    record = parse(line)
    if 'Ice Cube' == record[0]:
        print(int(record[1]))
SELECT year FROM artists WHERE name = 'Ice Cube';

Conclusion

  • データベースはどこにでもあるよ
  • リレーショナルデータベース上のクエリはリレーショナル代数で定義されてる
  • クエリの最適化+実行の話をするときにまたリレーショナル代数を見ることになるよ

(疑問点)

参考文献

  1. SQLアンチパターン. Bill Karwin, 和田 卓人, 和田 省二, 児島 修. pp.289-290
  2. 関係代数 (関係モデル) - Wikipedia
  3. Difference between DBMS and RDBMS - javatpoint
Share:
記事一覧
Dark