The Theory of Probabilistic Databases.

@inproceedings{DBLP:conf/vldb/CavalloP87,
  author    = {Roger Cavallo and
               Michael Pittarelli},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {The Theory of Probabilistic Databases},
  booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
               Large Data Bases, September 1-4, 1987, Brighton, England},
  publisher = {Morgan Kaufmann},
  year      = {1987},
  isbn      = {0-934613-46-X},
  pages     = {71-81},
  ee        = {db/conf/vldb/CavalloP87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A theory of probabilistic databases is outlined. This theory is one component of an integrated approach to data-modelling that accomodates both probabilistic and relational data. In fact, many of the results presented here were developed in the context of a framework for structural modelling of systems. Much that is fundamental to relational database theory was also developed in this context, and previous to the introduction by Codd of the relational model ofdata.

Probabilistic databases can store types of information that cannot be represented using the relational model. Probabilistic databases may also be viewed as generalisations of relational databases; any relational database can be represented without loss of information by a probabilistic database. A number of relational database concepts are shown to have probabilistic counterparts. In many cases, it is preferable to deal with the probabilistic formulation of a concept even when applying it to a relational database. For example, we define a new project-join mapping for relational databases that is based on transforming a relational to a probabilistic database. This mapping is shown to have more fixed points than the standard one.

Copyright © 1987 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[Aczel & Daroczy 1975]

...

[Ashby 1956]

...

[Ashby 1965]

...

[Bishop et al, 1975]

...

[Bourbaki 1954]

...

[Brodie 1984]

...

[Brown 1959]

David T. Brown: A Note on Approximations to Discrete Probability Distributions. Information and Control 2(4): 386-392(1959) BibTeX

[Cavallo 1980]

...

[Cavallo & Klir 1979a]

...

[Cavallo & Klir 1979b]

...

[Cavallo & Klir 1981]

...

[Codd 1970]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Denning 1982]

Dorothy E. Denning: Cryptography and Data Security. Addison-Wesley 1982
BibTeX

[Fagin 1977]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[Fagin 1983]

Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX

[Fagin et al, 1982]

Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX

[Good 1983]

...

[Higashi 1984]

...

[Khinchin 1957]

...

[Kolmogorov 1965]

...

[Kullback 1959]

...

[Kumar et al, 1986]

...

[Lewis 1959]

Philip M. Lewis II: Approximating Probability Distributions to Reduce Storage Requirements. Information and Control 2(3): 214-225(1959) BibTeX

[Madden & Ashby 1972]

...

[Maier 1983]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[Malvestuto 1983]

Francesco M. Malvestuto: Theory of random observables in relational data bases. Inf. Syst. 8(4): 281-289(1983) BibTeX

[Nambiar 1980]

K. K. Nambiar: Some Analytic Tools for the Design of Relational Database Systems. VLDB 1980: 417-428 BibTeX

[Ullman 1982]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Wiener 1914]

...

Referenced by

1. Curtis E. Dyreson, Richard T. Snodgrass: Supporting Valid-Time Indeterminacy. ACM Trans. Database Syst. 23(1): 1-57(1998)
2. 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)
3. Debabrata Dey, Sumit Sarkar: Extended SQL Support for Uncertain Data. ER 1997: 102-112
4. Debabrata Dey, Sumit Sarkar: A Probabilistic Relational Model and Algebra. ACM Trans. Database Syst. 21(3): 339-369(1996)
5. Simon Parsons: Current Approaches to Handling Imperfect Information in Data and Knowledge Bases. IEEE Trans. Knowl. Data Eng. 8(3): 353-372(1996)
6. Arbee L. P. Chen, Jui-Shang Chiu, Frank Shou-Cheng Tseng: Evaluating Aggregate Operations Over Imprecise Data. IEEE Trans. Knowl. Data Eng. 8(2): 273-284(1996)
7. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
8. Michael Pittarelli: An Algebra for Probabilistic Databases. IEEE Trans. Knowl. Data Eng. 6(2): 293-303(1994)
9. Francesco M. Malvestuto: Statistical versus Relational Join Dependencies. SSDBM 1994: 64-73
10. Daniel Barbará, Hector Garcia-Molina, Daryl Porter: The Management of Probabilistic Data. IEEE Trans. Knowl. Data Eng. 4(5): 487-502(1992)
11. Suk Kyoon Lee: Imprecise and Uncertain Information in Databases: An Evidential Approach. ICDE 1992: 614-621
12. W. Bruce Croft, Howard R. Turtle: Retrieval of Complex Objects. EDBT 1992: 217-229
13. Norbert Fuhr: A Probabilistic Framework for Vague Queries and Imprecise Information in Databases. VLDB 1990: 696-707
14. Daniel Barbará, Hector Garcia-Molina, Daryl Porter: A Probalilistic Relational Data Model. EDBT 1990: 60-74