Aggregate Queries on Sparse Databases

Summary: Algebraic semiring-based framework unifying query evaluation, aggregation, enumeration and maintenance, plus an FO extension supporting multi-semiring aggregation. For bounded‑expansion sparse classes, yields optimal linear-time preprocessing and a data structure for constant‑delay enumeration of answers. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1823
Venue: PODS
Year: 2020
Pagerank: 5.4119882e-05
Overall Rank: 8,528 | 41.50%
DOI: 10.1145/3375395.3387660

Incoming Non-self Citations Over Time

Authors

1. Szymon Toruńczyk (University of Warsaw)

BibTeX Citation

@inproceedings{torunczyk_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{Aggregate Queries on Sparse Databases}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387660},
        doi = {10.1145/3375395.3387660},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Toruńczyk, Szymon},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,166	Recursive Querying of Neural Networks via Weighted Structures	2026	PODS	5.093636e-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
17	Provenance Semirings	2007	PODS	0.00059843817
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
4,063	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS	6.9307541e-05
5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.3897022e-05
8,141	First-Order Query Evaluation with Cardinality Conditions	2018	PODS	5.4802066e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,063	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS
2	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
3	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
4	2,305	Querying Aggregate Data	1999	PODS
5	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
6	13,596	Enumerating Answers to First-Order Queries over Databases of Low Degree	2014	PODS
7	11,146	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS
8	4,098	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB
9	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
10	5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS