More on fixpoint semantics.. (read per your interest)

[Subbarao Kambhampati <rao@parichaalak.eas.asu.edu>]

In answer to a question from Hrishikesh, I said that the way to know
when a recursive plan is completely executed is to use fixpoint
semantics. In our case, this meant checking that the extension of the
recursive predicate(s) have not changed between iterations. 

Two more comments:

1. Much of the deductive database theory is about evaluating recursive 
   query plans efficienty (notice that SQL doesnt have to deal with
   it--since it can't express recursion). Some of the techniques at
   jargon/buzzword level are 

        Semi-naive evaluation
        Topdown vs. bottomup evaluation
          Magic sets as a way of combining the advantages of both

   The second volume of Ullman's book on databases covers deductive
 databases. 

2. Saying that "semantics flows from fix points" is a bit too pat a
   reply. Before we can say that we need to show that there is
   actually a single fix point. This can get quite hairy:

     --For example, for pagerank  computation, the irreducibility,
      aperiodicity necessary conditions for existence of a unique fix point
      (unique primary eigen vector)

    --For A/H computation, given two disconnected clusters of equal
      size, the A/H computation can converge to any of two different 
      fix points. 

    In both the above cases, the idea was to force enough constraints
on the problem that the existence of unique fixpoint is guaranteed. 

    Unfortunately, in many interesting problems--especially logical
queries, you _have_ to handle multiple possible fix points. It is well 
known that datalog programs with negation embedded in them can lead to 
multiple fix points. In such cases, one often attaches some preference 
notion to the fix points (e.g. consider the fix point that gives the
_smallest_ extension to the recursive predicate; or attach a
probability to each fixpoint).

===============================
   A somewhat infamous example of this is the so-called "Yale-Shooting 
problem"

   Here is the scenario. At time t=0 there was a loaded gun, and a
living person. At time t=t'>0, the gun was unloaded. 

  Question: Is the person alive or dead?

 You can write these as nice logical axioms..

 If a gun is loaded at t=0, and it was unloaded at t=t', then unless
there is something abnormal, the gun has been fired.

 If the gun has been fired, unless there is something abnormal, the
person will be dead. 

 If you unload a gun, it becomes unloaded.

 If a gun is loaded, then normally it is fired. 

 If something is normal, then it is not abnormal.
 If something is abnormal, then it is  not normal.

 If you don't fire at a person, unless there is something abnormal,
the person continues to be alive

Query: Is the person alive?

Here are several fixpoints

C1 The gun was unloaded, and the person is alive

C2 The gun was fired, and the person is alive

C3 The gun was unloaded, and the person is dead (because of abnormality)

C4 The gun was fired and the person is dead. 

The question is which of these fix points should we go with? (one idea 
is to minimize the extension of abnormality--ie. reduce the number of
things that will have to  be abnormal). For example, C3 requires two
abnormalities, while C1 requires only 1 abnormality.

=====================

Okay.. No more messing with your heads...

Rao
[Dec  2, 2002]