On Negation in HiLog.

Kenneth A. Ross: On Negation in HiLog. PODS 1991: 206-215

@inproceedings{DBLP:conf/pods/Ross91a,
  author    = {Kenneth A. Ross},
  title     = {On Negation in HiLog},
  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     = {206-215},
  ee        = {http://doi.acm.org/10.1145/113413.113432, db/conf/pods/Ross91a.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We study the second order logical langauge HiLog that has been chosen by the NAIL! group at Stanford University as the basis for its deductive database system. While HiLog has a second order syntax, its semantics is first order. We consider HiLog programs with negative literals in the body. We define a stable model semantics and a well-founded semantics for this class of programs, and show that these semantics generalize the stable model semantics and the well-founded semantics, respectively, for range-restricted normal programs. We investigate a second order property that we call preservation under extensions. Preservation under extensions ensures that the semantics of a program is not changed when rules having no symbols in common with the program are appended to the program. We show that for normal programs domain independence and preservation under extensions are equivalent, while for HiLog programs prese-vation under extensions is strictly stronger. We generalize range restrictedness to HiLog programs in two ways, and show that range restricted HiLog programs are preserved under extensions with respect to the well-founded semantics. We investigate conditions under which the well-founded semantics is two-valued, and generalize the class of modularly stratified programs to HiLog. We extend magic set techniques to HiLog programs with modularly stratified negation.

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, 914 KB]

Journal Version

Kenneth A. Ross: On Negation in HiLog. J. Log. Program. 18(1): 27-53(1994) BibTeX

References

[ABW88]: ...
[CH85]: Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[CKW89]: Weidong Chen, Michael Kifer, David Scott Warren: HiLog: A First-Order Semantics for Higher-Order Logic Programming Constructs. NACLP 1989: 1090-1114 BibTeX
[DiP69]: Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969) BibTeX
[GL88]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[Kol90]: Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX
[Nic82]: Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX
[Prz88]: ...
[Prz89]: Teodor C. Przymusinski: On the Declarative and Procedural Semantics of Logic Programs. J. Autom. Reasoning 5(2): 167-205(1989) BibTeX
[Ros90]: Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171 BibTeX
[VG86]: Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[VGRS88]: 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

BibTeX

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