Requêtes d'Agrégation – Aggreg
State of the art
1 Aggregate queries for databases
2 Tractable query classes
3 Aggregation in constraint satisfaction
4 Online query answering on data streams
5 Probabilistic approximation algorithms
6 Aggregate path queries
7 Aggregation over incomplete data
Working Packages, Tasks, and Deliverables
P1 Offline aggregation algorithms
P2 Online aggregation algorithms
P3 Aggregation complexity
Project en cours.
P1:
Jcss’14 [15], Tcs’14 [16], Stacs’15 [8], Sat’15 [6], Sat’14 [9], PhD thesis Capelli. Icalp’15 [3], Pods’16 [4], Cikm’15 [1], Icde’16 [5], Edbt’16 [2],
P2:
Tcs’15 [14], Sofsem’16 [23], Master thesis Sakho, QuiXPath tool, PhD thesis Sebastian [22]. PhD project Sakho (2016-19). Lata’15 [21]. BigData’15 [13], Esa’15 [18], Tcs’16 [12]. Lata’15 [10],
P3:
Jcss’16 [19], Master thesis Blind. PhD project Vigny (2015-18).
Stacs’16 [20], Pods’14 [17]. Ijcai’16 [7].
Le projet AGGREG vise prioritairement le développement d’algorithmes efficaces pour évaluer des requêtes d’agrégation relatives à des bases de données et des flux de données.
Ces requêtes sont au centre de calculs de statistiques sur les données: Rdf, bases de données NoSQL, flux d'arbres de données en XML ou JSON, bases de données relationnelles et entrepôts de données.
Sachant que le comptage est à la base des requêtes d'agrégation, l'enjeu est de surmonter la difficulté algorithmique intrinsèque de nombreux problèmes de comptage (beaucoup d'entre eux sont #P-difficiles, c'est-à-dire parmi les plus difficiles des problèmes de comptage associés à la classe NP). Cela exclut des solutions générales et efficaces.
Au lieu de cela, nous proposons :
d'étudier la complexité de fragments expressifs de la classe des requêtes d’agrégation,
de rechercher des algorithmes performants pour les fragments traitables et des algorithmes d'approximation efficaces pour les fragments difficiles,
d'identifier les paramètres qu’il faut fixer pour accéder à un traitement efficace de problèmes réputés difficiles en toute généralité.
Nous appliquerons des méthodes issues de l'algèbre, des automates, des probabilités, de l'algorithmique et de la théorie de la complexité.
Coordination du projet
Joachim NIEHREN (Institut National de Recherche en Informatique et en Automatique (INRIA) Centre Lille - Nord Europe)
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
LIF Laboratoire d'Informatique Fondamentale
INRIA Centre Lille-Nord Europe Institut National de Recherche en Informatique et en Automatique (INRIA) Centre Lille - Nord Europe
IMJ-PRG Institut de Mathématiques de Jussieu-Paris Rive Gauche
Aide de l'ANR 423 587 euros
Début et durée du projet scientifique :
septembre 2014
- 48 Mois
