15

私は次のようなテーブルを持っています

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

フィールドの重要性：

  • site_Id：サイトのID
  • parent_Id：サイトの親ID
  • site_desc：質問には関係ありませんが、サイトの説明があります

要件は、入力としてsite_idがあり、サイトの下にタグ付けされたすべてのIDが必要な場合です。例えば：

                    A
                   / \
                  B   C
                / | \ /\
               D  E F G H
              /\
             I  J

すべてのノードはsite_Idです。

テーブルには次のようなデータが含まれています。

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

.....。

AはBとCなどの親です。

Bが指定された入力である場合、クエリはD、E、I、F、Jをフェッチする必要があります

現在、ループ内の複数のクエリによって実現されていますが、最小限のクエリで実現することを考えていました。

私が現在していることは::

反対票

アルゴリズムは次のようになります：

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

データモデルの制約内で最適化された最適な手法が必要です。何か提案があれば、遠慮なく答えてください。
何か提案してください。前もって感謝します。

4

10 に答える 10

10

残念ながら、データモデルを変更できず、MySQLを使用している場合、再帰クエリが必要であり、再帰クエリをサポートしないDBMSを使用している状況で立ち往生しています。

Quassnoiは、階層データをクエリするための手法を示す、興味深い一連のブログ記事を作成しました。彼の解決策は非常に巧妙ですが、非常に複雑です。 http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQLは別のオープンソースRDBMSであり、再帰クエリをサポートしているため、表示されている方法で保存されているツリー全体をフェッチできます。ただし、データモデルを変更できない場合は、別のRDBMSに切り替えることはできないと思います。

任意の深さのツリーを簡単に取得できるようにする代替データモデルがいくつかあります。

  • クロージャーテーブル
  • ネストされたセット、別名変更されたプレオーダーツリートラバーサル
  • パス列挙、別名マテリアライズドパス

これらについては、プレゼンテーション「SQLとPHPを使用した階層データのモデル」、および「SQLアンチパターン：データベースプログラミングの落とし穴の回避」で説明しています。

最後に、 Slashdotのコードで、コメント階層に使用されている別の解決策があります。隣接リストのように「parent_id」を格納しますが、「root_id」列も格納します。特定のツリーのすべてのメンバーは、そのツリーで最も高い祖先ノードであるroot_idに同じ値を持ちます。次に、1つのクエリでツリー全体をフェッチするのは簡単です。

SELECT * FROM site WHERE root_id = 123;

次に、アプリケーションはすべてのノードをデータベースから配列にフェッチします。この配列をループするコードを記述して、ノードをメモリ内のツリーデータ構造に挿入する必要があります。これは、多数の個別のツリーがあり、各ツリーのエントリが比較的少ない場合に適したソリューションです。スラッシュドットの場合に適しています。

于 2013-02-01T23:48:33.407 に答える
8

昨日、私はあなたが説明したあなたの問題に正確に関連するこの質問に答えました：与えられた隣接リストから、あなたは特定の親のすべての子ノードを取得したいです-そしておそらくあなたが簡単にできる一次元配列で繰り返します。

これは、データベースへの1回の呼び出しのみを使用して実行できますが、ある種の落とし穴があります。テーブルからすべての行を返す必要があります。MySQLは再帰クエリをサポートしていないため、代わりに、基本的にSELECTアプリケーションコードでingを実行する必要があります。

上記でリンクした私の答えを繰り返しますが、基本的にPDOStatement->fetchAll(PDO::FETCH_ASSOC)は、次のような形式で結果セット（おそらく、または他のメソッドから）を返す場合です。

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

site_idこの再帰関数を使用して、（IDを知っている場合）任意のすべての子/孫/ひ孫/などを取得できます。

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

たとえば、のすべての子を取得したいsite_id D場合は、次のような関数を使用します。

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

出力します：

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

親の情報とその子、孫などの情報を保持していることに注意してください（ただし、ネストは深くなります）。

于 2012-07-17T06:53:29.737 に答える
5

単一のクエリでこれを実行できるようにする場合は、ネストされたセットモデルを確認してください：http：//mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

もう1つの方法は、すべての関係をリンクテーブルに含めることです。したがって、すべてのサイトには、その親、祖父母などへのリンクがあります。すべての関係は明示的です。次に、そのリンケージテーブルをクエリして、すべての子孫を取得します。

于 2012-06-16T16:07:47.127 に答える
3

まず、ツリーを格納するための少し異なる方法をお勧めします：クロージャーテーブル。それについてもっと知りたい場合は、SQLアンチパターンの本が非常に興味深いと思うかもしれません。

そうは言った。私の意見では、このような構造を生成する最も簡単な方法は次のとおりです。http: //jsbin.com/omexix/3/edit#javascript

