Inherent Complexity of Recursive Queries (Extended Abstract).

@inproceedings{DBLP:conf/pods/Cosmadakis99,
  author    = {Stavros S. Cosmadakis},
  title     = {Inherent Complexity of Recursive Queries (Extended Abstract)},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {148-154},
  ee        = {http://doi.acm.org/10.1145/303976.303991, db/conf/pods/Cosmadakis99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 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.

ACM SIGMOD DiSC

• 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/DISC001 or /cdrom

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

Printed Edition

Online Edition: ACM Digital Library

References

[A97]

Foto N. Afrati: Bounded Arity Datalog (not-)Queries on Graphs. J. Comput. Syst. Sci. 55(2): 210-228(1997) BibTeX

[AC89]

Foto N. Afrati, Stavros S. Cosmadakis: Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989: 113-126 BibTeX

[ACY95]

Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. J. Comput. Syst. Sci. 51(2): 177-196(1995) BibTeX

[AG94]

Miklós Ajtai, Yuri Gurevich: Datalog vs First-Order Logic. J. Comput. Syst. Sci. 49(3): 562-588(1994) BibTeX

[AP93]

Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Logic Programs. J. ACM 40(4): 891-916(1993) BibTeX

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[BKBR90]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. J. Comput. Syst. Sci. 41(2): 157-180(1990) BibTeX

[BMSU86]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX

[BR91]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) BibTeX

[CFI92]

...

[Eh61]

...

[EI95]

Kousha Etessami, Neil Immerman: Tree Canonization and Transitive Closure. LICS 1995: 331-341 BibTeX

[Fr54]

...

[Gai82]

...

[GJ79]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[Imm81]

Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981) BibTeX

[Imm91]

...

[KV95]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. J. Comput. Syst. Sci. 51(1): 110-134(1995) BibTeX

[LM89]

V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310 BibTeX

[SZ88]

Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. Theor. Comput. Sci. 62(1-2): 187-220(1988) BibTeX

[Ull89-I]

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

[Ull89-II]

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

[UvG88]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) BibTeX