Introduction

With the advent of big data, the presence of missing values inside database instances has been widely recognized as a complex problem to handle, especially for Relational Database Management Systems [1]. Moreover, several application contexts might require the absence of this data quality issue inside their datasets. For instance, machine learning processes could not provide good accuracy scores if trained on data with many missing values. In general, it is not possible to infer reliable knowledge using datasets with incomplete information [2].

The identification of the best values in a dataset to impute the missing ones is an extremely complex task, since it entails the evaluation of all possible combinations in the value distribution. Most of the approaches proposed in the literature focus on maximizing the number of imputed values, overshadowing the accuracy of single imputations. This discussion paper presents the data imputation algorithm proposed in [3], namely RENUVER (Rfd basEd NUll ValuE Repairer), which relies on Relaxed Functional Dependencies (rfds) for imputing missing values within a relational database instance. By adopting the concept of rfds as metadata for supporting the imputation process, we are able to perform a broader analysis of the correlations among SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy bbreve@unisa.it (B. Breve); lcaruccio@unisa.it (L. Caruccio); deufemia@unisa.it (V. Deufemia); gpolese@unisa.it (G. Polese) 0000-0002-3898-7512 (B. Breve); 0000-0002-2418-1606 (L. Caruccio); 0000-0002-6711-3590 (V. Deufemia); 0000-0002-8496-2658 (G. Polese) attributes, yielding an accurate and somewhat fast solution for the imputation of missing values within relational database instances. In fact, rfds are still widely considered for detecting and repairing many types of errors, such as duplicates, outliers, and constraint violations [4]. Thus, we made use them for identifying suitable candidate values for replacing missing ones in the data imputation process. RENUVER exploits rfds for: i) identifying the candidate tuples useful for the imputation of missing values, ii) ranking candidate tuples based on their similarity with respect to the tuples containing missing values, and iii) evaluating each imputation to guarantee the semantic consistency of the whole dataset.

In particular, RENUVER generates candidate tuples and rank them, according to rfds implying the attribute on which a value is missing. Moreover, the imputation strategy of RENUVER does not alter value consistency with respect to the ones in the original dataset. Finally, RENUVER exploits rfds to also judge whether it is possible to impute a missing value, in order to preserve the integrity of data and to avoid the insertion of inconsistent information.

The effectiveness of RENUVER has been evaluated on real-world datasets1 in terms of accuracy, and execution time. In order to extract rfds, we relied on an existing rfd discovery algorithm [5], since the problem of discovering rfds is out of the scope of this paper. Moreover, we introduce a novel method for the automatic evaluation of data imputation results, which permits to judge the imputed values even with different syntactical representations. Evaluation results demonstrate that RENUVER outperforms other data imputation approaches [6,7,8].

The paper is organized as follows: Section 2 provides preliminary notions on rfds. Section 3 introduces RENUVER's logic through the employment of the rfds in the data imputation problem. An experimental evaluation measuring the effectiveness RENUVER is presented in Section 4. Finally, conclusions and further research are reported in Section 5.

Preliminaries

Before describing how we approached the imputation problem through the employment of rfds, let us introduce some propaedeutics notions to our methodology. Functional Dependency. Given a relational database schema ℛ, and 𝑅 = {𝐴 1 , . . . , 𝐴 𝑚 } one of its relation schemas, and a tuple 𝑡 ∈ 𝑟, we use 𝑡[𝐴 𝑖 ], with 0 ≤ 𝑖 ≤ 𝑚, to denote the projection of 𝑡 onto 𝐴 𝑖 ; similarly, for a set of attributes 𝑋 = {𝐴 𝑖 1 , . . . , 𝐴 𝑖 𝑘 }, with 1 ≤ 𝑘 ≤ 𝑚, 𝑡[𝑋] ∈ 𝑑𝑜𝑚(𝐴 𝑖 1 ) × . . . × 𝑑𝑜𝑚(𝐴 𝑖 𝑘 ) represents the projection of 𝑡 onto 𝑋, also denoted with Π 𝑋 (𝑡). An fd on ℛ is a statement 𝑋 → 𝑌 (𝑋 implies 𝑌 ), with 𝑋, 𝑌 ⊆ 𝑎𝑡𝑡𝑟(𝑅), such that, given an instance 𝑟 of 𝑅, 𝑋 → 𝑌 is satisfied in 𝑟 if and only if for each pair of tuples (𝑡

1 , 𝑡 2 ) in 𝑟, whenever 𝑡 1 [𝑋] = 𝑡 2 [𝑋], then 𝑡 1 [𝑌 ] = 𝑡 2 [𝑌 ].

The sets of attributes 𝑋 and 𝑌 are named Left-Hand-Side (LHS) and Right-Hand-Side (RHS) of the fd, respectively.

