Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity.
Meghyn BienvenuStanislav KikotRoman KontchakovVladimir V. PodolskiiMichael ZakharyaschevPublished in: J. ACM (2018)
Keyphrases
- combined complexity
- conjunctive queries
- data complexity
- query answering
- regular path queries
- query evaluation
- conjunctive regular path queries
- query rewriting
- query complexity
- transitive closure
- query language
- lower complexity
- np complete
- integrity constraints
- expressive power
- exptime complete
- query containment
- data exchange
- queries using views
- probabilistic databases
- special case
- dl lite
- unions of conjunctive queries
- answering queries using views
- answering queries
- semantic web
- data integration
- query processing
- schema mappings
- datalog programs
- pspace complete
- knowledge representation
- ontology languages
- modal logic
- data sources
- knowledge base
- databases