Skip to Main content Skip to Navigation
Conference papers

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 - 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Wednesday, April 12, 2017 - 9:48:26 AM
Last modification on : Wednesday, September 7, 2022 - 8:14:05 AM
Long-term archiving on: : Thursday, July 13, 2017 - 12:24:17 PM


Files produced by the author(s)


  • HAL Id : hal-01413881, version 1


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⟩



Record views


Files downloads