A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom.
Olga GerasimovaStanislav KikotAgi KuruczVladimir V. PodolskiiMichael ZakharyaschevPublished in: KR (2020)
Keyphrases
- data complexity
- conjunctive queries
- query evaluation
- expressive power
- combined complexity
- query language
- query complexity
- query containment
- query answering
- probabilistic databases
- query rewriting
- ontology based data access
- np complete
- lower complexity
- query processing
- transitive closure
- exptime complete
- integrity constraints
- data model
- semantic web
- regular path queries
- relational queries
- database query languages
- answering queries
- datalog programs
- ontology languages
- database
- first order logic
- special case
- relational algebra
- domain ontology
- knowledge representation
- description logics
- monadic second order logic
- query answers
- data integration
- xml data
- databases
- data management
- natural language
- computational complexity
- regular expressions
- knowledge base
- consistent query answering
- owl ontologies