tags: leetcode 問題 Explore Problems アイデア 配列内の0を全て末尾の方に移せという問題です． 末尾の要素と交換をすれば良いですね． 大事なのは与えられた配列を操作することは許されていますが，新たにメモリ内に配列を作ってコピーしてはいけないとい…

tags: leetcode 30-Day LeetCoding Challengeが始まったので問題を解いていきます 問題 Problems アイデア 整数列が与えられるので，その部分数列の和が最大と成る配列を探せという問題です． 解法 Kadane's Algorithm 配列の全ての要素を走査します． 今ま…

tags: leetcode 問題 Explore Problems アイデア inorderのBSTとpostorderのBSTが与えられた時に，BSTを構築しろという問題です． 木の探索順序 木を探索する際の順序として以下の図ように Inorder(左→根→右) Preorder(根→左→右) Postorder(左→右→根) があり…

tags: leetcode 問題 Explore Problems 実際のコーディングテストでPython3を使うことが多いことから，Python3で書くことに… 発言に一貫性がないという点で自分は一貫性がある？ アイデア BSTに新たな値を挿入しろという問題です． その値はBST内に存在しな…

tags: 進捗報告 進捗リンク 1-3 数学関連 院試の前に留年して勉強する気がなくなったので 物理関連 留年して研究室に配属されずやる気が失せた CS 留年してやる気() 過去問は見たけど解いていない．暇だし解く． コンパイラは多少進んだ．DBMSは授業見終わっ…

tags: CMU DB Slides Video 授業 決定支援システムとは管理，処理のために働くアプリケーション． STAR vs SNOWFLAKE SCHEMA normalization 少ないストレージ空間を専有する． 非正規化されたデータモデルは整合性と一貫性の違反を負う可能性がある． query …

tags: CMU DB Slides Video 授業 OLTP vs OLAP On-line Transaction Processing(OLTP) 短命な読み書きtxn 小さなfootprint(稼働時に占有，消費する資源) 繰り返し処理 On-line Analytical Processing(OLAP) 長寿な読み込み専用クエリ 複雑な結合 探索的なク…

tags: CMU DB Slides Notes Video Homework 授業 distributed DBMSs parallel DB ノードは物理的にそれぞれ近い ノードは高速なLANで繋がれている ノード間の通信費用は小さいと仮定して良い distributed DB ノードは物理的にそれぞれ遠い ノードは公共のネ…

tags: CMU DB Slides Notes Video 授業 ARIES Algorithms for Recovery and Isolation Exploiting Semanticsの略称．1990年台初頭にIBMの研究所で開発された．全てのシステムがARIESを原著論文通りに定義はしていないが，十分似ている． ARIES recovery prot…

tags: CMU DB Slides Notes Video 授業 crash recovery DBの一貫性，txnの原子性，失敗に関わらない永続性を保証する．DBMSと失敗を分類する必要がある． recovery algorithmは2つの部分から成る 通常のtxtの間の，通常のDBMSが失敗から回復できるように保証…

tags: CMU DB Slides Notes Video 授業 multi-version concurrency control multi-version concurrency control(MVCC)とは単なる並行制御プロトコルよりも大きな概念．DBMSのデザインと実装の全ての側面を含む． DBMSはDB内の単一の論理オブジェクトの複数の…

tags: CMU DB Slides Notes Video 授業 timestamp ordering concurrency control timestamp ordering(t/o)とは楽観的な並行制御プロトコルのクラス．DBMSはトランザクションの衝突が稀だと仮定する． timestampを利用して，直列性を決定する． 各トランザク…

tags: CMU DB Slides Notes Video 授業 transaction locks DBMSは一元化されたlock managerを持っている。 shared lock 同じオブジェクトを同時に見る複数のトランザクションを許す 同時に1つのトランザクションだけが排他的なlockを持つことが可能 exclusiv…

tags: CMU DB Slides Notes Video 授業 今回はconcurrency(並行)についてやります．同時に1つのタスクしか出来ない中，複数のタスクを処理することです． transactions 1つ以上の一連の処理を実行することを言う． 基本的な変化の単位 これ以上分けられない …

tags: CMU DB Slides Notes Video 授業 今回は前回やったようにqueryの最適化についてやります． ここではcost-based searchを扱います． plan cost estimation queryが必要とする時間はいくらか CPU: あまり影響せず，予想するのは難しい Disk: ブロック転…

tags: CMU DB Slides Notes Video コロナで寮にずっと篭っているおかげで寮の人と過ごす時間が増えた気がします(？) 授業 SQLは宣言的．最適化はDBMSの仕事． query optimization heuristics 非効率な部分を除き，クエリを書き換える cost-based search 計画…