Locality of order-invariant first-order formulas
Martin Grohe, Thomas Schwentick · ACM Transactions on Computational Logic · 2000
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.