ProbView: a flexible probabilistic database system
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
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 restrictive combination 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 generic probabilistic relational algebra that neatly captures various strategies satisfying 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Foundations of the Theory of Probability
Brookes, B. C., & Kolmogorov, A. N. (1951) · The Mathematical Gazette · doi:10.2307/3611503 · Cited by 1,691
Incomplete Information in Relational Databases
Imieliński, T., & Lipski, W. (1984) · Journal of the ACM · doi:10.1145/1634.1886 · Cited by 1,013
Maintaining views incrementally
Gupta, A., Mumick, I. S., & Subrahmanian, V. S. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170066 · Cited by 654
Self-citationThe management of probabilistic data
Barbara, D., Garcia-Molina, H., & Porter, D. (1992) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.166990 · Cited by 449
Knowledge Discovery in Databases: An Attribute-Oriented Approach
Han, J., Cai, Y., & Cercone, N. J. (1992) · Very Large Data Bases · Cited by 447
Foundations of the Theory of Probability.
David, F. N., Kolmogorov, A. N., & Khintchine, A. (1952) · Biometrika · doi:10.2307/2332488 · Cited by 440
Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems
Raju, K. V. S. V. N., & Majumdar, A. K. (1988) · ACM Transactions on Database Systems · doi:10.1145/42338.42344 · Cited by 406
Probabilistic logic programming
Ng, R. T., & Subrahmanian, V. S. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90061-j · Cited by 357
Self-citationA homogeneous relational model and query languages for temporal databases
Gadia, S. K. (1988) · ACM Transactions on Database Systems · doi:10.1145/49346.50065 · Cited by 312
The Theory of Probabilistic Databases
Cavallo, R. E., & Pittarelli, M. (1987) · Very Large Data Bases · Cited by 273
Foundations of the theory of probability
Kolmogorov, A., & Morrison, N. (1956) · CERN Document Server (European Organization for Nuclear Research) · Cited by 167
Default reasoning and possibility theory
Didier Dubois, A., & Prade, H. M. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90014-8 · Cited by 108
Probabilistic deductive databases
Lakshmanan, L. V. S., & Sadri, F. (1994) · Cited by 95
Self-citationEfficient maintenance of materialized mediated views
Lu, J. J.-Q., Moerkotte, G., Schü, J., & Subrahmanian, V. S. (1995) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/223784.223850 · Cited by 76
Self-citation
Cited by
Efficient query evaluation on probabilistic databases
Dalvi, N., & Suciu, D. (2007) · The VLDB Journal · doi:10.1007/s00778-006-0004-3 · Cited by 962
Green, T. J., Karvounarakis, G., & Tannen, V. (2007) · Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1265530.1265535 · Cited by 812
“The papers on probabilistic databases [17, 33, 23] note the similarities with [19] but do not attempt a generalization.”
A Survey of Uncertain Data Algorithms and Applications
Aggarwal, C. C., & Yu, P. S. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.190 · Cited by 475
ULDBs: databases with uncertainty and lineage
Benjelloun, O., Sarma, A. D., Halevy, A. Y., & Widom, J. (2006) · doi:10.5555/1182635.1164209 · Cited by 447
Principles of dataspace systems
Halevy, A., Franklin, M., & Maier, D. (2006) · Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1142351.1142352 · Cited by 346
Metadata
- Authors
- Lakshmanan, L. V. S., Leone, N., Ross, R., & Subrahmanian, V. S.
- Venue
- ACM Transactions on Database Systems
- Published
- 1997-09
- Volume
- 22
- Issue
- 3
- Pages
- 419-469
- ISSN
- 0362-5915 (ISSN-L)
- 1557-4644
- OpenAlex
- W2024400846
- Cited by
- 338
- References
- 15
- FWCI
- 10.78
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.