Locality of queries and transformations: Invited talk

Arenas, M

Abstract

Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighborhood of its free variables. Such notions have proved to be useful in many applications especially in computer science. They all, however, refer to isomorphism of neighborhoods, which most local logics cannot test. A more relaxed notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighborhood. Or, since most logics are characterized by games, the truth value of a formula is determined by the type, with respect to a game, of that small neighborhood. Such game-based notions of locality can often be applied when traditional isomorphism-based locality cannot. In the first part of this talk, we show some recent results on game-based notions of locality. We look at two, progressively more complicated locality notions, and we show that the overall picture is much more complicated than in the case of isomorphism-based notions of locality. In the second part of this talk, we concentrate on the locality of transformations, rather than queries definable by formulas. In particular, we show how the game-based notions of locality can be used in data exchange settings to prove inexpressibility results. © 2006 International Federation for Information Processing.

Más información

Título según WOS: Locality of queries and transformations (Invited talk)
Título según SCOPUS: Locality of queries and transformations: Invited talk
Título de la Revista: Research and Practical Issues of Enterprise Information Systems II, Vol 2
Volumen: 209
Editorial: Springer
Fecha de publicación: 2006
Página de inicio: 3
Página final: 3
Idioma: English
URL: http://www.scopus.com/inward/record.url?eid=2-s2.0-33845642666&partnerID=q2rCbXpz
Notas: ISI, SCOPUS