On Monotonic Determinacy and Rewritability for Recursive Queries and Views

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

doi:10.1145/3375395.3387661

On Monotonic Determinacy and Rewritability for Recursive Queries and Views

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Publisher	Association for Computing Machinery
Pages	131-148
Number of pages	18
ISBN (Electronic)	9781450371087
DOIs	https://doi.org/10.1145/3375395.3387661
State	Published - 14 Jun 2020
Externally published	Yes
Event	39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020 - Virtual, Online, United States Duration: 14 Jun 2020 → 19 Jun 2020

Publication series

Name	Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
ISSN (Print)	1055-6338

Conference

Conference	39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020
Country/Territory	United States
City	Virtual, Online
Period	14/06/20 → 19/06/20

Keywords

datalog
monotone determinacy
rewriting

Access to Document

10.1145/3375395.3387661

Cite this

Benedikt, M., Kikot, S., Ostropolski-Nalewaja, P., & Romero, M. (2020). On Monotonic Determinacy and Rewritability for Recursive Queries and Views. In PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (pp. 131-148). (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). Association for Computing Machinery. https://doi.org/10.1145/3375395.3387661

Benedikt, Michael ; Kikot, Stanislav ; Ostropolski-Nalewaja, Piotr et al. / On Monotonic Determinacy and Rewritability for Recursive Queries and Views. PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, 2020. pp. 131-148 (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

@inproceedings{2b1bc5e4242544f8914cc8bf498891c4,

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

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

keywords = "datalog, monotone determinacy, rewriting",

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

note = "Publisher Copyright: {\textcopyright} 2020 Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. All rights reserved.; 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020 ; Conference date: 14-06-2020 Through 19-06-2020",

year = "2020",

month = jun,

day = "14",

doi = "10.1145/3375395.3387661",

language = "English",

series = "Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",

publisher = "Association for Computing Machinery",

pages = "131--148",

booktitle = "PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems",

}

Benedikt, M, Kikot, S, Ostropolski-Nalewaja, P & Romero, M 2020, On Monotonic Determinacy and Rewritability for Recursive Queries and Views. in PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Association for Computing Machinery, pp. 131-148, 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Virtual, Online, United States, 14/06/20. https://doi.org/10.1145/3375395.3387661

On Monotonic Determinacy and Rewritability for Recursive Queries and Views. / Benedikt, Michael; Kikot, Stanislav; Ostropolski-Nalewaja, Piotr et al.
PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, 2020. p. 131-148 (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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 - 2020/6/14

Y1 - 2020/6/14

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

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

KW - datalog

KW - monotone determinacy

KW - rewriting

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

U2 - 10.1145/3375395.3387661

DO - 10.1145/3375395.3387661

M3 - Conference contribution

AN - SCOPUS:85086272780

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 131

EP - 148

BT - PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020

Y2 - 14 June 2020 through 19 June 2020

ER -

Benedikt M, Kikot S, Ostropolski-Nalewaja P, Romero M. On Monotonic Determinacy and Rewritability for Recursive Queries and Views. In PODS 2020 - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery. 2020. p. 131-148. (Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems). doi: 10.1145/3375395.3387661

On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this