SQLアタマアカデミー
第6回 SQLで木構造を扱う~入れ子区間モデル (1)もしも無限の資源があったなら
はじめに
前回では,
そこで今回は,
ふだんこの連載は,
- 稼働環境
- すべてのリレーショナルデータベース
もしも無限の資源があったなら
座標に整数のみを使う場合の限界
入れ子集合モデルの大きな欠点は,
そう,
有理数, 実数にまで広げると
でも,
実はノードの座標が整数でなければならない理由は別にないのです。今まで整数を使っていたのは,
テーブルの再作成
そうと決まれば,
リスト1 入れ子区間モデルによる木構造の表現
CREATE TABLE OrgChart
(emp VARCHAR(32) PRIMARY KEY,
lft REAL NOT NULL,
rgt REAL NOT NULL,
CHECK (lft < rgt));
初期データは,
図2 初期データの状態
emp | lft | rgt |
---|---|---|
足立 | 1 | 14 |
猪狩 | 2 | 3 |
上田 | 4 | 13 |
江崎 | 5 | 8 |
木島 | 6 | 7 |
大神 | 9 | 10 |
加藤 | 11 | 12 |
図3 初期データの入れ子集合による表現
追加するノードの座標を決めるアルゴリズム
さて,
追加ノードの左端座標=(plft*2+prgt)/3 ― ⓐ
追加ノードの右端座標=(plft+prgt*2)/3 ― ⓑ
なぜこれでうまくいくかというと,
plft<(plft*2+prgt)/3<(plft+prgt*2)/3<prgt
理由は,
3plft<(plft*2+prgt)<(plft+prgt*2)<3prgt
今,
- 注1)
- 厳密に言うと,
利用する範囲は有理数に限られるのですが, 「有理数型」 というデータ型を持っているデータベースは存在しないので, 実数型を使います。実数は有理数を包含するので問題ありません。
データを追加してみる
座標に整数のみを利用する場合 (前回の方法)
これを,
座標に有理数を利用する場合
しかし,
国見氏の座標は,
左端座標=(2*2+3)=2.
333… 右端座標=(2+3*2)=2.
666…
このように,
- 注2)
- ただし,
追加ノードをリーフではなく親として挿入する場合は, 持つことになる子供の円とぶつからないようにするため, もう少し計算が複雑になります。
バックナンバー
SQLアタマアカデミー
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (5)集合指向と手続き型
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (4)OLAP関数と集約関数を組み合わせる
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (3)OLAP専用関数
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (2)OLAP関数の基本構文
- 最終回 OLAP関数で強力な統計処理を実現!―手続き型から理解するSQL (1)OLAP関数とは何か
- 第10回 結合大全 (5)非等値結合
- 第10回 結合大全 (4)自己結合
- 第10回 結合大全 (3)外部結合
- 第10回 結合大全 (2)内部結合
- 第10回 結合大全 (1)クロス結合