Complexity of Approximate Query Answering under Inconsistency in Datalog+/-
Authors: Thomas Lukasiewicz, Enrico Malizia, Cristian Molinaro
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog languages. We give a precise picture of the complexity of BCQ answering from existential rules under the IAR, ICR, GIAR, and GICR semantics, which is summarized in Fig. 1; it ranges from membership in AC0 to 2EXP-completeness. |
| Researcher Affiliation | Academia | 1 Department of Computer Science, University of Oxford, UK 2 Department of Computer Science, University of Exeter, UK 3 DIMES, University of Calabria, Italy |
| Pseudocode | No | The paper contains theoretical discussions, theorems, and proofs, but no structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | This is a theoretical paper that focuses on complexity analysis of query answering under inconsistency in Datalog. It does not utilize or refer to publicly available datasets in the context of empirical evaluation. |
| Dataset Splits | No | As a theoretical paper, it does not involve empirical experiments with datasets that would require training, validation, or test splits. |
| Hardware Specification | No | As a theoretical paper, no specific hardware used for experiments is mentioned or described. |
| Software Dependencies | No | The paper is theoretical and focuses on complexity analysis rather than empirical implementation. Therefore, it does not list software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that does not involve empirical experiments, and thus no experimental setup details or hyperparameters are provided. |