CE48 - Fondements du numérique : informatique, automatique, traitement du signal

Réponse efficace aux requêtes sous mises à jour – EQUUS

Résumé de soumission

Un des problèmes centraux en théorie des bases de données est l'évaluation efficace de requêtes, c'est-à-dire calculer le résultat d'une requête sur une base de données fournie en entrée. Ce domaine de recherche a une longue histoire et a mené à de nombreux résultats et directions, par exemple des algorithmes efficaces pour les requêtes d'agrégation, pour l'énumération des résultats, ou pour le calcul de la provenance. Cependant, la recherche théorique sur le sujet s'est concentrée sur des bases de données statiques, alors que les bases de données réelles sont des objets dynamiques et changent avec le temps. Pour cette raison, à chaque modification (même mineure) de la base de données sous-jacente, les bornes théoriques connues ne sont généralement pas meilleures que de réévaluer la requête en perdant toutes les informations calculées jusque là. Ceci ne correspond pas aux bases de données pratiques, qui calculent des index pour accélérer l'évaluation des requêtes et qui les maintiennent à jour quand les données sont modifiées.

Ce n'est que récemment que la communauté de recherche théorique s'est sérieusement intéressée à la complexité computationnelle de la réponse aux requêtes sous mises à jour. Certains travaux, notamment ceux des participants à ce projet, ont proposé des manières de gérer des mises à jour légères dans des contextes relativement simples, par exemple les requêtes conjonctives ou les requêtes sur des données arborescentes. L'objet du projet EQUUS est d'étudier de façon systématique comment maintenir des structures de données sous des mises à jour afin d'éviter un recalcul coûteux lorsque les données sont modifiées. Nous nous intéresserons notamment à prouver des garanties d'efficacité pour des algorithmes s'appliquant à des bases de données dynamiques. Nous chercherons aussi à montrer des bornes inférieures pour comprendre les ressources minimales nécessaires à de tels algorithmes. Nous étudierons ces questions pour différentes requêtes, en particulier les requêtes booléennes, les requêtes d'agrégation, et l'énumération de résultats. L'objectif d'EQUUS est de faire des mises à jour une question centrale en théorie des bases de données dès que de nouvelles classes de requêtes sont proposées.

EQUUS est structuré en trois tâches scientifiques portant sur des facettes différentes de la réponse aux requêtes sous mise à jour :
- Tâche 1 : Requêtes sur des données ayant une structure de graphe
- Tâche 2 : Mises à jour complexes
- Tâche 3 : Bornes inférieures
Il comprend également une tâche administrative (la Tâche 4) pour l'organisation du projet et la dissémination des résultats.

EQUUS est un projet binational qui implique des partenaires en France et en Allemagne : sa durée sera de 36 mois. Il est porté par 9 chercheurs renommés en théorie de la gestion de données (4 chercheurs allemands et 5 français) ayant un profil complémentaire. Le projet prévoit aussi le financement de deux thèses : une en Allemagne et l'autre en France. Les participants allemands sont affiliés à Humboldt-Universität zu Berlin et à Universität Bayreuth, et les participants français sont en Île de France (Inria Paris ; Télécom ParisTech ; IMJ ; Université Paris-Diderot) et en Hauts-de-France (CRIL, Lens ; Cristal, Lille). EQUUS est coordonné conjointement par Stefan Mengel (CNRS, France) et Nicole Schweikardt (HU Berlin).

L'objet d'EQUUS est de développer des collaborations entre les deux pays en finançant des rencontres et des visites régulières. Le projet permettra notamment aux étudiants en thèse d'effectuer des séjours prolongés dans l'autre pays afin d'apprendre au contact de chaque partenaire et développer leur réseau de collaborateurs à l'international.

Les résultats d'EQUUS seront publiés dans les meilleures conférences du domaine, par exemple PODS ou ICDT. De plus, tous les résultats seront également publiés dans des dépôts en libre accès et sur un site Web du projet.

Coordination du projet

Stefan Mengel (Centre de Recherche en Informatique de Lens)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Humboldt-Universität zu Berlin / Institut für Informatik
LTCI Télécom ParisTech Institut Mines Télécom
INRIA de Paris Centre de Recherche Inria de Paris
CRIL Centre de Recherche en Informatique de Lens

Aide de l'ANR 187 824 euros
Début et durée du projet scientifique : avril 2020 - 36 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter