2009 ProbabilisticDatabases

(Dalvi et al., 2009) ⇒ Nilesh Dalvi, Christopher Ré, and Dan Suciu. (2009). “Probabilistic Databases: diamonds in the dirt.” In: Communications of the ACM, 52(7). doi:10.1145/1538788.1538810

Subject Headings: Probabilistic Data Record Set.

Notes

Quotes

Facet 1: Semantics and Representation

The de facto formal semantics of a probabilistic database is the possible worlds model.^{[Dalvi & Suciu, 2007]} By contrast, there is no agreement on a representation system, instead there are several approaches covering a spectrum between expressive power and usability.^{[Benjelloun et al., 2008]} A key concept in most representation systems is that of lineage, which is derived from early work on incomplete databases by Immelinski and Lipski.^{[Imielinski & Lipski, 1984]}

Possible Worlds Semantics. In its most general form, a probabilistic database is a probability space over the possible contents of the database. It is customary to denote a (conventional) relational database instance with the letter I. Assuming there is a single table in our database, I is simply a set of tuples (records) representing that table; this is a conventional database. A probabilistic database is a discrete probability space PDB = (W, P), where W = {I₁,I₂, ..., I_n} is a set of possible instances, called possible worlds, and P: W → [0, 1] is such that Σ_j=1,nP(I_j) = 1. In the terminology of networks of belief, there is one random variable for each possible tuple whose values are 0 (meaning that the tuple is not present) or 1 (meaning that the tuple is present), and a probabilistic database is a joint probability distribution over the values of these random variables. *... Consider some tuple t (we use interchangeably the terms tuple and record in this article). The probability that the tuple belongs to a randomly chosen world is P(t) = ∑_j:t∈Ij P(I_j), and is also called the marginal probability of the tuple t. Similarly, if we have two tuples t₁, t₂, we can examine the probability that both are present in a randomly chosen world, denoted P(t₁t₂). When the latter is P(t₁)P(t₂), we say that t₁, t₂ are independent tuples; if it is 0 then we say that t₁, t₂ are disjoint tuples or exclusive tuples. If none of these hold, then the tuples are correlated in a nonobvious way. Consider a query Q, expressed in some relational query language like SQL, and a possible tuple t in the query's answer. P(t ∈ Q) denotes the probability that, in a randomly chosen world, t is an answer to Q. The job of a probabilistic database system is to return all possible tuples t₁, t₂, ...together with their probabilities P(t₁ ∈ Q), P(t₂ ∈ Q),....

-

References

