Tractable Lineages on Treelike Instances: Limits and Extensions

Summary: MSO probabilistic query evaluation is linear-time only on bounded-treewidth instances; FO already hard on any efficiently constructible unbounded-treewidth graph class. Lineages: MSO on bounded-treewidth yields bounded-treewidth circuits, poly-size OBDDs and linear d‑DNNFs; some UCQs with disequalities force superpolynomial OBDDs on unbounded-treewidth classes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1695
Venue: PODS
Year: 2016
Pagerank: 5.5766474e-05
Overall Rank: 7,640 | 47.59%
DOI: 10.1145/2902251.2902301

Incoming Non-self Citations Over Time

Authors

1. Antoine Amarilli (Centre National de la Recherche Scientifique; Télécom Paris; Université Paris-Saclay)
2. Pierre Bourhis (Centre National de la Recherche Scientifique; Université Lille 1)
3. Pierre Senellart (Centre National de la Recherche Scientifique; National University of Singapore; Télécom Paris; Université Paris-Saclay)

BibTeX Citation

@inproceedings{amarilli_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Tractable Lineages on Treelike Instances: Limits and Extensions}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902301},
        doi = {10.1145/2902251.2902301},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Amarilli, Antoine and Bourhis, Pierre and Senellart, Pierre},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,965	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.3852716e-05
6,713	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS	5.7961371e-05
7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.5638493e-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
17	Provenance Semirings	2007	PODS	0.00059843817
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	6.310093e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
6,839	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.7576811e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS
2	11,523	The Complexity of Conjunctive Queries with Degree 2	2022	PODS
3	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
4	6,713	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS
5	1,752	Approximate Lineage for Probabilistic Databases	2008	VLDB
6	8,032	Lineage Processing over Correlated Probabilistic Databases	2010	SIGMOD
7	7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
8	8,626	Charting the Tractability Frontier of Certain Conjunctive Query Answering	2013	PODS
9	9,864	Tractable Database Design through Bounded Treewidth	2006	PODS
10	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS