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 / Ganguly, S; Greco, Sergio; Zaniolo, C.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 51(2)(1995), pp. 244-259.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Extrema Predicates in Deductive Databases|
|Data di pubblicazione:||1995|
|Citazione:||Extrema Predicates in Deductive Databases / Ganguly, S; Greco, Sergio; Zaniolo, C.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 51(2)(1995), pp. 244-259.|
|Appare nelle tipologie:||1.1 Articolo in rivista|