KCODA - Knowledge COmpilation for Data Analysis

Coordinateur : Monsieur Florent Capelli Université de Lille CRIStAL

Équipe : LINKS du Groupe Thématique : DatInG.

Dates : 10/20 - 03/25

Résumé :

KCODA est une ANR JCJC dont le but est d’établir de nouveaux algorithmes permettant de résoudre des problèmes d’agrégation complexes en base de données grâce à des techniques issues de la compilation de connaissances.

Enjeux et objectifs

L’objectif principal de KCODA est de comprendre quels problèmes d’optimisation et d’apprentissage peuvent être résolus de façon plus efficace en exploitant le fait que les données utilisées sont structurées, ce qui est par exemple le cas lorsqu’elles sont générées par une requête de base de données. De nombreux algorithmes ont été proposés qui tirent parti du fait que la structure de la requête peut être exploitée pour réduire la complexité de l’approche naïve consistant à énumérer toutes les solutions de la requête avant de résoudre le problème en question. Nous proposons dans ce projet de réexpliquer ces résultats comme des manipulations élémentaires d’une structure de données permettant de représenter les solutions d’une requête de base de données sous forme factorisée. Nous étudierons ensuite la complexité d’autres problèmes plus complexes que nous tenterons de résoudre directement sur ces structures de données comme par exemple, la résolution de programme linéaire dont les variables sont les solutions d’une requête de base de données.

Abstract

KCODA is an ANR JCJC project which aims to design new algorithms for answering complex aggregation queries on databases using techniques and data structures from knowledge compilation.

Goal

The main goal of KCODA is to understand what optimization and learning problems can be solved efficiently when data is structured, which is the case when the data to be analysed is the answer set of a database query. Many algorithms exploits the structure of the query to solve aggregation problems more efficiently than the naive way of enumerating every answer before aggregating. In KCODA, we aim at explaining these aggregation algorithms as elementary operations on specialized data structure able to represent query answers in a factorized way. We also aim at using this unified framework to discover new tractable aggregation problems, such as solving linear programs whose variables are the answers of a database query.