Probabilistic Databases with an Infinite Open-World Assumption

Summary: Framework for open-world PDBs over countably infinite universes with finite instances, removing closed-world artifacts. Constructive existence/characterization of countable tuple-independent (and BID) PDBs; lift finite-query evaluation to obtain arbitrarily small additive approximations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1775
Venue: PODS
Year: 2019
Pagerank: 5.9514805e-05
Overall Rank: 6,170 | 57.67%
DOI: 10.1145/3294052.3319681

Incoming Non-self Citations Over Time

Authors

1. Martin Grohe (Rheinisch-Westfaelische Technische Hochschule Aachen)
2. Peter Lindner (Rheinisch-Westfaelische Technische Hochschule Aachen)

BibTeX Citation

@inproceedings{grohe_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Probabilistic Databases with an Infinite Open-World Assumption}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319681},
        doi = {10.1145/3294052.3319681},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grohe, Martin and Lindner, Peter},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,001	Generative Datalog with Continuous Distributions	2020	PODS	6.0133202e-05
6,741	Probabilistic Databases for All	2020	PODS	5.7866368e-05
8,259	Tuple-Independent Representations of Infinite Probabilistic Databases	2021	PODS	5.4574671e-05
9,225	Queries with Arithmetic on Incomplete Databases	2020	PODS	5.3035385e-05
9,819	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	5.214913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
331	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020936658
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
2,775	MayBMS: A Probabilistic Database Management System	2009	SIGMOD	8.1359291e-05
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05
6,508	Probabilistic XML via Markov Chains	2010	VLDB	5.8576101e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,367	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS
2	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
3	2,241	Finitely Representable Databases	1994	PODS
4	7,430	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS
5	557	The Theory of Probabilistic Databases	1987	VLDB
6	2,990	Knowledge Expansion over Probabilistic Knowledge Bases	2014	SIGMOD
7	5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
8	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
9	6,741	Probabilistic Databases for All	2020	PODS
10	8,259	Tuple-Independent Representations of Infinite Probabilistic Databases	2021	PODS