  Conjunctive queries select and are expected to return certain tuples from a
relational database. We study the potentially easier problem of counting all
selected tuples, rather than enumerating them. In particular, we are interested
in the problem's parameterized and data complexity, where the query is
considered to be small or fixed, and the database is considered to be large. We
identify two structural parameters for conjunctive queries that capture their
inherent complexity: The dominating star size and the linked matching number.
If the dominating star size of a conjunctive query is large, then we show that
counting solution tuples to the query is at least as hard as counting
dominating sets, which yields a fine-grained complexity lower bound under the
Strong Exponential Time Hypothesis as well as a #W[2]-hardness result.
Moreover, if the linked matching number of a conjunctive query is large, then
we show that the structure of the query is so rich that arbitrary queries up to
a certain size can be encoded into it; this essentially establishes
#A[2]-completeness. Using ideas stemming from Lov\'asz, we lift complexity
results from the class of conjunctive queries to arbitrary existential or
universal formulas that might contain inequalities and negations on constraints
over the free variables. As a consequence, we obtain a complexity
classification that generalizes previous results of Chen, Durand, and Mengel
(ToCS 2015; ICDT 2015; PODS 2016) for conjunctive queries and of Curticapean
and Marx (FOCS 2014) for the subgraph counting problem. Our proof also relies
on graph minors, and we show a strengthening of the Excluded-Grid-Theorem which
might be of independent interest: If the linked matching number is large, then
not only can we find a large grid somewhere in the graph, but we can find a
large grid whose diagonal has disjoint paths leading into an assumed
node-well-linked set.
