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 hierarchy 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 cannot be done in First Order Logic (FO).
• Say two managers want to find out if one of them is more powerful than the other. They need 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 cannot count"). This is the reason SQL is extended by a counting function.
• Consider a database $F$ of airports and connection flights among them, where $F(x,y)$means there is a direct flight from airport $x$ to airport $y$. We can write an order-zero query of the direct reachability of airport $b$ from airport $a$ as

$q_{0}(a,b)=F(a,b)$.

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

$q_{1}(a,b)=\exists _{c}F(a,c)\land F(c,b)$ and get $Q_{1}(a,b)=q_{0}(a,b)\lor q_{1}(a,b)$

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

$Q=\bigvee _{k\in \mathbb {N} }q_{k}$

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