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,…