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: h028921d6a52cfec4
Venue: PODS
Year: 2021
Pagerank: 5.3350162e-05
Overall Rank: 8,425 | 43.36%
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,683	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	4.9793485e-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
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020519525
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
1,009	Simulation of Database-Valued Markov Chains Using SimSQL	2013	SIGMOD	0.00012539827
1,549	Conditioning Probabilistic Databases	2008	VLDB	0.00010288725
2,082	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.0732581e-05
4,765	Probabilistic Databases with MarkoViews	2012	VLDB	6.4275411e-05
5,365	Certain Answers Meet Zero-One Laws	2018	PODS	6.1604893e-05
6,302	Probabilistic Databases with an Infinite Open-World Assumption	2019	PODS	5.8184782e-05
6,637	Probabilistic XML via Markov Chains	2010	VLDB	5.7262369e-05
6,839	Probabilistic Databases for All	2020	PODS	5.6674588e-05
9,401	Queries with Arithmetic on Incomplete Databases	2020	PODS	5.1845414e-05

Semantically Similar Papers

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