Comprendre comment transcrire une requête pour y répondre plus efficacement

Distinctions Informatique

Ah, le champ « Recherche » de votre site web préféré, il vous comprend et vous donne toujours les informations que vous cherchez en un temps record. Enfin… presque. En effet, les réponses sont en général obtenues en évaluant une requête sur une base de données. Pour ne pas attendre trop longtemps, tout un mécanisme est en œuvre pour transcrire votre demande dans le bon langage informatique, qui permettra d’activer les bons algorithmes pour obtenir la meilleure réponse dans les bases de données. C’est dans cette machinerie invisible que Pierre BourhisMichael Benediktet Michael Vanden Boom se sont illustrés, avec un des Best Paper Award obtenus à International Colloquium on Automata, Languages, and Programming (ICALP).

En gestion de l’information, un des problèmes majeurs est d’interroger efficacement les données. La méthode la plus classique est de stocker les données dans une base de données relationnelle (qui stockent les données sous forme d’un tableau) et de les interroger en écrivant une requête dans le langage SQL. Une approche pour interroger efficacement les données est d’établir des classes entre les différents types de demandes des utilisateurs, appelées requêtes. Ainsi, les requêtes ayant une forme particulière pourront être évaluées, c’est-à-dire obtenir une réponse, plus rapidement à l’aide d’algorithmes dédiés. Par exemple, les requêtes dites conjonctives acycliques obtiennent des réponses bien plus efficacement à l’aide d’un algorithme spécifique qu’avec les méthodes génériques. 

Bien sûr, il n’est pas réaliste de demander à un utilisateur de comprendre si sa question peut être écrite dans telle forme ou telle autre, et donc quels seraient les algorithmes adaptés pour y répondre efficacement. Certains travaux de recherche se concentrent donc sur le fait que ce soit l’ordinateur qui réalise par lui-même si la question de l’utilisateur peut être écrite dans une requête ayant une forme particulière, afin de profiter d’une réponse plus efficace, et que l’ordinateur trouve par lui-même la bonne classe de requêtes. 

Des travaux ont déjà été réalisés pour comprendre sous quelles conditions les requêtes peuvent être exprimables par la forme particulière des requêtes conjonctives acycliques. Dans le papier Characterizing Definability in Decidable Fixpoint Logics, ce problème a été généralisé dans un cadre bien plus général, dépassant les requêtes exprimables en SQL. Un cadre théorique a été développé permettant d’établir des équivalences, pour décider si une requête exprimable dans une logique L1 peut également être exprimable dans une logique L2. L’approche développée dans ce papier permet de trancher ce problème d’expression et d’équivalence de requêtes pour un très grand nombre de logiques L1 et L2 pour des logiques des propriétés particulières. Elle permet également de trouver la transcription de la requête originale dans la logique L2.

Publication : Characterizing Definability in Decidable Fixpoint Logics de Michael Benedikt1Pierre Bourhis 2Michael Vanden Boom1

  • 1 a b Department of Computer Science, University of Oxford, UK
  • 2 Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL - CNRS/Université de Lille/École Centrale de Lille)