LOCK-WAIT AND DEADLOCK DETECTION
                    --------------------------------

     Objects o(i)   (database records)
     Processes p(i)

     Granted locks are represented by the relation locks(p(i),o(j)).
     Lock-waits are represented by the relation waitsfor(p(i),o(j)).
     The state of the waiting processes can be represented by the graph
     G=<S,A>

     S={ p(j) / exists o(i) : waitsfor(p(j),o(i)) }
     A={ p(i)->p(j) / exists o(k) : locks(p(j),o(k)) and waitsfor(p(i),o(k)) }

     There is a deadlock when graph G contains a cycle.

     Initialy, G is empty.
     If we add edges to G such as a deadlock is not introduced, the graph 
     remains deadlock-free. Here is how:

     Process p(j) requests a lock on o(i), currently locked by p(k).
     Adding waitsfor(p(j),o(k)) to the DB state results in a cycle in graph
     G'=<S',A'>
     where     S'=S union {p(j)}
               A'=A union {p(j)->p(k)}
     only if graph F contains a path of the form pk->...->p(j).
     So, in order to determine if a waitsfor(p(j),o(k)) can be granted, it 
     suffices to explore all paths beginning from p(k). If p(j) is 
     encountered, process p(j) must be inhibited, if not, it can lock-wait.