On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Michael Benedikt - , University of Oxford (Author)
  • Stanislav Kikot - , RAS - Institute for Information Transmission Problems (Author)
  • Piotr Ostropolski-Nalewaja - , University of Wrocław (Author)
  • Miguel Romero - , Universidad Adolfo Ibáñez (Author)

Abstract

A query Q is monotonically determined over a set of views V 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 conjunctive query 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.

Details

Original languageEnglish
Article number3572836
Number of pages62
JournalACM Transactions on Computational Logic : TOCL
Volume24
Issue number2
Publication statusPublished - 17 Mar 2023
Peer-reviewedYes
Externally publishedYes

External IDs

Scopus 85152897999

Keywords