Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms
Authors: Meghyn Bienvenu, Magdalena Ortiz, Mantas Simkus
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families. Our results demonstrate that in data complexity, the cost of moving to this richer query language is as low as one could wish for: the problem is NL-complete for DL-Lite and P-complete for EL. The combined complexity of query answering increases from NP- to PSpace-complete, but for two-way regular path queries (without conjunction), we show that query answering is tractable even with respect to combined complexity. Our main contributions can be summarized as follows: We establish a P lower bound in combined complexity for answering 2RPQs in DL-Lite... We present an algorithm for answering 2RPQs over DL-Lite R and ELH knowledge bases that runs in polynomial time in combined complexity... We show that answering CRPQs is PSpace-hard for both DL-Lite and EL... We develop a query rewriting procedure for answering C2RPQs in DL-Lite R and ELH, which we use to show that the problem is feasible in PSpace for both logics. |
| Researcher Affiliation | Academia | Meghyn Bienvenu EMAIL Laboratoire de Recherche en Informatique, CNRS & Universit e Paris-Sud, France; Magdalena Ortiz EMAIL Mantas ˇSimkus EMAIL Institute of Information Systems, TU Wien, Austria. All authors are affiliated with academic institutions (CNRS, Université Paris-Sud, and TU Wien). |
| Pseudocode | Yes | In Figure 9, we present a simple non-deterministic algorithm Basic Eval for answering 2RPQs over DL-Lite RDFS knowledge bases... (p.16) ...the extended evaluation algorithm Eval Atom in Figure 11 that handles DL-Lite R and ELH KBs. (p.21) ...In Figure 13, we implement this intuition by defining an algorithm One Step that performs a single (non-deterministic) rewriting step. (p.23) In Figure 16, we present a non-deterministic algorithm Eval Query for C2RPQ answering in DL-Lite R and ELH. (p.29) In Figure 17, we present a deterministic query rewriting algorithm Poly Rewrite that takes as input an NFA α and a DL-Lite R or ELH TBox T and outputs a set of queries... |
| Open Source Code | No | An important challenge for future work is to implement and experimentally evaluate the developed algorithms. |
| Open Datasets | No | Example 2.1. As a motivating example, we consider the domain of public transport and urban mobility. A partial database for this domain is presented in Figure 2. ... which we call Amob... This is nothing else but a graphical representation of a DL ABox, which we call Amob, where each label A on a node b corresponds to the concept assertion A(b), and an arc labeled r from node b to node c corresponds to the role assertion r(b, c). |
| Dataset Splits | No | The paper is theoretical, focusing on algorithms and complexity bounds. It does not conduct empirical studies that would require dataset splits. |
| Hardware Specification | No | The paper is purely theoretical, focusing on the design and analysis of algorithms and complexity. There is no mention of experimental setup or hardware used for running any computations. |
| Software Dependencies | No | The paper is purely theoretical, focusing on the design and analysis of algorithms and complexity. There is no mention of software used for empirical experiments, nor any specific version numbers for any tools or libraries. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithms and complexity analysis. It does not contain details about experimental setup, hyperparameters, or training configurations, as no experiments were conducted. |