JavaScriptコードの読み取りに問題がないことを願っています。JavaScriptでの未分類のオブジェクトの作成はそれほどハックっぽく見えないので、私はそれを使用しました。多次元配列を使用することで、オブジェクト（または参照）を中継せずに同じものを実装することは可能ですが、少し混乱しているように見えます。

アルゴリズムの機能は次のとおりです。

  • ノードのリストを1回ループします
  • ノードの親が存在しない場合、プレースホルダーが配列に作成されます
  • ノードに親がない場合は、ルートノードのリストに配置されます
  • ノードの配列にプレースホルダーがない場合、プレースホルダーが作成されます
  • ノードからの値がプレースホルダーに割り当てられます
  • 親がいる場合、ノードは親に登録されます

これはそれについてです。基本的に、すべてのノードとルートノードのみの2つのリストを生成します。

于 2012-07-14T18:39:37.783 に答える
3

クロージャーテーブルのパターンを確認することをお勧めします。このサイトは有益だと思いました。私が見た限りでは、この概念に関するいくつかのStackOverflowの質問もあります。たとえば、ここにあります。

于 2013-02-01T19:12:08.547 に答える
2

テーブルを頻繁に更新しない場合はsite、次の戦略を使用できます。

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100),
parents_path varchar(X)
);

parents_pathルートから選択したノードへのパスと同じです。たとえば、葉のJ場合は|A|B|D|。

長所：-結果を取得するには、単一のクエリが必要です。

短所：-更新中のクエリが増えます（ただし、更新は賢明に行うことができます）。

それが役に立てば幸い

于 2012-07-13T14:05:29.993 に答える
2

他の人は、テーブル構造にわずかな変更を加えてこれを行う方法をすでに提案しています。

構造を変更したくない場合（これが最善であっても）、次のように行うことができます。

  • SELECT * FROM site ORDER BY Parent_ID、Site_id;

通常、一度割り当てられるとIDは変更されないと安全に想定できます。IDがシャッフルされない場合、つまりノードCがノードBの下に移動されない場合、子ノードは常に親よりも高いIDを持ち、上記の並べ替えにより、すべての親が子の前にフェッチされることが保証されます。 。

したがって、これらは仮説です。

- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around

したがって、メモリ内にツリーを作成することが可能になります（さらに、WHERE Site_ID> = Bを追加してクエリ自体を減らすこともできます）。

最初に通過するノードはBであり、ツリーに配置されます。

後続のすべてのノードは、以前に確実にロードされたParent_ID番目のノードに格納される場合があります。

これはPythonでは非常にうまくいきます（親ノードを直接変更します）。

「Bのすべての子孫を取得する」という要求は、PHPで次のように応答できます。

$nodes  = array( $parent_id );

$cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? "
        .  "ORDER BY Parent_ID, Site_Id ;", $parent_id);

while ($tuple = SQLFetchTuple($cursor))
    if (in_array($tuple['Parent_ID'], $nodes))
        $nodes[] = $tuple['Site_Id'];
SQLFree($cursor);

// The first node is the global parent, and may be array_shift'ed away
    // if desired.

別の方法
はかなりブルートフォース

別の可能性は、「descendant_of」関係を別のテーブルに再帰的に格納することです。

    TRUNCATE descendants;
    INSERT INTO descendants ( node, of ) VALUES ( -1, NULL );

    INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN
           descendants ON ( site.ParentId = descendants.of );

そして、挿入された行の数がゼロになるまでINSERTを繰り返します（または子孫の行の総数が増えなくなります。ほとんどのDBでは、テーブルサイズのクエリが非常に高速です）。

この時点で、すべての1レベルの関係が保存されています。今：

INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM
           descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);

...再び子孫の増加が止まるまで（レベルの最大数に等しい数の挿入が必要になります）。JOINの総数は、レベル数の2倍になります。

ここで、ノード16のすべての子孫を取得する場合は、クエリを実行するだけです。

SELECT node FROM descendants WHERE of = 16;
于 2012-07-16T21:43:05.680 に答える
2

このためのストアドプロシージャを作成できます。

これがmysqlでの私の実装です

DROP PROCEDURE IF EXISTS SearchTree;
DELIMITER go

CREATE PROCEDURE SearchTree( IN root CHAR(1) )
BEGIN
  DECLARE rows SMALLINT DEFAULT 0;
  DROP TABLE IF EXISTS reached;
  CREATE TABLE reached (
    site_Id CHAR(1) PRIMARY KEY
  ) ENGINE=HEAP;
  INSERT INTO reached VALUES (root);
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    INSERT IGNORE INTO reached 
      SELECT DISTINCT s.site_Id 
      FROM site AS s 
      INNER JOIN reached AS r ON s.parent_Id = r.site_Id;
    SET rows = ROW_COUNT();
    DELETE FROM reached 
      WHERE site_Id = root;
  END WHILE;
  SELECT * FROM reached;
  DROP TABLE reached;
END;
go
DELIMITER ;
CALL SearchTree('B');

