• 戻る（高度午前 - 技術要素）

技術要素 - データベース（高度：午前Ⅰ、午前Ⅱ）

• データベース ≒ RDBMS
• 一部、DWHや、NoSQL、ビッグデータ系も含まれる。

• ファイル構成、インデックスの編成など。

• B木インデックス構造

  • ルートノードは

    • 1≦i≦2k レコード
    • 2k+1 枝

  • ルートノード以外は 0≦i≦2k レコード

    • k≦i≦2k レコード
    • 2k+1 枝

• B+木インデックス構造
  全てのレコードは葉ノードに格納され、
  内部ノードにはキーのみが格納される。

• 対象世界をモデル化した、ER図

• 用語

  • 弱実体(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

• ビューの目的

  • 論理データ独立性の担保
  • データの保護

• 多対多の２つのエンティティ間に挿入されるエンティティ

• ２つのエンティティの主キーを足した主キーを持つ。

• 以下の様に関連に"*"が集まる感じになる。

  （Ａ）1 ---- *（関連）* ---- 1（Ｂ）
  

• 問題

  • {A, B} → C
  • {B, C} → D
  • D → {A, E}

• 分析
  推移関数従属を除いてルートを辿って候補キーを見つける。

  • 関数従属がループしていない時は難しくない。

  • 関数従属がループしている時は候補が増える感じ。

    • 起点にできる属性 or 冗長性の無い属性の組が候補キーになる。
    • 組み合わせの選定が難しい感ある。↓の例では、{B, D} → C
    • 関数従属のXXX律を使用して候補キーを見つける
      方法もあるようだが解法に規則性が無いので難しい。

  • 図示

    {{┌A┐, B} → C} → D
      └E┘←──────┘
    

• 非正規形

  • 繰り返し項目を持つ
  • 導出項目（算出できる値）を持つ

• 第1正規形

  • 繰り返し項目を持たない
  • 導出項目（算出できる値）を持たない

• 第2正規形

  • 第1正規形を満たしている
  • 主キーに対してすべての非キー属性が完全関数従属（≒部分関数従属しない状態）

• 第3正規形

  • 第2正規形を満たしている
  • どの候補キーに対しても非キー属性の推移的関数従属性が排除されている。

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

• 3値論理を採用している。

  • true
  • false
  • unknown

• 3値論理の論理演算

  • OR

    • false < unknown < true
    • trueが１つでもあったらtrue
    • unknownは、trueかfalseが存在しない時に考慮。

  • AND

    • true < unknown < false
    • ORの逆でfalseが１つでもあったらfalse
    • unknownは、trueかfalseが存在しない時に考慮。

  • NOT
    !unknown == unknown

DML

• 射影（projection）
  SELECT DISTINCT での列指定

• 選択（selection）
  SELECTのWHERE

• 結合（join）

  • 直積（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

• 関数

  • AVG
  • SUM
  • , etc.

• GROUP BY で

  • 集計対象のデータ列を指定する。または表示に含めたいデータ列を指定する。
  • 表示に含めたいデータ列が一意でないと、グループが変わり、意図した結果にならないことがある。

• HAVING で
  集計結果レコードが持っているデータ値をチェックして、集計結果からレコードを省く。

DCL

• GRANT 権限 ON オブジェクト TO ユーザ（グループ）

• WITH GRANT OPTION
  付与権を付与する。

ネスト化ループ結合（IPA的には、入れ子フープ法）の計算量を問う問題が出る。

• nがタプル（タプルは列）の場合、O(n^2)となる。

  • Oはオーダー法
  • 2重ループなので2乗

• 参考

  • 計算量オーダーについて - Qiita
    https://qiita.com/asksaito/items/59e0d48408f1eab081b5
  • SQL Server 結合方式の問題を監視する - マイクロソフト系技術情報 Wiki

ACIDとは、信頼性のあるトランザクションシステムの持つべき性質

• 原子性（atomicity）
• 一貫性（consistency）
• 独立性（isolation）
• 永続性（durability）

• コンピュータ内で実行される、
  分けることのできない一連の情報処理の一単位

• 2フェーズ・コミット

• DBMSのロック・分離戦略と同時実行制御

• 同時実行における３つの問題

• ロックの互換性

• デッドロック

• , etc.

ネットワーク、プロセス間通信を行わないので高速。

• 透過性
  利用者にXXXXを意識させない的な。

  • 位置透過性
    配置位置を意識させない。

  • 移動透過性
    移動時の影響を意識させない。

  • 複製透過性
    複製配置を意識させない。

  • 分割透過性
    分割配置を意識させない。

  • データモデル透過性
    RDBMSの違いを意識させない。

  • 障害透過性
    障害を意識させない≒冗長化技術と思われる。

• 2フェーズ・コミット
  トランザクションのコミット処理を 2 段階のフェーズにわける。

  • 第 1 フェーズ：各DBに対してコミットできる状態であるかどうかを確認する。
  • 第 2 フェーズ：各DBに対してコミットかロールバックかの決定を行う。

• 障害発生時でもACID特性を保障するための操作履歴

• ログ先行書き込み（WAL : Write Ahead Log）プロトコル

  • トランザクションがログを安定記憶(ディスク)に書き出すタイミングについての取り決め
  • ファイルシステムの分野では、ログ先行書き込みのことをジャーナリングと呼ぶ。

• SQL Server の障害復旧

• 復旧モデル

  • 完全バックアップ
  • 差分バックアップ
  • 増分バックアップ ≒ トランザクション ログ バックアップ

• トランザクション ログ

  • チェック ポイント
  • ロールバック・ロールフォワード

• 以下のものがある。

  • クラスタリング
  • ミラーリング
  • レプリケーション

• RDBMSによって異なるが、
  IPA定義では以下の様になっている。

  • クラスタリング
    可用性・性能向上技術

  • ミラーリング
    レプリケーション的技術を併用した可用性・性能向上技術

  • レプリケーション
    読取専用のスレーブを作成する性能向上技術。
    （ミラーリングより遅延が大きい的な説明）

• 尺度として以下を用いる
  （詳しくはデータマイニング（DM）- CRISP-DMの該当節を参照）。

  • 再現率 recall

    • = 検索された適合データ / 蓄積されている適合データ
    • 正解データが、どの程度が検索結果セットにヒットするかを示す。

  • 適合率 precision（精度）

    • = 検索された適合データ / 検索により表示されたデータ
    • 検索結果セット中にどの程度、正解データが含まれるかを示す。

  • F値 = （2×適合率×再現率）/（適合率＋再現率）

• 一般に、

  • 再現率の高いシステムは適合率が低く（ガバガバ過ぎ）
  • その逆に、適合率が高いシステムは再現率が低い（絞り過ぎ）

  傾向にある。

• ビジネス インテリジェンス（BI）

• ビッグデータ

• 人工知能（AI）

  • 機械学習（machine learning）
  • 深層学習（deep learning）

移行メモ

• &color(red){DISTINCT}; による強調は太字にした。
• 元 Wiki では「制約と操作」と「関係演算」の 2 つの見出しが 同一のアンカ（#b2b075d7）を持っていたが、 GitHub Wiki では見出しから別々のアンカが生成される。
• 元 Wiki の行頭空白による図・式は、フェンス付きコードブロックにした。
• 元 Wiki で見出しそのものが他ページへのリンクになっていた箇所 （「ロック・分離レベル」「障害復旧」）は、 GitHub Wiki では見出しからアンカが生成されるため、 見出しをプレーン・テキストとし、リンクは直下の本文に置いた。
• マイクロソフト系技術情報 Wiki（techinfoofmicrosofttech.osscons.jp）への URL リンクは、移行済みの SQL Server 結合方式の問題を監視する / DBMSのロック・分離戦略と同時実行制御 / SQL Server の障害復旧 に張り替えた。
• PukiWiki のページ内アンカ（#xxxxxxxx）は GitHub Wiki では再現できないため、 同一ページ内のアンカは見出しから生成されるアンカに張り替え、 他ページのアンカを指すリンクは「〜（ページ名 の該当節を参照）」の形に置き換えた。

---

Tags: 移行, 資格, 高度午前, 技術要素, データベース, RDBMS, 3層スキーマ, B木, 関数従属, 正規形, DDL, DML, DCL, 関係演算, 集合演算, ACID, トランザクション, 分散DB, 2フェーズ・コミット, 障害復旧, 再現率, 適合率