Search

• < Previous
• 1
• 2
• Next >

---

First-order queries on classes of structures with bounded expansion

Wojtek Kazana ; Luc Segoufin.

We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor. It was known that over a class of databases with bounded&nbsp;[&hellip;]

---

Enumerating Answers to First-Order Queries over Databases of Low Degree

Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin.

A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree bounded by $\log n$. It is known that over a&nbsp;[&hellip;]

---