  In this paper, we study the complexity of evaluating Conjunctive Queries with
negation (\cqneg). First, we present an algorithm with linear preprocessing
time and constant delay enumeration for a class of CQs with negation called
free-connex signed-acyclic queries. We show that no other queries admit such an
algorithm subject to lower bound conjectures. Second, we extend our algorithm
to Conjunctive Queries with negation and aggregation over a general semiring,
which we call Functional Aggregate Queries with negation (\faqneg). Such an
algorithm achieves constant delay enumeration for the same class of queries,
but with a slightly increased preprocessing time which includes an inverse
Ackermann function. We show that this surprising appearance of the Ackermmann
function is probably unavoidable for general semirings, but can be removed when
the semiring has specific structure. Finally, we show an application of our
results to computing the difference of CQs.
