ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Constraints among Argument Sizes in Logic Programs.

Kirack Sohn: Constraints among Argument Sizes in Logic Programs. PODS 1994: 68-74
@inproceedings{DBLP:conf/pods/Sohn94,
  author    = {Kirack Sohn},
  title     = {Constraints among Argument Sizes in Logic Programs},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {68-74},
  ee        = {http://doi.acm.org/10.1145/182591.182599, db/conf/pods/pods94-68.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In logic programs the argument sizes of derivable facts w.r.t. an n-ary predicate are viewed as a set of points in Rn, which are approximated by their convex hull. Interargument constraint w.r.t. a predicate is essentially a set of constraints that every derivable fact of the predicate satisfies. We formalize such constraints by a fixpoint of recursive transformation similar to immediate consequence operator. However, the transformation does not necessarily converge finitely. Approximating polycones to their affine hulls provides useful interargument constraints in many practical programs, guaranteeing finite convergence. For a class of linear recursive logic programs satisfying translative- ness property, precise interargument constraints can be obtained by an analysis of structures of recursive transformations.

Copyright © 1994 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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

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

References

[APP+89]
Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: On the Convergence of Query Evaluation. J. Comput. Syst. Sci. 38(2): 341-359(1989) BibTeX
[BS89a]
Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199 BibTeX
[BS89b]
Alexander Brodsky, Yehoshua Sagiv: On Termination of Datalog Programs. DOOD 1989: 47-64 BibTeX
[BS91]
Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240 BibTeX
[CH78]
Patrick Cousot, Nicolas Halbwachs: Automatic Discovery of Linear Restraints Among Variables of a Program. POPL 1978: 84-96 BibTeX
[DLH90]
Saumya K. Debray, Nai-Wei Lin, Manuel V. Hermenegildo: Task Granularity Analysis in Logic Programs. PLDI 1990: 174-188 BibTeX
[MUVG86]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX
[Plü90]
...
[Roc70]
...
[Sch86]
...
[SVG91]
Kirack Sohn, Allen Van Gelder: Termination Detection in Logic Programs using Argument Sizes. PODS 1991: 216-226 BibTeX
[Ull85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[UVG88]
Jeffrey D. Ullman, Allen Van Gelder: Efficient tests for top-down termination of logical rules. J. ACM 35(2): 345-373(1988) BibTeX
[VG91]
Allen Van Gelder: Deriving Constraints Among Argument Sizes in Logic Programs. PODS 1990: 47-60 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:10 2009