EnglishCommencer

Datalog : récursivité et négation

Règles récursives, évaluation jusqu'au point fixe, règles sûres, négation stratifiée et équivalent SQL avec WITH RECURSIVE.

  • 23 cartes
  • 4 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Mises en situation

Quelques cartes du deck

  • Fermeture transitive : de quoi s'agit-il ?

    Voir la réponse

    Relation qui contient toutes les paires reliées par un chemin de n'importe quelle longueur dans une relation de départ.

    Si a→b et b→c, la fermeture contient aussi a→c. Une seule règle récursive la calcule en Datalog, alors qu'un SELECT simple ne le peut pas.

  • Arcs : a→b, b→c, c→d. Règles : chemin(X, Y) :- arc(X, Y). et chemin(X, Z) :- arc(X, Y), chemin(Y, Z). Combien de faits chemin contient le point fixe ?

    • 6
    • 3
    • 5
    • 12
    Voir la réponse

    6

    Tour 1 : (a,b), (b,c), (c,d). Tour 2 : (a,c) et (b,d). Tour 3 : (a,d). Tour 4 : rien de nouveau. Soit 3 + 2 + 1 = 6 paires. 3 s'arrête aux arcs, 5 oublie (a,d), et 12, toutes les paires de nœuds distincts, supposerait des arcs dans les deux sens.

  • On évalue un programme Datalog tour par tour et on s'arrête quand un tour ne déduit … : c'est le ….

    Voir la réponse

    On évalue un programme Datalog tour par tour et on s'arrête quand un tour ne déduit aucun fait nouveau : c'est le point fixe.

    Le dernier tour ne sert qu'à constater que plus rien ne change.

  • Point fixe : de quoi s'agit-il ?

    Voir la réponse

    Ensemble de faits atteint quand un nouveau tour d'application des règles ne déduit plus rien de nouveau.

    Sans fonction ni calcul, le nombre de faits possibles est fini : l'évaluation s'arrête toujours, même avec des cycles.

  • Le moteur refuse la règle p(X, Y) :- q(X). en la déclarant non sûre. Quelle réparation est juste ?

    • p(X, Y) :- q(X), not r(Y).
    • p(X, Y) :- q(X), r(X, Y).
    • p(X, Y) :- not q(X).
    • p(X, Y) :- q(X), Y > 0.
    Voir la réponse

    p(X, Y) :- q(X), r(X, Y).

    Y doit apparaître dans un atome positif du corps pour avoir un ensemble de valeurs fini, ici r(X, Y). Ni une négation ni une comparaison comme Y > 0 ne lient une variable.

Réviser ce deck