On Datalog vs. Polynomial Time.
Foto N. AfratiStavros S. CosmadakisMihalis YannakakisPublished in: J. Comput. Syst. Sci. (1995)
Keyphrases
- expressive power
- special case
- deductive databases
- query answering
- transitive closure
- query language
- logic programming
- datalog programs
- computational complexity
- approximation algorithms
- worst case
- approximation ratio
- data complexity
- np hardness
- data exchange
- np hard
- search algorithm
- database
- polynomial hierarchy
- databases