期待される結果を返します。

于 2013-01-31T08:28:25.693 に答える
2

ここでのコメントに基づいて、何百ものアプリケーションが既存のデータモデルを使用しているため、既存のデータモデルを変更したくないと思います（他のデータモデルに置き換えると壊れます）。

問題の根本は、どのサイトでも、それが直接の親であることがわかっているだけなので、ルートサイトが見つかるまで、その親の親を再帰的に検索する必要があるということです。

サイトをネストできる深さ/レベルの制限を回避できる場合は、すべての作業を実行し、起動にそれほど時間がかからない1つの優れたクエリを作成できます。クエリの起動によるオーバーヘッドのほとんどは、接続やネットワーク帯域幅などの設定に起因します。MySQLは非常に高速です。

複数のクエリを実行するとすべてのオーバーヘッドが増えるため、これは望ましくありません。SELECT *を実行してから、アプリケーションロジックで計算するということは、毎回すべてのデータをフェッチし、ネットワークオーバーヘッドを最大化することを意味するため、これは望ましくありません。

ツリーの深さの制限が許容できる場合は、複数のクエリを1つの巨大なクエリに結合して、すべての作業を実行し、必要な正確な結果セットを返すことができます。例として、私はあなたのデータを使用しましたが、A、B、Cなどを1、2、3に置き換えました（列はintであるため）。

ルートノードのすべての直接の子（site_id = 1）を取得するには、次のようにします。

select site_id from site where parent_id = 1

ルートノードの孫を取得するには、次のようにします。

select grandchild.site_id 
from site grandchild, site child 
where grandchild.parent_id = child.site_id 
and child.parent_id = 1

ルートノードの曽孫を取得するには、次のようにします。

select greatgrandchild.site_id 
from site greatgrandchild, site grandchild, site child 
where greatgrandchild.parent_id = grandchild.site_id 
and grandchild.parent_id = child.site_id 
and child.parent_id = 1

ルートノードのすべての子孫を取得するには、上記のクエリを次のように1つの巨大なクエリに結合します。

select site_id
from site
where site_id in (
    select site_id 
    from site 
    where parent_id = 1
)
or site_id in (
    select grandchild.site_id 
    from site grandchild, site child 
    where grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)
or site_id in (
    select greatgrandchild.site_id 
    from site greatgrandchild, site grandchild, site child 
    where greatgrandchild.parent_id = grandchild.site_id 
    and grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)

これがどのように機能しているかがわかると思います。追加のレベルごとに、子孫を検索しているサイトからその数レベル離れているノードを見つけるクエリを作成し、そのクエリを追加の'またはsite_idを（）'でスーパークエリに追加します。

ご覧のとおり、3つのレベルだけで、これはすでに大きなクエリになっています。たとえば、10レベルをサポートする必要がある場合、このクエリは巨大になり、その中のすべてのORとINによって速度が低下します...ただし、すべてを取得したり、複数のクエリを使用したりするよりも、おそらく高速です。可能なレベルの任意の量をサポートする必要がある場合、このクエリは役に立ちません。それは無限に大きくなる必要があります。その場合、残っているのはより良い方法を使用することです...

とはいえ、これをコピーして貼り付けてコーディングを開始する前に、このような巨大なクエリを回避し、任意の深さをサポートし、下位互換性を損なうことのない方法があります。データモデルを変更する必要がありますが、このデータモデルを使用している他のプログラムを傷つけることのない小さなものです。要するに...

より良い方法

各ノードからルートまでのフルパスをエンコードするために、彼の回答で言及されているravnurのようなものを使用して、追加の列parent_pathsを追加します

挿入、更新、削除のトリガーを使用して、その列を動的に入力します。現在、冗長データを維持しています。他のプログラムを傷つけることはありませんが、パフォーマンスに大きなメリットをもたらす可能性があります。ただし、追加の列のデータは常にテーブルの通常のデータと同期している必要があるため、トリガーが防弾であることを確認してください（おそらく最も難しい部分です）。

ravnurが示したような短くて甘いクエリを使用して、parent_paths列の任意の場所でsite_idの出現を検索し、再帰なしでそのsite_idを持つサイトのすべての子孫を直接取得します。

于 2013-02-01T21:42:44.843 に答える
1

また、関係を再帰的に照会する方法を自問し、私の脳がこのソリューションを生成しました（：

SELECT * FROM
(
    SELECT t2.* FROM table t1, table t2 where t2.parent = t1.id OR t2.parent 0 GROUP BY t2.id, t2.parent
) as all_relations
WHERE all_relations.parent >= '_the_id_'

# if you dont want a subtree use only the inner select

100％確信はありませんが、IDが自動的にインクリメントされ、子が親として小さいIDを持たない限り（これは通常の場合です）、これは解決策になる可能性がありますか？

于 2013-11-20T17:09:25.880 に答える