The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard (Extended Abstract).
Bartosz BednarczykSebastian RudolphPublished in: Description Logics (2021)
Keyphrases
- extended abstract
- conjunctive queries
- np complete
- query containment
- pspace complete
- query answering
- data complexity
- query evaluation
- description logics
- dl lite
- exptime complete
- integrity constraints
- relational database theory
- query rewriting
- decision procedures
- unions of conjunctive queries
- upper bound
- query language
- acyclic conjunctive queries
- bounded treewidth
- special case
- boolean expressions
- regular path queries
- decision problems
- data exchange
- probabilistic databases
- satisfiability problem
- first order logic
- datalog programs
- logic programming
- computational complexity
- relational queries
- functional dependencies
- dnf formulas
- np hard
- answering queries
- database design
- schema mappings
- regular expressions
- knowledge representation
- universal relation