Temporal datalog with existential quantification
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...
| Main Authors: | , , , |
|---|---|
| פורמט: | Conference item |
| שפה: | English |
| יצא לאור: |
IJCAI
2023
|
| _version_ | 1826310713633669120 |
|---|---|
| author | Lanzinger, M Nissl, M Sallinger, E Walega, PA |
| author_facet | Lanzinger, M Nissl, M Sallinger, E Walega, PA |
| author_sort | Lanzinger, M |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:56:03Z |
| format | Conference item |
| id | oxford-uuid:7390f9fd-efe9-4e59-9cfe-b8beaaed8e7d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:56:03Z |
| publishDate | 2023 |
| publisher | IJCAI |
| record_format | dspace |
| spelling | oxford-uuid:7390f9fd-efe9-4e59-9cfe-b8beaaed8e7d2023-08-21T08:56:17ZTemporal datalog with existential quantificationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:7390f9fd-efe9-4e59-9cfe-b8beaaed8e7dEnglishSymplectic ElementsIJCAI2023Lanzinger, MNissl, MSallinger, EWalega, PAExistential 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. |
| spellingShingle | Lanzinger, M Nissl, M Sallinger, E Walega, PA Temporal datalog with existential quantification |
| title | Temporal datalog with existential quantification |
| title_full | Temporal datalog with existential quantification |
| title_fullStr | Temporal datalog with existential quantification |
| title_full_unstemmed | Temporal datalog with existential quantification |
| title_short | Temporal datalog with existential quantification |
| title_sort | temporal datalog with existential quantification |
| work_keys_str_mv | AT lanzingerm temporaldatalogwithexistentialquantification AT nisslm temporaldatalogwithexistentialquantification AT sallingere temporaldatalogwithexistentialquantification AT walegapa temporaldatalogwithexistentialquantification |