Structural Totality and Constraint Stratification.

Kenneth A. Ross: Structural Totality and Constraint Stratification. PODS 1995: 184-195

@inproceedings{DBLP:conf/pods/Ross95,
  author    = {Kenneth A. Ross},
  title     = {Structural Totality and Constraint Stratification},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {184-195},
  ee        = {http://doi.acm.org/10.1145/212433.220211, db/conf/pods/Ross95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

In previous work we proposed a condition that generalizes local stratification, that ensures a two-valued well-founded model, and that can be syntactically determined from the rules and some monotonicity constraints on the facts in the program. This condition was called "universal constraint stratification." In this paper we generalize the class of constraints from monotonicity constraints to an arbitrary constraint domain. We generalize universal constraint stratification to the more general case, and prove that the condition always ensures a two-valued well-founded model for finite databases. We also provide an alternative characterization of local stratification using a version of universal constraint stratification with equality constraints. We extend Papadimitriou and Yannakakis' notion of structural totality. Papadimitriou and Yannakakis proved that a program is structurally total if and only if it is stratified. We extend their notion of structural totality so that schema-level constraint information about the variables in the rules is considered part of the "structure." We prove that, for constraints expressed in certain "exact" constraint domains, a program satisfies our extended notion of structural totality if and only if it is universally constraint stratified.

Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX

Online Edition: ACM Digital Library

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

References

[AB90]: Krzysztof R. Apt, Marc Bezem: Acyclic Programs. ICLP 1990: 617-633 BibTeX
[BF91]: Nicole Bidoit, Christine Froidevaux: Negation by Default and Unstratifiable Logic Programs. Theor. Comput. Sci. 78(1): 86-112(1991) BibTeX
[BS89]: Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199 BibTeX
[CC77]: Patrick Cousot, Radhia Cousot: Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. POPL 1977: 238-252 BibTeX
[DE92]: ...
[GL88]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[JL87]: Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
[JM94]: Joxan Jaffar, Michael J. Maher: Constraint Logic Programming: A Survey. J. Log. Program. 19/20: 503-581(1994) BibTeX
[PP90]: ...
[Prz88]: ...
[Prz89]: Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX
[PY92]: Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. PODS 1992: 16-22 BibTeX
[Ros91]: ...
[Ros94a]: Kenneth A. Ross: Modular Stratification and Magic Sets for Datalog Programs with Negation. J. ACM 41(6): 1216-1266(1994) BibTeX
[Ros94b]: Kenneth A. Ross: A Syntactic Stratification Condition Using Constraints. SLP 1994: 76-90 BibTeX
[Ull88]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[VGRS91]: 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

Sin Yeung Lee, Tok Wang Ling: A Path Removing Technique for Detecting Trigger Termination. EDBT 1998: 341-355

BibTeX

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