Как эффективно запрашивать ориентированный ациклический граф

Все основные приложения баз данных (включая MySQL и MariaDB) теперь поддерживают рекурсивные запросы с использованием общих табличных выражений. Это было введено в MySQL версии 8.0 и версии MariaDB 10.2.2. PostgreSQL поддерживался еще раньше. Он есть у Oracle, и SQL Server добавил его в версии 2005 года. Фактически, быстрый поиск показывает, что Sqlite также поддерживает Common Table Expressions.

Поэтому ответ, который вы, возможно, ищете, заключается в использовании общих табличных выражений и рекурсивных запросов. Некоторые причины, по которым это считается лучшим решением по сравнению с "Модель для представления направленных ациклических графов (DAG) в базах данных SQL" объясняется здесь:

Кодирование и запрос графов в реляционной модели
https://drtom.ch/posts/2012/02/11/Encoding_and_Querying_Graphs_in_the_Relational_Model/

(Вы можете проигнорировать ту часть, где он говорит: «Он не будет работать, в частности, на MySQL или sqlite3, которые просто не поддерживают CTE». Как я уже упоминал, это уже не так.)

Как вы отметили в своем вопросе, «когда я использую этот метод, в этой таблице будут миллионы данных». Само по себе это может быть не так уж плохо, если вы обмениваете пространство на эффективность во всем, но, как объясняет пост доктора Тома на одном примере:

Операция удаления или вставки красной дуги также требует усилий в θ(n^2).

Это n-квадрат усилий для этих операций; вы получаете эффективность запросов, но за счет неэффективности пространства и неэффективности вставки/удаления. Далее он указывает, что

практически все крупные сети реального мира разрежены. У них гораздо меньше ребер, чем было бы возможно, т. е. m

Справедливости ради, статья Кемаля Эрдогана в Code Project, на которую вы ссылаетесь, датируется 2008 годом; В то время CTE не были доступны повсеместно. Кроме того, Эрдоган сделал осознанный выбор в отношении компромисса, как он объяснил здесь:

Решение, которое у меня есть, основано на рекурсии [тоже]. Однако вместо того, чтобы откладывать рекурсию до времени запроса, я выполняю рекурсию во время вставки, предполагая, что граф на самом деле больше запрашивается, чем модифицируется (что верно для всех случаев, с которыми я сталкивался до сих пор).

Если после прочтения статьи доктора Тома вы в конечном итоге предпочитаете компромиссы Эрдогана, вы можете ограничить другие неэффективности, взглянув на реализацию Laravel здесь:

GitHub — telkins/laravel-dag-manager: решение для направленного ациклического графа (DAG) на основе SQL для Laravel. 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,

Отказ от ответственности: я только сейчас изучаю это для себя. У меня пока нет опыта работы ни с одним из этих решений.

Вы говорите об ациклическом графе, так что, возможно, я ошибаюсь, но в то же время это звучит так, как будто вам нужно что-то для нормальной иерархии руководителей и сотрудников? так можно ли это сделать с древовидной структурой?

Я не уверен, но похоже, что вам нужна только древовидная структура ?? и я думаю, что самый простой способ узнать, кто находится над одним человеком, — это сохранить все имена в одной таблице и использовать два поля для обновления отношений между людьми. Поля будут левые и правые.

                              _______  
                           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