Jean-François Baget

Imaginons une ontologie contenant la connaissance « tous les mélomanes écoutent de la musique », ce qui peut s'écrire sous la forme d'une règle existentielle ecoute(X, Y), musique(Y) :- melomane(X)..

Une première façon de raisonner avec une telle ontologie est d'utiliser le chainage avant (ou saturation, ou chase). On part d'une base de faits (par exemple melomane(sebastien).), et on y rajoute toutes les connaissances qu'on peut en déduire en appliquant les règles (ici ecoute(sebastien, Y0), musique(Y0)). Lorsqu'on interroge la base de connaissances (base de faits + ontologie), on n'a plus qu'à interroger la base de faits saturée (c'est-à-dire une base de données), en oubliant l'ontologie.

La façon de raisonner qui nous intéresse pour ce stage est le chainage arrière (ou réécriture). Cette fois-ci on part de la requête (conjonctive) et on cherche tous les joueurs qui écoutent quelque chose, ce qu'on peut écrire : ?(X) :- joueur(X), ecoute(X, Y). Le but de la réécriture est de reformuler la requête de façon à ce que les réponses à la requête réécrite dans la base de faits initiale soient les même que celles de la requête initiale dans la base de faits saturée. Dans ce cas notre opérateur de récriture remarque que ecoute(X, Y) peut être prouvé si on prouve melomane(X) (c'est le rôle de notre unificateur), et une nouvelle requête est générée en effaçant la partie qui serait prouvée, et en rajoutant la partie qui reste à prouver. On obtient ainsi une requête qui est une disjonction de toutes les réécritures possibles, ici :

?(X) :- joueur(X), ecoute(X, Y) | joueur(X), melomane(X).

Nous pouvons aujourd'hui dans la plateforme Integraal évaluer des requêtes plus riches que les unions de requêtes conjonctives (et en particulier des unions de conjonctions d'unions...). Nous voulons profiter de cette expressivité accrue pour améliorer notre moteur de réécriture. En particulier nous faisions jusqu'à présent une réécriture de la forme:

?() :- P1, P2. se réécrit en ?() :- P1, P2 | P1, P3. où P2 est la partie de la requête qui serait prouvée par application d'une règle, P3 la partie qu'il faudrait prouver pour appliquer la règle, et P1 la partie de la requête non prouvée par l'application de la règle.

Nous souhaitons maintenant un opérateur de réécriture qui réécrit ?() :- P1, P2. en ?() :- P1, (P2 | P3).. Cette factorisation est très simple, donnée par le mécanisme de réécriture, et devrait nous donner une évaluation de requête plus rapide (ce qui reste à prouver). Mais de nombreux problèmes se posent...

L'évaluation de la requête est-elle vraiment plus rapide ? Dans tous les cas ? Peut-on identifier les cas où ce n'est pas efficace ? Les réécritures se faisant récursivement, il faudra trouver les unificateurs avec la nouvelle requête réécrite (pour l'instant l'unificateur ne gère pas les disjonctions, et ceci peut poser des problèmes techniques). Il serait également intéressant de comparer ce nouvel algorithme avec celui proposé par Mélanie König, dans le cas où on réécrit avec des règles compilables.

L'objectif prioritaire de ce stage est l'extension des unificateurs à ces requêtes plus générales. Suivants vos intérêts personnels, ce travail préalable pourra être complété par l'étude théorique des algorithmes obtenus (complexité), l'utilisation de langages de requêtes encore plus expressifs (par exemple négation) pour une meilleure optimisation, ou l'implémentation de ces algorithmes.

La plateforme Integraal, écrite en Java, permet de raisonner avec des bases de connaissances écrites dans le formalisme des règles existentielles. Depuis 2021, nous avons implémenté la possibilité d'ajouter aux raisonnements logiques des “fonctions utilisateurs” écrites en Java. Ainsi, nous pouvons donc évaluer la requête suivante:

?(P, Y) :- birthday(P, D), Y = extractYearFromDate(D).

Cette requête retourne toutes les paires (Personne, Année) où les personnes et leur date de naissance sont extraites d’une table birthday, et l'année de naissance est extraite de la date par une fonction, écrite en java par le concepteur de la base de connaissances.

Depuis cette année, nous disposons également d'une librairie écrite en Python permettant d'accéder à Integraal: Py4Graal. Nous avons jugé celà nécessaire pour offrir la possibilité d'utiliser Integraal à des utilisateurs ne maitrisant pas Java. Cependant, ces utilisateurs, si ils décident d'utiliser des “fonctions utilisateurs”, doivent encore écrire celles-ci en Java…

