Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity.
Meghyn BienvenuStanislav KikotRoman KontchakovVladimir V. PodolskiiMichael ZakharyaschevPublished in: CoRR (2016)
Keyphrases
- first order logic
- combined complexity
- data complexity
- expressive power
- transitive closure
- regular path queries
- knowledge representation
- conjunctive regular path queries
- conjunctive queries
- query containment
- unions of conjunctive queries
- dl lite
- exptime complete
- query answering
- lower complexity
- query complexity
- incomplete information
- query evaluation
- np complete
- answering queries
- query rewriting
- data exchange
- special case
- semantic web
- answering queries using views
- datalog programs
- query language
- probabilistic databases
- description logics
- integrity constraints
- data integration
- knowledge base