Tractability Frontier of Data Complexity in Team Semantics.

Arnaud Durand Juha Kontinen Nicolas de Rugy-Altherre Jouko Väänänen

Published in: GandALF (2015)

Keyphrases

data complexity
np complete
expressive power
query answering
fixpoint semantics
schema mappings
conjunctive queries
query evaluation

query complexity
data exchange
exptime complete
lower complexity
inconsistent databases
formal semantics
logic programming
computational complexity

dl lite
query containment
double exponential
ontology languages
constraint satisfaction
query answers
datalog programs
first order logic

database query languages
satisfiability problem
regular path queries
data sets
np hard
relational databases
multi agent
artificial intelligence