Computing Query Probability with Incidence Algebras

Summary: Applies Möbius inversion in incidence algebras to compute probabilities of unions of conjunctive queries over tuple-independent PDBs, yielding a simple PTIME algorithm for the class of “safe” queries and FP#P-hardness for all unsafe ones. Shows Möbius-based inclusion–exclusion can compute some safe queries despite unsafe subqueries and uses lattice-theoretic analysis to prove lifted-conditioning approaches are incomplete. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hf2a1fcec2000727f
Venue: PODS
Year: 2010
Pagerank: 7.4519264e-05
Overall Rank: 3,291 | 77.88%
DOI: 10.1145/1807085.1807113

Incoming Non-self Citations Over Time

Authors

1. Nilesh Dalvi (Yahoo)
2. Karl Schnaitter (University of California Santa Cruz)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{dalvi_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Computing Query Probability with Incidence Algebras}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807113},
        doi = {10.1145/1807085.1807113},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dalvi, Nilesh and Schnaitter, Karl and Suciu, Dan},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,323	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.6658586e-05
4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.6226901e-05
4,765	Probabilistic Databases with MarkoViews	2012	VLDB	6.4275411e-05
5,994	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	5.922611e-05
6,653	Queries with Difference on Probabilistic Databases	2011	VLDB	5.7196642e-05
7,427	Local Structure and Determinism in Probabilistic Databases	2012	SIGMOD	5.5304729e-05
7,466	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	5.5199634e-05
7,794	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	5.451528e-05
12,541	Provenance-based Dictionary Refinement in Information Extraction	2013	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
658	The Complexity of Query Reliability	1998	PODS	0.00015051203
1,065	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.0001219981
2,860	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	7.9338024e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,466	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
2	8,906	A Query Engine for Probabilistic Preferences	2018	SIGMOD
3	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
4	7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
5	4,389	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
6	8,908	Querying Probabilistic Preferences in Databases	2017	PODS
7	10,007	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
8	7,569	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS
9	1,065	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS
10	5,340	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB