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}
}

BibTeX

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/...

BibTeX

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 BibTeX

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 BibTeX
[3]: ...
[4]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[5]: Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX
[6]: Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 BibTeX
[7]: Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX
[8]: S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511 BibTeX
[9]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[10]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
[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) BibTeX

Referenced by

David B. Kemp, Kotagiri Ramamohanarao: Efficient Recursive Aggregation and Negation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 10(5): 727-745(1998)
Alexandra Poulovassilis, Carol Small: Algebraic Query Optimisation for Database Programming Languages. VLDB J. 5(2): 119-132(1996)
Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Databases. PODS 1992: 114-126
Sergio Greco, Carlo Zaniolo, Sumit Ganguly: Greedy by Choice. PODS 1992: 105-113
Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138
Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104
S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
Shalom Tsur: Deductive Databases in Action. PODS 1991: 142-153

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]