资源论文The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules

The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules

2019-11-11 | |  67 |   38 |   0
Abstract 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 2E XP T IME-hard. This quite surprising result together with a 2E X P T IME 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 E XP T IME. Finally, we show that frontier-guarded rules, combined with negative constraints, are strictly more expressive than DL-LiteH bool , one of the most expressive languages of the DL-Lite family. We also show that query answering under DL-LiteH bool is 2E XP T IME complete in combined complexity.

上一篇:Positive Subsumption in Fuzzy EL with General t-Norms

下一篇:Abstract Dialectical Frameworks Revisited

用户评价
全部评价

热门资源

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Rating-Boosted La...

    The performance of a recommendation system reli...

  • Hierarchical Task...

    We extend hierarchical task network planning wi...