With respect to fd definition, the rfd generalizes the comparison paradigm, by including similarity/distance-based comparisons between tuple projections, also admitting the possibility for a dependency to hold only on a subset of tuples. The latter can be defined through either a coverage measure, quantifying the portion of the dataset on which a dependency holds or a condition restricting the domain on which a dependency can hold [9]. Since the proposed

) ∈ 𝑟 for which 𝑡 1 [𝑋] and 𝑡 2 [𝑋] satisfy the constraint 𝜑 𝑖 [𝑋 𝑖 ] for each 𝑋 𝑖 ∈ 𝑋, then 𝑡 1 [𝑌 ] and 𝑡 2 [𝑌 ] satisfy the constraint 𝜑 𝑖 [𝑌 𝑖 ] for each 𝑌 𝑖 ∈ 𝑌 .

For sake of simplicity, in the following, we apply a more compact notation for the constraints, showing only the operator and the numeric threshold associated with each attribute. 1, derived from a database of restaurants in USA. Within this database, each tuple represents a restaurant providing information about its name, address, city, phone number, type of cuisine, and class. The latter is a numeric id associated to the type of cuisine. On such dataset, the following rfd c holds: Name (≤4) − → Phone (≤1) which states that, if two restaurants have a similar name, then they also have a similar phone number. This should be true despite the names and/or the phone numbers of restaurants being written in different ways or using different abbreviations.

Example. Let us consider the sample relation shown in Table

From a theoretical point of view, rfd c s permit to use any type of similarity/distance functions, e.g., edit distance, abs differences, and so forth. However, they are usually inherited from the functions involved in the automatic rfd c discovery process [5]. For the scope of this proposal, without loss of generality, we can consider rfd c s with a single attribute on the RHS, and the associated constraint 𝜑 2 . In particular, we considered 𝜑 2 composed of a distance function, the operator ≤, and a distance threshold.

A particular type of rfd c is the key-rfd c , which is defined in the following.

Key rfd

The RENUVER imputation approach

In this section, we formalize the data imputation problem by defining some of its underlying concepts, then describing the basics of the proposed imputation approach. Let us start defining the concept of missing value.

Missing value. Given a relation schema 𝑅, defined over a set of attributes 𝑎𝑡𝑡𝑟(𝑅), an instance 𝑟 of 𝑅, an attribute 𝐴 ∈ 𝑎𝑡𝑡𝑟(𝑅), and a tuple 𝑡 ∈ 𝑟, a missing value of tuple 𝑡 on the attribute 𝐴, denoted as

𝑡[𝐴] = _, is such that 𝑡[𝐴] is null.

Here, 𝑟 is said to be an incomplete instance, and 𝑟 ˆ⊆ 𝑟 contains only incomplete tuples. The general missing value imputation problem is formally defined as follows.

Missing value imputation problem. Given a relation schema 𝑅, and an instance 𝑟 of 𝑅, for every tuple 𝑡 ∈ 𝑟 and every attribute 𝐴 ∈ 𝑎𝑡𝑡𝑟(𝑅) for which 𝑡[𝐴] = _, the imputation problem consists of finding a plausible value 𝑎 ∈ 𝑑𝑜𝑚(𝐴), such that the database instance 𝑟 ′ resulting from the imputation process does not contain inconsistent values.

A missing value imputation approach also requires the application of constraints for evaluating the consistency of values at the end of the imputation process. The proposed approach exploits rfds to both guarantee the verification of the semantic consistency, and to drive the searching of meaningful candidates for all missing values. In what follows we define the criteria used by RENUVER for deciding when a tuple can be considered as a plausible candidate, which is based on rfd c s.

Semantically

Plausible candidate tuple. Given a missing value 𝑡[𝐴]

=_ over a database instance 𝑟 of a relation schema 𝑅, and an rfd c 𝜙 : 𝑋 Φ 1 → 𝐴 𝜑 2 holding on 𝑟, a tuple 𝑡 ′ ∈ 𝑟 can be considered as a plausible candidate tuple for imputing 𝑡[𝐴] according to 𝜙 iff 𝑡 and 𝑡 ′ , are similar according to the constraints in Φ 1 .

The candidate tuple generation process performed according to the definition presented above, has to be generalized in order to perform the imputation process on tuples containing more than one missing value, and for each 𝑡 ∈ 𝑟 ˆ. 1.

Missing value imputation

yields to another important issue that RENUVER deals with, i.e., minimizing the number of non-imputed values. Figure 1 summarizes the imputation logic of RENUVER2 through an example. In particular, we show how the aforesaid definitions empower the imputation of a missing value in the Restaurant dataset, previously introduced. In details, we can identify three major phases yielding the imputation of certain missing value, that are:

