第5回 SQLで木構造を扱う～入れ子集合モデル （1）入れ子集合モデルとは何か | gihyo.jp
はじめに 木構造と呼ばれるデータ構造の一種があります。1つのルート（根）と呼ばれるノードを始点として、（通常）複数のリーフ（葉）と呼ばれるノードまでを経路で結んでできるデータ構造です。その名のとおり自然界にある「木」の構造ですし、学校時代、確率の授業で樹状図を書いた経験のある人もいるでしょう。 この構造は、私たちの周囲にとてもたくさん存在します。家系図や組織図も木ですし、IT関連の例では、ヒープやRDBのインデックス、ディレクトリ（フォルダ）によるファイルシステムやXMLも木構造です。Webの掲示板でも、最初の書き込みをルートとしてそれに対してコメントがつけられ、そのコメントにまたコメントがつけられるというプロセスで木構造を形成します。ここでは1つの書き込みがノードになります。 このように、IT技術と木構造は切っても切れない関係にありますし、多くの分野で応用されてもいるのですが、実は長い
第5回 SQLで木構造を扱う～入れ子集合モデル （2）入れ子集合モデルにおける検索 | gihyo.jp
入れ子集合モデルにおける検索 ルートとリーフを求める まず入れ子集合の検索で基本となる考え方を理解しましょう。それは「包含関係を調べる」ことです。 たとえば、ルート（ここで言う足立社長）とリーフ（猪狩、木島氏ら）を求めることを考えます。リーフの円は、自分の中に下位の円を一つも含まないという特性を持ちます。したがって、NOT EXISTSによって表現できます（リスト1、図5）。 リスト1 リーフの円を求める SELECT * FROM OrgChart Boss WHERE NOT EXISTS (SELECT * FROM OrgChart Workers WHERE Workers.lft > Boss.lft AND Workers.lft < Boss.rgt); 図5 リスト1の実行結果
第6回 SQLで木構造を扱う～入れ子区間モデル （1）もしも無限の資源があったなら | gihyo.jp
はじめに 前回では、入れ子集合モデルという、リレーショナルデータベースで木構造を扱うための新しい方法論を紹介しました。このモデルは、RDB、SQLと親和性の高い優れたものではあるのですが、挿入など更新時に、無関係のノードまで変更対象としなければならないのが大きな難点でした。 そこで今回は、上記の欠点を解消する進化版のモデルを紹介します。この方法を理解していく過程で、私たちはRDBと集合論の結び付きの深さを再確認することになります。 ふだんこの連載は、1回完結の読み切り形式なのですが、今回に限り、前号の内容を前提としています。未読の方は、前号を先に読むと理解が増すでしょう。 稼働環境 すべてのリレーショナルデータベース もしも無限の資源があったなら 座標に整数のみを使う場合の限界 入れ子集合モデルの大きな欠点は、ノードを挿入（追加）するときに、自分より「右側」にある無関係なノードをもっと右へ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SQLで木と階層構造のデータを扱う――入れ子集合モデル
