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) ioport
  7. Arai, Benjamin; Das, Gautam; Gunopulos, Dimitrios; Koudas, Nick: Anytime measures for top-$k$ algorithms on exact and fuzzy data sets (2009) ioport
  8. Das Sarma, Anish; Benjelloun, Omar; Halevy, Alon; Nabar, Shubha; Widom, Jennifer: Representing uncertain data: models, properties, and algorithms (2009) ioport
  9. Kimelfeld, Benny; Kosharovsky, Yuri; Sagiv, Yehoshua: Query evaluation over probabilistic XML (2009) ioport
  10. Ré, Christopher; Suciu, Dan: The trichotomy of HAVING queries on a probabilistic database (2009) ioport
  11. van Keulen, Maurice; de Keijzer, Ander: Qualitative effects of knowledge rules and user feedback in probabilistic data integration (2009) ioport
  12. Zhang, Xi; Chomicki, Jan: Semantics and evaluation of top-$k$ queries in probabilistic databases (2009) ioport
  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) ioport
  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) ioport
  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) ioport
  18. Dalvi, Nilesh; Suciu, Dan: Efficient query evaluation on probabilistic databases (2007) ioport
  19. Burdick, Doug; Deshpande, Prasad M.; Jayram, T.S.; Ramakrishnan, Raghu; Vaithyanathan, Shivakumar: OLAP over uncertain and imprecise data (2006) ioport
  20. Gal, Avigdor; Anaby-Tavor, Ateret; Trombetta, Alberto; Montesi, Danilo: A framework for modeling and evaluating automatic semantic reconciliation (2005) ioport

1 2 next