Abstract
It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the core dialect of DL-Lite. The proof exploits known properties of query matches in this logic and involves a query-dependent modification of the data. To obtain a more practical approach, we next propose a concrete polynomial-time algorithm for answering acyclic CQs based upon a rewriting into datalog. We also show how the algorithm can be extended to a larger class of (nearly acyclic) CQs. A preliminary evaluation of our proof-of-concept implementation suggests the interest of our approach for handling large acyclic CQs.