NDLI: Maximizing Conjunctive Views in Deletion Propagation

Content Provider	ACM Digital Library
Author	Vondrák, Jan Williams, Ryan Kimelfeld, Benny
Copyright Year	2012
Description	Author Affiliation: Stanford University(Vondrk, Jan; Ibm research -- almaden (kimelfeld, Benny; Williams, Ryan))
Abstract	In deletion propagation, tuples from the database are deleted in order to reflect the deletion of a tuple from the view. Such an operation may result in the (often necessary) deletion of additional tuples from the view, besides the intentionally deleted one. The article studies the complexity of deletion propagation, where the view is defined by a conjunctive query (CQ), and the goal is to maximize the number of tuples that remain in the view. Buneman et al. showed that for some simple CQs, this problem can be solved by a straightforward algorithm, which is called here the unidimensional algorithm. The article identifies additional cases of CQs where the unidimensional algorithm succeeds, and in contrast, shows that for some other CQs the problem is NP-hard to approximate better than some constant ratio. In fact, it is shown here that among the CQs without self joins, the hard CQs are exactly the ones that the unidimensional algorithm fails on. In other words, the following dichotomy result is proved: for every CQ without self joins, deletion propagation is either APX-hard or solvable (in polynomial time) by the unidimensional algorithm. The article then presents approximation algorithms for certain CQs where deletion propagation is APX-hard. Specifically, two constant-ratio (and polynomial-time) approximation algorithms are given for the class of sunflower CQs (i.e., CQs having a sunflower hypergraph) without self joins. The first algorithm, providing the approximation ratio $1 ™ 1/\textit{e},$ is obtained by formulating the problem at hand as that of maximizing a monotone submodular function subject to a matroid constraint, and then using a known algorithm for such maximization. The second algorithm gives a smaller approximation ratio, 1/2, yet in polynomial time even under combined complexity. Finally, it is shown that self joins can significantly harden approximation in deletion propagation.
Starting Page	1
Ending Page	37
Page Count	37
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2389241.2389243
Volume Number	37
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Deletion propagation Approximation Dichotomy
Content Type	Text
Resource Type	Article
Subject	Information Systems

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

Maximizing conjunctive views in deletion propagation

Amaximizing conjunctive views in deletion propagation∗.

Maximizing conjunctive views in deletion propagation (2011)

The dichotomy of probabilistic inference for unions of conjunctive queries

A dichotomy in the complexity of deletion propagation with functional dependencies

Constant Delay Enumeration for Conjunctive Queries

Certain conjunctive query answering in first-order logic

Containment of conjunctive queries: beyond relations as sets

Views and queries: Determinacy and rewriting

Maximizing Conjunctive Views in Deletion Propagation

Similar Documents

Maximizing conjunctive views in deletion propagation

Amaximizing conjunctive views in deletion propagation∗.

Maximizing conjunctive views in deletion propagation (2011)

The dichotomy of probabilistic inference for unions of conjunctive queries

A dichotomy in the complexity of deletion propagation with functional dependencies

Constant Delay Enumeration for Conjunctive Queries

Certain conjunctive query answering in first-order logic

Containment of conjunctive queries: beyond relations as sets

Views and queries: Determinacy and rewriting

Maximizing Conjunctive Views in Deletion Propagation