Existential Rule Languages with Finite Chase: Complexity and Expressiveness
Authors: Heng Zhang, Yan Zhang, Jia-Huai You
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a novel approach for classifying the rule languages with finite chase. Using this approach, a family of decidable rule languages, which extend the existing languages with the finite chase property, are naturally defined. We then study the complexity of these languages. Although all of them are tractable for data complexity, we show that their combined complexity can be arbitrarily high. Furthermore, we prove that all the rule languages with finite chase that extend the weakly acyclic language are of the same expressiveness as the weakly acyclic one, while rule languages with higher combined complexity are in general more succinct than those with lower combined complexity. |
| Researcher Affiliation | Academia | Heng Zhang1 and Yan Zhang1 and Jia-Huai You2 1School of Computing, Engineering and Mathematics, University of Western Sydney, Penrith, NSW 2751, Australia 2Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada |
| Pseudocode | No | The paper contains formal definitions, theorems, and proof sketches, but no explicit pseudocode or algorithm blocks are provided. |
| Open Source Code | No | The paper does not contain any statement about releasing source code or provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical in nature, focusing on complexity and expressiveness of rule languages. It does not involve empirical experiments with datasets, and therefore, does not provide information about public datasets. |
| Dataset Splits | No | The paper is a theoretical work and does not involve empirical experiments with datasets. Therefore, it does not provide details about training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical in nature and does not describe any experimental setup, hyperparameters, or training configurations. |