Just-In-Time Compilation of Knowledge Bases

Since the first principles of Knowledge Compilation (KC), most of the work    has been focused in finding a good compilation target language in terms of    compromises between compactness and expressiveness. The central idea    remained unchanged in the last fifteen years: an off-line, very hard, stage,    allows to ``compile'' the initial theory in order to guarantee    (theoretically) an efficient on-line stage, on a set of predefined queries    and operations.  We propose a new ``Just-in-Time'' approach    for KC. Here, any Knowledge Base (KB) will be immediately available for    queries, and the effort spent on past queries will be partly amortized for    future ones.  To guarantee efficient answers, we rely on the    tremendous progresses made in the practical solving    of SAT and incremental SAT applicative problems. Even if each query may    be theoretically hard, we  show that our approach outperforms    previous KC approaches on the set of classical problems used in the field,    and allows to handle problems that are out of the scope of current    approaches.