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 D KB ; 2) the problem is efficiently solved using D KB 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. D KB is a database, to be synthesized from KB by means of an appropriate view. Q is rewritten, thus obtaining Q r . We show syntactic restrictions on Q implying that a polynomial-size D KB and a first-order Q r 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 D KB or no first-order Q r exist (unless the PH collapses). Compilation to other complexity classes is also addressed.
complexity logic in databases deductive databases.