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.

Extrema Predicates in Deductive Databases

GRECO, Sergio;
1995

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/137398
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 18
social impact