On monotonic determinacy and rewritability for recursive queries and views
A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, monotonic determinacy coincides with rewritability as a union of conjunctive queries, and it is decidable in important speci...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM Press
2020
|
| Subjects: | |
| Online Access: | https://repository.londonmet.ac.uk/5792/1/2003.05898.pdf |
| _version_ | 1825625489122787328 |
|---|---|
| author | Benedikt, Michael Kikot, Stanislav Ostropolski-Nalewaja, Piotr Romero, Miguel |
| author_facet | Benedikt, Michael Kikot, Stanislav Ostropolski-Nalewaja, Piotr Romero, Miguel |
| author_sort | Benedikt, Michael |
| collection | LMU |
| description | A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, monotonic determinacy coincides with rewritability as a union of conjunctive queries, and it is decidable in important special cases, such as for CQ views and queries. We investigate the situation for views and queries in the recursive query language Datalog. We give both positive and negative results about the ability to decide monotonic determinacy, and also about the co-incidence of monotonic determinacy with Datalog rewritability. |
| first_indexed | 2024-07-09T04:00:33Z |
| format | Article |
| id | oai:repository.londonmet.ac.uk:5792 |
| institution | London Metropolitan University |
| language | English |
| last_indexed | 2024-07-09T04:00:33Z |
| publishDate | 2020 |
| publisher | ACM Press |
| record_format | eprints |
| spelling | oai:repository.londonmet.ac.uk:57922021-03-15T12:56:43Z https://repository.londonmet.ac.uk/5792/ On monotonic determinacy and rewritability for recursive queries and views Benedikt, Michael Kikot, Stanislav Ostropolski-Nalewaja, Piotr Romero, Miguel 000 Computer science, information & general works A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, monotonic determinacy coincides with rewritability as a union of conjunctive queries, and it is decidable in important special cases, such as for CQ views and queries. We investigate the situation for views and queries in the recursive query language Datalog. We give both positive and negative results about the ability to decide monotonic determinacy, and also about the co-incidence of monotonic determinacy with Datalog rewritability. ACM Press 2020-06 Article PeerReviewed text en https://repository.londonmet.ac.uk/5792/1/2003.05898.pdf Benedikt, Michael, Kikot, Stanislav, Ostropolski-Nalewaja, Piotr and Romero, Miguel (2020) On monotonic determinacy and rewritability for recursive queries and views. PODS 2020: Proceedings of 39th international conference on Principles of Database Systems. https://dl.acm.org/doi/proceedings/10.1145/3375395 |
| spellingShingle | 000 Computer science, information & general works Benedikt, Michael Kikot, Stanislav Ostropolski-Nalewaja, Piotr Romero, Miguel On monotonic determinacy and rewritability for recursive queries and views |
| title | On monotonic determinacy and rewritability for recursive queries and views |
| title_full | On monotonic determinacy and rewritability for recursive queries and views |
| title_fullStr | On monotonic determinacy and rewritability for recursive queries and views |
| title_full_unstemmed | On monotonic determinacy and rewritability for recursive queries and views |
| title_short | On monotonic determinacy and rewritability for recursive queries and views |
| title_sort | on monotonic determinacy and rewritability for recursive queries and views |
| topic | 000 Computer science, information & general works |
| url | https://repository.londonmet.ac.uk/5792/1/2003.05898.pdf |
| work_keys_str_mv | AT benediktmichael onmonotonicdeterminacyandrewritabilityforrecursivequeriesandviews AT kikotstanislav onmonotonicdeterminacyandrewritabilityforrecursivequeriesandviews AT ostropolskinalewajapiotr onmonotonicdeterminacyandrewritabilityforrecursivequeriesandviews AT romeromiguel onmonotonicdeterminacyandrewritabilityforrecursivequeriesandviews |