• Pre-processing: during this phase, missing values within a database instance are identi-fied and isolated. Furthermore, RENUVER excludes all key-rfd c s from the set of the rfd c s which can be employed for the imputation of any missing value (see Figure 1.a).

• rfd c selection: following the selection of a missing value to impute, during this phase RENUVER identifies all the rfd c s that can be useful for its imputation. rfd c s are then organized in a set of clusters according to their threshold on the RHS (see Figure 1.b).

• Imputing missing values: during this phase, RENUVER performs a series of operations leading to the imputation of a missing value by retrieving the value from a set of plausible candidate tuples relying on the same database instance (see Figure 1.c). In particular, RENUVER iteratively performs the following operations:

generates a set of plausible candidate tuples that satisfy the LHS constraints of an rfd c s belonging to one of the clusters previously generated.

computes a distance value for each plausible candidate tuple with respect to the tuple having the missing value. The evaluation is performed by considering the LHS attributes of the rfd c selected. Finally the candidate tuple having the minimum distance is the exploited for the imputation of the missing value.

verifies whether the imputed value causes a violation of holding rfd c s. In this case, RENUVER selects the next plausible candidate tuple with the lowest distance value. These operations are repeated for each cluster as long as the imputation is not successful.

Experimental Evaluation

In this section, we present a comparative evaluation of RENUVER w.r.t. other approaches exploiting different imputation strategies. In particular, we benchmarked RENUVER against an holistic-machine learning-based approach, namely Holoclean [6], (considering its attentionbased expansion module AimNet [10]) and a differential dependencies guided approach [7] named Derand, for which we employed the same rfd c s as RENUVER. All evaluations were performed under the same conditions on an iMac Pro with an 8-core CPU and 32GB RAM.

Datasets. The considered algorithms have been evaluated on two real-world datasets 2 in order to perform a stress test on RENUVER and all compared imputation approaches, aiming to determine their time and memory requirements. To this end, we stopped the executions exceeding 48 hours of execution time and/or 30GB of memory consumption, respectively. Furthermore, in order to obtain an accurate comparison between the imputed values and the expected ones, missing values have been artificially injected in a random manner. Moreover, to avoid an arrangement of missing values over one algorithm, for each missing injection we produced five different datasets, yielding a total of twenty-five variants of the same dataset. The metrics adopted for the comparison are then averaged over each missing rate.

Evaluation metrics. The effectiveness of the data imputation approaches have been evaluated by considering three different metrics: precision, recall, F1-measure. Which can be formally defined as: precision = |true Results. The first evaluation session is focused on the Restaurant dataset by considering the following missing rates: [5%, 10%, 20%, 30%, 40%] (see Table 2). We can notice that the fastest approach is Holoclean, whereas Derand registered severely higher execution times, exceeding the 48h time limit starting from the 10% of missing rate. The faster execution times of Holoclean can be justified by the conspicuously lower number of metadata to be processed during the imputation process, i.e., 9 Denial of Constraints, compared to 1961 rfd c s. Nevertheless, RENUVER registered the best performances on all the considered qualitative metrics.

The second evaluation session is focused on the Physician dataset, by fixing the missing rate and by varying the number of tuples to be considered. This dataset is particularly complex to analyze, since it also contains a high number of attributes (i.e., 13 attributes). In fact, this dataset allowed us to catch a time and/or memory limit for all considered approaches (i.e., RENUVER, Derand, and Holoclean), as shown in Table 2. In particular, we can notice that, on average, both RENUVER and Holoclean registered faster execution times than Derand. In fact, the latter exceeds the time limit of 48h on the datasets having 2072 and 10359 tuples, respectively. On the other hand, Holoclean manages to achieve reasonable executions times, but the huge amount of consumed memory makes it exceed the 30GB memory limit on the dataset having 10359 tuples. Finally, RENUVER also exceeds the time limit on the largest dataset, despite a more reasonable memory consumption. This evaluation session proved the capability of RENUVER to outperform the compared approaches on the considered qualitative metrics. It also emphasized that Derand's execution times are strongly dependent on the number of missing values, whereas although Holoclean provided overall faster execution times, it resulted heavily memory-consuming.

Conclusion

In this paper, we proposed RENUVER, a data imputation algorithm that exploits relaxed functional dependencies. The latter enables RENUVER to select and evaluate tuple candidates to be used during the imputation process. The whole imputation process preserves the semantic consistency of the data, by guaranteeing that no imputation can violate any rfd c . Evaluation results demonstrated that RENUVER outperforms recent approaches using different imputation strategies: machine learning-based (Holoclean) and dependency-based (Derand).

In the future, we would like to extend RENUVER with the possibility of selecting plausible candidate tuples among multiple datasets. Finally, we would like to study the applicability of RENUVER over incremental scenarios, like for example those related to the imputation of time series [11], which would require the usage of incremental rfd c discovery algorithms [12,13].