摘要：We consider the evaluation of first-order queries over classes of databaseswith bounded expansion. The notion of bounded expansion is fairly broad andgeneralizes bounded degree, bounded treewidth and exclusion of at least oneminor. It was known that over a class of databases with bounded expansion,first-order sentences could be evaluated in time linear in the size of thedatabase. We give a different proof of this result. Moreover, we show thatanswers to first-order queries can be enumerated with constant delay after alinear time preprocessing. We also show that counting the number of answers toa query can be done in time linear in the size of the database.
