Можно ли разложить ориентированный граф в список? - PullRequest
Новая
       148

Можно ли разложить ориентированный граф в список?

0 голосов
/ 25 января 2020

Это скорее теоретический вопрос, но для DAG возможно ли это сжать в список операций? Или это структура данных, которая не может быть разбита на плоский список в следующем порядке: 

STEPS = [
    filter A to country = 'US',
    (join A to B on A.id=B.id) AS c,
    filter C to...
]

Можно ли создать группу обеспечения доступности баз данных, которая не может быть разложена без потери информации?

1 Ответ

1 голос
/ 04 февраля 2020

Да, ориентированный ациклический c граф (DAG) может быть сведен в упорядоченный список операций, , если , фактически DAG представляет данные, проходящие через операции. Таким образом, упорядоченный список операторов присваивания и вызовов функций может быть выражен в виде DAG, и наоборот.

DAG для приведенного выше примера может выглядеть как 

+-----+     +-------------+
|     |  A  |   filter I1 | A'
|  A  |-----|1  to country|---+                    
|     |     |       ='US' |   |                                           
+-----+     +-------------+   |  +--------------+   +-----------+   +----------+
                              +--|1  join I1 to | C |   filter  | C'|   Result |
                                 |   I2 on I1.id|---|1  I1 to...|---|1    = I1 |
                              +--|2      = I2.id|   |           |   |          |
                  +-------+   |  +--------------+   +------- ---+   +----------+
                  |       | B |                                  
                  |   B   |---+
                  |       |
                  +-------+

В качестве альтернативы «Список операций» можно рассматривать как вызов вложенных функций, оцениваемых от наиболее глубоко вложенных до наименее глубоко вложенных. Например, 

Result = Fn3( Fn2( Fn1(A), B ) ).

Группа обеспечения доступности баз данных такая же, как и перерисованная здесь без отображения промежуточных переменных и с упрощенными именами функций. 

+-----+     +-------------+
|     |     |             |
|  A  |-----|1    Fn1     |---+                    
|     |     |             |   |                                        
+-----+     +-------------+   |  +--------------+   +-----------+   +----------+
                              +--|1             |   |           |   |          |
                                 |      Fn2     |---|1   Fn3    |---|1  Result |
                              +--|2             |   |           |   |          |
                  +-------+   |  +--------------+   +------- ---+   +----------+
                  |       |   |                                  
                  |   B   |---+
                  |       |
                  +-------+

Я не знаю ни одной ситуации, в которой информация будет потеряна при декомпозиции из DAG в «список операций». Эти две формы эквивалентны друг другу.

Практический пример того, как построить группы обеспечения доступности баз данных для представления списков операций, можно найти в IEC 61131-3: 2013 , который "определяет синтаксис и семантику языков программирования для программируемых контроллеров ..." Этот стандарт называет DAG сетью, определяемой как "максимальный набор взаимосвязанных графических c элементов" (в контексте частично упорядоченного набора ) и представляет правила оценки, в том числе правило: «Ни один элемент сети не должен оцениваться до тех пор, пока не будут оценены состояния всех его входов». Это правило обеспечивает основу для порядка операций.

...