Answering Conjunctive Regular Path Queries over Guarded Existential Rules
Authors: Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, Michael Thomazo
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We obtain tight complexity results for both combined and data complexities over guarded rules and their linear subclass. Namely, CRPQ answering in the linear case is EXPTIME-complete in combined complexity, PSPACE-complete in combined complexity with bounded arity and NL-complete in data complexity (Thm 1); hence, it is not more difficult than RPQ answering, except for combined complexity with bounded arity (in which case the complexity is again the same as for DL-Lite R). In the guarded case, CRPQ answering is 2EXPTIME-complete in combined complexity, EXPTIME-complete in combined complexity with bounded arity, and PTIME-complete in data complexity (Thm 2); hence, it is not more difficult than plain CQ answering. To achieve these results, we first investigate the case of linear rules and provide a CRPQ answering algorithm that uses RPQ answering as an oracle and runs within the mentioned complexity classes. The matching lower bounds come from earlier results on RPQ and CQ answering. We next provide a non-trivial reduction of the guarded case to the linear case. |
| Researcher Affiliation | Academia | Jean-François Baget Inria, France baget@lirmm.fr Meghyn Bienvenu CNRS, France meghyn@lirmm.fr Marie-Laure Mugnier Univ. Montpellier, France mugnier@lirmm.fr Michael Thomazo Inria, France michael.thomazo@inria.fr |
| Pseudocode | No | The paper describes algorithms and procedures (e.g., 'CRPQ answering algorithm', 'alternative chase procedure'), but it does not present them in a structured pseudocode block or a clearly labeled 'Algorithm' section. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no training data is mentioned or made available. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no validation data or splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity results and algorithms, thus there is no mention of specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on complexity results and algorithms; it does not mention any specific software dependencies with version numbers for replication. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity results and algorithms; it does not describe an experimental setup with hyperparameters or system-level training settings. |