How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC.
Bartosz BednarczykSebastian RudolphPublished in: J. Artif. Intell. Res. (2023)
Keyphrases
- conjunctive queries
- np complete
- dl lite
- query answering
- query evaluation
- relational database theory
- decision procedures
- description logics
- data complexity
- integrity constraints
- bounded treewidth
- query rewriting
- acyclic conjunctive queries
- query language
- data exchange
- conjunctive query containment
- np hard
- logic programming
- upper bound
- boolean expressions
- probabilistic databases
- logic programs
- special case
- query containment
- unions of conjunctive queries
- schema mappings
- answering queries
- database
- incomplete information
- data integration
- database systems