This paper reports on recent advances in semantic query optimization. We focus
on the core class of conjunctive queries (CQs). Since CQ evaluation is
NP-complete, a long line of research has concentrated on identifying fragments
of CQs that can be efficiently evaluated. One of the most general such
restrictions corresponds to bounded generalized hypertreewidth, which extends
the notion of acyclicity. Here we discuss the problem of reformulating a CQ
into one of bounded generalized hypertreewidth. Furthermore, we study whether
knowing that such a reformulation exists alleviates the cost of CQ evaluation.
In case a CQ cannot be reformulated as one of bounded generalized
hypertreewidth, we discuss how it can be approximated in an optimal way. All
the above issues are examined both for the constraint-free case, and the case
where constraints, in fact, tuple-generating and equality-generating
dependencies, are present.