On Datalog vs. Polynomial Time.
Foto N. AfratiStavros S. CosmadakisMihalis YannakakisPublished in: PODS (1991)
Keyphrases
- expressive power
- deductive databases
- special case
- query answering
- query language
- logic programming
- integrity constraints
- datalog programs
- computational complexity
- approximation algorithms
- transitive closure
- database
- ontology based data access
- database languages
- approximation ratio
- np hardness
- relational algebra
- worst case
- relational databases
- data sets