Functional dependency restricted insertion propagation
type: Item
instance of: scholarly article
title: Functional dependency restricted insertion propagation
zbMATH Open document ID: 1440.68058
author: Dongjing Miao
author: Zhipeng Cai
author: Xianmin Liu
author: Jianzhong Li
published in: Theoretical Computer Science
publication date: 2020-04-08T00:00:00Z
review text: Views in database systems provide an excerpt of underlying information, and they can be used to restrict the amount of information that specific target users need to know or are allowed to access. While processing of queries over views is simple, propagating updates expressed over views to the underlying base data is known to be hard (and impossible in a side-effect-free manner for large classes of views). This paper presents complexity results to decide whether there is a side-effect-free propagation of given insertions into subclasses of monotonic views expressed in the relational algebra over relations with functional dependencies. The problem is abbreviated with the acronym FD-vsef-IP (Functional Dependency, view side-effect-free, Insertion Propagation) and considered for insertions of single tuples as well as groups of tuples. In their theorems, the authors establish the following results: FD-vsef-IP is NP-complete for union views under group insertions on data complexity (Theorem 1). FD-vsef-IP is coNP-complete for select-join queries under group insertions on combined complexity (Theorem 2). FD-vsef-IP is NP-complete for select-project-join queries under group insertions with finite domain on data complexity; it is in PTime for select-project-join queries without self-joins under single insertions on data complexity (Theorem 3). FD-vsef-IP is \(\Sigma_2^{\mathrm{P}}\)-complete for select-project-join queries under group insertions with finite domain on combined complexity (Theorem 4). FD-vsef-IP is \(\Sigma_2^{\mathrm{P}}\)-complete for select-join-union queries under group insertions with finite domain on combined complexity (Theorem 5). This paper is restricted to the above complexity results. Practical aspects (such as (a) what to do if an insertion cannot be propagated in a side-effect-free manner or (b) whether to allow view updates if such cases can arise) are not considered.
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7188525
zbMATH Keywords: view update
zbMATH Keywords: complexity
zbMATH Keywords: relational algebra
zbMATH Keywords: insertion propagation
zbMATH Keywords: functional dependency
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.03.043
OpenAlex ID: W2607189612
cites work: On the correct translation of update operations on relational views
cites work: Update semantics of relational views
cites work: Updates of Relational Views
cites work: On the complexity of sampling query feedback restricted database repair of functional dependency violations
cites work: Q4864249
DOI: 10.1016/J.TCS.2017.03.043
Recommended article: On the Complexity of Insertion Propagation with Functional Dependency Constraints
Recommended article: Inclusion dependencies and their interaction with functional dependencies
Recommended article: Q3813330
Recommended article: Computer Aided Verification
Recommended article: Relational decomposition through partial functional dependencies
Recommended article: Functional dependencies in incomplete databases with limited domains
Recommended article: Perspectives of System Informatics
Recommended article: Q3792281
Recommended article: Abstract functional dependency structures
Recommended article: Understanding functional dependencies via constraint handling rules
description: scientific article; zbMATH DE number 7188525