Finite Model Theory/FO Localities

Basic idea: bringing neighbourhoods in relational structures together with queries written in certain languages. Like an area of land and a watchtower with a visual range, a neighbourhood has a sort of sprawl that it covers, and queries may have a sort of operating distance over which they can relate elements.

Such queries are said to have the locality property. This concept now can be expanded to whole languages. For example, for FO it can be shown that all FO-queries have the locality property.

Neighbourhood

universe with 1 relation: distance-1-neighbour

expand a: distance-2-neighbour

expand b: 2 relations with d-1-neighb

expand a+b: ...

Gaifman graph

Gaifman graph of a structure with relations Blue and Green

We define a Gaifman graph as a sort of overlay of all relations of a structure S, and then make use of it for measuring a distance between elements of S, i.o.w. how far it is to walk from one element to the other, on a path paved by the relations of S.

Definition Gaifman Graph

Let S be a relational structure with a universe U and relations Ri. A graph G (N, E) is said to be the Gaifman Graph of S iff N = U, for all e exists a r in some Ri or e = (u, u).

Remarks

1. G is reflexive
2. the orientation of the edges in Ri doesn't matter in G

Examples

1. If S is a graph, G is basically the same plus reflexivity
2. If S is a digraph, G is basically the same plus reflexivity, plus symmetry (i.e. edges lose orientation)
3. If S has only the relations R1 and R2, G is their union plus reflexivity, plus symmetry
4. In the example image a Gaifman graph (a) is derived from the 2 relations (digraphs) Blue (b) and Green (c) by 'overlaying' the edges, 'forgetting' orientation and adding loops.

Definition Distance between elements

Disatnces in Graphs btw elements and sets.

Let S be a structure with universe U with elements u1, u2 and Gaifman graph G. The length of a shortest path between u1 and u2 in G with ... is said to be the distance of u1 and u2 (in S).

Definition Distance between sets

Let S be a structure with universe U with subsets U1, U2 and Gaifman graph G. Then the minimal distance btw elms of U1 and U2 is said to be the distance btw U1 and U2 (in S).

Remarks

1. Example elms: shorter path, infinite, zero
2. Example sets: path, zero?

Neighbourhood

Graph with 1-neighbourhood with Relations Blue and Green

First, a ball is defined as a subset of elements of a structure S. Next, a neighbourhood is defined as a partial structure of S, based on a ball.

Definition Ball

Let S be a relational structures with a universe U, a be a sequence, r a natural. A set of elements of U is said to be a ball of radius r around a, B(S, r; a), iff

B(S, r; a) = { u | d(a, u) le r }

Definition Neighbourhood

Let B(S, r; a) be a Ball around a. Then a structure N(Sn, r; a) is said to be the r-neighbourhood of a in Sn, with Sn having

1. the universe B(S, r; a)
2. each relation from S, restricted to B
3. the elements of a as additional constants a₁, ..., a__n

Remarks

1. examples of 'locally look the same'
2. Isomorphism: ai -> bi - overlap?
3. => equi classes decompose with increasing radius - no swap of class?

Gaifman Locality

Neighbourhoods & Queries

Graph G

1-Neighbourhood: {1, 6,7}, {2, 3,5},{4}, {8, 9}

2-Neighbourhood: {1, 6}, {7}, {2}, {3}, {5}, {4}, {8, 9}