Logic for Computer Science/Applications

In the following we briefly consider some applied problems where the expressibility of languages matter. It easily becomes clear that FO does not suffice for many cases. To overcome the restrictions of FO there exist many extensions such as fixed-point logic, counting logic, miscellaneous flavours of second-order logic, etc. which are not covered in this ~~chaper~~ [chapter | paper].

Database Theory: SQL

Relations have named columns called attributes

   frequents |  drinker  bar
   ----------|---------------
             |

   serves    |  bar  beer
   ----------|---------------
             |

   likes     |  drinker  beer
   ----------|---------------
             |

Standard Query Language:

Relational calculus variant of FO on relational vocabulary (no functions just relations).

Here constants have a fixed interpretation, this is slightly different than in FO logic.

Examples of relational queries:

(i) Find all bars that serve Bud

$\{b:bar|serves(b,Bud)\}$

b is a free variable, Bud is a constant.

(ii) Find the ~~drunkers~~ [drinkers | drunkards] who frequent some bar that serves Bud
$\{d:drinker|\exists b(frequents(d,b)\wedge serves(b,Bud))\}$

(iii) Find the drinkers who frequent only bars serving Bud
$\{d:drinker|\forall b[frequents(d,b)\longrightarrow serves(b,Bud)]\}$

(iv) Find drinkers who frequent only bars serving some beer they like
$\{d:drinker|\forall b(freq(d,b)\longrightarrow \exists c(serves(b,c)\wedge likes(d,c)))\}$

SQL Representation of these queries:

   SELECT s.bar
   FROM serves s
   WHERE s.beer = 'Bud'

   SELECT f.drinker
   FROM freq f, serves s
   WHERE f.bar = s.bar and s.beer = 'Bud'

   SELECT drinker
   FROM freq
   WHERE dr NOT IN
   (
       SELECT f.drinker
       FROM frequents f
       WHERE f.bar NOT IN
           (SELECT bar
            FROM serves
            WHERE beer = 'Bud')
   )

Relational Algebra

Is an alternative representation language used in SQL. What you can represent using relational algebra is absolutely the same as what you can represent in FO logic. It constitutes of simple operations on relations that allow you to specify queries.

Main Operations

$\Pi$ Projection : Project relations on a subset of its columns (attributes).

$\sigma$ Selection : Selects a subset of tuples from a particular relation, based upon a specified selection cond ition.

$\cup$ , $-$ Union, Diff : similar to set operations.

|><| Join : allows you to combine tuples from two relations.

Rename : renames A to B.

Expressions built from these expressions are called a relational algebra query. Whatever you can express in algebra we can represent in FO.

Examples:

(i) $\Pi _{bar}(\Sigma _{beer=Bud}(serves))$

(ii) $\Pi _{dr}(freq|><|\sigma _{beer=Bud}(serves))$

(iii) $\Pi _{d}(freq)-\Pi _{d}[freq|><|(\Pi _{bar}(freq)-\Pi _{bar}(\Sigma _{beer=Bud}(serves)))]$

Expressive Power

Graph properties correspond to properties of datastructures in relational databases (see the chapter on database queries), e.g.:

Consider a companies database that contains all managers together with the 'is superordinate' relation amongst them. In a proper heirachy 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 airports 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)=\exists _{c}F(a,c)\land F(c,b)$ and get $Q_{1}(a,b)=q_{1}(a,b)\lor 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

$\bigvee _{k\in \mathbb {N} }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.

Descriptive Complexity Theory

As mentioned above Hamiltonicity can not be expressed in FO. So now one can think of an extension of FO in order to express this property. This can be done like

$\exists L\exists S(isLinOrd(L)\land isSucRelOf(S,L)\land \forall _{x}\exists _{y}(L(x,y)L\lor L(y,x))\land \forall _{x}\forall _{y}(S(x,y)\implies E(x,y)))$

where the quantifiers on the left state the existence of the binary relations L and S that satisfy the formula on the right. The realtion isLinOrd states that L is a linear order and isSucRelOf means that S is the successor relation of L. Both can be expressed in FO. The pattern as above, second-order existential quantifiers followed by a first order formula is called existential second order logic.

Now it is well known that Hamiltonicity is a NP-complete problem and one can ask: is there a natural connection between NP and second order logic? Indeed, there is a very amazing one: existential second-order logic corresponds exactly (!) to the class of NP-complete problems! This result is known as Fagin's theorem, it has lead to the new area of descriptive complexity where complexity classes are described by means of logical formalisms.