プログラマのためのSQLグラフ原論リレーショナルデータベースで木と階層構造を扱うために

2020年1月8日

翔泳社

著者：ジョー・セルコ
監訳：ミック

序文－ジョー・セルコ
翻訳・監修にあたって－ミック
著者について
目次

第1章グラフ、木、階層
1.1　階層を定義する
1.1.1　木
1.1.2　階層の性質
1.1.3　階層の種類
1.2　ネットワークデータベース
1.3　プログラムにおけるグラフのモデル化
1.4　大論争
1.5　再帰に関するメモ
・グラフ理論に関する参考文献

第2章隣接リストモデル
2.1 単純な隣接リストモデル
2.2 単純な隣接リストモデルは正規化されていない
2.2.1 更新異常
2.2.2 挿入異常
2.2.3 削除異常
2.2.4 構造異常
2.3 隣接リストモデルを修正する
2.3.1 NULLの使用について
2.4 隣接リストモデルにおける探索
2.4.1 カーソルと手続き型のコード
2.4.2 自己結合
2.4.3 再帰共通表式を使って部分木を見つける
2.4.4 ループで部分木を見つける
2.4.5 上司を見つける
2.5 隣接リストモデルにおけるノード追加
2.6 隣接リストモデルにおけるノード削除
2.6.1 部分木全体を削除する
2.6.2 削除の後に部下を昇格させる
2.6.3 削除の後に部分木全体を昇進させる
2.7 階層に番号を割り当てた隣接リストモデル
2.7.1 階層に番号を割り振る
2.7.2 階層における集約

第3章経路列挙モデル
3.1 木の深さを測る
3.2 子ノードを見つける
3.3 親ノードを見つける
3.4 部分木を削除する
3.5 単一のノードを削除する
3.6 新しいノードを挿入する
3.7 経路の文字列を分割する
3.8 SQL ServerのHIERARCHYID
3.9 エッジ列挙モデル
3.1 XPathとXML

第4章入れ子集合モデル
4.1 ルートとリーフを見つける
4.2 部分木を見つける
4.3 木の深さをと経路を調べる
4.3.1 木の高さを調べる
4.3.2 部分木の高さを調べる
4.3.3 最も序列の高い子ノードと最も序列の低い子ノードを見つける
4.3.4 ノード間の経路を見つける
4.3.5 相対位置を見つける
4.4 入れ子集合モデルにおける関数
4.5 ノードと部分木を削除する
4.5.1 部分木を削除する
4.5.2 単一ノードを削除する
4.5.3 部分木を隠ぺいする
4.6 座標の欠番を埋める
4.7 木に対する集計関数
4.7.1 部分展開表の繰り返し集計
4.7.2 再帰計算
4.8 木に対する挿入と更新
4.8.1 木の中で部分木を移動させる－その1
4.8.2 木の中で部分木を移動させる－その2
4.8.3 部分木を挿入する
4.8.4 部分木の複製
4.8.5 ノードの入れ替え
4.9 入れ子集合モデルを隣接リストモデルへ変換する
4.10 隣接リストモデルを入れ子集合モデルに変換する
4.10.1 スタックアルゴリズム
4.11 エッジとノードの分離
4.11.1 多重構造
4.11.2 属性を持つノード
4.12 ノードと構造を比較する

第5章頻繁に挿入が行なわれる木
5.1 (lft,rgt)のデータ型
5.1.1 整数の範囲を余すところなく使う
5.1.2 FLOAT、REAL、DOUBLE PORECISION
5.1.3 NUMERICとDECIMAL
5.2 ノードの幅を計算する
5.2.1 除数のパラメータ化
5.2.2 除数を計算式で決める
5.2.3 除数をテーブル参照で決める
5.2.4 木の部分的な再構成
5.2.5 右方向へのノード幅の拡張
5.3 木の全体的な再構成
5.3.1 組織図テーブルの再構成
5.3.2 再帰による再構成
5.4 有理数と入れ子区間モデル
5.4.1 半順序のマッピング
5.4.2 xy座標の合計
5.4.3 親ノードと兄弟ノードの座標を見つける
5.4.4 ノード間の経路と距離の計算
5.4.5 階層を構築する
5.4.6 左端座標を利用した深さ優先列挙
5.4.7 右端座標を利用した深さ優先列挙
5.4.8 上位ノードと下位ノードを選択する
5.5 エジプト式分数

