On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Michael Benedikt; Stanislav Kikot; Piotr Ostropolski-Nalewaja; Miguel Romero

doi:10.1145/3572836

On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Michael Benedikt
, Stanislav Kikot
, Piotr Ostropolski-Nalewaja
, Miguel Romero

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	3572836
Journal	ACM Transactions on Computational Logic
Volume	24
Issue number	2
DOIs	https://doi.org/10.1145/3572836
State	Published - 17 Mar 2023
Externally published	Yes

Keywords

Datalog
Views

Access to Document

10.1145/3572836

Cite this

@article{ef596d2b80ae42f39d7b556d833421ec,

title = "On Monotonic Determinacy and Rewritability for Recursive Queries and Views",

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.",

keywords = "Datalog, Views",

author = "Michael Benedikt and Stanislav Kikot and Piotr Ostropolski-Nalewaja and Miguel Romero",

note = "Publisher Copyright: {\textcopyright} 2023 Association for Computing Machinery.",

year = "2023",

month = mar,

day = "17",

doi = "10.1145/3572836",

language = "English",

volume = "24",

journal = "ACM Transactions on Computational Logic",

issn = "1529-3785",

publisher = "Association for Computing Machinery",

number = "2",

}

TY - JOUR

T1 - On Monotonic Determinacy and Rewritability for Recursive Queries and Views

AU - Benedikt, Michael

AU - Kikot, Stanislav

AU - Ostropolski-Nalewaja, Piotr

AU - Romero, Miguel

PY - 2023/3/17

Y1 - 2023/3/17

N2 - 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.

AB - 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.

KW - Datalog

KW - Views

UR - https://www.scopus.com/pages/publications/85152897999

U2 - 10.1145/3572836

DO - 10.1145/3572836

M3 - Article

AN - SCOPUS:85152897999

SN - 1529-3785

VL - 24

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

IS - 2

M1 - 3572836

ER -

On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Abstract

Keywords

Access to Document

Fingerprint

Cite this