Digital Symposium Collection 2000

Inherent Complexity of Recursive Queries (Extended Abstract) Stavros S. Cosmadakis   View Paper (PDF)   Return to Views/Queries Abstract We give lower bounds on the complexity of evaluating Datalog queries; our results delimit the possibility of optimizing such queries by compile-time techniques. The main technical tool is a new class of linear first-order formulas, whose quantifier depth (respectively, number of variables) measures the sequential (respectively, parallel) complexity of Datalog programs. We define a combinatorial game, and use it to prove non-expressibility of certain Datalog queries by linear formulas; we thus obtain lower bounds for sequential and for parallel complexity. We prove tight versions of our results, for queries of restricted form, by exploiting uniformity and invariance properties of Datalog programs. References Note: References link to DBLP on the Web. [A97] Foto N. Afrati : Bounded Arity Datalog (not-)Queries on Graphs. JCSS 55(2) : 210-228(1997) [AC89] Foto N. Afrati , Stavros S. Cosmadakis : Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989 : 113-126 [ACY95] Foto N. Afrati , Stavros S. Cosmadakis , Mihalis Yannakakis : On Datalog vs. Polynomial Time. JCSS 51(2) : 177-196(1995) [AG94] Miklós Ajtai , Yuri Gurevich : Datalog vs First-Order Logic. JCSS 49(3) : 562-588(1994) [AP93] Foto N. Afrati , Christos H. Papadimitriou : The Parallel Complexity of Simple Logic Programs. JACM 40(4) : 891-916(1993) [AU79] Alfred V. Aho , Jeffrey D. Ullman : The Universality of Data Retrieval Languages. POPL 1979 : 110-120 [BKBR90] Catriel Beeri , Paris C. Kanellakis , François Bancilhon , Raghu Ramakrishnan : Bounds on the Propagation of Selection into Logic Programs. JCSS 41(2) : 157-180(1990) [BMSU86] François Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D. Ullman : Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986 : 1-16 [BR91] Catriel Beeri , Raghu Ramakrishnan : On the Power of Magic. JLP 10(1/2/3&4) : 255-299(1991) [CFI92] ... [Eh61] ... [EI95] Kousha Etessami , Neil Immerman : Tree Canonization and Transitive Closure. LICS 1995 : 331-341 [Fr54] ... [Gai82] ... [GJ79] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [Imm81] Neil Immerman : Number of Quantifiers is Better Than Number of Tape Cells. JCSS 22(3) : 384-406(1981) [Imm91] ... [KV95] Phokion G. Kolaitis , Moshe Y. Vardi : On the Expressive Power of Datalog: Tools and a Case Study. JCSS 51(1) : 110-134(1995) [LM89] V. S. Lakshmanan , Alberto O. Mendelzon : Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989 : 301-310 [SZ88] Domenico Saccà , Carlo Zaniolo : The Generalized Counting Method for Recursive Logic Queries. TCS 62(1-2) : 187-220(1988) [Ull89-I] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1 Contents [Ull89-II] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X Contents [UvG88] Jeffrey D. Ullman , Allen Van Gelder : Parallel Complexity of Logical Query Programs. Algorithmica 3 : 5-42(1988) BIBTEX @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},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM