License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2018.15
URN: urn:nbn:de:0030-drops-85971
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8597/
Go to the corresponding LIPIcs Volume Portal

Jung, Jean Christoph ; Lutz, Carsten ; Martel, Mauricio ; Schneider, Thomas

Querying the Unary Negation Fragment with Regular Path Expressions

pdf-format:
LIPIcs-ICDT-2018-15.pdf (0.5 MB)

Abstract

The unary negation fragment of first-order logic (UNFO) has recently been proposed as a generalization of modal logic that shares many of its good computational and model-theoretic properties. It is attractive from the perspective of database theory because it can express conjunctive queries (CQs) and ontologies formulated in many description logics (DLs). Both are relevant for ontology-mediated querying and, in fact, CQ evaluation under UNFO ontologies (and thus also under DL ontologies) can be `expressed' in UNFO as a satisfiability problem. In this paper, we consider the natural extension of UNFO with regular expressions on binary relations. The resulting logic UNFOreg can express (unions of) conjunctive two-way regular path queries (C2RPQs) and ontologies formulated in DLs that include transitive roles and regular expressions on roles. Our main results are that evaluating C2RPQs under UNFOreg ontologies is decidable, 2ExpTime-complete in combined complexity, and coNP-complete in data complexity, and that satisfiability in UNFOreg is 2ExpTime-complete, thus not harder than in UNFO.

BibTeX - Entry

@InProceedings{jung_et_al:LIPIcs:2018:8597,
  author =	{Jean Christoph Jung and Carsten Lutz and Mauricio Martel and Thomas Schneider},
  title =	{{Querying the Unary Negation Fragment with Regular Path Expressions}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8597},
  URN =		{urn:nbn:de:0030-drops-85971},
  doi =		{10.4230/LIPIcs.ICDT.2018.15},
  annote =	{Keywords: Query Answering, Regular Path Queries, Decidable Fragments of First-Order Logic, Computational Complexity}
}

Keywords: Query Answering, Regular Path Queries, Decidable Fragments of First-Order Logic, Computational Complexity
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI