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

https://hal.inria.fr/hal-01413881
Contributor : Inria Links <>
Submitted on : Wednesday, April 12, 2017 - 9:48:26 AM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM
Long-term archiving on: : Thursday, July 13, 2017 - 12:24:17 PM

File

transitive.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

574

Files downloads

200