Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli 1 Michael Benedikt 2 Pierre Bourhis 3 Michael Vanden Boom 2
1 DBWeb
LTCI - Laboratoire Traitement et Communication de l'Information
3 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.
Type de document :
Communication dans un congrès
Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, Jul 2016, New York, United States
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01413881
Contributeur : Inria Links <>
Soumis le : mercredi 12 avril 2017 - 09:48:26
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : jeudi 13 juillet 2017 - 12:24:17

Fichier

transitive.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01413881, version 1

Citation

Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom. Query Answering with Transitive and Linear-Ordered Data. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, Jul 2016, New York, United States. 〈hal-01413881〉

Partager

Métriques

Consultations de la notice

179

Téléchargements de fichiers

21