ProbView

ProbView: a flexible probabilistic database system. Probability theory is mathematically the best understood paradigm for modeling and manipulating uncertain information. Probabilities of complex events can be computed from those of basic events on which they depend, using any of a number of strategies. Which strategy is appropriate depends very much on the known interdependencies among the events involved. Previous work on probabilistic databases has assumed a fixed and restrictivecombination strategy (e.g., assuming all events are pairwise independent). In this article, we characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory. (1) We propose a probabilistic relational data model and a genericprobabilistic relational algebra that neatly captures various strategiessatisfying the postulates, within a single unified framework. (2) We show that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra. (3) We establish various containments and equivalences between algebraic expressions, similar in spirit to those in classical algebra. (4) We develop algorithms for maintaining materialized probabilistic views. (5) Based on these ideas, we have developed a prototype probabilistic database system called ProbView on top of Dbase V.0. We validate our complexity results with experiments and show that rewriting certain types of queries to other equivalent forms often yields substantial savings.

This software is also peer reviewed by journal TOMS.


References in zbMATH (referenced in 24 articles )

Showing results 1 to 20 of 24.
Sorted by year (citations)

1 2 next

  1. Flesca, Sergio; Furfaro, Filippo; Parisi, Francesco: Consistency checking and querying in probabilistic databases under integrity constraints (2014)
  2. Doder, Dragan; Grant, John; Ognjanović, Zoran: Probabilistic logics for objects located in space and time (2013)
  3. Parisi, Francesco; Sliva, Amy; Subrahmanian, V.S.: A temporal database forecasting algebra (2013)
  4. Simari, Gerardo I.; Martinez, Maria Vanina; Sliva, Amy; Subrahmanian, V.S.: Focused most probable world computations in probabilistic logic programs (2012)
  5. Qin, Biao; Wang, Shan: Combining intensional with extensional query evaluation in tuple independent probabilistic databases (2011)
  6. Zhang, Wenjie; Lin, Xuemin; Zhang, Ying; Pei, Jian; Wang, Wei: Threshold-based probabilistic top-$k$ dominating queries (2010)
  7. Arai, Benjamin; Das, Gautam; Gunopulos, Dimitrios; Koudas, Nick: Anytime measures for top-$k$ algorithms on exact and fuzzy data sets (2009)
  8. Das Sarma, Anish; Benjelloun, Omar; Halevy, Alon; Nabar, Shubha; Widom, Jennifer: Representing uncertain data: models, properties, and algorithms (2009)
  9. Kimelfeld, Benny; Kosharovsky, Yuri; Sagiv, Yehoshua: Query evaluation over probabilistic XML (2009)
  10. Ré, Christopher; Suciu, Dan: The trichotomy of HAVING queries on a probabilistic database (2009)
  11. van Keulen, Maurice; de Keijzer, Ander: Qualitative effects of knowledge rules and user feedback in probabilistic data integration (2009)
  12. Zhang, Xi; Chomicki, Jan: Semantics and evaluation of top-$k$ queries in probabilistic databases (2009)
  13. Zhang, Yingqian; Manisterski, Efrat; Kraus, Sarit; Subrahmanian, V.S.; Peleg, David: Computing the fault tolerance of multi-agent deployment (2009)
  14. Benjelloun, Omar; Das Sarma, Anish; Halevy, Alon; Theobald, Martin; Widom, Jennifer: Databases with uncertainty and lineage (2008)
  15. Candan, K.Selçuk; Cao, Huiping; Qi, Yan; Sapino, Maria Luisa: System support for exploration and expert feedback in resolving conflicts during integration of metadata (2008)
  16. Magnani, Matteo; Montesi, Danilo: Management of interval probabilistic data (2008)
  17. Roelleke, Thomas; Wu, Hengzhi; Wang, Jun; Azzam, Hany: Modelling retrieval models in a probabilistic relational algebra with a new operator: The relational Bayes (2008)
  18. Dalvi, Nilesh; Suciu, Dan: Efficient query evaluation on probabilistic databases (2007)
  19. Burdick, Doug; Deshpande, Prasad M.; Jayram, T.S.; Ramakrishnan, Raghu; Vaithyanathan, Shivakumar: OLAP over uncertain and imprecise data (2006)
  20. Gal, Avigdor; Anaby-Tavor, Ateret; Trombetta, Alberto; Montesi, Danilo: A framework for modeling and evaluating automatic semantic reconciliation (2005)

1 2 next