15 lines
1.1 KiB
TeX
15 lines
1.1 KiB
TeX
%!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:
|