8

我在我的 Web 应用程序中使用 mysql。应用程序表包含一个主管表和一个员工表。员工表包含有关每个员工的信息。主管表包含如下两列。

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

但是当我使用这种方法时，该表将拥有数百万条数据。而且效率低下。

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

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/

（您可以忽略他所说的部分，“它不会特别在 MySQL 或 sqlite3 上运行，它们根本不支持 CTE。”正如我所提到的，情况不再如此。）

正如您在问题中指出的那样，“当我使用这种方法时，该表将拥有数百万条数据。” 如果您要为效率而交易空间，仅此一项可能并没有那么糟糕，但正如汤姆博士的帖子在一个示例中所解释的那样：

删除或插入红色弧线的操作也需要在 θ(n^2) 上付出努力。

对于这些操作，这是 n 平方的努力；您可以获得查询效率，但代价是空间效率低下和插入/删除效率低下。他进一步指出，

实际上，所有大型现实世界网络都是稀疏的。它们的边缘比可能的要少得多，即 m«n^2。

公平地说，您链接的 Kemal Erdogan 的代码项目文章来自 2008 年；那时 CTE 还没有普及。此外，正如他在此解释的那样，埃尔多安在权衡取舍方面做出了明智的选择：

我拥有的解决方案[也是]基于递归。但是，我没有将递归推迟到查询时间，而是在插入时间进行递归，假设图形实际上被查询多于修改（这对于我迄今为止遇到的所有情况都是如此）。

如果在阅读了 Tom 博士的文章之后，您最终更喜欢 Erdogan 的权衡，您可以通过查看 Laravel 的实现来限制其他低效率：

laravel-dag-manager,Laravel 的基于 SQL 的有向无环图 (DAG) 解决方案,下载laravel-dag-manager的源码_GitHub_帮酷 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 | 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
                          _____                _______

摩西的老板是谁？每个拥有较高权利和左边情人的人都会给您 Bill、Abraham、Maria、Paul 和 Peter :-) 这完全不需要数据库中的时间来提取。如果这很有趣，我可以使用有关如何执行此操作的详细信息来更新此答案。

 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 回答