「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。
目次 †
概要 †
データベース = RDBMS
詳細 †
3層スキーマ †
内部スキーマ †
- B+木インデックス構造
全てのレコードは葉ノードに格納され、
内部ノードにはキーのみが格納される。
概念スキーマ †
- 弱実体(weak entity)
ON DELETE CASCADEの子エンティティ
- 関数従属
# | 律 | 説明 |
1 | 反射律 | {X, Y} → X |
2 | 増加律 | X → Y なら {X, Z} → {Y, Z} |
3 | 推移律 | X → Y and Y → Z なら X → Z |
4 | 合併律 | X → Y and X → Z なら X → {Y, Z} |
5 | 分解律 | X → {Y, Z} なら X → Y and X → Z |
- 候補キー
行を一意に特定できる属性 or 冗長性の無い属性の組
- テクニック的な
- PKに依存リレーションシップを足さないと重複登録できないみたいな。
外部スキーマ †
- ビューなど。
- サブスキーマともいう。
- n列の射影の組合せは、2^n
モデリング †
関連エンティティ †
関数従属・候補キー †
- 問題
- {A, B} → C
- {B, C} → D
- D → {A, E}
- 分析
推移関数従属を除いてルートを辿って候補キーを見つける。
- 関数従属がループしていない時は難しくない。
- 関数従属がループしている時は候補が増える感じ。
- 起点にできる属性 or 冗長性の無い属性の組が候補キーになる。
- 組み合わせの選定が難しい感ある。↓の例では、{B, D} → C
- 関数従属のXXX律を使用して候補キーを見つける
方法もあるようだが解法に規則性が無いので難しい。
正規形 †
- 非正規形
- 繰り返し項目を持つ
- 導出項目(算出できる値)を持つ
- 第1正規形
- 繰り返し項目を持たない
- 導出項目(算出できる値)を持たない
- 第2正規形
- 第1正規形を満たしている
- 主キーに対してすべての非キー属性が完全関数従属(≒部分関数従属しない状態)
- 第3正規形
- 第2正規形を満たしている
- どの候補キーに対しても非キー属性の推移的関数従属性が排除されている。
DDL/DML/DCL †
テーブル †
DDL
- CREATE TABLE
≒ 関数従属・候補キーの問題
(なので、uniqueだから主キーに含めタロとか言う判断はダメ)
インデックス †
DDL
- n段のB木インデックスの最大レコード数
- n = 2段、K=1で計算すると、
- 1段目 : 2k = 2
- 2段目 : 2k * (2k+1) = 6
- 合計 : 2 + 6 = 8
- 適合する式
以下は、等比数列の和の公式に
初項 a=2k, 公比 r=2k+1 項数 n を代入したもの。
= (( 2k + 1 ) ^ n) - 1
- XレコードのB+木インデックスのアクセス回数
- 前提
- 次数(辺の数) k
- 深さ(ルートから末端に至る段数) h
- 最大レコード数は、k^h
- アクセス回数は、h = log kX
制約と操作 †
DDL/DML
- 制約で禁止され得る操作
- 外部参照
- マスタ側に無いデータをトランザクション側に挿入
- トランザクション側にあるデータをマスタ側から削除
論理演算 †
DML
- OR
false < unknown < true
- AND
true < unknown < false
関係演算 †
DML
- 射影(projection)
SELECT DISTINCTでの列指定
- 選択(selection)
SELECTのWHERE
- 直積(CROSS JOIN)+選択
SELECTのFROMに複数のテーブルを指定し、WHEREに結合条件を指定。
- 内部結合(INNER JOIN)
SELECTのINNER JOINに、結合テーブル、ONに結合条件を指定。
- 外部結合(OUTER JOIN)
SELECTのOUTER JOINに、結合テーブル、ONに結合条件を指定。
(結合が出来なかった列も残る。LEFTやRIGHTで残す列を選択可能。
LEFT OUTER JOINが一般的で、主問い合わせのテーブルの列が残る。)
- 商(division)
割られる側の関係(表)の中から割る側の値の組み合わせを含む組(行)を抽出し、
重複する組(行)と割る側に含まれる属性を取り除いたものを求める。
RDBMSに商を実行する句は無いので、他の方法で代替して実行するらしい。
集合演算 †
DML
集合演算は直積を除いて、型適合≒和両立(union-compatibility)が必要。
- 和(集合)
集合のいずれか少なくとも一つに含まれているような要素を全て集める
ことにより得られる集合(を求める演算でRDBMSではUNION、UNION ALLが使える)。
- 差(集合)
ある集合の中から別の集合に属する要素を取り去って
得られる集合(を求める演算でRDBMSではEXCEPT、MINUSが使える)
- 積(集合)
交叉とも言う共通部分(を求める演算でRDBMSではINTERSECTが使える)。
- 直積(集合)
- (全ペアみたいな)全組合せ(を求める演算でRDBMSではCROSS JOINが使える)。
- 積集合と言うとコチラを意味するケースが多いので前述の積集合は共通部分と呼ぶケースが多いらしい。
※ 共通部分 (R∩S) は、差 (R-(R-S)) で表現できるという問題が出たりする。
副問合せ †
DML
- 副問合せ
- 副問合せを行った後に、主問い合わせで副問合せ結果を条件に使う。
- WHERE IN (副問い合わせ)
- 相関副問合せ
- 主問合せを行った後に、副問い合わせで主問合せ結果を条件に使う。
- WHERE EXISTS(またはNOT EXISTS) (副問い合わせ)
※ 副問合せは相関副問合せで書き直せる。これを使った問題が出たりする。
集計関数 †
DML
- GROUP BY で
- 集計対象のデータ列を指定する。または表示に含めたいデータ列を指定する。
- 表示に含めたいデータ列が一意でないと、グループが変わり、意図した結果にならないことがある。
- HAVING で
集計結果レコードが持っているデータ値をチェックして、集計結果からレコードを省く。
GRANT †
DCL
- GRANT 権限 ON オブジェクト TO ユーザ(グループ)
- WITH GRANT OPTION
付与権を付与する。
ネスト化ループ結合(IPA的には、入れ子フープ法)の計算量を問う問題が出る。
- nがタプル(タプルは列)の場合、O(n^2)となる。
ACID †
ACIDとは、信頼性のあるトランザクションシステムの持つべき性質
- 原子性(atomicity)
- 一貫性(consistency)
- 独立性(isolation)
- 永続性(durability)
トランザクション †
- コンピュータ内で実行される、
分けることのできない一連の情報処理の一単位
- 同時実行における3つの問題
- ロックの互換性
- デッドロック
- , etc.
機能 †
ストアド †
ネットワーク、プロセス間通信を行わないので高速。
分散DB †
- データモデル透過性
RDBMSの違いを意識させない。
- 障害透過性
障害を意識させない≒冗長化技術と思われる。
- 2フェーズ・コミット
トランザクションのコミット処理を 2 段階のフェーズにわける。
- 第 1 フェーズ:各DBに対してコミットできる状態であるかどうかを確認する。
- 第 2 フェーズ:各DBに対してコミットかロールバックかの決定を行う。
運用 †
トランザクション・ログ †
- 障害発生時でもACID特性を保障するための操作履歴
- ログ先行書き込み(WAL : Write Ahead Log)プロトコル
- トランザクションがログを安定記憶(ディスク)に書き出すタイミングについての取り決め
- ファイルシステムの分野では、ログ先行書き込みのことをジャーナリングと呼ぶ。
- 復旧モデル
- 完全バックアップ
- 差分バックアップ
- 増分バックアップ≒トランザクション ログ バックアップ
- トランザクション ログ
- チェック ポイント
- ロールバック・ロールフォワード
冗長化・複製 †
- RDBMSによって異なるが、
IPA定義では以下の様になっている。
- ミラーリング
レプリケーション的技術を併用した可用性・性能向上技術
- レプリケーション
読取専用のスレーブを作成する性能向上技術。
(ミラーリングより遅延が大きい的な説明)
その他(応用) †
検索システムの評価 †
- 再現率 recall
- = 検索された適合データ / 蓄積されている適合データ
- 正解データが、どの程度が検索結果セットにヒットするかを示す。
- 適合率 precision(精度)
- = 検索された適合データ / 検索により表示されたデータ
- 検索結果セット中にどの程度、正解データが含まれるかを示す。
- F値 = (2×適合率×再現率)/(適合率+再現率)
- 一般に、
- 再現率の高いシステムは適合率が低く(ガバガバ過ぎ)
- その逆に、適合率が高いシステムは再現率が低い(絞り過ぎ)
傾向にある。
データ分析系 †