Abstract
Conjunctive Queries (CQ) is one of the most basic and studied query languages in database theory, and it corresponds to the primitive positive fragment of first-order logic. The evaluation problem for CQs is known to be NP-complete in combined complexity and W[1]-hard in parameterized complexity. However, some syntactic fragments such as acyclic CQs and CQs of bounded tree-width are known to be tractable: CQs from these fragments can be evaluated in polynomial time.
A natural optimization problem is whether a CQ can be rewritten into an equivalent CQ from a tractable fragment. In this talk I will report on some of the recent advances in this area for classes of acyclic and bounded tree-width CQs and in the presence of data constraints (e.g., functional dependencies, tgds, etc).