Knowledge Compilation for Data Analysis – KCODA

Our method is based on the fact that one can often represent every answer of a database query in a factorized, yet tractable way. To do so, one can use data structure inspired by the ones used in knowledge compilation. These data structures have originally been used to represent Boolean functions in a way that is more succinct than its truth table. Yet, they still support efficient operations such as model counting. These data structures can be generalized to represent database tables on non-Boolean domains, and appear in the literature under the name of Factorized Databases, introduced by Dan Olteanu. These data structures have how never been systematically studied. We aim at conducting such a study in order to unify and generalize many existing results in data base theory that are spilled over several papers and to propose in-database implementations.

The goal of KCODA is to study how succinct representation of data sets can be used to solve various optimization problems and AI tasks that are relying on big data sets. We propose to use data structures studied in the field of Knowledge Compilation that can succinctly represent data sets by factorizing common part while still allowing efficient analyses of the data they represent. The first goal of KCODA is to study how one can solve optimization and learning problems efficiently on these representations. The second goal of KCODA is to provide better integration of these techniques in Database Management Systems by improving the algorithmic techniques to build such factorized representations to represent the answer set of a database query and by providing in-database encoding of these representations.