Tuple-Independent Representations of Infinite Probabilistic Databases
Summary: Characterizes which countably infinite probabilistic databases are expressible as first-order views over tuple-independent (and block-independent-disjoint) PDBs, supplying a necessary condition and a sufficient criterion phrased via the PDB's probability distribution. Shows FO-conditioning adds no extra expressive power and isolates logical versus arithmetic obstructions to representability, with examples delineating the limits of the criteria. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Nofar Carmeli
- 2. Martin Grohe
- 3. Peter Lindner
- 4. Christoph Standke
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,161 | Querying Incomplete Numerical Data: Between Certain and Possible Answers | 2023 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 101 | ULDBs: Databases with Uncertainty and Lineage | 2006 | VLDB | 0.0004955674 |
| 477 | Model-Driven Data Acquisition in Sensor Networks | 2004 | VLDB | 0.00022221803 |
| 627 | Management of Probabilistic Data: Foundations and Challenges | 2007 | PODS | 0.00018959005 |
| 1,158 | Simulation of Database-Valued Markov Chains Using SimSQL | 2013 | SIGMOD | 0.0001361064 |
| 1,730 | Conditioning Probabilistic Databases | 2008 | VLDB | 0.00010736755 |
| 2,331 | Orion 2.0: Native Support for Uncertain Data | 2008 | SIGMOD | 9.018559e-05 |
| 5,266 | Probabilistic Databases with MarkoViews | 2012 | VLDB | 5.5972559e-05 |
| 6,147 | Probabilistic Databases with an Infinite Open-World Assumption | 2019 | PODS | 5.1854833e-05 |
| 6,284 | Probabilistic XML via Markov Chains | 2010 | VLDB | 5.128131e-05 |
| 6,683 | Probabilistic Databases for All | 2020 | PODS | 4.9638979e-05 |
| 8,947 | Queries with Arithmetic on Incomplete Databases | 2020 | PODS | 4.4248197e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,706 | Aggregation in Probabilistic Databases via Knowledge Compilation | 2012 | VLDB | 5.9820914e-05 |
| 12,222 | GRN Model of Probabilistic Databases: Construction, Transition and Querying | 2010 | SIGMOD | 4.1945683e-05 |
| 4,720 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB | 5.973811e-05 |
| 12,476 | Materialized Views in Probabilistic Databases | 2007 | VLDB | 4.1945683e-05 |
| 5,213 | Algebraic Versus Probabilistic Independence in Data Bases (Extended Abstract) | 1985 | PODS | 5.6252544e-05 |
| 9,653 | Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration | 2021 | PODS | 4.3109001e-05 |
| 450 | The Theory Of Probabilistic Databases | 1987 | VLDB | 0.00022822073 |
| 1,649 | Finitely Representable Databases | 1994 | PODS | 0.00011017687 |
| 6,683 | Probabilistic Databases for All | 2020 | PODS | 4.9638979e-05 |
| 6,147 | Probabilistic Databases with an Infinite Open-World Assumption | 2019 | PODS | 5.1854833e-05 |