We study the complexity of conjunctive query answering under (weakly-)(frontier-)guarded disjunctive existential rules,i.e.,existential rules extended with disjunction,and their main subclasses,linear rules and inclusion dependencies (IDs).Our main result states that conjunctive query answering under a fixed set of disjunctive IDs is 2EXPTIME-hard.This quite surprising result together with a 2EXPTIME upper bound for weakly-frontier-guarded disjunctive rules,obtained by exploiting recent results on guarded negation first-order logic,gives us a complete picture of the computational complexity of our problem.We also consider a natural subclass of disjunctive IDs,namely frontier-one (only one variable is propagated),for which the combined complexity decreases to EXPTIME.Finally,we show that frontier-guarded rules,combined with negative constraints,are strictly more expressive than DL-LiteHbool,one of the most expressive languages of the DL-Lite family.We also show that query answering under DL-LiteHbool is 2EXPTIMEcomplete in combined complexity.
展开▼
