Database Paper Browser

Back to papers

On Propagation of Deletions and Annotations Through Views

Summary: Dichotomy: for monotone queries, finding minimal source deletions that remove a view tuple is either in P or NP-hard, for both view- and source-side-effect objectives. Also formalizes annotation-placement (minimize source annotations producing a view annotation), linking why/where-provenance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1260
Venue
PODS
Year
2002
Pagerank
0.00018608845
Overall Rank
655 | 95.45%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
101 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.0004955674
265 A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification 2005 SIGMOD 0.00029763412
561 An Annotation Management System for Relational Databases 2004 VLDB 0.00020115419
809 Curated Databases 2008 PODS 0.00016430384
2,602 Tracing Data Errors with View-Conditioned Causality 2011 SIGMOD 8.4667197e-05
2,797 Query-Oriented Data Cleaning with Oracles 2015 SIGMOD 8.1108589e-05
2,832 Intensional Associations Between Data and Metadata 2007 SIGMOD 8.050082e-05
2,857 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 8.0037703e-05
3,104 Computing Local Sensitivities of Counting Queries with Joins 2020 SIGMOD 7.5578613e-05
3,218 Reverse Data Management 2011 VLDB 7.3592173e-05
4,260 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB 6.3124474e-05
4,361 The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries 2016 VLDB 6.2559141e-05
4,937 New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins 2020 PODS 5.8187108e-05
4,971 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 5.7938195e-05
6,021 Securing history: Privacy and accountability in database systems 2007 CIDR 5.2415551e-05
6,610 bdbms – A Database Management System for Biological Data 2007 CIDR 4.995269e-05
7,022 A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations 2023 SIGMOD 4.8576599e-05
7,066 On Multiple Semantics for Declarative Database Repairs 2020 SIGMOD 4.8445108e-05
7,556 Interactive Query Explanations Using Fine Grained Provenance 2022 SIGMOD 4.7117814e-05
8,345 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 4.5426916e-05
8,508 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 4.4952414e-05
8,721 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 4.4608778e-05
9,130 Enabling Personal Consent in Databases 2022 VLDB 4.3900952e-05
9,171 InsightNotes: Summary-Based Annotation Management in Relational Databases 2014 SIGMOD 4.3848773e-05
9,851 Adaptive Schema Databases 2017 CIDR 4.2721228e-05
10,355 Resilience for Regular Path Queries: Towards a Complexity Classification 2025 PODS 4.1945683e-05
10,359 Smallest Synthetic Witnesses for Conjunctive Queries 2025 PODS 4.1945683e-05
10,631 Is Integer Linear Programming All You Need for Deletion Propagation? 2025 VLDB 4.1945683e-05
10,875 SDEcho: Efficient Explanation of Aggregated Sequence Difference 2025 VLDB 4.1945683e-05
11,632 Programmable View Update Strategies on Relations 2020 VLDB 4.1945683e-05
11,922 Proactive Annotation Management in Relational Databases 2015 SIGMOD 4.1945683e-05
12,052 Provenance-based Dictionary Refinement in Information Extraction 2013 SIGMOD 4.1945683e-05
12,103 Linguistic Foundations for Bidirectional Transformations (Invited Tutorial) 2012 PODS 4.1945683e-05
12,457 Provenance in Databases (Tutorial Outline) 2007 SIGMOD 4.1945683e-05
12,495 Meta-data Indexing for XPath Location Steps 2006 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
671 Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins 1985 PODS 0.00018370973
895 Updates Of Relational Views 1983 PODS 0.00015534879
2,389 Choosing a View Update Translator by Dialog at View Definition Time 1986 VLDB 8.9124635e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,385 Propagating Functional Dependencies with Conditions 2008 VLDB 5.0875028e-05
5,306 On the Computation of Relational View Complements 2002 PODS 5.5769585e-05
4,971 Maximizing Conjunctive Views in Deletion Propagation 2011 PODS 5.7938195e-05
8,721 Aggregated Deletion Propagation for Counting Conjunctive Query Answers 2021 VLDB 4.4608778e-05
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
10,631 Is Integer Linear Programming All You Need for Deletion Propagation? 2025 VLDB 4.1945683e-05
6,186 On Provenance Minimization 2011 PODS 5.166082e-05
4,260 Multi-Tuple Deletion Propagation: Approximations and Complexity 2013 VLDB 6.3124474e-05
895 Updates Of Relational Views 1983 PODS 0.00015534879
2,857 A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies 2012 PODS 8.0037703e-05