Tractable Fragments of Datalog with Metric Temporal Operators
Authors: Przemysław A. Wałęga, Bernardo Cuenca Grau, Mark Kaminski, Egor V. Kostylev
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the data complexity of reasoning for fragments of Datalog MTL an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in Datalog MTL is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the core fragment, which disallows conjunction in rule bodies, and show that reasoning remains PSPACE-hard. Intractability prompts us to also limit the kinds of temporal operators allowed in rules, and we propose a practical core fragment for which reasoning becomes TC0-complete. Finally, we show that this fragment can be extended by allowing linear conjunctions in rule bodies (with at most one IDB atom), and show that the resulting fragment is NLcomplete, thus no harder than plain linear Datalog. |
| Researcher Affiliation | Academia | Department of Computer Science, University of Oxford, UK {przemyslaw.walega, bernardo.cuenca.grau, mark.kaminski, egor.kostylev}@cs.ox.ac.uk |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository link, explicit statement of code release) for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis. It defines "dataset" as a theoretical concept within its formal framework but does not refer to any specific publicly available dataset used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, hyperparameters, or training configurations. |