Author Description

We introduce and study new notions of locality that extend those previously known by replacing the very restricted notion of isomorphism with the broader and more applicable notion of logical equivalence, or, equivalently, indistinguishability by logical games. These game-based notions of locality have the advantage that they can often be applied when traditional isomorphism-based notions cannot.We then show an application of these techniques in the problem of data exchange, that is, translation of data between two different---source and target---database schemas. Query answering in data exchange depends on the existence of query rewriting over some specific ways of constructing target instances. We show that game-based locality techniques turn out to be crucial for establishing criteria on the existence of query rewriting in data exchange, and for proving structural properties of transformations that construct target instances.In this dissertation we study locality of logics over finite models. Locality properties say that the truth values of logical formulae can be determined by looking only at a small neighborhood around their free variables. They have been shown to be very useful in finding simple inexpressibility proofs for first-order logic and some of its counting extensions.