Knowledge compilation = Query rewriting + View synthesis

In Knowledge Compilation (KC) an intractable deduction problem KB ⊨ f is split into two phases: 1) KB is preprocessed, thus obtaining a data structure DKB; 2) the problem is efficiently solved using DKB and f. Our goal is to study KC in the context of relational databases: Both KB and f are represented as databases, and '⊨' is represented as a query Q in second-order logic. DKB is a database, to be synthesized from KB by means of an appropriate view. Q is rewritten, thus obtaining Qr. We show syntactic restrictions on Q implying that a polynomial-size DKB and a first-order Qr exist, which imply that phase 2 can be done in polynomial time. We also present classes of queries (in some sense complementary to the former ones) for which either no polynomial-size DKB or no first-order Qr exist (unless the PH collapses). Compilation to other complexity classes is also addressed.