The extraction of metadata from dynamic data sources represents an extremely challenging task of the data profiling research area, since it requires to handle the update of the inferred metadata without processing the whole dataset from scratch upon modifications. This discussion paper presents IndiBits, an approach for discovering relaxed functional dependencies (rfds for short), which represent data relationships relying on approximate matching paradigms. It exploits a binary representation of data similarities, a new validation method, and specific search methods, to dynamically update the set of rfds, based on previously holding rfds and the type of modifications performed over data. Experimental results demonstrate the efectiveness of IndiBits on real-world datasets, even in comparison with fd and rfd discovery algorithms in both static and dynamic scenarios.
Data profiling refers to the process aiming to analyze data in order to extract useful metadata
from them [
As for fds, rfds have been used in several application contexts, especially those in which
data are collected from heterogeneous sources [
Incremental scenarios make the rfd discovery problem more complex and challenging,
especially for the representation and management of data and results. In fact, the number of fds
and rfds holding on a given dataset can be exponential in the number of attributes, requiring
the exploration of an extremely large and complex search space [
The paper is organized as follows. Section 2 presents the theoretical foundations of considered profiling metadata. Section 3 provides an overview of IndiBits, by also describing details of the validation method underlying it, and the discovery strategy to handle insertion and deletion data modifications. Section 4 reports experimental results to analyze the efectiveness of IndiBits on real-world datasets, also when compared with other fd and rfd discovery algorithms. Finally, summary and future directions are included in Section 5.
In this section, we formally introduce preliminary concepts related to rfd. rfd. Given a relational database schema ℛ, and = {1, . . . , } one of its relation schemas, an rfd on ℛ is denote by Φ1 → Φ2 (1) where • , ⊆ (); • Φ 1 contains (for each attribute ∈ ) a constraint [] that can be used to determine whether pair of tuples with values in () are “similar” enough (likewise for each attribute ∈ with [ ] ∈ Φ 2). More specifically, each [] ( [ ] resp.) requires the specification of a similarity/distance function defined on the domain of ( , resp.), an operator, and a threshold setting the boundaries for the satisfaction of the constraint.
Given a relation instance of , satisfies the rfd , denoted by |= , if and only if: ∀ (1, 2) ∈ , if Φ 1 indicates true, then also Φ 2 indicates also true. Without loss of generality, in what follows we consider only candidate rfds with a single attribute on the RHS: Φ1 → 2 . Moreover, in the following, we consider a more compact notation for the constraints.
One of the most important characteristics of an rfd is the minimality guaranteeing that the rfd no longer holds after either () increasing one or more thresholds on the LHS constraints, () removing an LHS attribute, or () decreasing the RHS threshold. Notice that, the minimality property can be restricted to case () when fixed constraints for each attribute are considered.
The discovery of rfds is the problem of finding a set of all minimal rfds holding on a relation instance . One of the possible strategies for discovering rfds (namely column-based) models the search space as a lattice, which permits to consider candidate rfds at diferent levels in terms of edges. By following the lattice-based search space representation, a column-based discovery strategy first generates attribute sets at level , and then formulates all the possible rfds Φ1 → 2 , with ∈/ , to be successively validated. Then, considering the rfds validated at level , several pruning strategies can be applied in order to avoid the validation of not minimal candidate rfds. Thus, whenever the constraints are specified for each attribute of the relation, the discovery of rfds reduces to verify if whenever tuples satisfy the constraints on the LHS attributes, then they also satisfy the one on the RHS attribute. This requires tackling a problem that, in the worst case, is exponential in the number of columns and quadratic in the number of rows. Nevertheless, diferently from the equality, the similarity does not satisfy the transitivity property, preventing the possibility to adopt the validation methods of fds. This leads to the necessity of conceiving new validation methods for evaluating candidate rfds.
IndiBits is an incremental discovery algorithm for rfds relying on a column-based search strategy capable of discovering rfds from a single relation. It considers an input threshold for each attribute to form distance constraints that will be then used for validating candidate rfds.
IndiBits monitors changes that occurred in a relation instance in terms of insertion and deletion operations and it incrementally updates the set of valid rfds. Notice that update operations can be expressed as a combination of deletion and insertion operations. In what follows, we will use the term batch to refer to groups of change operations.
An overview of the discovery process underlying IndiBits is shown in Fig. 1. The latter describes how IndiBits iteratively performs the discovery of rfds as data is updated over time.
To eficiently handle the representation of the similarity among tuples with respect to the input thresholds Φ , we devised an ad-hoc data structure mapping the satisfiability degree between attribute values, limited by the input thresholds, through a vector of integers, named similarity vector. In particular, similarity vectors are generated for each attribute, according to a theoretical concept called Binary Attribute Satisfiability (BAS) Distance Matrix. For a given attribute , a BAS Distance Matrix represents a triangular matrix whose row and column indices correspond to the tuples of a relation instance at a given time . Each matrix entry will contain either the value 0 or 1 depending on whether the pair of tuples agree with the threshold associated with . A BAS Distance Vector [] describes the tuples similar to on attribute . As an example, in Figure 1, acuity[2] corresponds to the bit vector 011, indicating that at time = 0, the tuple 2 is similar, with respect to the attribute acuity, only with tuple 3 as well as itself. Finally, the similarity vector denoted as , is a vector whose length is to the dataset size. Each element of the vector is characterized by the decimal conversion of the bit vector for a given tuple, where the more significant bit is the far-most right. As an example, ...
...
each element of similarity vector is the decimal conversion of the corresponding BAS
Distance Vector produced for a certain tuple at time , i.e., ( acuity[1]) = (001) = 1,
( acuity[2]) = (011) = 6, and ( acuity[3]) = (011) = 6. Thus, the similarity
vector is 166. Further updates on the dataset over time are transposed to similarity
vectors by means of bitwise operations, optimizing their management in an eficient way. A
more detailed and formal description of similarity vectors is provided in the full article [
According to the similarity representation underlying IndiBits, we can now describe the
overall process of IndiBits (see Figure 1). In particular, IndiBits reads the first batch of tuples
at time = 0 and creates the binary representation of the data according to the thresholds
in Φ defined as input. Then, it performs the discovery process by considering only insertion
operations and extracts the set of holding rfds. For each time > 0, IndiBits first processes
all the deletions defined in a batch (represented in the image by the tuple crossed out in red), and
then the insertion operations (green highlighted tuples), enabling the correct handling of the
update operations on tuples. Consequently, IndiBits browses the search space according to the
types of operations, and starting from rfds holding at time , it properly generates candidate
rfds by means of specialization/generalization strategies (see Section 3.2). In particular, for
each rfd holding at time as a new candidate rfd at time + 1, it will be surely valid if the
last operation was a deletion, but it could no longer be minimal; whereas it might not hold if the
last operation was an insertion. In case the operation is a deletion, : Φ′1 → 2 not minimal,
then IndiBits must generate and validate new candidate rfds ′ that are generalization of ,
that is, ′ : Φ′′1 → 2 , with ′ ⊂ , and Φ ′1 is a conjunction of the similarity constraints
defined on attributes in ′. Accordingly, in case the last operation is an insertion, then it
must generate and validate new candidate rfds ′′ that are specialization of , that is, ′′ :
Φ′′′1′ → 2 , with ⊂ ′′ and Φ ′1′ is a conjunction of the similarity constraints defined on
the attributes ′′. Furthermore, IndiBits eficiently validates each candidate rfd following
the methodology described in Section 3.1.
3.1. rfd Validation
Starting from the representation provided by the similarity vectors , it is possible to eficiently
verify if a candidate rfd is satisfied on a given relation instance at time by exploiting the
refinement property between patterns of similarity values introduced in [
More formally, given an attribute set , it is possible to consider [] computed as ⋀︀∈ [], where each [] is an element of and whose binary representation maps all tuples that are similar to on the values of each attribute in , according to the similarity constraints defined by Φ . Then, according to the refinement property, if we consider a set ∪ ⊃ , it is possible to say that ∪ always refines , since each tuple pair is similar on ∪ if and only if it is also similar on . Thus, it is possible to count the number of tuples that are similar to each tuple , by counting the number of bits having the value 1 in [], according to the following formula: || || = ∑︀∈ (|2 []|− 1) where | []| is the number of bits equal to 1 in the binary representation of [], and represents the number of similar tuples in . The value 1 is subtracted to exclude comparing the tuple with itself, whereas the division by 2 allows to consider each tuple pair only once.
Example. Let us suppose we have the following similarity vectors: pain = [65, 350,
350, 350, 350, 928, 95, 672, 830, 928], chiefcomplaint = [
2
During the discovery process, the insertion operations can or cannot confirm the validity of
rfds already validated at time . This strategy enables IndiBits to avoid re-executing the
discovery process from scratch, by keeping track of the previously holding rfds. Notice that
during the first execution of IndiBits, the most general rfds in the search space are considered
as starting points. Then, IndiBits performs the validation from the most general to the most
specialized rfds. More specifically, IndiBits validates each candidate rfd and prunes the
search space according to the strategy proposed in [
On the other hand, the deletion of one or more tuples always confirms, at time + 1, the validity of the previously holding rfds, but it could lead to the validation of some rfds that were not valid at time . In the last case, it is necessary to check the minimality of previously valid rfds with respect to those newly validated at time + 1. In particular, IndiBits starts by considering the minimal rfds holding on a relation instance at time and for each of them considers their direct generalizations as new candidate rfds at time + 1. If none of these = 1 = 8 * DiM Time Limit Both Time Limit are valid, IndiBits confirms the validity of the rfd from which the generalizations have been produced. On the contrary, for each candidate rfd validated at time + 1, IndiBits removes all the rfds that are specializations of it, and it continues to generalize them as long as possible.
We present experimental results concerning the performances of IndiBits and compare them
with those of DiM [
We implemented IndiBits in Java 17, using the Levenshtein distance for comparing textual attributes, the absolute diference for numerical attributes, and the alphabetic distance for individual characters. We evaluated IndiBits on diferent real-world datasets whose characteristics are publicly available on the oficial repository 1. For each dataset, we used the same threshold for all of their attributes, i.e., 0, 1, 2, 4, and 8, and we considered 4 batch size (e.g., the number of changes, in terms of insertion and/or deletion operations, to be considered at each time instant), i.e., 1, 10, 100, 1000. Finally, we considered a time limit (TL) of 3 hours.
Our first experiment measured the execution times and the memory consumption of IndiBits on the top-6 datasets in terms of attributes (see Fig. 2 (a)). Since these datasets have not been designed for incremental discovery, we simulated an incremental scenario in which tuples are ifrst inserted and then deleted. In particular, for each dataset, we first performed the insertion operations of all tuples, and then we randomly deleted 90% of them.
We report the average runtimes and memory peaks in Fig. 2 (a), by grouping the results according to batch sizes and distance constraints. In particular, IndiBits almost always required less than 104 MB of memory, except for Movement-Libras, Uniprot, and Tuandromd, in which the resulting memory peaks never exceed 105 MB. In general, the low memory consumption of IndiBits is mainly due to the lightweight representation of data and distances that makes the 1https://github.com/DastLab/TestDataset memory requirements not severely afected by the dimensionality of datasets and the number of holding rfds.
In general, we can notice that runtimes are quite stable or slightly grow when the batch size increases. Moreover, the average times are over a few seconds, except for particularly borderline configurations, where IndiBits still requires no more than 1 sec. Only on last three datasets IndiBits exceeded the TL in some configurations. Although such datasets represent the three biggest datasets in terms of attributes, for the Movement-Libras and Tuandromd datasets, IndiBits reached a time limit only with threshold 0 in the last batch size, but the average runtimes for other configurations do not exceed 103 sec. Instead, concerning the Uniprot dataset, IndiBits completed the discovery process with the two highest attribute comparison thresholds, considering batch sizes equal to 1, 10, and 100.
Summarizing, for the biggest considered datasets (i.e., Movement-Libras, Uniprot, and Tuandromd) IndiBits achieved good time performances with respect to both the number of tuples and attributes. Overall, we cannot identify a strict correlation between the dimensionality of the datasets and both the number of rfds and the IndiBits runtimes.
We also compared the performances of IndiBits to those of DiM [
In this experiment, we will focus on the discovery of rfds by analyzing in which conditions IndiBits under- or out-performs DiM. To this end, we gradually scale up the size of the dataset according to a defined batch size, each time executing DiM on an increased dataset. Then, we plot the average runtimes of IndiBits against those of DiM, by considering the speedup measure. A speed-up of 10 indicates that IndiBits has been 10 times faster than DiM, 1 indicates that they obtained the same runtime, while a value lower than 1 indicates that DiM is faster. Fig. 2 (b) shows the results of the comparative evaluation. We can notice that IndiBits is almost always faster than DiM. Conversely, only a few times DiM outperforms IndiBits, i.e., on the Lymphography dataset with threshold 0 and batch sizes set to 100 and 1000, and on the Sonar dataset with threshold 0 and batch sizes set to 100 and 1000, and with thresholds 4 and 8 and batch size 1000. As mentioned above, this can be due to the fact that IndiBits performs worse when there are many invalidations in each batch. Moreover, for the Sonar dataset, a static approach like DiM performs better because its discovery strategy exploits rfds discovered on lowest lattice levels to reduce the execution of validation processes. In general, we notice that DiM sufers when executing datasets with a high number of attributes since it reaches the TL in many configurations. Instead, IndiBits reaches the TL only in a few cases of the three datasets with the highest number of columns.
Concerning the comparative evaluation between IndiBits and DynFD, we set up insertion and deletion operations by considering the experimental configuration introduced in Section 4.1, but limiting the analysis to only the similarity threshold 0, i.e., the fds. This is due to the fact that DynFD focuses only on holding fds upon the insertion and deletion of batches of tuples, but not on rfds. In Fig. 3 we show the execution times achieved considering insertions only (Fig. 3 (a)) and deletion only (Fig. 3 (b)). Notice that, although IndiBits is not optimized for the discovery of fds, it is able to achieve competitive runtimes with respect to one of the most eficient incremental fd discovery algorithms. In fact, the results show that in many cases IndiBits outperforms or achieves average execution times similar to DynFD. In particular, concerning the insertion operations, we notice that IndiBits typically outperforms DynFD with smaller batches of tuples, i.e., 1, 10, and 100, while for batches with sizes 1000, although it seems that DynFD outperforms IndiBits for Glass and Australian datasets, the average execution times are of the same order of magnitude. The gap in execution times is greater for Lymphography, which represented an extremely challenging dataset for IndiBits when the similarity threshold is set to 0 due to the large amount of fds with a high number of attributes on the LHS.
Fig. 3 (a) highlights that IndiBits is capable of completing the discovery process without reaching the TL also when DynFD exceeded it, as in the case of Sonar, Movement-Libras, and Tuandromd. On the other hand, Fig. 3 (b) highlights that the task of updating fds after deletion operations is more challenging for both algorithms, which on average required more time for completing the discovery process, as can be seen by the gap between the algorithms in terms of average execution times being significantly reduced. Finally, both algorithms reached the TL when processing datasets with a high number of columns, except for the Tuandromd, dataset for which IndiBits was able to complete the discovery process for 1, 10, and 100 batch sizes.
In this paper, we presented IndiBits, an rfds discovery algorithm for incremental scenarios. To the best of our knowledge, IndiBits represents the first incremental discovery algorithm for rfds. It relies on a novel method for representing similarities between tuple pairs, which permits to eficiently update rfds holding at a given time instant, starting from those holding at a previous time instant. Experimental results show that IndiBits considerably reduces execution times for discovering rfds with respect to a static discovery algorithm and turns out to be competitive also for the discovery of fds in dynamic scenarios.
In the future, we would like to extend IndiBits in order to enable the discovery of rfds also from data streams. Another interesting issue concerns the possibility of updating rfds together with thresholds forming similarity constraints. Finally, we would like to investigate the meaningfulness of the discovered rfds in diferent application domains.
This work was partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU.