DATALOG Queries with Stratified Negation and Choice: from P to D^P.

@inproceedings{DBLP:conf/icdt/GrecoSZ95,
  author    = {Sergio Greco and
               Domenico Sacc{\`a} and
               Carlo Zaniolo},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {DATALOG Queries with Stratified Negation and Choice: from P to
               D$^{\mbox{P}}$},
  booktitle = {Database Theory - ICDT'95, 5th International Conference, Prague,
               Czech Republic, January 11-13, 1995, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {893},
  year      = {1995},
  isbn      = {3-540-58907-4},
  pages     = {82-96},
  ee        = {db/conf/icdt/GrecoSZ95.html},
  crossref  = {DBLP:conf/icdt/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

References

[1]

Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX

[2]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX

[3]

Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25 BibTeX

[4]

Krzysztof R. Apt, Howard A. Blair, Adrian Walker: Towards a Theory of Declarative Knowledge. Foundations of Deductive Databases and Logic Programming. 1988: 89-148 BibTeX

[5]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[6]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[7]

...

[8]

Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX

[9]

Fosca Giannotti, Dino Pedreschi, Domenico Saccà, Carlo Zaniolo: Non-Determinism in Deductive Databases. DOOD 1991: 129-146 BibTeX

[10]

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

[11]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[12]

David S. Johnson: A Catalog of Complexity Classes. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 67-161 BibTeX

[13]

Paris C. Kanellakis: Elements of Relational Database Theory. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 1073-1156 BibTeX

[14]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX

[15]

Phokion G. Kolaitis, Christos H. Papadimitriou: Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43(1): 125-144(1991) BibTeX

[16]

John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX

[17]

V. Wiktor Marek, Miroslaw Truszczynski: Autoepistemic Logic. J. ACM 38(3): 588-619(1991) BibTeX

[18]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[19]

...

[20]

...

[21]

Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250 BibTeX

[22]

Domenico Saccà: The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries. J. Comput. Syst. Sci. 54(3): 441-464(1997) BibTeX

[23]

Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX

[24]

John S. Schlipf: The Expressive Powers of the Logic Programming Semantics. PODS 1990: 196-204 BibTeX

[25]

...

[26-1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[26-2]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[27]

Allen Van Gelder: Negation as Failure using Tight Derivations for General Logic Programs. J. Log. Program. 6(1&2): 109-133(1989) BibTeX

[28]

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

[29]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

1. Sergio Flesca, Sergio Greco: Querying Graph Databases. EDBT 2000: 510-524