DBScholar

Back to papers

Circuit Treewidth, Sentential Decision, and Query Compilation

Summary: Bounded circuit treewidth iff bounded SDD width, giving a tight analogue of the circuit-pathwidth/OBDD-width correspondence. Implications for query compilation: SDD-based compilability (constant-width linear-size and polynomial-size SDDs) refines tractability of UCQ lineages with/without inequalities. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1704
Venue
PODS
Year
2017
Pagerank
5.7961371e-05
Overall Rank
6,713 | 53.95%
DOI
10.1145/3034786.3034787

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bova_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Circuit Treewidth, Sentential Decision, and Query Compilation}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034787},
        doi = {10.1145/3034786.3034787},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bova, Simone and Szeider, Stefan},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
7,430 Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases 2020 PODS 5.6200093e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
644 The Complexity of Query Reliability 1998 PODS 0.00015367965
1,041 The Dichotomy of Conjunctive Queries on Probabilistic Structures 2007 PODS 0.00012453494
7,640 Tractable Lineages on Treelike Instances: Limits and Extensions 2016 PODS 5.5766474e-05
Previous Page 1 / 1 Next

Semantically Similar Papers