Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna.
Olga GerasimovaStanislav KikotMichael ZakharyaschevPublished in: Description Logic, Theory Combination, and All That (2019)
Keyphrases
- data complexity
- query evaluation
- combined complexity
- query complexity
- expressive power
- query language
- query answering
- conjunctive queries
- conp complete
- unions of conjunctive queries
- np complete
- query processing
- constraint satisfaction problems
- answering queries
- lower complexity
- query answers
- transitive closure
- monadic second order logic
- knowledge base
- data management
- semantic web
- data exchange
- exptime complete
- ontology languages
- probabilistic databases
- xml data
- database query languages
- integrity constraints
- regular path queries
- constraint satisfaction
- knowledge representation
- database
- range queries
- database systems
- query containment
- datalog programs
- query rewriting
- data model
- schema mappings
- domain ontology
- data mining
- databases
- first order logic
- tuple generating dependencies
- sum queries
- regular expressions