Tractable fragments of datalog with metric temporal operators
We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the co...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
International Joint Conferences on Artificial Intelligence
2020
|
| _version_ | 1826312775019790336 |
|---|---|
| author | Wałęga, PA Cuenca Grau, B Kaminski, M Kostylev, EV |
| author_facet | Wałęga, PA Cuenca Grau, B Kaminski, M Kostylev, EV |
| author_sort | Wałęga, PA |
| collection | OXFORD |
| description | We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language 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, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog. |
| first_indexed | 2024-03-07T00:41:21Z |
| format | Conference item |
| id | oxford-uuid:83256542-65eb-4c47-8a7b-88c47af2388b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-04-23T08:25:53Z |
| publishDate | 2020 |
| publisher | International Joint Conferences on Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:83256542-65eb-4c47-8a7b-88c47af2388b2024-04-17T10:16:43ZTractable fragments of datalog with metric temporal operatorsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:83256542-65eb-4c47-8a7b-88c47af2388bEnglishSymplectic ElementsInternational Joint Conferences on Artificial Intelligence2020Wałęga, PACuenca Grau, BKaminski, MKostylev, EVWe study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language 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, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog. |
| spellingShingle | Wałęga, PA Cuenca Grau, B Kaminski, M Kostylev, EV Tractable fragments of datalog with metric temporal operators |
| title | Tractable fragments of datalog with metric temporal operators |
| title_full | Tractable fragments of datalog with metric temporal operators |
| title_fullStr | Tractable fragments of datalog with metric temporal operators |
| title_full_unstemmed | Tractable fragments of datalog with metric temporal operators |
| title_short | Tractable fragments of datalog with metric temporal operators |
| title_sort | tractable fragments of datalog with metric temporal operators |
| work_keys_str_mv | AT wałegapa tractablefragmentsofdatalogwithmetrictemporaloperators AT cuencagraub tractablefragmentsofdatalogwithmetrictemporaloperators AT kaminskim tractablefragmentsofdatalogwithmetrictemporaloperators AT kostylevev tractablefragmentsofdatalogwithmetrictemporaloperators |