Minimum and Maximum Predicates in Logic Programming.

Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163

@inproceedings{DBLP:conf/pods/GangulyGZ91,
  author    = {Sumit Ganguly and
               Sergio Greco and
               Carlo Zaniolo},
  title     = {Minimum and Maximum Predicates in Logic Programming},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {154-163},
  ee        = {http://doi.acm.org/10.1145/113413.113427, db/conf/pods/GangulyGZ91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A novel approach is proposed for ezpressing and computing eficienily a large class of problems, including finding the shortest path in a graph, that were previously considered impervious to an efiient treatment in the declarative framework of logic-baaed 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 when certain monotonicity conditions hold then (1) there exists a total well-founded model for these programs containing negation, (2) this model can be computed effciently using a procedure called greedy fixpoint, and (3) the original program can be rewritten into a more efficient one by pushing min and max predicates into recursion. The greedy fixpoint evaluation of the program expressing the shorted path problem coincides with Dijkstra's algorithm.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 973 KB]

References

[1]: ...
[2]: Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
[3]: ...
[4]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080
[5]: Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
[6]: Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120
[7]: Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217
[8]: S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
[9]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[10]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10
[11]: ...
[12]: Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991)