Database Management Systemsの18章。 マインドマップから再構成したまとめ 何？ History of actions 。 ログの tail はオンメモりにあり定期的に disk へ。 Log Record Unique ID を振る。LSN（Log Sequence Number） prevLSN, transID, type 書かれるタイ…

Database Management Systemsの18章。 マインドマップから再構成したまとめ revercory manager は以下を維持 Atomicity コミットしないもの Undo Durability ARIES リカバリアルゴリズム 動き クラッシュ 起動 リカバリマネージャ起動 Analysis buffer pool …

Database Management Systemsの17章。 マインドマップから再構成したまとめ 背景 Lock によるコントロールは悲観的 競合が少ないシステムでも Lock コストを払う必要がある 楽観的なコントロール 前提：多くのトランザクションは conflict なし Read: データ…

Database Management Systemsの16章。 マインドマップから再構成したまとめ Concurrency Control in B+ Tree naive な実装ではページ単位でロックを行う root に近い場所で競合が発生する ではどうする？ Search 基本は検索経路のページに Shared Lock をか…

Database Management Systemsの16章。 マインドマップから再構成したまとめ デッドロックの検出 2つの方法 タイムアウト waits-for graph を維持 サイクルになったらデッドロック ロックの少ないものを abort デッドロックを防ぐ 2 つの方法 Conservative 2P…

Database Management Systemsの16章。 マインドマップから再構成したまとめ Lock の管理は Lock Manager が行う lock table を保持する Lock table key : Lock する Object の ID value : lock entry Lock entry そのロックを獲得しているトランザクション数…

Database Management Systemsの16章。 Serializablity と Recoverability が重要である事は理解できる。 また conflict equivalent conflict serializable strict でない 2PL の定義自体は理解できる。 それぞれがどう絡みあい、どのような意義があるのかが…

Database Management Systemsの16章。 マインドマップから再構成したまとめ 背景 Serializable を実現したい Recoverable を実現したい Strict 2PL とは プロトコル 1. read/modify するなら shared/execlsive lock をリクエスト 2. トランザクション完了時…

Database Management Systemsの16章。 マインドマップから再構成したまとめ スケジュールとは？ list of actions（DBMS視点） read write commit abort concurrent interleave の動機 パフォーマンス I/O 待ちなどのスループット向上 長いトランザクションに…

Database Management Systemsの16章。 やっと Transaction に突入。 マインドマップから再構成したまとめ DB は ACID を維持する Atomic トランザクションは全てのアクションが実行される or 全く実行されないのどちらかしかありえない 中途半端に実行される…

Database Management Systemsの15章。 マインドマップから再構成したまとめ SQL -> ALGEBRA 流れ：SQL => 分解 => Blocks => Algebra Block とは： 1つの Select, 1つの from 。 Block -> Algebra select => projection from => cross product where => sele…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Set Union と Difference 方法 2つ Sort & Merge Partitioning (h & h2) Aggregate AVG, MIN, MAX など。 group by が付加する事も。 Basic な方法：Scan + 必要な情報を保持 Group…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Nested Loop Join simple, but slow I/O 多すぎる Block Nested Loop Join 前提：B バッファページ利用可能 R を B に読み込み、S の tuple と比較 R を読み込むのではなく B にメ…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Projection の手順 不要 attribute を削除 重複 tuple の削除 Projection based on Sorting Scan して attribute 削除 tuple を Sort sort result を scan して重複を削除 External…

Database Management Systemsの14章。 マインドマップから再構成したまとめ 簡単な Selection reserves (100件/page, 1000 pages) select * from reserves where rname = 'Joe' 何も考えない方法：1000 I/O No Index, Sorted Data: log2(1000) = 10 I/O prac…

Database Management Systemsの13章。 マインドマップから再構成したまとめ 背景 データ量 > メモリ メモリ上でソートできない I/O を最小にするアルゴリズムが必要 Two way merge sort 学習用の例。書き込みに 1 ページ、読み込み用に 2 ページの計 3 ペー…

Database Management Systemsの12章。 マインドマップから再構成したまとめ Selection clustered index あり => index を読むだけ un-clustered index あり => index + match した tuple の data を read index なし => full scan Projection 特徴1：出力を …

Database Management Systemsの12章。 マインドマップから再構成したまとめ Overview of Query Evaluation CNF(Conjunctive Normal Form) 複数の attr op value 形式の条件の結合したもの - Hash Index は CNF が attr = value で attr が key のときにマッ…

Database Management Systemsの11章。 マインドマップから再構成したまとめ Linear Hashing 特徴 Extendible Hashing と違い、ディレクトリを持たない（仮想的に考える事はできる） bucket は徐々に増加する（Extendible Hashing 一度に2倍になる） space 効…

Database Management Systemsの11章。 マインドマップから再構成したまとめ Hash-Based Indexing 特徴 search= が速い 1 I/O sarch range ができない 総合的には Tree-Based Indexing が上 Static Hashing ISAM と同様の考え方で Hash-Based 1 〜 N - 1 の p…

Database Management Systemsの10章。 マインドマップから再構成したまとめ Bulk loading 複数のデータから B+-Tree を 1 から構築するとき。 通常の insert アルゴリズムだと root から 1 データずつ insert。効率悪い ある程度まとめてデータを insert す…

Database Management Systems の 9章。 Heap file フォーマット。 ページ管理 Linked List レコードが可変長だと不利 Directory of pages レコード管理 fixed-length bitmap そのまま並べる variable-length slot direcotry で length, offset 管理 レコード…

Database Management Systems の 10章。ISAM(Indexed Sequential Access Method) 読み方は「あいさむ」 構造が「ほぼ」Static Page が物理的に整列されるように構築 データは Leaf Node と Overflow pages へ。 Overflow pages が大きくなると速度的に不利 T…

Database Management Systems の 9章。 DBMS の Buffer management と OS のそれは似ている。なぜ OS のものを利用しないの？ DBMS は次のページリクエストを予想したりアクセスパターンを知る事が出来る Page のプリフェッチが可能に。プリフェッチにより2…

Database Management Systems の 8章。 Heap Files, Clustered Files, Heap Files with Unclustered Hash Index などのデータ格納形式に関して scan search= searh range delete insert などのコスト概算。例えば Heap files with Unclustered Tree Index だ…

Database Management Systems の 4-7章。 SQLやApplication などは知っているので飛ばし読み。速読本や mumurik 氏にたたきこまれたのは、「何を飛ばし読みしているか」「飛ばし読みしている根拠は何か？」などを意識する事。

Database Management Systems の 2章と3章。 2章は速読の文脈におけるメインアイディアを意識してとばし読み。3章は知っている内容だったのでさらにとばし読み。

1章 Overview Of Database Systems 2-3章 Introduction to Database Design, The Relational ModelOverview Of Database Systems 4-7章 Comparison of File Orgnization Storing data disk and files Heap file format ISAM B+-Tree in Practice Hash-Based …