DBScholar

Back to papers

Tight Bounds of Circuits for Sum-Product Queries

Summary: Bounds tight on circuits for a Boolean CQ's provenance over semirings; tropical case: log|F| ≥ (1−ε)·da-entw with an idempotent construction. Uses provenance polynomials, tree-decompositions, and Datalog; extends to formulas and non-Boolean CQs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
1950
Venue
PODS
Year
2024
Pagerank
5.5181056e-05
Overall Rank
7,904 | 45.78%
DOI
10.1145/3651588

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{fan_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Tight Bounds of Circuits for Sum-Product Queries}},
        url = {https://dl.acm.org/doi/10.1145/3651588},
        doi = {10.1145/3651588},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Austen Z. and Koutris, Paraschos and Zhao, Hangdong},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
2,927 In-Database Learning with Sparse Tensors 2018 PODS 7.9531195e-05
3,457 Bag Query Containment and Information Theory 2020 PODS 7.3981641e-05
4,128 The Relational Data Borg is Learning 2020 VLDB 6.8850804e-05
5,854 Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis 2023 PODS 6.064817e-05
6,398 Query Evaluation by Circuits 2022 PODS 5.8867918e-05
8,047 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.500514e-05
8,960 An Intermediate Representation for Hybrid Database and Machine Learning Workloads 2021 VLDB 5.3444589e-05
Previous Page 1 / 1 Next

Semantically Similar Papers