Finite Model Theory/Motivation

We give a simple example of applications of FMT first and then some typical examples.

FMT everywhere

Some simple examples that show how elementary the issues are that FMT cares about:

• ...

Databases

A typical application area of FMT is database theory:

• Consider a companies database that contains all managers together with the 'is superordinate' relation amongst them. In a proper hierachy the database should contain no circles, i.e. a manager can not be a superordinate of his superordinate. Querying this corresponds to checking a graph for cyclicity. As from above this can not be done in FO.
• Say two managers want to find out if one of them is more powerful than the other. So the want to query the database if the number of their subordinates is equal, i.e. the cardinalities of the sets of subordinates (say, directly and indirectly) is equal. This can't be done in FO ("FO can not count"). This is the reason why SQL is extended by a counting function.
• Consider a database of aiports and connection flights among them. In order to query the direct reachibility of airport b from airport a we can write

$q_0(a,b)=F(a,b)$.

Now in order to query connections with one change of plane we write

$q_1(a,b)={\mathrm{\exists }}_{c}F(a,c)\wedge F(c,b)$ and get $Q_1(a,b)=q_0(a,b)\vee q_1(a,b)$

for connections with zero or one change. Thus in order to extend this to reachibility (of no matter how many changes) we have to write

$\underset{k\in \mathbb{N}}{\bigvee }{q}_k$

what is not a FO expression. So we are fine with FO for a restricted reachibility up to a certain k but not for reachibility as it appears in graph theory. In fact it can be shown that reachibility can not be queried in FO.