On the complexity of single-rule datalog queries
Authors:
- 8 March 2003
- journal article
- Published by Elsevier in Information and Computation
- Vol. 183 (1) , 104-122
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Complexity and expressive power of logic programmingACM Computing Surveys, 2001
- Undecidable boundedness problems for datalog programsThe Journal of Logic Programming, 1995
- Finite Model Theory1995
- The parallel complexity of simple logic programsJournal of the ACM, 1993
- Satisfiability of the smallest binary programInformation Processing Letters, 1993
- Capturing complexity classes by fragments of second-order logicTheoretical Computer Science, 1992
- Boundedness is undecidable for datalog programs with a single recursive ruleInformation Processing Letters, 1989
- Subsumption and implicationInformation Processing Letters, 1987
- Embedded implicational dependencies and their inference problem1981
- Optimal implementation of conjunctive queries in relational data bases1977