Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases
Authors: Gianluca Cima, Marco Console, Roberto Maria Delfino, Maurizio Lenzerini, Antonella Poggi
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we embark in a refined analysis of the combined complexity of answering CQs with inequality atoms and safe negation over RDFS ontologies augmented with disjointness axioms. Firstly, we provide a unified Πp 2 query answering algorithm for the general problem. Secondly, we confirm the generally held conjecture according to which answering CQs with two inequality atoms over such ontologies is already Πp 2hard. This result closes an important gap in the current literature and has an impact on the widely influential problem of query containment. Lastly, for CQs with safe negation, we prove a behavior similar to that of CQs with inequality atoms. |
| Researcher Affiliation | Academia | Gianluca Cima, Marco Console, Roberto Maria Delfino, Maurizio Lenzerini, Antonella Poggi Sapienza University of Rome EMAIL |
| Pseudocode | No | The paper describes algorithms and reductions in prose, such as 'In this section, we provide a nondeterministic algorithm for answering UCQ s, =s over DL-Lite RDFS ontologies.' and 'We illustrate here a LOGSPACE reduction from -CNF...'. However, there are no clearly structured pseudocode or algorithm blocks presented. |
| Open Source Code | No | The paper does not contain any statements regarding the release of source code, nor does it provide links to any code repositories for the described methodologies. |
| Open Datasets | No | The paper is theoretical in nature and analyzes the complexity of query answering over DL-Lite RDFS ontologies. It does not describe or use any specific empirical datasets that would be made publicly available. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental evaluation with datasets, thus the concept of training/test/validation dataset splits is not applicable. |
| Hardware Specification | No | The paper is a theoretical work on computational complexity and query answering algorithms. It does not describe any experiments or implementations that would require specific hardware specifications. |
| Software Dependencies | No | The paper describes theoretical results and algorithms. It does not mention any specific software, libraries, or their version numbers used in an implementation or experimental setup. |
| Experiment Setup | No | The paper presents a theoretical analysis of query answering complexity and algorithms, rather than empirical experiments. Therefore, there are no experimental setup details, hyperparameters, or training configurations described. |