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 27 articles )

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

1 2 next

  1. Omri, Asma; Benouaret, Karim; Benslimane, Djamal; Omri, Mohamed Nazih: Towards an understanding of cloud services under uncertainty: a possibilistic approach (2018)
  2. Gullo, Francesco; Ponti, Giovanni; Tagarelli, Andrea; Greco, Sergio: An information-theoretic approach to hierarchical clustering of uncertain data (2017)
  3. Flesca, Sergio; Furfaro, Filippo; Parisi, Francesco: Consistency checking and querying in probabilistic databases under integrity constraints (2014)
  4. Doder, Dragan; Grant, John; Ognjanović, Zoran: Probabilistic logics for objects located in space and time (2013)
  5. Parisi, Francesco; Sliva, Amy; Subrahmanian, V. S.: A temporal database forecasting algebra (2013)
  6. Simari, Gerardo I.; Martinez, Maria Vanina; Sliva, Amy; Subrahmanian, V. S.: Focused most probable world computations in probabilistic logic programs (2012)
  7. Qin, Biao; Wang, Shan: Combining intensional with extensional query evaluation in tuple independent probabilistic databases (2011)
  8. Zhang, Wenjie; Lin, Xuemin; Zhang, Ying; Pei, Jian; Wang, Wei: Threshold-based probabilistic top-(k) dominating queries (2010) ioport
  9. Arai, Benjamin; Das, Gautam; Gunopulos, Dimitrios; Koudas, Nick: Anytime measures for top-(k) algorithms on exact and fuzzy data sets (2009) ioport
  10. Das Sarma, Anish; Benjelloun, Omar; Halevy, Alon; Nabar, Shubha; Widom, Jennifer: Representing uncertain data: models, properties, and algorithms (2009) ioport
  11. Kimelfeld, Benny; Kosharovsky, Yuri; Sagiv, Yehoshua: Query evaluation over probabilistic XML (2009) ioport
  12. Ré, Christopher; Suciu, Dan: The trichotomy of HAVING queries on a probabilistic database (2009) ioport
  13. van Keulen, Maurice; de Keijzer, Ander: Qualitative effects of knowledge rules and user feedback in probabilistic data integration (2009) ioport
  14. Zhang, Xi; Chomicki, Jan: Semantics and evaluation of top-(k) queries in probabilistic databases (2009) ioport
  15. Zhang, Yingqian; Manisterski, Efrat; Kraus, Sarit; Subrahmanian, V. S.; Peleg, David: Computing the fault tolerance of multi-agent deployment (2009)
  16. Benjelloun, Omar; Das Sarma, Anish; Halevy, Alon; Theobald, Martin; Widom, Jennifer: Databases with uncertainty and lineage (2008) ioport
  17. 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) ioport
  18. Kimmig, Angelika; Santos Costa, Vítor; Rocha, Ricardo; Demoen, Bart; De Raedt, Luc: On the efficient execution of ProbLog programs (2008)
  19. Magnani, Matteo; Montesi, Danilo: Management of interval probabilistic data (2008)
  20. Roelleke, Thomas; Wu, Hengzhi; Wang, Jun; Azzam, Hany: Modelling retrieval models in a probabilistic relational algebra with a new operator: The relational Bayes (2008) ioport

1 2 next