A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom.
Olga GerasimovaStanislav KikotAgi KuruczVladimir V. PodolskiiMichael ZakharyaschevPublished in: CoRR (2020)
Keyphrases
- data complexity
- conjunctive queries
- query evaluation
- expressive power
- combined complexity
- query language
- query complexity
- query answering
- probabilistic databases
- query containment
- query rewriting
- ontology based data access
- query processing
- integrity constraints
- exptime complete
- relational queries
- lower complexity
- np complete
- description logics
- answering queries
- first order logic
- data model
- transitive closure
- ontology languages
- dl lite
- regular path queries
- data exchange
- xml data
- special case
- database
- database query languages
- data management
- query answers
- relational algebra
- tuple generating dependencies
- complexity of query answering
- datalog programs
- domain ontology
- databases
- semantic web
- knowledge representation
- knowledge base
- tree patterns
- data integration
- consistent query answering