ACM SIGMOD Anthology TODS dblp.uni-trier.de

ProbView: A Flexible Probabilistic Database System.

Laks V. S. Lakshmanan, Nicola Leone, Robert B. Ross, V. S. Subrahmanian: ProbView: A Flexible Probabilistic Database System. ACM Trans. Database Syst. 22(3): 419-469(1997)
@article{DBLP:journals/tods/LakshmananLRS97,
  author    = {Laks V. S. Lakshmanan and
               Nicola Leone and
               Robert B. Ross and
               V. S. Subrahmanian},
  title     = {ProbView: A Flexible Probabilistic Database System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {22},
  number    = {3},
  year      = {1997},
  pages     = {419-469},
  ee        = {http://doi.acm.org/10.1145/261124.261131, db/journals/tods/LakshmananLRS97.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1871 KB]

References

[Barbara et al. 1992]
Daniel Barbará, Hector Garcia-Molina, Daryl Porter: The Management of Probabilistic Data. IEEE Trans. Knowl. Data Eng. 4(5): 487-502(1992) BibTeX
[Bell et al. 1994]
Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. J. ACM 41(6): 1178-1215(1994) BibTeX
[Blakeley et al. 1989]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[Boole 1854]
...
[Cavallo and Pittarelli 1987]
Roger Cavallo, Michael Pittarelli: The Theory of Probabilistic Databases. VLDB 1987: 71-81 BibTeX
[Dayal 1989]
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 BibTeX
[Dayal and Hwang 1984]
Umeshwar Dayal, Hai-Yann Hwang: View Definition and Generalization for Database Integration in a Multidatabase System. IEEE Trans. Software Eng. 10(6): 628-645(1984) BibTeX
[Dubois and prade 1988]
Didier Dubois, Henri Prade: Default Reasoning and Possibility Theory. Artif. Intell. 35(2): 243-257(1988) BibTeX
[Dumais 1993]
...
[Dyreson and Snodgrass 1993]
Curtis E. Dyreson, Richard T. Snodgrass: Valid-time Indeterminancy. ICDE 1993: 335-343 BibTeX
[Fenstad 1980]
...
[Gadia 1988]
Shashi K. Gadia: A Homogeneous Relational Model and Query Languages for Temporal Databases. ACM Trans. Database Syst. 13(4): 418-448(1988) BibTeX
[Garey and Johnson 1979]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[Güntzer et al. 1991]
Ulrich Güntzer, Werner Kießling, Helmut Thöne: New Directions For Uncertainty Reasoning In Deductive Databases. SIGMOD Conference 1991: 178-187 BibTeX
[Gupta et al. 1993]
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
[Hillier and Lieberman 1974]
...
[Imielinski and Lipski 1984]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[Iyengar et al. 1995]
...
[Han et al. 1992]
Jiawei Han, Yandong Cai, Nick Cercone: Knowledge Discovery in Databases: An Attribute-Oriented Approach. VLDB 1992: 547-559 BibTeX
[Harrison and Dietrich 1992]
John V. Harrison, Suzanne W. Dietrich: Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. Workshop on Deductive Databases, JICSLP 1992: 56-65 BibTeX
[Kemper et al. 1994]
Alfons Kemper, Christoph Kilger, Guido Moerkotte: Function Materialization in Object Bases: Design, Realization, and Evaluation. IEEE Trans. Knowl. Data Eng. 6(4): 587-608(1994) BibTeX
[Kießling et al. 1992]
Werner Kießling, Helmut Thöne, Ulrich Güntzer: Database Support for Problematic Knowledge. EDBT 1992: 421-436 BibTeX
[Kifer and Li 1988]
Michael Kifer, Ai Li: On the Semantics of Rule-Based Expert Systems with Uncertainty. ICDT 1988: 102-117 BibTeX
[Kolmogorov 1956]
...
[Lakshmanan 1994]
Laks V. S. Lakshmanan: An Epistemic Foundation for Logic Programming with Uncertainty. FSTTCS 1994: 89-100 BibTeX
[Lakshmanan and Sadri 1994a]
Laks V. S. Lakshmanan, Fereidoon Sadri: Probabilistic Deductive Databases. SLP 1994: 254-268 BibTeX
[Lakshmanan and Sadri 1994b]
Laks V. S. Lakshmanan, Fereidoon Sadri: Modeling Uncertainty in Deductive Databases. DEXA 1994: 724-733 BibTeX
[Lakshmanan et al. 1996]
...
[Lu et al. 1995]
James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351 BibTeX
[Ng and Subrahmanian 1993]
Raymond T. Ng, V. S. Subrahmanian: Probabilistic Logic Programming. Inf. Comput. 101(2): 150-201(1992) BibTeX
[Ng and Subrahmanian 1995]
Raymond T. Ng, V. S. Subrahmanian: Stable Semantics for Probabilistic Deductive Databases. Inf. Comput. 110(1): 42-83(1994) BibTeX
[Raju and Majumdar 1988]
K. V. S. V. N. Raju, Arun K. Majumdar: Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems. ACM Trans. Database Syst. 13(2): 129-166(1988) BibTeX
[Schmidt et al. 1987]
Helmut Schmidt, Nikolaus Steger, Ulrich Güntzer, Werner Kießling, Rüdiger Azone, Rudolf Bayer: Combining Deduction by Certainty with the Power of Magic. DOOD 1989: 103-122 BibTeX
[Silberschatz et al. 1991]
Abraham Silberschatz, Michael Stonebraker, Jeffrey D. Ullman: Database Systems: Achievements and Opportunities. Commun. ACM 34(10): 110-120(1991) BibTeX
[Thöne et al. 1995]
...
[Vardi 1985]
Moshe Y. Vardi: Querying Logical Databases. PODS 1985: 57-65 BibTeX

Referenced by

  1. Curtis E. Dyreson, Richard T. Snodgrass: Supporting Valid-Time Indeterminacy. ACM Trans. Database Syst. 23(1): 1-57(1998)
  2. Erich Grädel, Yuri Gurevich, Colin Hirsch: The Complexity of Query Reliability. PODS 1998: 227-234
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:21 2008