C'est plus une question théorique, mais pour un DAG est-il possible de condenser cela en une liste d'opérations ? Ou s'agit-il d'une structure de données qui ne peut pas être décomposée en une liste plate dans l'ordre de quelque chose comme :

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

Serait-il possible de construire un DAG qui ne puisse être décomposé sans perdre d'informations ?

0
David542 25 janv. 2020 à 02:30

1 réponse

Meilleure réponse

Oui, un graphe acyclique orienté (DAG) peut être condensé en une liste d'opérations ordonnée, si, en fait, le DAG représente le flux de données par des opérations. C'est-à-dire qu'une liste ordonnée d'instructions d'affectation et d'appels de fonction peut être exprimée sous la forme d'un DAG, et vice versa.

Un DAG pour l'exemple ci-dessus pourrait ressembler à

+-----+     +-------------+
|     |  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   |---+
                  |       |
                  +-------+

Alternativement, la "liste d'opérations" pourrait être considérée comme des appels de fonctions imbriquées, évalués du plus profondément imbriqué au moins profondément imbriqué. Par exemple,

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

Le DAG est le même, tel que redessiné ici sans afficher les variables intermédiaires et avec des noms de fonctions simplifiés.

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

Je ne suis au courant d'aucune situation dans laquelle des informations seraient perdues lors de la décomposition du DAG en "liste d'opérations". Les deux formes sont équivalentes.


Un exemple pratique de la façon de construire des DAG pour représenter des listes d'opérations peut être trouvé dans IEC 61131-3:2013< /a>, qui "spécifie la syntaxe et la sémantique des langages de programmation pour les automates programmables..." Cette norme appelle le DAG un réseau, défini comme "un ensemble maximal d'éléments graphiques interconnectés" (dans le contexte d'un ensemble partiellement ordonné) et présente des règles d'évaluation, y compris la règle selon laquelle « Aucun élément d'un réseau ne doit être évalué tant que les états de toutes ses entrées n'ont pas été évalués ». Cette règle constitue la base de l'ordre des opérations.

1
Hammersnout 4 févr. 2020 à 15:20