Towards Efficient Reasoning under Guarded-based ...
Document type :
Communication dans un congrès avec actes
Title :
Towards Efficient Reasoning under Guarded-based Disjunctive Existential Rules
Author(s) :
Bourhis, Pierre [Auteur]
Linking Dynamic Data [LINKS]
Morak, Michael [Auteur]
Departement of Computer of Science University of Oxford
Pieris, Andréas [Auteur]

Linking Dynamic Data [LINKS]
Morak, Michael [Auteur]
Departement of Computer of Science University of Oxford
Pieris, Andréas [Auteur]
Conference title :
Mathematical Foundations of Computer Science (MFCS)
City :
Budapest
Country :
Hongrie
Start date of the conference :
2014-08-25
Publication date :
2014-08-25
HAL domain(s) :
Informatique [cs]/Intelligence artificielle [cs.AI]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
The complete picture of the complexity of answering (unions of) conjunctive queries under the main guarded-based classes of disjunc- tive existential rules has been recently settled. It has been shown that the problem is ...
Show more >The complete picture of the complexity of answering (unions of) conjunctive queries under the main guarded-based classes of disjunc- tive existential rules has been recently settled. It has been shown that the problem is very hard, namely 2ExpTime-complete, even for fixed sets of rules expressed in lightweight formalisms. This gives rise to the question whether its complexity can be reduced by restricting the query language. Several subclasses of conjunctive queries have been proposed with the aim of reducing the complexity of classical database problems such as query evaluation and query containment. Three of the most prominent subclasses of this kind are queries of bounded hypertree-width, queries of bounded treewidth and acyclic queries. The central objective of the present paper is to understand whether the above query languages have a positive impact on the complexity of query answering under the main guarded-based classes of disjunctive existential rules. We show that (unions of) conjunctive queries of bounded hypertree- width and of bounded treewidth do not reduce the complexity of our problem, even if we focus on predicates of bounded arity, or on fixed sets of disjunctive existential rules. Regarding acyclic queries, although our problem remains 2ExpTime-complete in general, in some relevant set- tings the complexity reduces to ExpTime-complete; in fact, this requires to bound the arity of the predicates, and for some expressive guarded- based formalisms, to fix the set of rules.Show less >
Show more >The complete picture of the complexity of answering (unions of) conjunctive queries under the main guarded-based classes of disjunc- tive existential rules has been recently settled. It has been shown that the problem is very hard, namely 2ExpTime-complete, even for fixed sets of rules expressed in lightweight formalisms. This gives rise to the question whether its complexity can be reduced by restricting the query language. Several subclasses of conjunctive queries have been proposed with the aim of reducing the complexity of classical database problems such as query evaluation and query containment. Three of the most prominent subclasses of this kind are queries of bounded hypertree-width, queries of bounded treewidth and acyclic queries. The central objective of the present paper is to understand whether the above query languages have a positive impact on the complexity of query answering under the main guarded-based classes of disjunctive existential rules. We show that (unions of) conjunctive queries of bounded hypertree- width and of bounded treewidth do not reduce the complexity of our problem, even if we focus on predicates of bounded arity, or on fixed sets of disjunctive existential rules. Regarding acyclic queries, although our problem remains 2ExpTime-complete in general, in some relevant set- tings the complexity reduces to ExpTime-complete; in fact, this requires to bound the arity of the predicates, and for some expressive guarded- based formalisms, to fix the set of rules.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-01053179/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01053179/document
- Open access
- Access the document
- document
- Open access
- Access the document
- mfcs2014.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- mfcs2014.pdf
- Open access
- Access the document