如何有效地查询有向无环图

Question

我在我的网络应用程序上使用mysql.应用程序表包含一个supervisor表和一个employee表.员工表包含有关每个员工的信息.主管表包含两列,如下所示.

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

每个下属可以有多个主管,一个主管下属可以是其他员工的主管.所以表格记录可以跟随.

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

但是当我使用这种方法时,它会有数百万的数据与该表.这是低效的.

我的问题是有任何有效的方法来做到这一点.我的表结构有什么问题阻止我有效地进行这种查询.

Answer 1

你说的是非循环图，所以也许我离这里很远 - 但同时听起来你需要一些东西来实现正常的主管和员工层次结构？那么可以用树结构来完成吗？

我不确定，但听起来你只需要一个树结构？我认为找出谁超过一个人的最简单方法是将所有姓名存储在一个表中，并使用两个字段来更新人之间的关系。田地会向左和向右。

                              _______  
                           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