8

Web アプリケーションの 1 つに mysql を使用しています。アプリケーション テーブルには、スーパーバイザー テーブルと従業員テーブルが含まれています。employee テーブルには、各従業員に関する情報が含まれています。スーパーバイザー テーブルには、次の 2 つの列が含まれます。

supervisor_id -> which is employee id of the supervisor
subordinate_id -> which is the employee id of the subordinate.

各部下は複数の監督者を持つことができ、1 人の監督者の部下が他の従業員の監督者になることができます。したがって、テーブル レコードは次のようになります。

supervisor_id | subordinate_id
1             | 2
1             | 3
2             | 4
4             | 5
3             | 6
3             | 4

上記の例では、スーパーバイザー チェーンがあります。スーパーバイザー 1 には、部下として 2、3、4、5、および 6 がいます。スーパーバイザー 2 には、部下として 4、5 がいます。また、部下に対して複数のスーパーバイザーを持つこともできます。

現在、スーパーバイザー 2 のすべての部下を照会する場合、次のようなクエリを使用します。

public function getSubordinate($id) {
 $query = "SELECT * FROM supervisor WHERE subordinate_id = $id";
 // get results and return
}

したがって、私が現在行っていることは、最初に id を 2 として送信して、その直属の部下を取得することです。次に、結果として得られるすべての部下に対して、クエリを何度も実行して完全な部下チェーンを取得します。

これは、小さなデータセットで問題ありません。しかし、このスーパーバイザー テーブルには数千のデータが含まれるため、スーパーバイザー チェーンを見つけるために何千ものクエリを実行する必要があり、結果が得られるまでに時間がかかります。

部下は複数のスーパーバイザーを持つことができるため、ネストされたセットはこれに対する正確な答えにはなりません。

私もこの解決策を経験しました。http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o

しかし、この方法を使用すると、そのテーブルに何百万ものデータが含まれます。そしてそれは非効率的です。

私の問題は、これを行う効率的な方法があることです。この種のクエリを効率的に行うのを妨げるテーブル構造に問題はありますか?

4

2 に答える 2

1

主要なデータベース アプリケーション (MySQL や MariaDB を含む) はすべて、共通テーブル式を使用した再帰クエリをサポートするようになりました。これは、MySQL バージョン 8.0 および MariaDB バージョン 10.2.2 で導入されました。PostgreSQL はそれ以前からサポートしていました。Oracle にはそれがあり、SQL Server には 2005 バージョンで追加されました。実際、簡単に検索すると、Sqlite も Common Table Expressions をサポートしていることがわかります。

したがって、探している答えは、共通テーブル式と再帰クエリを使用することです。「 SQL データベースで有向非巡回グラフ (DAG) を表すモデル」と比較して、それがより良い解決策と見なされるいくつかの理由をここで説明します。

リレーショナル モデルでのグラフのエンコードとクエリ
https://drtom.ch/posts/2012/02/11/Encoding_and_Querying_Graphs_in_the_Relational_Model/

(彼が「CTE をサポートしていない MySQL や sqlite3 では特に動作しない」と言っている部分は無視してかまいません。前述のとおり、それはもはや当てはまりません。)

質問で指摘したように、「この方法を使用すると、そのテーブルに何百万ものデータが含まれます。」効率のためにスペースを交換していた場合、それだけでそれほど悪くはないかもしれませんが、Tom 博士の投稿が 1 つの例で説明しているように:

赤い弧を削除または挿入する操作は、θ(n^2) にも労力が必要です。

これは、これらの操作の n 乗の労力です。クエリの効率は向上しますが、スペースの非効率性と挿入/削除の非効率性が犠牲になります。彼はさらに次のことを指摘している.

実質的にすべての大規模な現実世界のネットワークはまばらです。可能なエッジよりもはるかに少ないエッジ、つまり m«n^2 があります。

公平を期すために、あなたがリンクした Kemal Erdogan による Code Project の記事は 2008 年のものです。当時、CTE はどこでも利用できるわけではありませんでした。さらに、エルドアン大統領は、ここで説明したように、トレードオフに関して十分な情報に基づいた選択を行いました。

私が持っている解決策は、[あまりにも]再帰に基づいています。ただし、クエリ時まで再帰を延期する代わりに、挿入時に再帰を行います。これは、グラフが実際には変更されたものよりもクエリされていることを前提としています (これは、これまでに直面したすべてのケースに当てはまります)。

Dr. Tom の記事を読んだ後、最終的に Erdogan のトレードオフを好む場合は、ここで Laravel の実装を確認することで、他の非効率性を制限できる可能性があります。

GitHub - telkins/laravel-dag-manager: Laravel 用の SQL ベースの有向非巡回グラフ (DAG) ソリューション。https://github.com/telkins/laravel-dag-manager

特に、Max Hops を見て、独自のソリューションにそのようなものを実装してください。

これはLaravel構成ファイルにあります：

/*
|--------------------------------------------------------------------------
| Max Hops
|--------------------------------------------------------------------------
|
| This value represents the maximum number of hops that are allowed where
| hops "[i]ndicates how many vertex hops are necessary for the path; it is
| zero for direct edges".
|
| The more hops that are allowed (and used), then the more DAG edges will
| be created.  This will have an increasing impact on performance, space,
| and memory.  Whether or not it's negligible, noticeable, or impactful
| depends on a variety of factors.
*/

'max_hops' => 5,

免責事項：私は今、自分でこれを研究しているだけです. これらのソリューションのいずれについても、まだ経験がありません。

于 2018-12-12T01:46:07.030 に答える
0

あなたは非巡回グラフを言っているので、私はここから離れているかもしれませんが、同時に、通常の監督者と従業員階層のために何かが必要なように聞こえますか? ツリー構造でそれを行うことができますか？

よくわかりませんが、ツリー構造だけが必要なようですね?? 誰が 1 人を超えているかを引き出す最も簡単な方法は、すべての名前を 1 つのテーブルに格納し、2 つのフィールドを使用して人々の間の関係を更新することだと思います。フィールドは左右になります。

                              _______  
                           1 | peter | 20
                              _______
             ______                        ______
          2 | paul | 17                18 | john | 19
             ______                        ______
    _____            _______
 3 |judas | 4      5 | maria | 16
    _____            _______


               _____             ________
            6 |seth  | 7      8 | abraham | 15
               _____             _______

                                ______          
                              9 |bill | 14
                                 _____

                          _____                _______
                      10 |kenny | 11      12 | moses | 13
                          _____                _______

モーセの上司は誰ですか？より高い権利と恋人の左を持つすべての人は、ビル、エイブラハム、マリア、ポール、ピーターを与えます:-) これは、データベースから引き出すのにまったく時間がかかりません。これが興味深い場合は、これを行う方法の詳細でこの回答を更新できます。

 table  left   right

 peter  1      20
 paul   2      7
 judas  3      4
 maria  5      16
 seth   6      7
 ... etc


 select * from people where left < 12 and right > 13

結果：

 bill     9     14
 abraham  8     15
 maria    4     16
 paul     2     17
 peter    1     20
于 2013-02-09T12:09:51.400 に答える