sql - SQL - 階層を保存してナビゲートする方法は?

Question

データベース内の階層情報をモデル化し、取得するためにどのような方法を使用していますか?

score 31 · Accepted Answer

Modified Preorder Tree Traversal Algorithm が気に入っています。この手法により、ツリーのクエリが非常に簡単になります。

しかし、Zend Framework (PHP) の寄稿者の Web ページ (2007 年 6 月 5 日の 15:52 に Laurent Melmoux によって投稿されました) からコピーしたトピックに関するリンクのリストを次に示します。

リンクの多くは言語に依存しません。

データベースで階層構造を表すには、主に 2 つの表現とアルゴリズムがあります。

ネストされたセットは、修正されたプレオーダーツリートラバーサルアルゴリズムとも呼ばれます
隣接リストモデル

ここでよく説明されています：

ここに私が集めたいくつかのリンクがあります：

隣接リストモデル

http://www.sqlteam.com/item.asp?ItemID=8866

ネストされたセット

http://www.sqlsummit.com/AdjacencyList.htm
http://www.edutech.ch/contribution/nstrees/index.php
http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
http://www.dbmsmag.com/9604d06.html
http://en.wikipedia.org/wiki/Tree_traversal
http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html (アプレット java montrant le fonctionnement )

グラフ

http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

クラス：

ネストされたセット DB ツリー Adodb

http://www.phpclasses.org/browse/package/2547.html

訪問モデル ADOdb

http://www.phpclasses.org/browse/package/2919.html

PEAR::DB_NestedSet

ナシの木

nstrees

http://www.edutech.ch/contribution/nstrees/index.php

score 15 · Accepted Answer

この主題に関する決定的な記事は Joe Celko によって書かれ、彼はそれらの多くを Joe Celko's Trees and Hierarchies in SQL for Smarties という本にまとめました。

彼は、有向グラフと呼ばれる手法を好みます。この主題に関する彼の作品の紹介は、ここで見つけることができます

score 11 · Accepted Answer

SQL データベースで階層を表現する最良の方法は何ですか? 一般的で移植可能な技術？

階層の大部分は読み取られますが、完全に静的ではないと仮定しましょう。それが家系図だとしましょう。

これを行わない方法は次のとおりです。

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

そして、次のようにデータを挿入します。

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

代わりに、ノードと関係を 2 つのテーブルに分割します。

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

データは次のように作成されます。

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

ノードと同じ行に階層関係がある場合に発生する、テーブル自体の結合を伴わない任意のクエリを実行できるようになりました。

祖父母がいるのは誰？

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

すべての子孫:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

おじは誰ですか？

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

サブクエリを介してテーブルをそれ自体に結合するすべての問題を回避します。一般的な制限は 16 サブクエリです。

問題は、祖先テーブルを維持するのが難しいことです。ストアドプロシージャを使用するのが最適です。

score 10 · Accepted Answer

私はジョシュに反対しなければなりません。会社組織のような巨大な階層構造を使用している場合はどうなりますか。人々は会社に参加/退職したり、報告ラインを変更したりできます...「距離」を維持することは大きな問題であり、2 つのデータテーブルを維持する必要があります。

このクエリ (SQL Server 2005 以降) では、任意の人物の行全体を表示し、階層内での位置を計算できます。必要なのは、ユーザー情報の 1 つのテーブルだけです。子関係を見つけるように変更できます。

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;

score 4 · Accepted Answer

参考までに: SQL Server 2008 では、この種の状況のために新しいHierarchyIDデータ型が導入されています。行が「ツリー」のどこに位置するか、水平方向と垂直方向を制御できます。

score 3 · Accepted Answer

オラクル: SELECT ... START WITH ... CONNECT BY

Oracle には、ツリーベースの検索を容易にする SELECT の拡張機能があります。おそらく、SQL Server にも同様の拡張機能がありますか?

このクエリは、入れ子関係が親列と子列に格納されているテーブルをトラバースします。

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

score 2 · Accepted Answer

Josh と Mark Harrison が使用したテクニックの組み合わせが好きです。

2 つのテーブル。1 つは Person のデータを含み、もう 1 つは階層情報 (person_id、parent_id [、mother_id]) を含みます。このテーブルの PK が person_id の場合、ノードごとに親が 1 つだけの単純なツリーになります (これはこの場合、会計勘定のような他の場合ではありません)

この階層テーブルは、再帰的な手順によって、または DB が SELECT... BY PRIOR (Oracle) のような文によってサポートされている場合に横断できます。

他の可能性は、維持したい階層データの最大深さがわかっている場合、階層のレベルごとに一連の列を持つ単一のテーブルを使用することです

score 1 · Accepted Answer

[fleXive]のツリーコンポーネントを実装し、 MySQLドキュメントの tharkun によって言及されたネストされたセットツリーモデルアプローチを使用したときに、同じ問題が発生しました。

物事を (劇的に) 高速化することに加えて、スプレッドアプローチを使用しました。これは単に、すべての左右の値を再計算することなくノードを挿入および移動できるようにする、トップレベルの右境界に最大の Long 値を使用したことを意味します。左と右の値は、ノードの範囲を 3 で割って計算され、内側の3 分の 1 を新しいノードの境界として使用します。

Java コードの例は、ここで見ることができます。

score 0 · Accepted Answer

SQL Server 2005 を使用している場合は、このリンクで階層データを取得する方法が説明されています。

共通テーブル式 (CTE) は、使い慣れたら友達になることができます。

sql - SQL - 階層を保存してナビゲートする方法は?

9 に答える 9

Related

Reference