Query Answering with Transitive and Linear-Ordered Data

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

JAIR 2018 pp. 191-264

doi:10.1613/JAIR.1.11240 /jair/2018/amarilli2018jair-query/

Abstract

We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions 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 variants 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 these conditions lead to undecidability.

PDF JAIR Semantic Scholar

Cite

Text

Amarilli et al. "Query Answering with Transitive and Linear-Ordered Data." Journal of Artificial Intelligence Research, 2018. doi:10.1613/JAIR.1.11240

Markdown

[Amarilli et al. "Query Answering with Transitive and Linear-Ordered Data." Journal of Artificial Intelligence Research, 2018.](https://mlanthology.org/jair/2018/amarilli2018jair-query/) doi:10.1613/JAIR.1.11240

BibTeX

@article{amarilli2018jair-query,
  title     = {{Query Answering with Transitive and Linear-Ordered Data}},
  author    = {Amarilli, Antoine and Benedikt, Michael and Bourhis, Pierre and Boom, Michael Vanden},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2018},
  pages     = {191-264},
  doi       = {10.1613/JAIR.1.11240},
  volume    = {63},
  url       = {https://mlanthology.org/jair/2018/amarilli2018jair-query/}
}