Finite Model Theory/Motivation

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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

FMT everywhere[edit | edit source]

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

  • ...

Databases[edit | edit source]

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.