The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard.
Bartosz BednarczykSebastian RudolphPublished in: CoRR (2021)
Keyphrases
- conjunctive queries
- np complete
- query containment
- pspace complete
- query answering
- dl lite
- data complexity
- query evaluation
- relational database theory
- description logics
- exptime complete
- integrity constraints
- query rewriting
- query language
- upper bound
- decision procedures
- data exchange
- acyclic conjunctive queries
- bounded treewidth
- np hard
- unions of conjunctive queries
- probabilistic databases
- special case
- boolean expressions
- datalog programs
- conjunctive query containment
- schema mappings
- data integration
- logic programming
- regular path queries
- computational complexity
- decision problems
- dnf formulas
- first order logic
- fixpoint
- transitive closure
- satisfiability problem
- incomplete information
- expressive power
- tuple generating dependencies
- knowledge representation
- data sources