A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom
Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L...
| Main Authors: | , , , , |
|---|---|
| Format: | Monograph |
| Language: | English |
| Published: |
International Joint Conferences on Artificial Intelligence Organization
2020
|
| Subjects: | |
| Online Access: | https://repository.londonmet.ac.uk/6021/1/2006.04167.pdf |
| _version_ | 1825625511560216576 |
|---|---|
| author | Gerasimova, Olga Kikot, Stanislav Kurucz, Agi Podolskii, Vladimir Zakharyaschev, Michael |
| author_facet | Gerasimova, Olga Kikot, Stanislav Kurucz, Agi Podolskii, Vladimir Zakharyaschev, Michael |
| author_sort | Gerasimova, Olga |
| collection | LMU |
| description | Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0/NL/P/CONP tetrachotomy of path queries under the assumption that the covering classes are disjoint. |
| first_indexed | 2024-07-09T04:01:02Z |
| format | Monograph |
| id | oai:repository.londonmet.ac.uk:6021 |
| institution | London Metropolitan University |
| language | English |
| last_indexed | 2024-07-09T04:01:02Z |
| publishDate | 2020 |
| publisher | International Joint Conferences on Artificial Intelligence Organization |
| record_format | eprints |
| spelling | oai:repository.londonmet.ac.uk:60212020-11-30T09:21:21Z https://repository.londonmet.ac.uk/6021/ A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom Gerasimova, Olga Kikot, Stanislav Kurucz, Agi Podolskii, Vladimir Zakharyaschev, Michael 000 Computer science, information & general works Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSPACE-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0/NL/P/CONP tetrachotomy of path queries under the assumption that the covering classes are disjoint. International Joint Conferences on Artificial Intelligence Organization 2020-07-21 Monograph PeerReviewed text en https://repository.londonmet.ac.uk/6021/1/2006.04167.pdf Gerasimova, Olga, Kikot, Stanislav, Kurucz, Agi, Podolskii, Vladimir and Zakharyaschev, Michael (2020) A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom. Technical Report. International Joint Conferences on Artificial Intelligence Organization. https://arxiv.org/abs/2006.04167 10.24963/kr.2020/41 10.24963/kr.2020/41 |
| spellingShingle | 000 Computer science, information & general works Gerasimova, Olga Kikot, Stanislav Kurucz, Agi Podolskii, Vladimir Zakharyaschev, Michael A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title | A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title_full | A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title_fullStr | A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title_full_unstemmed | A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title_short | A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom |
| title_sort | data complexity and rewritability tetrachotomy of ontology mediated queries with a covering axiom |
| topic | 000 Computer science, information & general works |
| url | https://repository.londonmet.ac.uk/6021/1/2006.04167.pdf |
| work_keys_str_mv | AT gerasimovaolga adatacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT kikotstanislav adatacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT kuruczagi adatacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT podolskiivladimir adatacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT zakharyaschevmichael adatacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT gerasimovaolga datacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT kikotstanislav datacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT kuruczagi datacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT podolskiivladimir datacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom AT zakharyaschevmichael datacomplexityandrewritabilitytetrachotomyofontologymediatedquerieswithacoveringaxiom |