NDLI: A dichotomy in the complexity of deletion propagation with functional dependencies

Please wait, while we are loading the content...

What next?: a half-dozen data management research goals for big data and the cloud

Graph sketches: sparsification, spanners, and subgraphs

The ACM PODS Alberto O. Mendelzon test-of-time award 2012

Linguistic foundations for bidirectional transformations: invited tutorial

The power of the dinur-nissim algorithm: breaking privacy of statistical and graph databases

Space-efficient range reporting for categorical data

Approximate computation and implicit regularization for very large-scale data analysis

Query-based data pricing

The wavelet trie: maintaining an indexed sequence of strings in compressed space

Classification of annotation semirings over query containment

Space-efficient estimation of statistics over sub-sampled streams

Approximating and testing k-histogram distributions in sub-linear time

Worst-case optimal join algorithms: [extended abstract]

A rigorous and customizable framework for privacy

Dynamic top-k range reporting in external memory

Max-Sum diversification, monotone submodular functions and dynamic updates

Local transformations and conjunctive-query equivalence

On the optimality of clustering properties of space filling curves

Efficient approximations of conjunctive queries

Rectangle-efficient aggregation in spatial data streams

Mergeable summaries

Deterministic regular expressions in linear time

Static analysis and optimization of semantic web queries

Indexability of 2D range search revisited: constant redundancy and weak indivisibility

A dichotomy in the complexity of deletion propagation with functional dependencies

Nearest-neighbor searching under uncertainty

On the complexity of package recommendation problems

Randomized algorithms for tracking distributed count, frequencies, and ranks

The complexity of evaluating path expressions in SPARQL

Continuous distributed counting for non-monotonic streams

A dichotomy in the complexity of deletion propagation with functional dependencies

Content Provider	ACM Digital Library
Author	Kimelfeld, Benny
Abstract	A classical variant of the view-update problem is deletion propagation, where tuples from the database are deleted in order to realize a desired deletion of a tuple from the view. This operation may cause a (sometimes necessary) side effect---deletion of additional tuples from the view, besides the intentionally deleted one. The goal is to propagate deletion so as to maximize the number of tuples that remain in the view. In this paper, a view is defined by a self-join-free conjunctive query (sjf-CQ) over a schema with functional dependencies. A condition is formulated on the schema and view definition at hand, and the following dichotomy in complexity is established. If the condition is met, then deletion propagation is solvable in polynomial time by an extremely simple algorithm (very similar to the one observed by Buneman et al.). If the condition is violated, then the problem is NP-hard, and it is even hard to realize an approximation ratio that is better than some constant; moreover, deciding whether there is a side-effect-free solution is NP-complete. This result generalizes a recent result by Kimelfeld et al., who ignore functional dependencies. For the class of sjf-CQs, it also generalizes a result by Cong et al., stating that deletion propagation is in polynomial time if keys are preserved by the view.
Starting Page	191
Ending Page	202
Page Count	12
File Format	PDF
ISBN	9781450312486
DOI	10.1145/2213556.2213584
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Dunctional dependencies Complexity dichotomy Deletion propagation
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A dichotomy in the complexity of deletion propagation with functional dependencies (extended version). Accessible from the author’s home (2012)

A dichotomy in the complexity of deletion propagation with functional dependencies (extended version). Accessible from the author’s home (2012)

Maximizing conjunctive views in deletion propagation

Maximizing Conjunctive Views in Deletion Propagation

A complexity dichotomy for finding disjoint solutions of vertex deletion problems (2009).

Parameterized Complexity Dichotomy for ( r , l )-Vertex Deletion ⋆

A complexity dichotomy for finding disjoint solutions of vertex deletion problems

Approximate Interval-Based Temporal Dependencies: The Complexity Landscape

Multi-tuple deletion propagation: approximations and complexity (2013).

A dichotomy in the complexity of deletion propagation with functional dependencies

Similar Documents

A dichotomy in the complexity of deletion propagation with functional dependencies (extended version). Accessible from the author’s home (2012)

A dichotomy in the complexity of deletion propagation with functional dependencies (extended version). Accessible from the author’s home (2012)

Maximizing conjunctive views in deletion propagation

Maximizing Conjunctive Views in Deletion Propagation

A complexity dichotomy for finding disjoint solutions of vertex deletion problems (2009).

Parameterized Complexity Dichotomy for ( r , l )-Vertex Deletion ⋆

A complexity dichotomy for finding disjoint solutions of vertex deletion problems

Approximate Interval-Based Temporal Dependencies: The Complexity Landscape

Multi-tuple deletion propagation: approximations and complexity (2013).

A dichotomy in the complexity of deletion propagation with functional dependencies