EXTREMA PREDICATES IN DEDUCTIVE DATABASES

A novel approach is proposed for expressing and computing efficiently a large class of problems, including finding the shortest path in a gr aph, that were previously considered impervious to an efficient treatm ent in the declarative framework of logic-based languages, Our approac h is based on the use of min and max predicates having a first-order s emantics defined using rules with negation in their bodies. We show th at, under certain monotonicity conditions, (1) there exists a total we ll-founded model for these programs expressed using negation, (2) this model can be computed efficiently using a procedure called greedy fix point, and (3) programs with min/max goals on recursively defined cost predicates can often be rewritten into more efficient ones by pushing min and max predicates into recursion. The greedy fixpoint evaluation of the program expressing the shortest path problem coincides with Di jkstra's algorithm, once the finite differencing techniques of seminai ve fixpoint are applied. (C) 1995 Academic Press, Inc.