Connecting Width and Structure in Knowledge Compilation

Pierre Senellart 1 Antoine Amarilli 2 Mikaël Monet 2
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it is important to leverage some width parameters of the circuit, such as bounded treewidth or pathwidth, to convert the circuit to structured classes, e.g., deterministic structured NNFs (d-SDNNFs) or OBDDs. In this work, we show how to connect the width of circuits to the size of their structured representation, through upper and lower bounds. For the upper bound, we show how bounded-treewidth circuits can be converted to a d-SDNNF, in time linear in the circuit size. Our bound, unlike existing results, is constructive and only singly exponential in the treewidth. We show a related lower bound on monotone CNF or DNF formulas, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable). Specifically, any d-SDNNF for such a formula must be of exponential size in its treewidth; and the same holds for pathwidth when compiling to OBDDs. Our lower bounds, in contrast with most previous work, apply to any formula of this class, not just a well-chosen family. Hence, for our language of CNF and DNF, pathwidth and treewidth respectively characterize the efficiency of compiling to OBDDs and d-SDNNFs, that is, compilation is singly exponential in the corresponding width parameter. We conclude by applying our lower bound results to the task of query evaluation.
Type de document :
Pré-publication, Document de travail
32 pages, no figures, 39 references. Submitted. 2017
Liste complète des métadonnées
Contributeur : Pierre Senellart <>
Soumis le : mercredi 11 octobre 2017 - 10:14:06
Dernière modification le : mardi 19 juin 2018 - 10:44:02

Lien texte intégral


  • HAL Id : hal-01614551, version 1
  • ARXIV : 1709.06188


Pierre Senellart, Antoine Amarilli, Mikaël Monet. Connecting Width and Structure in Knowledge Compilation. 32 pages, no figures, 39 references. Submitted. 2017. 〈hal-01614551〉



Consultations de la notice