1. Andritsos, P. and Fuxman, A., Miller, R.J. Clean answers over dirty databases. In ICDE (2006).
2. Antova, L., Jansen, T., Koch, C. and Olteanu, D. Fast and simple relational processing of uncertain data. In ICDE (2008).
3. Barbara, D., Garcia-Molina, H. and Porter, D. The management of probabilistic data. IEEE Trans. Knowl. Data Eng. 4, 5 (1992), 487502.
4. Benjelloun, O., Sarma, A.D., Halevy, A., Theobald, M. and Widom, J. Databases with uncertainty and lineage. VLDBJ 17, 2 (2008), 243264.
5. Burdick, D., Deshpande, P., Jayram, T.S., Ramakrishnan, R. and Vaithyanathan, S. Efficient allocation algorithms for OLAP over imprecise data. In VLDB (2006), 391402.
6. Cavallo, R. and Pittarelli, M. The theory of probabilistic databases. In Proceedings of VLDB (1987), 7181.
7. Cheng, R., Kalashnikov, D. and Prabhakar, S. Evaluating probabilistic queries over imprecise data. In SIGMOD (2003), 551562.
8. Codd, E.F. Relational completeness of data base sublanguages. In Database Systems (1972), Prentice-Hall, 6598.
9. Cowell, R., Dawid, P., Lauritzen, S. and Spiegelhalter D., eds. Probabilistic Networks and Expert Systems (1999), Springer.
10. Dalvi, N. and Suciu, D. The dichotomy of conjunctive queries on probabilistic structures. In PODS (2007), 293302.
11. Dalvi, N. and Suciu, D. Efficient query evaluation on probabilistic databases. VLDB J. 16, 4 (2007), 523544.
12. Dalvi, N. and Suciu, D. Management of probabilistic data: Foundations and challenges. In PODS (Beijing, China, 2007) 112 (invited talk).
13. Darwiche, A. A differential approach to inference in bayesian networks. J. ACM 50, 3 (2003), 280305.
14. DeRose, P., Shen, W., Chen, F., Lee, Y., Burdick, D., Doan, A. and Ramakrishnan, R. Dblife: A community information management platform for the database research community. In CIDR (2007), 169172.
15. Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J.M. and Hong, W. Model-driven data acquisition in sensor networks. In VLDB (2004), 588599.
16. Fagin, R., Lotem, A. and Naor, M. Optimal aggregation algorithms for middleware. In Proceedings of the 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (2001), ACM Press, 102113.
17. Friedman, N., Getoor, L., Koller, D. and Pfeffer A. Learning probabilistic relational models. In IJCAI (1999), 13001309.
18. Fuhr, N. and Roelleke, T. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans. Inf. Syst. 15, 1 (1997), 3266.
19. Grädel, E., Gurevich, Y. and Hirsch, C. The complexity of query reliability. In PODS (1998), 227234.
20. Gupta, R. and Sarawagi, S. Creating probabilistic databases from information extraction models. In VLDB (2006), 965976.
21. Halevy, A. Answering queries using views: A survey. VLDB J. 10, 4 (2001), 270294.
22. Imielinski, T. and Lipski, W. Incomplete information in relational databases. J. ACM 31 (Oct. 1984), 761791.
23. Jampani, R., Xu, F., Wu, M., Perez, L., Jermaine, C. and Haas, P. MCDB: A Monte Carlo approach to managing uncertain data. In SIGMOD (2008), 687700.
24. Jayram, T., Kale, S. and Vee, E. Efficient aggregation algorithms for probabilistic data. In SODA (2007).
25. Kanagal, B. and Deshpande, A. Online filtering, smoothing and probabilistic modeling of streaming data. In ICDE (2008), 11601169.
26. Lafferty, J., Andrew McCallum and Pereira, F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML (2001).
27. Lakshmanan, L., Leone, N., Ross, R. and Subrahmanian, V. Probview: A flexible probabilistic database system. ACM Trans. Database Syst. 22, 3 (1997).
28. Nierman, A. and Jagadish, H. ProTDB: Probabilistic data in XML. In VLDB (2002), 646657.
29. Olteanu, D., Huang, J. and Koch, C. SPROUT: Lazy vs. eager query plans for tuple independent probabilistic databases. In ICDE (2009).
30. Rastogi, V., Suciu, D. and Hong, S. The boundary between privacy and utility in data publishing. In VLDB (2007).
31. Ré, C., Dalvi, N. and Suciu, D. Efficient Top-k query evaluation on probabilistic data. In ICDE (2007).
32. Ré, C., Suciu, D. Efficient evaluation of having queries on a probabilistic database. In Proceedings of DBPL (2007).
33. Ré, C. and Suciu, D. Materialized views in probabilistic databases for information exchange and query optimization. In: Proceedings of VLDB (2007)
34. Ré, C., Letchner, J., Balazinska, M. and Suciu, D. Event queries on correlated probabilistic streams. In SIGMOD (Vancouver, Canada, 2008).
35. Roth, D. On the hardness of approximate reasoning. Artif. Intell. 82, 12 (1996), 273302.
36. Sen, P. and Deshpande, A. Representing and querying correlated tuples in probabilistic databases. In ICDE, 2007.
37. Soliman, M.A., Ilyas, I.F. and Chang, K.C.-C. Probabilistic top- and ranking-aggregate queries. ACM Trans. Database Syst. 33, 3 (2008).
38. Vardi, M.Y. The complexity of relational query languages. In Proceedings of 14th ACM SIGACT Symposium on the Theory of Computing (San Francisco, California, 1982), 137146.
39. Verma, T. and Judea Pearl Causal networks: Semantics and expressiveness. Uncertainty Artif. Intell. 4 (1990), 6976.
40. Wong, E. A statistical approach to incomplete information in database systems. ACM Trans. Database Syst. 7, 3 (1982), 470488.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ProbabilisticDatabases	Nilesh Dalvi Christopher Ré Dan Suciu			Probabilistic Databases: diamonds in the dirt		Communications of the ACM		10.1145/1538788.1538810		2009

2009 ProbabilisticDatabases

Notes

Quotes

Facet 1: Semantics and Representation

References

Navigation menu

Search