系統樹アルゴリズム

Question

私はこのドメインでは新しく、系図データを管理するアプリケーションを書くのが好きです。私の主な関心事は、MySQLからこれらのデータを保存して取得する方法です。私は、OracleのようなDBは再帰的なクエリのために最適化されていることを知っていますが、私はundestandをサポートしていないMySQLを使用する代替ソリューションを見つけることができます。 PS。私は何千もの既存のオープンソースソリューションがあることを知っていますが、これらのデータは機能の限られた部分であり、完全なコードを管理する必要があります。

私はウェブ上をすばやく見て、興味深いアプローチを見つけました。たとえば、インターバルベースのalgoはクエリには最適ですが、更新/削除には満足できません。

私はPrefix-based（Dewey）のアプローチについて見ていきますが、効率的で実績のある共有アプローチを知っているかもしれませんか？

おかげ

ジル

Answer 1

まず問題、設計データスキーマ：私は親行への外部キーでhierarchis続けます。それは単純です。

第2の問題は、昇順/子孫を検索します。：あなたが説明したように、問題はselectで選択されます：一部の人とすべての子孫を選択します。これを解決するには、新しいツリーテーブルを作成する必要があります。このテーブルには、ペアが含まれています。彼らは先祖のすべての（と自分自身）を持つ人へのアル組み合わせ：

people(id, name, id_parent) 
people_tree(id, id_ancestor, distance) 

Noticieこの構造の階層を照会することは容易であること。サンプル：誰かのすべての子孫：

select people.*, distance 
from 
    people p 
    inner join 
    people_tree t 
    on (p.id = t.id) 
where 
    id_ancesor = **sombody.id ** 

あなたが唯一の祖父母、grandwchildrenなどを取得する距離で遊ぶことができます...

最終問題、木を保つ：ツリーは最高のすべての時間でなければなりませんデータ。

：これは系譜の木なので、一人一人が両方の参照、親と母親を持っている必要があります

EDITED、CRUD操作のため

をpeopleオーバートリガーまたはストア手順：あなたはこれを自動化すべきです

people(id, name, id_parent, id_mother) 

その後、2つのツリーが必要です。

parent_ancestors_tree(id, id_ancestor, distance) 
mother_ancestors_tree(id, id_ancestor, distance) 

デビッドサンプルデータを求めます：

people: id name id_parent id_mother 
     1 Adam   NULL  NULL 
     2 Eva   NULL  NULL 
     3 Cain   1   2 
     .. ... 
     8 Enoc   3   5 

parent_ancestors_tree id id_ancestor distance 
       (Adam) 1    1   0 
       (Eva) 2    2   0 
       (Cain) 3    3   0 
         3    1   1 
       (Enoc) 8    8   0 
         8    3   1 
         8    1   2 

mother_ancestors_tree id id_ancestor distance 
       (Adam) 1    1   0 
       (Eva) 2    2   0 
       (Cain) 3    3   0 
         3    2   1 
       (Enoc) 8    8   0 
        -- here ancestors of Enoc's mother -- 

についてです。

Answer 2

また、隣接するツリーモデルをお勧めします。より複雑なロジックについては、単純なmysqlクエリ（結合）を使用することをお勧めします。ツリーを作成することが最も重要です。アプリケーションが終了し、すべてが正常になったら、より多くのデータマイニングを行うことができます。