Stavros Cosmadakis
- A97.F. Afrati. Bounded arity Datalog(~=) queries on graphs. Journal of Computer and System Sciences 55, 1997. Google Scholar
Digital Library
- AC89.F. Afrati, S. Cosmadakis. Expressiveness of restricted recursive queries. Proc. 21st A CM Syrup. on Theory of Computing, 113-126, 1989. Google ScholarDigital Library
- ACY95.F. Afrati, S. Cosmadakis, M. Yannakakis. On Datalog vs. polynomial time. Journal of Computer and System Sciences, 51:2, 177-196, 1995. Google ScholarDigital Library
- AG94.M. Ajtai, Y. Gurevich. Datalog vs First-Order Logic. Journal of Computer and System Sciences, 1994. Google ScholarDigital Library
- AP93.F. Afrati, C. tt. Papadimitriou. The parallel complexity of simple logic programs. Journal of the A CM 40, 1993. Google ScholarDigital Library
- AU79.A.V. Aho and J. D. Ullman. Universality of data retrieval languages. Proc. 6th A CM Symp. on Principles of Programming Languages, 110-117, 1979. Google ScholarDigital Library
- BKBR90.C. Beeri, P. Kanellakis, F. Bancilhon, R. Ramakrishnan. Bounds on the Propagation of Selection into Logic Programs. Journal of Computer and System Sciences 41, 1990. Google ScholarDigital Library
- BMSU86.F. Bancilhon, D. Maier, Y. Sagiv, J. D. Ullman. Magic sets and other strange ways to implement logic programs. Proc. 5th A CM Symp. on Principles of Database Systems, 1-15, 1986. Google ScholarDigital Library
- BR91.C. Beeri, R. Ramakrishnan. On the power of magic. J. Logic Programming 10, 1991. Google ScholarDigital Library
- CFI92.Y. Cai, M. Furer, N. Immerman. An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica 12, 1992.Google Scholar
- Eh61.A. Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math., 49:129-141, 1961.Google ScholarCross Ref
- EI95.K. Etessami, N. Immerman. Tree Canonization and Transitive Closure. Proceedings, Tenth Annual IEEE Symposium on Logic in Computer Science, 1995. Google ScholarDigital Library
- Fr54.R. Fraiss~. Sur quelques classifications des syst~mes de relations. Publications Scientifiques de l'Universitd d'Algerie, Sdries A, 1:35-182, 1954.Google Scholar
- Gai82.H. Gaifman. On local and nonlocal properties. In J. Stern, ed., Logic Colloquium '81, 105-135, North Holland 1982.Google Scholar
- GJ79.M. Garey, D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. Google ScholarDigital Library
- Imm81.N. Immerman. Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences 51, 1981.Google Scholar
- Imm91.N. Immerman. DSPACE(nk) = VAR(k ~ 1). Proceed- ~ngs of the 6th Annual Conference on S~ructure in Complexity Theory, 1991.Google Scholar
- KV95.Ph. G. Kolaitis, M. Y. Vardi. On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences 51,110-134, 1995. Google ScholarDigital Library
- LM89.V. '~ ,~. Lakshmanan, A. O. Mendelzon Inductive pebble games and the expressive power of Datalog. Proc. 8th A CM Symp. on Principles of Database Systems, 301-310, 1989. Google ScholarDigital Library
- SZ88.D. Sacca, C. Zaniolo. The generalized counting method for recursive logic queries. Theoretical Computer Science 62, 1988. Google ScholarDigital Library
- Ull89.J. D. Ullman. Database and Knowledge-Base Systems, Vols I and II. Computer Science Press, 1989. Google ScholarDigital Library
- UvG88.J.D. Ullman, A. Van Gelder. Parallel complexity of logical query programs. Algorithmica, 3:1, 5-42, 1988.Google ScholarDigital Library
Index Terms
- Inherent complexity of recursive queries
Recommendations
Decidable containment of recursive queries
Database theoryOne of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Decidable Containment of Recursive Queries
ICDT '03: Proceedings of the 9th International Conference on Database TheoryOne of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment, is crucial in several contexts, such as query optimization, ...
Inherent Complexity of Recursive Queries
We give lower bounds on the complexity of certain Datalog queries. Our notion of complexity applies to compile-time optimization techniques for Datalog; thus, our results indicate limitations of these techniques. The main new tool is linear first-order ...
Comments