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
N1 - Funding Information:
Benedikt and Kikot were supported by the Engineering and Physical Sciences Research Council, EP/M005852/1,EP/N014359/1, and P/L012138/1. Ostropolski-Nalewaja was supported by the Polish National Science Centre (NCN) grant 2016/23/B/ST6/01438. Romero was funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
Publisher Copyright:
© 2020 Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. All rights reserved.
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 - http://www.scopus.com/inward/record.url?scp=85086272780&partnerID=8YFLogxK
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 -