Stratified negation in limit datalog programs
There has recently been an increasing interest in declarative data analysis, where analytic tasks are specified using a logical language, and their implementation and optimisation are delegated to a general-purpose query engine. Existing declarative languages for data analysis can be formalised as v...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Published: |
IJCAI-ECAI 2018
2018
|
| _version_ | 1826302539885182976 |
|---|---|
| author | Kaminski, M Cuenca Grau, B Kostylev, E Motik, B Horrocks, I |
| author_facet | Kaminski, M Cuenca Grau, B Kostylev, E Motik, B Horrocks, I |
| author_sort | Kaminski, M |
| collection | OXFORD |
| description | There has recently been an increasing interest in declarative data analysis, where analytic tasks are specified using a logical language, and their implementation and optimisation are delegated to a general-purpose query engine. Existing declarative languages for data analysis can be formalised as variants of logic programming equipped with arithmetic function symbols and/or aggregation, and are typically undecidable. In prior work, the language of limit programs was proposed, which is sufficiently powerful to capture many analysis tasks and has decidable entailment problem. Rules in this language, however, do not allow for negation. In this paper, we study an extension of limit programs with stratified negation-as-failure. We show that the additional expressive power makes reasoning computationally more demanding, and provide tight data complexity bounds. We also identify a fragment with tractable data complexity and sufficient expressivity to capture many relevant tasks. |
| first_indexed | 2024-03-07T05:49:06Z |
| format | Conference item |
| id | oxford-uuid:e83a72c7-f4eb-4eed-b272-7965826efeba |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:49:06Z |
| publishDate | 2018 |
| publisher | IJCAI-ECAI 2018 |
| record_format | dspace |
| spelling | oxford-uuid:e83a72c7-f4eb-4eed-b272-7965826efeba2022-03-27T10:45:09ZStratified negation in limit datalog programsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e83a72c7-f4eb-4eed-b272-7965826efebaSymplectic Elements at OxfordIJCAI-ECAI 20182018Kaminski, MCuenca Grau, BKostylev, EMotik, BHorrocks, IThere has recently been an increasing interest in declarative data analysis, where analytic tasks are specified using a logical language, and their implementation and optimisation are delegated to a general-purpose query engine. Existing declarative languages for data analysis can be formalised as variants of logic programming equipped with arithmetic function symbols and/or aggregation, and are typically undecidable. In prior work, the language of limit programs was proposed, which is sufficiently powerful to capture many analysis tasks and has decidable entailment problem. Rules in this language, however, do not allow for negation. In this paper, we study an extension of limit programs with stratified negation-as-failure. We show that the additional expressive power makes reasoning computationally more demanding, and provide tight data complexity bounds. We also identify a fragment with tractable data complexity and sufficient expressivity to capture many relevant tasks. |
| spellingShingle | Kaminski, M Cuenca Grau, B Kostylev, E Motik, B Horrocks, I Stratified negation in limit datalog programs |
| title | Stratified negation in limit datalog programs |
| title_full | Stratified negation in limit datalog programs |
| title_fullStr | Stratified negation in limit datalog programs |
| title_full_unstemmed | Stratified negation in limit datalog programs |
| title_short | Stratified negation in limit datalog programs |
| title_sort | stratified negation in limit datalog programs |
| work_keys_str_mv | AT kaminskim stratifiednegationinlimitdatalogprograms AT cuencagraub stratifiednegationinlimitdatalogprograms AT kostyleve stratifiednegationinlimitdatalogprograms AT motikb stratifiednegationinlimitdatalogprograms AT horrocksi stratifiednegationinlimitdatalogprograms |