%!TEX root=./main.tex
\section{Conclusions and Future Work}\label{sec:concl-future-work}

We have studied the problem of calculating the expected multiplicity of a bag-query result tuple, 
 a problem that has a practical application in probabilistic databases over multisets. 
We show that under various parameterized complexity hardness results/conjectures computing the expected multiplicities exactly is not possible in time linear in the corresponding deterministic query processing time.
We prove that it is possible to approximate the expectation of a lineage polynomial in linear time
 in the deterministic query processing over TIDBs and BIDBs (assuming that there are few cancellations).
Interesting directions for future work include development of a dichotomy for bag \abbrPDB\xplural.  While we can handle higher moments (this follows fairly easily from our existing results-- see \Cref{sec:momemts}), more general approximations are an interesting area for exploration, including those for more general data models. 

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: