Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to improve the training efficiency. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data. In this paper, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we further propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Experimental results show the effectiveness and efficiency of our framework with low cost.

The view propagation problem is a class of view update problem in relational databases [7] , involving deletion and insertion propagations. Given source database $D$ , conjunctive query $Q$ , view $V$ generated by query $Q(D)$ and a deletion (insertion) on view $\Delta V$ , deletion (insertion) propagation is to find a side effect free update $\Delta D$ on $D$ such that the deletion (insertion) of $\Delta D$ from (into) $D$ will delete (insert) the intentional ones $\Delta V$ without resulting in the deletion (insertion) of additional tuples from (into) the view. Generally, such a deletion (insertion) is side effect free. The related data management applications include query result explanation, data debugging, and anonymizing datasets, which rely on understanding how interventions in a database affect the output of a query. View propagation is a natural and typical way to define such interventions, which seems to be well-studied. However, in general, the candidate update on a source database is picked up aimlessly in advance, making the updated database to be very distant from the original one no matter whether it is the maximum one. In this paper, we formally define the bounded view propagation problem, where candidate update $\Delta D$ is bounded as a subset of potential $C$ which is a fixed small tuple set of $D$ . We study the complexity of this problem for conjunctive queries, and make contributions to the previous results of the problems of side-effect free deletion propagation. Specifically, our bounded view propagation problem decreases computational complexity regardless of conjunctive query structure. We show the fixed potential is actually a dichotomy for both deletion and insertion propagations, and figure out the results on combined complexity which is neglected previously. Based on our results, for view propagation, we map out a complete picture of the computational complexity hierarchy for conjunctive queries on both data and combined complexities. Moreover, this bounded version is an update forbidden case of view propagation, and our results can be applied to it.

Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to save the computational cost of training. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data. In this article, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Moreover, a group-based strategy is utilized to further accelerate the coreset selection with incomplete data given large datasets. Experimental results show the effectiveness and efficiency of our framework with low cost.