Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion
Summary: For classes of structures of bounded expansion (generalizing bounded degree, bounded treewidth, and minor-free), provides a new proof of linear-time FO model checking and shows FO query answers can be enumerated with constant delay after linear preprocessing. Also proves counting query answers is achievable in linear time, unifying efficient evaluation, enumeration and counting for FO queries on bounded-expansion classes. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Wojciech Kazana (Ecole Normale Superieure de Cachan; INRIA)
- 2. Luc Segoufin (Ecole Normale Superieure de Cachan; INRIA)
BibTeX Citation
@inproceedings{kazana_pods13,
address = {New York, NY, USA},
series = {{PODS} '13},
title = {{Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion}},
url = {https://dl.acm.org/doi/10.1145/2463664.2463667},
doi = {10.1145/2463664.2463667},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Kazana, Wojciech and Segoufin, Luc},
year = {2013}
}Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,063 | Enumeration for FO Queries over Nowhere Dense Graphs | 2018 | PODS | 6.9307541e-05 |
| 4,097 | Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates | 2018 | PODS | 6.9038261e-05 |
| 8,141 | First-Order Query Evaluation with Cardinality Conditions | 2018 | PODS | 5.4802066e-05 |
| 8,528 | Aggregate Queries on Sparse Databases | 2020 | PODS | 5.4119882e-05 |
| 8,673 | Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration | 2020 | PODS | 5.3872753e-05 |
| 13,596 | Enumerating Answers to First-Order Queries over Databases of Low Degree | 2014 | PODS | - |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018893507 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,777 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS |
| 2 | 5,736 | On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) | 1997 | PODS |
| 3 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |
| 4 | 6,412 | Ranked Enumeration of Join Queries with Projections | 2022 | VLDB |
| 5 | 636 | Answering Conjunctive Queries under Updates | 2017 | PODS |
| 6 | 4,393 | Bounded Conjunctive Queries | 2014 | VLDB |
| 7 | 2,745 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB |
| 8 | 8,528 | Aggregate Queries on Sparse Databases | 2020 | PODS |
| 9 | 4,063 | Enumeration for FO Queries over Nowhere Dense Graphs | 2018 | PODS |
| 10 | 13,596 | Enumerating Answers to First-Order Queries over Databases of Low Degree | 2014 | PODS |