Optimal Nonrecursive Datalog Rewritings of Linear TGDs and Bounded (Hyper)Tree-Width Queries.
Meghyn BienvenuStanislav KikotRoman KontchakovVladislav RyzhikovMichael ZakharyaschevPublished in: Description Logics (2017)
Keyphrases
- conjunctive queries
- tree width
- query language
- datalog programs
- tuple generating dependencies
- query evaluation
- query answering
- query rewriting
- query containment
- data complexity
- unions of conjunctive queries
- expressive power
- combined complexity
- answering queries
- probabilistic databases
- regular path queries
- integrity constraints
- database theory
- data exchange
- inconsistent databases
- deductive databases
- data model
- decision procedures
- special case
- dl lite
- np complete
- transitive closure
- complexity of query answering
- query processing
- relational algebra
- database
- consistent query answering
- dynamic programming
- object oriented