  We study the complexity of evaluating queries on probabilistic databases
under bag semantics. We focus on self-join free conjunctive queries, and
probabilistic databases where occurrences of different facts are independent,
which is the natural generalization of tuple-independent probabilistic
databases to the bag semantics setting. For set semantics, the data complexity
of this problem is well understood, even for the more general class of unions
of conjunctive queries: it is either in polynomial time, or #P-hard, depending
on the query (Dalvi & Suciu, JACM 2012).
  A reasonably general model of bag probabilistic databases may have unbounded
multiplicities. In this case, the probabilistic database is no longer finite,
and a careful treatment of representation mechanisms is required. Moreover, the
answer to a Boolean query is a probability distribution over (possibly all)
non-negative integers, rather than a probability distribution over { true,
false }. Therefore, we discuss two flavors of probabilistic query evaluation:
computing expectations of answer tuple multiplicities, and computing the
probability that a tuple is contained in the answer at most k times for some
parameter k. Subject to mild technical assumptions on the representation
systems, it turns out that expectations are easy to compute, even for unions of
conjunctive queries. For query answer probabilities, we obtain a dichotomy
between solvability in polynomial time and #P-hardness for self-join free
conjunctive queries.
