2026-07-24T14:56:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8597 2024-03-06T10:42:28Z ddc:004 open_access

Querying the Unary Negation Fragment with Regular Path Expressions Jung, Jean Christoph Lutz, Carsten Martel, Mauricio Schneider, Thomas Query Answering Regular Path Queries Decidable Fragments of First-Order Logic Computational Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean Christoph Jung and Carsten Lutz and Mauricio Martel and Thomas Schneider 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.15 urn:nbn:de:0030-drops-85971 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode