Date Added: Mar 2011
The goal of Knowledge Compilation is to represent a Boolean expression in a format in which it can answer a range of online-queries in PTIME. The online-query of main interest to one is model counting, because of its application to query evaluation on probabilistic databases, but other online-queries can be supported as well such as testing for equivalence, testing for implication, etc. In this paper, the authors study the following problem. Given a database query q, decide whether its lineage can be compiled efficiently into a given target language.