On Monotonic Determinacy and Rewritability for Recursive Queries and Views

被引：0
作者：
Benedikt, Michael [1 ]
Kikot, Stanislav [2 ]
Ostropolski-Nalewaja, Piotr [3 ]
Romero, Miguel [4 ]
机构：
[1] Univ Oxford, Parks Rd, Oxford OX1 3QD, England
[2] Inst Informat Transmiss Problems, Moscow, Russia
[3] Univ Wroclaw, Wroclaw, Poland
[4] Univ Adolfo Ibanez, Santiago, Chile
来源：
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC | 2023年 / 24卷 / 02期
基金：
英国工程与自然科学研究理事会;
关键词：
Views; Datalog; DATALOG; EQUIVALENCE;
D O I：
10.1145/3572836
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页数：62
相关论文
共 25 条
  • [1] On Monotonic Determinacy and Rewritability For Recursive Queries and Views
    Benedikt, Michael
    Kikot, Stanislav
    Ostropolski-Nalewaja, Piotr
    Romero, Miguel
    PODS'20: PROCEEDINGS OF THE 39TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2020, : 131 - 148
  • [2] Views and Queries: Determinacy and Rewriting
    Nash, Alan
    Segoufin, Luc
    Vianu, Victor
    ACM TRANSACTIONS ON DATABASE SYSTEMS, 2010, 35 (03):
  • [3] Optimizing Recursive Queries with Monotonic Aggregates in DeALS
    Shkapsky, Alexander
    Yang, Mohan
    Zaniolo, Carlo
    2015 IEEE 31ST INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE), 2015, : 867 - 878
  • [4] Determinacy and query rewriting for conjunctive queries and views
    Afrati, Foto N.
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (11) : 1005 - 1021
  • [5] Asymptotic Determinacy of Path Queries Using Union-of-Paths Views
    Francis, Nadime
    THEORY OF COMPUTING SYSTEMS, 2017, 61 (01) : 156 - 190
  • [6] Asymptotic Determinacy of Path Queries Using Union-of-Paths Views
    Nadime Francis
    Theory of Computing Systems, 2017, 61 : 156 - 190
  • [7] Optimizing Recursive Queries with Program Synthesis
    Wang, Yisu Remy
    Khamis, Mahmoud Abo
    Ngo, Hung Q.
    Pichler, Reinhard
    Suciu, Dan
    PROCEEDINGS OF THE 2022 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA (SIGMOD '22), 2022, : 79 - 93
  • [8] First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
    Barcelo, Pablo
    Berger, Gerald
    Lutz, Carsten
    Pieris, Andreas
    PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2018, : 1707 - 1713
  • [9] Decidable containment of recursive queries
    Calvanese, D
    De Giacomo, G
    Vardi, MY
    THEORETICAL COMPUTER SCIENCE, 2005, 336 (01) : 33 - 56
  • [10] First-order rewritability of ontology-mediated queries in linear temporal logic
    Artale, Alessandro
    Kontchakov, Roman
    Kovtunova, Alisa
    Ryzhikov, Vladislav
    Wolter, Frank
    Zakharyaschev, Michael
    ARTIFICIAL INTELLIGENCE, 2021, 299
123