Conference item
Temporal datalog with existential quantification
- Abstract:
- Existential rules, also known as tuple-generating dependencies (TGDs) or Datalog± rules, are heavily studied in the communities of Knowledge Representation and Reasoning, Semantic Web, and Databases, due to their rich modelling capabilities. In this paper we consider TGDs in the temporal setting, by introducing and studying DatalogMTL∃—an extension of metric temporal Datalog (DatalogMTL) obtained by allowing for existential rules in programs. We show that DatalogMTL∃ is undecidable even in the restricted cases of guarded and weakly-acyclic programs. To address this issue we introduce uniform semantics which, on the one hand, is well-suited for modelling temporal knowledge as it prevents from unintended value invention and, on the other hand, provides decidability of reasoning; in particular, it becomes 2-ExpSpace-complete for weakly-acyclic programs but remains undecidable for guarded programs. We provide an implementation for the decidable case and demonstrate its practical feasibility. Thus we obtain an expressive, yet decidable, rule-language and a system which is suitable for complex temporal reasoning with existential rules.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 262.1KB, Terms of use)
-
- Publisher copy:
- 10.24963/ijcai.2023/365
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Grant:
- EP/V050869/1
- Grant:
- EP/S019111/1 RG95975
- Grant:
- EP/S032347/1
- Publisher:
- IJCAI
- Pages:
- 3277-3285
- Publication date:
- 2023-08-11
- Acceptance date:
- 2023-04-20
- Event title:
- 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023)
- Event location:
- Macau, SAR
- Event website:
- https://ijcai-23.org/
- Event start date:
- 2023-08-19
- Event end date:
- 2023-08-25
- DOI:
- Language:
-
English
- Keywords:
- Pubs id:
-
1341475
- Local pid:
-
pubs:1341475
- Deposit date:
-
2023-05-18
- ARK identifier:
Terms of use
- Copyright date:
- 2023
- Notes:
- This paper was presented at the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023), 19th - 25th August 2023, Macau, SAR. For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission. This is the accepted manuscript version of the article. The final version is available online from IJCAI at: https://doi.org/10.24963/ijcai.2023/365
If you are the owner of this record, you can report an update to it here: Report update to this record