Functional dependencies (fds) were conceived in the early '70s, and were mainly used to verify database design and assess data quality. Nowadays they are automatically discovered from data since they can be exploited for many di erent purposes, such as query relaxation, data cleansing, and record matching. In the context of big data, the speed at which new data is being created demand for new e cient algorithms for fd discovery. In this paper, we propose an incremental fd discovery approach, which is able to update the set of holding fds upon insertions of new tuples to the data instance, without having to restart the discovery process from scratch. It exploits a bit-vector representation of fds, and an upward/downward search strategy aiming to reduce the overall search space. Experimental results show that such algorithm achieves extremely better time performances with respect to the re-execution of the algorithm from scratch.
With the advent of Big Data, both industry and research communities have
manifested a tremendous interest in technologies capable of extracting
information and their correlations among data. One way to represent such relationships
is to use functional dependencies (fds), which represent relationships among
database columns that can be used for several advanced database operations,
such as query optimisation, data cleansing, and data integration [
While fds were originally speci ed at database design time, as properties
of a schema that should hold on every instance of it, there has been the need
to automatically discover them from data for reducing the design e ort and for
supporting their evolution in the application domains. This is made possible
also thanks to the availability of big data collections, and to the contributions
of several research areas, such as machine learning and knowledge discovery [
Copyright c 2019 for the individual papers by the papers authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
The problem of discovering fds is extremely complex, since the number of holding fds for a given database instance could be exponential with respect to the number of database columns. In fact, most of the discovery algorithms described in the literature aimed to provide solutions in which the search space complexity is reduced by exploiting the theoretical properties of fds. However, while the availability of big data collections stimulates the discovery of meaningful fds from data, the necessity to update them according to the evolution of database instances require that also fds are updated. In fact, one of the characteristics describing big data is the velocity, which includes the fact that data are continuously produced.
In this paper, we propose an incremental discovery approach for fds, which updates the complete set of holding fds according to the new added tuples. The approach exploits a bit-vector representation of fds, and an upward/downward search strategy aiming to prune the search space. Experimental results achieved on twenty-eight datasets show that the proposed approach achieves better time performances with respect to the re-execution of the algorithm from scratch.
The paper is organised as follows. Section 2 reviews the fd discovery algorithms existing in the literature. Section 3 provides some background de nitions about fds and formulates the problem of fd discovery. Section 4 presents the proposed methodology for the incremental discovery of fds from data, whose evaluation is reported in Section 5. Finally, summary and concluding remarks are included in Section 6. 2
The fd discovery problem dates back to the '80s, when the rst discovery
algorithms were de ned [
In the literature there are two main categories of methods to automatically
discover fds from data, namely column-based and row-based methods. The
former exploit an attribute lattice to generate candidate fds, which are successively
tested to verify their validity. The whole process is made e cient by exploiting
valid fds to prune the search space for new candidates. Examples of top-down
approaches include the algorithms TANE [
Experimental results show that column-based algorithms usually
outperform row-based ones on datasets with many rows and few columns, whereas
on datasets with few rows and many columns the row-based algorithms usually
perform better [
One of the rst theoretical proposal of incremental algorithm for fd discovery
has been proposed in 2001 [
Before discussing the problem of discovering fds, let us rst recall the de nition of the canonical fd. Given a relational database schema R, de ned over a set of attributes attr(R), derived as the union of attributes from relation schemas R composing R, assuming w.l.o.g. they all have unique names. For each attribute A 2 attr(R), its domain is denoted by dom(A). Moreover, given an instance r of R and a tuple t 2 r, we use t[A] to denote the projection of t onto A; similarly, for a set X of attributes in attr(R), t[X] denotes the projection of t onto X. An fd over R is a statement X ! Y (X implies Y ) with X; Y attr(R), such that, given an instance r over R, X ! Y is satis ed in r if and only if for every pair of tuples (t1, t2) in r, whenever t1[X] = t2[X], then t1[Y ] = t2[Y ]. X,Y are also named Left-Hand-Side (LHS) and Right-Hand-Side (RHS) of an fd.
The goal of dependency discovery is to nd meaningful dependencies
holding among columns of a dataset. They represent domain knowledge and can
be used to assess database design and data quality [
Discovering fds over a relation instance r entails nding all the possible column combinations, and for each of them nd all the possible partitions forming the LHS and RHS of candidate fds. Without loss of generality, we can consider only candidates with a single attribute on the RHS. Given this, the fd discovery problem has an extremely large search space. In fact, given a relation r with M attributes and n tuples, we need to consider all the possible combinations of 2 to M attributes, counting each of them as many times as the number of attributes in it, in order to account for the number of di erent candidates with a single RHS attribute. This complexity is synthesised by the following formula: M X
Since this complexity represents only the number of candidate fds that could be potentially checked, the discovery algorithms need to tackle several other issues, such as the validation of each candidate whose complexity is linear in the number of tuples.
The general fd discovery problem is described by the following de nition. De nition 1. Given a relation instance r of a relation R, an fd discovery algorithm has to nd the minimal cover set of fds holding in r, having the property that tuples equal on the LHS must be equal also on the RHS.
According to this de nition, an fd discovery algorithm has to identify the minimal cover of fds holding on a relation instance r. The minimal cover will contain all valid fds even if they have low support. Thus, an holding fd does not appear in the minimal cover P only when it can be inferred by other fds in P . For these reasons, given a set P of all minimal fds holding on r, and computed at time , it is necessary to update P whenever one or more tuples have been added from time to time 0, since new tuples can violate one or more fds of P . Details on how we deal with such a problem are discussed into the next section. 4
This section presents the structure of the proposed incremental approach for fds discovery by introducing the data representation and the search strategies. Data structures, pruning, and validation processes of fds will, therefore, be described. 4.1
Incremental Methodology fd discovery algorithms operating on static datasets require to be re-execute upon the insertion of new tuples. This is a computationally expensive operation, especially for database instances with a large number of rows and columns. The main problem with the database instance evolution is that fds found at time can be invalidated at time 0. For this reason, it is necessary to implement incremental approaches that reduce the time for searching and validating fds.
In our study, we propose an incremental discovery approach that takes in input the fds associated to a relation instance r, represents fds using bitsets, and performs an upward and downward search strategy. Figure 1 shows the binary representation of an fd with k attributes. In particular, each dependency X ! A requires two bitsets: the rst contains all the LHS attributes, while the second contains the RHS attribute of the fd.
Each location of a bitset B represents an attribute of a relation instance r. In particular, given an fd X ! A on r, if BX [i] = 1 then the i-th attribute in r belongs to X. The size of each bitset corresponds to the number of attributes of the considered instance r. In this way, it is possible to represent dependencies with hundreds of attributes in a compact and lightweight fashion.
In our methodology, all binary fds holding on a instance at time are stored in a linked ordered hash map. This data structure was used to ensure that information are quickly saved and retrieved. The map uses as key the bit-vector representation of fds, and as value the next dependency, according to an ordering criteria based on the LHS cardinality. Moreover, two fast arrays link the map in order to reduce the insertion times of the fds. This data organisation allows to perform a level-wise discovery based on a lattice search strategy. Furthermore, it guarantees an immediate pruning of dependencies that are not minimal.
As said above, inserting new tuples in a relation instance could a ect the validity of the fds. In particular, the main e ects that can be produced by new tuples are: { Invalidation of functional dependencies. Let X ! A be a minimal fd with X; A attr(R) at time , such that for each pair of tuples (t1 ; t2 ) belonging to the instance r, whenever t1 [X] = t2 [X] then t1 [A] = t2 [A]. If at time + 1 there exist a new tuple t3+1 such that:
t1 [X] = t3+1[X] ^ t1 [A] 6= t3+1[A] or two new tuples t4+1, t5+1, which verify the following property: t4+1[X] = t5+1[X] ^ t4+1[A] 6= t5+1[A] then the fd X ! A is no longer valid. { Con rmation of minimality. If a minimal functional dependency is valid at time and has not been invalidated by any tuple at time + 1, then this dependency is minimal also at time + 1.
Based on these considerations, the methodology considers the rst functional
dependency extracted at time with the smallest LHS cardinality and the
attribute partitions of the relation instance. In the pre-processing phase, the fds
holding at time are mapped within the linked ordered hash map and the
partitions are updated according to the set of new tuples. The use of tuple partitions
avoids to access data during the discovery and allows to validate the fds through
the re nement property [
De nition 2. Re nement. A functional dependency X ! A holds on r i j X j = j (X[A)j, where X and (X[A) are the sets of equivalence classes, i.e., they are the partitions of r on X and X [ A.
If a minimal fd X ! A is invalidated at time + 1, then new candidate dependencies need to be analysed. In particular, it is necessary to validate all non-trivial fds XB ! A for each B 2 attr(R), with B 2= X [A. This means that a higher level in the lattice search strategy is considered. In fact, only candidates of higher levels w.r.t. the holding fds at time can hold at time + 1. Moreover, it is not necessary to verify the dependencies X n B ! A for each B 2 X, since such fds were not valid at time , and cannot be valid at time + 1. However, it is necessary to guarantee the minimality of XB ! A. In fact, such dependency can be considered as minimal at time + 1 if and only if it cannot be inferred by other holding fds at time + 1.
De nition 3. Inference. A functional dependency XB ! A is inferred by another dependency XB n Z ! A with Z XB i XB n Z ! A holds at time + 1, and Z 6= ;.
The inference checking is performed in the proposed search process by exploiting the previously introduced linked ordered hash map. In fact, it is necessary to verify if does not exist an fd, among those already validated at time + 1, which is minimal with respect to XB ! A. In particular, in order to speed up the inference checking process, we used a hash map that links the possible fd's RHS with all minimal fds already validated at time + 1. This allows to prune the number of fds to be checked.
The complete discovery process de ned according to the proposed methodology is described by Algorithm 1. In particular, for each fd holding at time (line 1), it veri es if X ! A also holds at time + 1 through the REFINEMENT function (line 2). Next, if X ! A is not valid, the algorithm generates new candidate fds at a higher level, by excluding those that can be inferred (lines 3-6). Instead, if X ! A is valid, the latter is added to the result set only i it cannot be inferred by other holding fds at a lower level (lines 8-11).
In general, the proposed approach can drastically reduce the execution time for two main reasons: 1. the bit-vector representation of fds permits to quickly process new con gurations of fds by computing the new LHSs in terms of attribute supersets or subsets. In other words, it optimises the downward/upward search strategies; 2. the ordered linked hash map permits to extremely prune the search process, since it guarantees a fast minimality test.
Example 1. Table 1 shows a database instance r in which three new tuples have
been added at time + 1. Starting from the partitions of the instance r at time
, that is, A = f[0; 1]; [3; 4]; [
C0 = f[0; 2; 5; 7]; [
Figure 2 shows the linked ordered hash map obtained at time +1 for the new instance of Table 1. It visualises all the considered candidate fds. In particular, each bit-vector in Figure 2 represents: 1) a minimal fd holding at time + 1, 2) a candidate fd that has been invalidated at time + 1, or 3) a candidate fd that is not minimal at time + 1.
Initially, the dependency with the lowest LHS cardinality is selected by using a fast array to directly link the rst dependency with a given LHS cardinality. In Figure 2 this corresponds to (0110) ! (0001). Using the re nement property, this fd is removed because j X j 6= j (X[A)j. Starting from this, the algorithm calculates the next candidates, which consider LHS supersets. For each of them the inference checking is applied, and only those that cannot be inferred are added to the map. Therefore, in the example, the fds (1110) ! (0001) and (0111) ! (1000) are added to the ordered map, also updating the links that preserve the map ordering. The execution proceeds until all fds are explored. In particular, the fd (0111) ! (1000) is removed because it is not minimal with respect to (0101) ! (1000), which has been previously validated. Finally, the algorithm returns the new minimal set of fds holding on the instance at time + 1, so avoiding the re-execution of the discovery algorithm from scratch. In the following, we present experimental results concerning the performance of the proposed approach in discovering fds. In particular, the performed tests show how much the new proposed approach can improve time performances with respect to the re-execution of the fd discovery algorithm.
Implementation details. The algorithm has been developed in Java 11.0.2. In particular, in order to improve the performance of the algorithm and avoid the re-calculation of partitions, we also introduced a methodology for caching partitions, since the latter are widely used for the validation of candidate fds. Hardware and datasets. The tests has been performed on a Mac with an Intel Xeon processor at 3.20 GHz 8-core and 64GB of RAM. Moreover, to ensure a proper execution on the considered datasets, the Java memory heap size allocation has been set to 40GB to permit a proper execution on datasets with a high number of tuples/attributes.
We evaluated the proposed approach on several real world datasets,
previously used for testing fd discovery algorithms [
Abalone Adult Balance-scale Breast-cancer-wisc.
Breast-cancer
Bridges
Bupa
CalIt
Cars
Car data
Chess
Citations
Citeseer
Citeseer
Cmc
DBLP
Echocardiogram
Ecoli
Haberman
Hayes-roth
Iris
Letter
Mammography
Nursery
Servo
Tae
Tax
Wine
Evaluation process. We carried out di erent tests by using as starting point
the minimal fds extracted through the TANE algorithm [
The second test aimed to evaluate the relationship between the execution times and the sizes of the datasets. In particular, we selected datasets by varying (a) Citations (c) Letter (d) Nursery the number of tuples inserted at time + 1 in the range of 5%-40% w.r.t. the complete dataset. Results are shown in Figure 3. In particular, the results for nursey (Figure 3(d)) and citeseer (Figure 3(b)) show an extremely reduction of the execution times when considering the incremental approach. This is probably due to the fact that the number of minimal fds at time was small. Moreover, although this number is higher for citations and letter, the time performances of our approach is still lower than the execution of TANE (Figures 3(a) and 3(c)).
The last test allowed us to evaluate the discovery time of the incremental algorithm on datasets with a xed number of tuples but a variable number of columns ( rst session), and with a xed number of attributes but a variable number of tuples within an interval range of [2000 20000] tuples with step 2000 (second session). For these experiments dblp and citeseer datasets have been selected. Table 3 contains the characteristics of the datasets and the results of the experiments with a variable number of attributes. Instead, the results of the second session are shown in the Figure 4. By analysing Table 3, we can notice that the execution times of the proposed approach are always lower than the execution times of TANE. Moreover, we noticed that for our incremental approach the dblp dataset is more critical than citeseer when the number of attributes increases. Also in this case, this is probably due to the higher number Dataset Tuples Attributes %Inserts DBLP DBLP DBLP DBLP DBLP DBLP Citeseer Citeseer Citeseer Citeseer Citeseer Citeseer 20K 20K 20K 20K 20K 20K 20K 20K 20K 20K 20K 20K of fds discovered at time + 1. Di erent results have been obtained when we consider the variation in the number of tuples (Figure 4). In this case, although non monotonic the time trend grows faster for TANE. 6
In this paper we have proposed an incremental approach for discovering fds, which permits to update the set of holding fds without the need of exploring the complete search space. A bit-vector representation of the fds allowed us to optimise this process. Experimental results show that the proposed approach considerably reduces the execution times with respect to a re-execution from scratch.
In the future, we would like to further improve this approach in order to
automatically updates fds even for other database instance modi cations, such
as the deletion and the updating of tuples. Another interesting issue concerns
the possibility of updating also Relaxed Functional Dependencies (rfds) [