Le but de ce stage est dans un premier temps d'évaluer différentes solutions pour permettre à ces utilisateurs d'écrire du code python qui sera appelé par la VM java. Il en existe de nombreuses, dont: Jython, JEP, GraalVM, RPC (par exemple avec FastAPI)… Les tests à réaliser par l'étudiant devront tenir compte des contraintes suivantes:

• la phase de compilation/liaison du code python peut ne pas être rapide, puisqu'elle ne sera réalisée qu'une fois à l'analyse de la requête
• la phase d’exécution, par contre, doit être la plus rapide possible, puisqu'elle peut être appelée un très grand nombre de fois
• il serait utile que la solution proposée puisse facilement s'adapter à d'autres langages, si, par exemple, notre utilisateur souhaitait écrire ses fonctions en C++.

Dans un second temps, l'étudiant devra s'inspirer de la méthode utilisée dans Intégraal (un fichier json de description de la fonction) pour lier une fonction utilisateur java à un programme logique Integraal, afin de proposer et d'implémenter une méthode similaire (et la plus générique possible) pour les fonctions Python.

Supposons que nous souhaitions interroger une base de connaissances avec la requête conjonctive suivante:

?(V) :- human(U), parent(U, V). %% queries all parents of a human

Nous avons pour l'instant récupéré toutes les réponses à cette requête dans une base de faits F. Nous saturons la base de faits F avec la règle suivante:

human(X) :- man(X). %% every man is a human

Imaginons maintenant que nous ayons man(bob) et man(sam) dans la base de faits F. La saturation va créer deux nouveaux atomes: human(bob) et human(sam). Et ceci nous donnera (peut-être) de nouvelles réponses à notre requête. Il faut donc réévaluer la requête, ce qui, malheureusement, mènera à reparcourir le même espace de recherche que la première fois.

L'objectif est donc de trouver une requête reformulée qui nous donne toutes les nouvelles réponses, le moins possible d'anciennes réponses, et seulement des réponses.

Une solution (théorique) avait été proposée en 2004. En utilisant les unificateurs par pièce, il est possible de reformuler la requête afin de ne prendre en compte que les connaissances qui ont été rajoutées par la saturation. Ainsi, au lieu de réévaluer la requête initiale, il suffit d'évaluer la requête:

?(V) :- parent(bob, V) | parent(sam, V). %% queries parents of sam or parents of bob

Pourtant, les tests effectués sous InteGraal (notre plateforme de raisonnement, écrite en Java) n'ont jamais pu mettre en évidence un quelconque gain d'efficacité en utilisant cette reformulation. Notre interprétation est que les sous-requêtes parent(bob, V) et parent(sam, V) sont évaluées de façon indépendante et que, lorsqu'elles sont plus complexes, elles parcourent inutilement les mêmes parties de l'espace de recherche.

Integraal a depuis évolué. Il est possible, maintenant, d'exprimer notre requête reformulée de la façon suivante (en utilisant des sous-requêtes disjonctives):

?(V) :- parent(U, V), (U = bob | U = sam).

où même (en utilisant des fonctions calculées):

?(V) :- parent(U, V), #isMemberOf(U, bob, sam).

Le travail de développement du stagiaire sera organisé en trois parties:

• comprendre le papier de 2004, les dépendances, et la reformulation, et implémenter ces nouvelles façons de coder la requête reformulée (la plupart des méthodes difficiles à coder sont déjà dans Integraal)
• mettre en place un protocole de test pour évaluer l'efficacité de cette nouvelle méthode
• si aucun gain d'efficacité n'est décelé, voir si ce n'est pas du à l'implémentation naïve des sous-requêtes disjonctives dans Integraal. Dans ce cas, on pourra s'inspirer de différentes optimisations présentes dans les BD relationnelles.

Pour charger les objets sur lesquels elle va raisonner, notre plateforme Integraal utilise un format textuel: DLGP. Nous souhaitons aujourd'hui utiliser des objets plus complexes, et c'est pourquoi nous étudions en ce moment une extension du langage, DLGPE. Le travail qui a pour l'instant été réalisé sur ce langage inclut les développements suivants:

• une grammaire écrite en ANTLR4, ainsi qu'un visiteur pouvant appeler les constructeurs d'objets Integraal en parcourant l'AST (Abstract Syntax Tree) généré par ANTLR4
• une première implémentation du Language Server Protocol (LSP) de Microsoft, qui permet d'envoyer les résultats de l'analyse sémantique d'un document DLGPE à un client (utilisation de LSP4J)
• un éditeur JavaFX implémentant le client LSP afin d'afficher les erreurs et d'assurer la coloration (sémantique) du document.

