Conference item
DatalogMTL over integer timeline
- Alternative title:
- Conference paper
- Abstract:
- We study DatalogMTL—an extension of Datalog with metric temporal operators—under integer semantics, where the temporal domain of both interpretations and temporal operators consists of integer time points only. This is in contrast to the standard semantics, which is defined over the rational timeline. DatalogMTL under integer semantics is an interesting KR language: on the one hand, one can often assume the integer timeline in applications; on the other hand, it captures prominent temporal extensions of Datalog such as Datalog1S. We show that the choice of integer semantics leads to more favourable computational properties. We first show that reasoning over integers is at most as hard as reasoning over rationals for DatalogMTL and its natural fragments. Then, we investigate fragments of DatalogMTL where adopting the integer semantics makes reasoning easier. In particular, we show that complexity drops from P-hard to NC1-complete for the propositional fragment (where all object variables are grounded), and from TC0-hard to ACC0 for the linear fragment where the past diamond operator is the only metric operator allowed in rule bodies. Thus, reasoning in such fragments is both tractable and highly parallelisable, which suggests their appropriateness for data-intensive applications.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 350.1KB, Terms of use)
-
- Publisher copy:
- 10.24963/kr.2020/79
Authors
+ Engineering & Physical Sciences Research Council
More from this funder
- Grant:
- EP/L012138/1
- EP/N014359/1
- EP/K00607X/1
- Publisher:
- IJCAI Organization
- Host title:
- Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning—Main Track
- Pages:
- 768-777
- Publication date:
- 2020-09-17
- Acceptance date:
- 2020-06-03
- Event title:
- KR2020: 17th International Conference on Principles of Knowledge Representation and Reasoning
- Event location:
- Rhodes, Greece
- Event website:
- https://kr2020.inf.unibz.it/
- Event start date:
- 2020-09-12
- Event end date:
- 2020-09-18
- DOI:
- Language:
-
English
- Keywords:
- Pubs id:
-
1111102
- Local pid:
-
pubs:1111102
- Deposit date:
-
2020-06-09
Terms of use
- Copyright holder:
- International Joint Conferences on Artificial Intelligence Organization
- Copyright date:
- 2020
- Rights statement:
- © 2020 International Joint Conferences on Artificial Intelligence Organization.
- Notes:
- This conference paper was presented at KR2020: 17th International Conference on Principles of Knowledge Representation and Reasoning, September 12-18, 2020, Rhodes, Greece. This is the accepted manuscript version of the paper. The final version is available online from the International Joint Conferences on Artificial Intelligence Organization at: https://doi.org/10.24963/kr.2020/79
If you are the owner of this record, you can report an update to it here: Report update to this record