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 graph, that were previously considered impervious to an efficient treatment in the declarative framework of logic-based languages. Our approach is based on the use of min and max predicates having a first-order semantics defined using rules with negation in their bodies. We show that, under certain monotonicity conditions, (1) there exists a total well-founded model for these programs expressed using negation, (2) this model can be computed efficiently using a procedure called greedy fixpoint, 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 Dijkstra′s algorithm, once the finite differencing techniques of seminaive fixpoint are applied.