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)

Paper ID: 1842
Venue: PODS
Year: 2021
Pagerank: 5.4574671e-05
Overall Rank: 8,259 | 43.34%
DOI: 10.1145/3452021.3458315

Incoming Non-self Citations Over Time

Authors

1. Nofar Carmeli (Technion)
2. Martin Grohe (Rheinisch-Westfaelische Technische Hochschule Aachen)
3. Peter Lindner (Rheinisch-Westfaelische Technische Hochschule Aachen)
4. Christoph Standke (Rheinisch-Westfaelische Technische Hochschule Aachen)

BibTeX Citation

@inproceedings{carmeli_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Tuple-Independent Representations of Infinite Probabilistic Databases}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458315},
        doi = {10.1145/3452021.3458315},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Carmeli, Nofar and Grohe, Martin and Lindner, Peter and Standke, Christoph},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,367	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
993	Simulation of Database-Valued Markov Chains Using SimSQL	2013	SIGMOD	0.00012789598
1,520	Conditioning Probabilistic Databases	2008	VLDB	0.00010510496
2,042	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.2691675e-05
4,680	Probabilistic Databases with MarkoViews	2012	VLDB	6.5675814e-05
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05
6,170	Probabilistic Databases with an Infinite Open-World Assumption	2019	PODS	5.9514805e-05
6,508	Probabilistic XML via Markov Chains	2010	VLDB	5.8576101e-05
6,741	Probabilistic Databases for All	2020	PODS	5.7866368e-05
9,225	Queries with Arithmetic on Incomplete Databases	2020	PODS	5.3035385e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,098	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
2	12,417	GRN Model of Probabilistic Databases: Construction, Transition and Querying	2010	SIGMOD
3	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
4	2,936	Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization	2007	VLDB
5	6,123	Algebraic Versus Probabilistic Independence in Data Bases (Extended Abstract)	1985	PODS
6	9,819	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
7	557	The Theory of Probabilistic Databases	1987	VLDB
8	2,241	Finitely Representable Databases	1994	PODS
9	6,741	Probabilistic Databases for All	2020	PODS
10	6,170	Probabilistic Databases with an Infinite Open-World Assumption	2019	PODS