TY - GEN
T1 - Oblivious and semi-oblivious boundedness for existential rules
AU - Bourhis, Pierre
AU - Leclère, Michel
AU - Mugnier, Marie Laure
AU - Tison, Sophie
AU - Ulliana, Federico
AU - Galois, Lily
N1 - Publisher Copyright:
© 2019 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem.
AB - We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem.
U2 - 10.24963/ijcai.2019/219
DO - 10.24963/ijcai.2019/219
M3 - Conference contribution
AN - SCOPUS:85074904787
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 1581
EP - 1587
BT - Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
A2 - Kraus, Sarit
PB - International Joint Conferences on Artificial Intelligence
T2 - 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
Y2 - 10 August 2019 through 16 August 2019
ER -