Computing event probability in probabilistic databases

The problem of computing event probability originates from the probability theory. It has been extensively studied in the artificial intelligence area, which has proven its exponential worst-case time complexity. In the data management field, along with the consistently emerging uncertain data to be managed and queried, probabilistic databases enter the playground, where computing event probability again becomes a key issue to be resolved. Facing a huge volume of probabilistic data, a computational tractable and practical solution is a must. In this paper, we survey existing strategies developed in the probabilistic database field, which fall into two categories, namely, exact solutions and approximation solutions. We also discuss some possible improvement based on the existing approaches. It is our hope that this survey work could stimulate the discussion and re-examination of the classic problem among interdisciplinary researchers in math, artificial intelligence, and data management towards compromised high-quality solutions.