第6章入れ子集合モデルの線形バージョン
6.1 挿入と削除
6.2 ノードからルートへの経路を見つける
6.3 ノードの階層を計算する
6.4 レシート問題

第7章二分木
7.1 二分木の探索
7.2 二分木のクエリ
7.2.1 親ノードを見つける
7.2.2 再帰共通表式で部分木を見つける
7.2.3 データの位置から部分木を求める
7.3 二分木からの削除
7.4 二分木への挿入
7.5 ヒープ
7.6 多分木を二分木で表わす
7.7 シュターン・ブロコ木

第8章木を表現するその他のモデル
8.1 自己参照を伴う隣接リストモデル
8.2 従属隣接リスト
8.3 ハイブリッドモデル
8.3.1 隣接リスト入れ子集合モデル
8.3.2 階層付き入れ子集合モデル
8.3.3 階層付き隣接リストモデル
8.3.4 先順走査と後順走査の応用
8.4 素数の積を使った経路列挙
8.4.1 あるノードの下位ノードを見つける
8.4.2 あるノードの上位ノードを見つける
8.4.3 深さ付きの階層
8.4.4 子ノードの挿入
8.4.5 ノードを削除する
8.4.6 経路を分解する
8.4.7 有用な関数

第9章木を扱うための実装依存の拡張
9.1 Oracleの独自拡張
9.1.1 類似の拡張
9.2 DB2のWITH演算子
9.3 デイトのEXPLODE演算
9.4 ティルキストとクオによる隣接リストの拡張
9.5 マイクロソフトの拡張
9.6 その他の方法
・参考文献

第10章データモデリングにおける階層
10.1 階層のタイプ
10.2 DDLにおける制約
10.2.1 一意制約
10.2.2 排他的な階層
10.2.3 1:1、1:m、n:mの関連を表わす

第11章階層を持ったコード体系
11.1 ZIPコード
11.2 デューイ十進分類法(DDC)
11.3 長所と短所
11.4 商品のカテゴリ

第12章 SQLにおけるグラフ
12.1 隣接リストモデルのグラフ
12.1.1 SQLと隣接リストモデル
12.1.2 隣接行列モデル
12.2 グラフを入れ子集合モデルで表わす
12.2.1 ノードの一意性
12.2.2 経路の両端
12.2.3到達可能ノード
12.2.4 エッジ
12.2.5 入次数と出次数
12.2.6 さまざまなタイプのノードを見つける
12.2.7 非循環グラフを入れ子集合に変換する

第13章ペトリネット
13.1 ペトリネットのためのDDL
・参考文献

第14章状態遷移グラフ
14.1 遷移の時間的側面

第15章階層型データベース（IMS）
15.1 データベースの種類
15.2 データベースの歴史
15.2.1 DL/I
15.2.2 制御ブロック
15.2.3 データ通信
15.2.4 アプリケーションプログラム
15.2.5 階層型データベース
15.2.6 長所と短所
15.3 サンプルの階層型データベース
15.3.1 学部データベース
15.3.2 学生データベース
15.3.3 設計時の考慮点
15.3.4 サンプルデータベースの拡張
15.3.5 データの構造
15.3.6 階層の順序
15.3.7 階層におけるデータ経路
15.3.8 データベースのレコード
15.3.9 セグメントのフォーマttp
15.3.10 セグメントの定義
15.4 まとめ
・参考文献