Horn Rewritability vs PTime Query Answering for Description Logic TBoxes.
André HernichCarsten LutzFabio PapacchiniFrank WolterPublished in: Description Logics (2017)
Keyphrases
- description logics
- dl lite
- query answering
- conjunctive queries
- data complexity
- conjunctive query answering
- np hard
- transitive roles
- data exchange
- knowledge base
- integrity constraints
- reasoning tasks
- computational properties
- knowledge representation
- answering queries
- unions of conjunctive queries
- incomplete information
- semantic web
- combined complexity
- exptime complete
- data integration
- reasoning problems
- ontology languages
- tight complexity bounds
- complexity of query answering
- query rewriting
- expressive power
- inverse roles
- inconsistent databases
- decision procedures
- owl ontologies
- regular path queries
- data management
- query containment
- number restrictions
- datalog programs
- machine learning
- double exponential
- optimal solution
- np complete