notesum.ai

Published at November 26

A Unified and Practical Approach for Generalized Deletion Propagation

cs.DB

Released Date: November 26, 2024

Authors: Neha Makhija¹, Wolfgang Gatterbauer

Aff.: ¹Northeastern University, USA

Arxiv: http://arxiv.org/abs/2411.17603v1

Refer to caption

Symbol	Definition
$Q$	Conjunctive query (CQ)
$\mathcal{D}$	Database Instance, i.e., a set of tables
$Q(\mathcal{D})$	A view representing the evaluation of query $Q$ on database $D$
$v$	A view tuple i.e., a valuation of the head variables of a query $Q$ that is permitted by a database $\mathcal{D}$
$\bm{\mathbf{w}}$	A witnesses i.e., a valuation of all variables of a query $Q$ that is permitted by a database $\mathcal{D}$
$\mathtt{GDP}$	The Generalized Deletion Propagation problem
$\mathcal{Q}_{\texttt{del}}$	An ordered set of queries that define the deletion views i.e., the views from which output must be deleted
$\mathcal{Q}_{\texttt{pres}}$	An ordered set of queries that define the preservation views i.e., the views that must be preserved
$\mathcal{Q}_{\texttt{min}}$	An ordered set of queries that define the minimization views i.e., the views from which deletions must be minimized
$\mathcal{Q}_{\texttt{max}}$	An ordered set of queries that define the maximization views i.e., the views from which deletions are maximized
$\bm{\mathbf{k}}_{\texttt{del}}$	Vector of positive integers that define the number of tuples that must be deleted for each view in $\mathcal{Q}_{\texttt{del}}(\mathcal{D})$
$\bm{\mathbf{k}}_{\texttt{pres}}$	Vector of positive integers that define the number of tuples that must be preserved for each view in $\mathcal{Q}_{\texttt{pres}}(\mathcal{D})$
$\mathtt{ILP}[\mathtt{GDP}]$	The ILP for $\mathtt{GDP}$ (with wildcard semantics and smoothing constraints)
$\mathtt{DP\textsf{-}SS}$	The Deletion Propagation with Side-Effects problem
$\mathtt{DP\textsf{-}VS}$	The Deletion Propagation with View-Effects problem
$\mathtt{SWP}$	The Smallest Witness Problem
$\mathtt{ADP}$	The Aggregated Deletion Propagation Problem
$X[..]$	A binary variable in an (Integer) Linear Program