The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.
Neil ImmermanAlexander Moshe RabinovichThomas W. RepsShmuel SagivGreta YorshPublished in: CSL (2004)
Keyphrases
- transitive closure
- query containment
- expressive power
- description logics
- number restrictions
- recursive queries
- unions of conjunctive queries
- first order logic
- query language
- constraint databases
- relational algebra
- query evaluation
- exptime complete
- data complexity
- modal logic
- spatial databases
- decision procedures
- directed acyclic graph
- artificial intelligence
- database
- data model
- database systems
- databases