Evaluation of conjunctive queries (CQs) is NP-complete, but becomes tractable
for syntactically defined fragments. One of the oldest and most studied such
fragments is the class of acyclic CQs. Here we look at the problem of semantic
acyclicity, i.e., given a CQ q, is there an acyclic CQ q' that is equivalent to
it? This notion is important in CQ evaluation, as semantically acyclic CQs can
be evaluated in polynomial time. The notion of semantic acyclicity itself is
decidable, with the same complexity as the usual static analysis tasks for CQs,
i.e., NP-complete. 

Unfortunately, semantic acyclic is not general enough for practical purposes,
as only CQs whose core is acyclic belong to this class. In this tutorial we
present two approaches that have been developed to make the notion more
flexible and take better advantage of the ideas that underlie it. These are
computing approximations and making use of semantic information in the form of
constraints. For approximations, we look at the case when q is not semantically
acyclic and explain how to find and evaluate those acyclic CQs q' that are as
"close" as possible to q in terms of containment. As for constraints, they
enrich semantic acyclicity since they can be applied on a CQ q to produce an
acyclic reformulation of it. We present results that establish the boundary of
decidability for semantic acyclicity under usual database constraints such as
tuple and equality-generating dependencies, and show their applicability in
query evaluation.