A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic.
Johann Brault-BaronPublished in: CSL (2012)
Keyphrases
- acyclic conjunctive queries
- conjunctive queries
- np complete
- relational database theory
- boolean formulae
- bounded treewidth
- tuple generating dependencies
- query evaluation
- integrity constraints
- query answering
- data complexity
- database theory
- conp complete
- decision procedures
- np hard
- query rewriting
- data exchange
- query language
- dnf formulas
- conjunctive query containment
- universal relation
- special case
- probabilistic databases
- pac learnability
- datalog programs
- functional dependencies
- logical equivalence
- optimal solution