Functional dependency restricted insertion propagation
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.
- On the Complexity of Insertion Propagation with Functional Dependency Constraints
- Inclusion dependencies and their interaction with functional dependencies
- scientific article; zbMATH DE number 4083037
- Computer Aided Verification
- Relational decomposition through partial functional dependencies
- Functional dependencies in incomplete databases with limited domains
- Implication of functional dependencies for recursive queries
- scientific article; zbMATH DE number 4057062
- Abstract functional dependency structures
- Understanding functional dependencies via constraint handling rules
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- On the complexity of sampling query feedback restricted database repair of functional dependency violations
- On the correct translation of update operations on relational views
- Update semantics of relational views
- Updates of Relational Views
This page was built for publication: Functional dependency restricted insertion propagation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1986557)
