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
- 2. Luc Segoufin
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,652 | Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration | 2020 | PODS | 4.4753042e-05 |
| 11,557 | Aggregate Queries on Sparse Databases | 2020 | PODS | 4.1945683e-05 |
| 13,395 | 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 |
|---|---|---|---|---|
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,437 | Insert-Only versus Insert-Delete in Dynamic Query Evaluation | 2024 | PODS | 4.5138778e-05 |
| 3,387 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.1573735e-05 |
| 5,709 | On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) | 1997 | PODS | 5.3602702e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 7,166 | Ranked Enumeration of Join Queries with Projections | 2022 | VLDB | 4.8124491e-05 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 4,546 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0987778e-05 |
| 3,715 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 6.8220943e-05 |
| 11,557 | Aggregate Queries on Sparse Databases | 2020 | PODS | 4.1945683e-05 |
| 13,395 | Enumerating Answers to First-Order Queries over Databases of Low Degree | 2014 | PODS | - |