Greedy by Choice.

Sergio Greco, Carlo Zaniolo, Sumit Ganguly: Greedy by Choice. PODS 1992: 105-113

@inproceedings{DBLP:conf/pods/GrecoZG92,
  author    = {Sergio Greco and
               Carlo Zaniolo and
               Sumit Ganguly},
  title     = {Greedy by Choice},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {105-113},
  ee        = {http://doi.acm.org/10.1145/137097.137836, db/conf/pods/GrecoZG92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The greedy paradigm of algorithm design is a well known tool used for efficiently solving many classical computational problems within the framework of procedural languages. However, it is very dificult to express these algorithms within the declarative framework of logic-based languages. In this paper, we extend the framework of Datalog-like languages to provide simple and declarative formulations of such problems, with computational complexities comparable to those of procedural formulations. This is achieved through the use of constructs, such as least and choice, that have semantics reducible to that of negative programs under stable model semantics. Therefore, we show that the formulation of greedy algorithms using these constructs lead to a syntactic class of programs, called stage-stratified programs, that are easily recognized at compile time. The fixpoint-based implementation of these recursive programs is very efficient and, combined with suitable storage structures, yields asymptotic complexities comparable to those obtained using procedural languages.

Copyright © 1992 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 Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 840 KB]

References

[1]: Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163 BibTeX
[2]: ...
[3]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[4]: Fosca Giannotti, Dino Pedreschi, Domenico Saccà, Carlo Zaniolo: Non-Determinism in Deductive Databases. DOOD 1991: 129-146 BibTeX
[5]: ...
[6]: ...
[7]: Ravi Krishnamurthy, Shamim A. Naqvi: Non-Deterministic Choice in Datalog. JCDKB 1988: 416-424 BibTeX
[8]: ...
[9]: Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX
[10]: ...
[11]: 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
[12]: ...

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)
Weidong Chen, David Scott Warren: Computation of Stable Models and Its Integration with Logical Query Processing. IEEE Trans. Knowl. Data Eng. 8(5): 742-757(1996)
Sergio Greco, Domenico Saccà, Carlo Zaniolo: DATALOG Queries with Stratified Negation and Choice: from P to D^P. ICDT 1995: 82-96
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250

BibTeX

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