Finite Model Theory/Motivation

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

FMT everywhere edit

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

  • ...

Databases edit

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   of airports and connection flights among them, where  means there is a direct flight from airport   to airport  . We can write an order-zero query of the direct reachability of airport   from airport   as


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

  and get  

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


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.