Le problème actuel est l'édition de très grands documents DLGPE. En l'état actuel, le client LSP de l'éditeur, à chaque modification du document, envoie l'ensemble du document au serveur, qui réanalyse l'ensemble de ce document avant de renvoyer le résultat de cette analyse au client. Ceci ne pose pas de problème pour des fichiers de quelques dizaines, voire centaines de lignes, mais peut vite ralentir le système dans le cas de gros fichiers.

Heureusement, LSP prévoit que le client puisse n'envoyer que la partie modifiée d'un document depuis la dernière transaction. Il faudra alors repérer la partie de l'AST généré par ANTLR4 concernée par la modification, recalculer l'AST sur cette partie modifiée, et intégrer les nouvelles informations à envoyer au client dans une sauvegarde des données envoyées lors de la dernière transaction.

Le but de ce stage est de déterminer très précisément la partie de l'AST qui doit être regénéré après une modification du document (attention, certaines instructions en DLGPE ont une portée globale), avant d'implémenter correctement cette optimisation en utilisant LSP4J en Java. Une ADT Inria commençant en janvier 2026 autour de DLGPE, le stagiaire pourra bénéficier du soutien des ingénieurs Inria du SED.

Contexte

Integraal est un moteur de raisonnement fondé sur les règles existentielles. Le calcul des conséquences et des réponses aux requêtes repose sur des homomorphismes, qui associent les variables d'une requête ou du corps d'une règle à des termes : par exemple {X : a, Y : b, Z : T}.

Pour mieux capturer des structures hiérarchiques (résultats groupés, agrégations, sous-explications, etc.), il devient nécessaire de passer de ces homomorphismes “plats” à des tree_homomorphisms, de la forme : {X : a, Y : T, Z : [{U : a, V : b}, {U : c, V : W}]}, c'est-à-dire des homomorphismes dont certaines composantes sont elles-mêmes des collections d'homomorphismes organisées de manière arborescente.

Par ailleurs, Integraal offre un mécanisme de vues pour interroger des sources de données hétérogènes (SQL, RDF, CSV, JSON, …). L'objectif de ce stage est d'exploiter ces capacités pour construire un serveur de pages web dynamiques entièrement piloté par des règles existentielles.

Objectifs du stage

Le stage vise à :

1. Introduire les tree_homomorphisms dans Integraal
   • Représenter ces nouveaux objets dans le code du moteur.
   • Adapter les interfaces existantes des homomorphismes afin d'assurer la cohérence entre homomorphismes “plats” et arborescents.
   • Modifier le mécanisme de réponse aux requêtes pour qu’il puisse produire et manipuler des tree_homomorphisms.
2. Étendre le langage de requêtes
   • Concevoir et implémenter des requêtes capables de retourner des tree_homomorphisms.
   • Étudier, si possible, l'impact de ces nouvelles réponses sur l'expressivité et les performances (par exemple en vue d'opérateurs d'agrégation fondés logiquement).
3. Définir une application démonstratrice pour le web
   • Proposer une petite bibliothèque permettant de lier :
     • un pattern HTML (gabarit de fragment de page),
     • une requête Integraal dont chaque résultat remplit une instance du pattern.
   • Montrer comment, dans le cas de règles existentielles fes et de requêtes sans contexte, le chaînage avant peut produire des pages statiques pré-calculées.
   • Illustrer le tout sur un exemple “vitrine” choisi avec le ou la stagiaire, mettant en avant la compacité du code et la puissance du moteur logique.

Programme de travail indicatif

1. Prise en main d'Integraal et du formalisme des règles existentielles Comprendre la représentation actuelle des homomorphismes et le pipeline de réponse aux requêtes.
2. Conception et implémentation des tree_homomorphisms Définition des structures de données, adaptation des interfaces, tests unitaires.
3. Adaptation des requêtes et de la génération de réponses Support des tree_homomorphisms dans le moteur de requêtes, expérimentation sur de petits cas d'usage.
4. Conception de la bibliothèque web et réalisation de l’exemple applicatif Définition du format des patterns HTML, intégration avec Integraal, développement d'un exemple démonstrateur documenté.

Profil recherché

• Niveau M2 en informatique (ou équivalent).
• Intérêt pour la logique, les langages de requêtes et/ou les systèmes de raisonnement.
• Bonnes compétences en programmation objet (le moteur Integraal est actuellement développé en Java).
• Goût pour la modélisation et la conception de petites bibliothèques logicielles.

Le stage offre un terrain d'expérimentation à l'interface entre raisonnement logique, ingénierie de logiciels et génération de contenus web, avec des perspectives d'extensions théoriques (agrégations, analyse de schémas de règles) au-delà de la durée du stage.