Query answering with transitive and linear-ordered data

Antoine Amarilli; Michael Benedikt; Pierre Bourhis; Michael Vanden Boom

Query answering with transitive and linear-ordered data

Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English
Pages (from-to)	893-899
Number of pages	7
Journal	IJCAI International Joint Conference on Artificial Intelligence
Volume	2016-January
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States Duration: 9 Jul 2016 → 15 Jul 2016

Cite this

@article{e5a5b6b550054ba9bfb620147488a8bf,

title = "Query answering with transitive and linear-ordered data",

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.",

author = "Antoine Amarilli and Michael Benedikt and Pierre Bourhis and \{Vanden Boom\}, Michael",

year = "2016",

month = jan,

day = "1",

language = "English",

volume = "2016-January",

pages = "893--899",

journal = "IJCAI International Joint Conference on Artificial Intelligence",

issn = "1045-0823",

note = "25th International Joint Conference on Artificial Intelligence, IJCAI 2016 ; Conference date: 09-07-2016 Through 15-07-2016",

}

TY - JOUR

T1 - Query answering with transitive and linear-ordered data

AU - Amarilli, Antoine

AU - Benedikt, Michael

AU - Bourhis, Pierre

AU - Vanden Boom, Michael

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

M3 - Conference article

AN - SCOPUS:85006164454

SN - 1045-0823

VL - 2016-January

SP - 893

EP - 899

JO - IJCAI International Joint Conference on Artificial Intelligence

JF - IJCAI International Joint Conference on Artificial Intelligence

T2 - 25th International Joint Conference on Artificial Intelligence, IJCAI 2016

Y2 - 9 July 2016 through 15 July 2016

ER -

Query answering with transitive and linear-ordered data

Abstract

Fingerprint

Cite this