Approximate functional dependencies are used in many emerging application domains, such as the identi cation of data inconsistencies or patterns of semantically related data, query rewriting, and so forth. They can approximate the canonical de nition of functional dependency (fd) by relaxing on the data comparison (i.e., by considering data similarity rather than equality), on the extent (i.e., by admitting the possibility that the dependency holds on a subset of data), or both. Approximate fds are di cult to be identi ed at design time like it happens with fds. In this paper, we propose a genetic algorithm to discover approximate fds from data. An empirical evaluation demonstrates the e ectiveness of the algorithm.
In the last decades, functional dependencies have been extended to deal with
new problems, such as data cleansing [
While fds were originally speci ed at database design time, as properties
of a schema that should hold on every instance of it, in order to reduce the
designer e ort and to dynamically adapt the rfds to the evolution of the
application domain, it is necessary to automatically discover them from data. 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 [
Most of the discovery algorithms described in the literature are intended for
fds [
The paper is organized as follows. Section 2 reviews the rfd discovery algorithms existing in the literature. Section 3 provides some background de nitions about rfds and formulates the problem of rfd discovery. Section 4 presents the proposed genetic algorithm named GA-rfd for discovering rfds from data, whose performance are reported in Section 5. Finally, summary and concluding remarks are included in Section 6. 2
In the literature there are two main categories of methods to automatically
discover fds from data, namely top-down and bottom-up methods. The formers
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 candidate fds. Examples of
topdown approaches include the algorithms TANE [
Although a recent survey listed thirdy-four di erent types of rfds [
Approximate functional dependencies (afds) are fds holding for `most' rather
than `all' the tuples of a relation r [
Like afds, conditional functional dependencies (cfds) are fds holding for
a subset of tuples, but in this case the subset is identi ed by specifying
conditions [
Matching dependencies (mds) are rfdc de ned in terms of similarity
predicates to accommodate errors, and di erent representations in unreliable data
sources [
Di erential dependencies (dds) are rfdc based on di erential constraints on
attribute values [
As opposed to these discovery algorithms, which focus each on a speci c rfd,
the discovery algorithm proposed in [
The algorithm proposed in this paper further extends the class of discovered rfds, by also including those relaxing on the extent. 3 3.1
Before de ning rfds we need to introduce the concept of similarity constraint, which expresses the similarity of two values on a speci c domain, and it is represented through a function . In particular, given two attributes A and B on a domain D, (A; B) evaluates the similarity of A and B. As an example, can be de ned in terms of a similarity metric ≈, like for instance the edit distance, such that a≈b is true if a and b are \close" enough w.r.t. a prede ned threshold.
Given a relational schema R de ned over a xed set of attributes, and R1 = (A1; : : : ; Ak) and R2 = (B1; : : : ; Bm) two relation schemas of R, an rfd ' on R is denoted by ≥ Dc1 × Dc2 ∶ (X1; X2) 1 ÐÐ→ (Y1; Y2) 2 (1) where k m { Dc1 ×Dc2 = (t1; t2) ∈ dom(R1)×dom(R2) S i⋀1 c1i (t1[Ai]) ⋀ j⋀1 c2j (t2[Bj]) = = where c1 = (c11 ; : : : ; c1k ) and c2 = (c21 ; : : : ; c2m ), with c1i and c2j predicates on dom(Ai) and dom(Bj), respectively, that lter the tuples on which ' applies; { X1; Y1 ⊆ attr(R1), and X2; Y2 ⊆ attr(R2), with X1 ∩ Y1 = ∅ and X2 ∩ Y2 = ∅; { 1 ( 2, resp.) is a set of constraints [X1; X2] ( [Y1; Y2], resp.) on attributes X1 and X2 (Y1 and Y2, resp.). For any pair of tuples (t1, t2)∈ Dc1 × Dc2 , the constraint [X1; X2] ( [Y1; Y2], resp.) indicates true, if the similarity of t1 and t2 on attributes X1 and X2 (Y1 and Y2, resp.) agrees with the constraint speci ed by [X1; X2] ( [Y1; Y2], resp.). { is a coverage measure de ned on Dc1 × Dc2 , which quanti es the satis ability degree of ' on r, and can be de ned as a function ∶ dom(X)×dom(Y ) → R measuring the amount of tuples in r violating or satisfying '. { is a threshold indicating the lower bound (or upper bound in case the comparison operator is ≤) for the result of the coverage measure.
Given r1 ⊆ Dc1 and r2 ⊆ Dc2 two relation instances on (R1; R2), (r1; r2) satis es the rfd ', denoted by (r1; r2) ⊧ ', if and only if: ∀ (t1; t2) ∈ (r1; r2), if [X1; X2] indicates true for each constraint ∈ 1, then almost always [Y1; Y2] indicates true for each constraint ∈ 2. Here, almost always means that ( X1 (r1) X2 (r2); Y1 (r1) Y2 (r2)) ≥ .
For rfds de ned on single relation schemas (i.e., R1 = R2), if X1 = X2 and Y1 = Y2, then we will simplify the rfd notation given in (1) by using Dc, X, and Y to refer to the Cartesian product Dc1 × Dc2 , and to the pairs (X, X) and (Y , Y ), respectively. Moreover, if the rfd has to be satis ed by all tuples in r, then the symbol err(0) is shown on the arrow. Such coverage measure corresponds to the expression (X; Y ) = 0, where (X; Y ) measures the number of tuples violating the rfd. As an example, the canonical fd can also be written err(0) as: Dtrue ∶ Xeq ÐÐÐÐ→ Yeq, where true is a sequence of tautologies, hence Dtrue = dom(R1), whereas eq is the equality constraint.
As an example, in a database of body measures it is likely to have a similar shoe size for people having a similar height. Thus, the following rfd might hold Dtrue ∶ Height≈ ÐÐerÐrÐ(0→) Shoe Size≈, where ≈ is a di erential function. On the other hand, there might be exceptions to this dependencies, since few people might have close heights but more di erent shoe sizes. This can be modeled by introducing a di erent coverage measure into the rfd, making it approximate (Height;ShoeSize)≤0:02 Dtrue ∶ Height≈ ÐÐÐÐÐÐÐÐÐÐÐÐÐÐ→ Shoe Sizeeq, where (Height; ShoeSize) ≤ 0:02 indicates that at most for 2% of tuples the rfd does not hold. 3.2
Given a relation r, the discovery of rfds is the problem of nding a minimal
cover set of valid rfds that hold in r. This problem introduces further complexity
to the already complex task of fd discovery from data, due to the signi cantly
larger search space, which derives from the several similarity/distance functions
that may be de ned over each attribute [
In this paper, we analyze the problem of rfd discovery from data given a set of thresholds for both attribute comparison and coverage measure. Although this reduces the overall complexity of the problem, it still remains more complex than the fds discovery one. In fact, as said in Section 3.1, an rfd X → Y holds on a relation r i whenever the distance between two tuples t1 and t2 in r is below a threshold value A on each attribute A belonging to X, then their distance is below a threshold value B on each attribute B belonging to Y , with a degree of certainty greater than a threshold value . For this reason, we have to analyze the similarity between portions of tuple pairs rather than their equality. This does not permit to exploit the equivalence classes of attribute values, usually used for fd discovery. Indeed, an attribute value might be similar to other attribute values that are not similar to each other. 4
The proposed algorithm discovers rfds by comparing tuples pairwise, based on the similarity of subsets of their attributes. In particular, pairs of tuples with a similarity higher than a threshold are represented with the value 1, and 0 otherwise. In this way, we reduce the rfd discovery problem to a search one, which is solved through a GA. The latter implements a simulation in which a population of candidate solutions to an optimization problem evolves towards better solutions. The process usually starts from a population of randomly generated individuals (Initialization), which evolves by stochastically selecting multiple individuals from the current population (based on a tness function), and modi ed (recombined and possibly randomly mutated) to form a new population. The algorithm terminates when either a maximum number of generations has been produced, or a satisfactory tness level has been reached for the population. In the rst case, a satisfactory solution may or may not have been reached. 4.1
GA-RFD In this section, we explain the GA to discover rfds, which is named GA-rfd. In particular, in the following we rst explain how the discovery problem has been encoded for GA processing, then we de ne the tness function to evaluate the satisfactory degree of individuals, and nally, we present the GA-rfd algorithm. Encoding. Given the thresholds for attribute comparison and coverage measure, the problem of rfd discovery reduces to nd all possible dependencies X → Y satisfying the following rule: tuples that are similar on the LHS must correspond to those that are similar on the RHS. Such a rule must hold for almost all set of tuples that are similar on the LHS attributes, according to the threshold speci ed for the coverage measure.
In order to accomplish this with a GA, the dataset has to be modeled in a way that highlights similarity between tuple pairs. For this reason, in the proposed methodology we transform an input dataset in terms of a di erence dataset. The latter contains the input dataset attributes as columns, the input dataset tuple pairs as rows, and the similarity between tuple pairs as values. In particular, given an attribute Xi and a tuple pair (t1; t2), the di erence dataset will have the value 1 if t1[Xi] is similar to t2[Xi] according to the threshold associated to Xi, and the value 0 otherwise.
Example 1. Let us consider the sample dataset shown in Table 1a, and the similarity thresholds: 1 for the attributes Height and Shoe Size, and 10 for the attribute Weight. By using the absolute di erence as a distance function, we can derive the di erence dataset shown in Table 1b.
In order to construct individuals in the population we use an array of integers representing the attribute indices in the di erence dataset. In particular, each item i of the array corresponds to a speci c attribute Xi in the dataset. In particular, since all the rfds can be reduced w.l.o.g. to a format with a single attribute on the RHS, each individual of size k will represent a candidate rfd, where the k − 1 attributes on the LHS correspond to the rst k − 1 items in the array, and the last one corresponds to the attribute on the RHS. It is worth to notice that the algorithm can be iterated with several values for k in order to consider rfds with di erent sizes on the LHS.
Example 2. The individual [3; 1] for the dataset in Table 1a will represent the candidate rfd: Shoe Size → Height.
Fitness Function. In order to discover rfds we exploit the concepts of support
and con dence commonly used in the context of association rule mining. In
particular, several studies have demonstrated the relationship existing between
fds and association rules [
In our context, sup(X) represents the ratio of tuple pairs that are similar on all attributes in X. In this way, we can use the con dence as the tness function to determine if a candidate rfd X → Y is valid: conf (X → Y ) = suspupp(pX(X∪Y) ) : This tness function returns 1 if and only if whenever tuple pairs are similar on attributes in X, then they are similar also on Y . In order to validate a candidate rfd the proposed algorithm associates the threshold speci ed for the coverage measure to the tness function.
Example 3. If we consider the individual [3; 1] of Example 2, representing the candidate rfd: Shoe Size → Height, the associated support and con dence are: sup(Shoe Size) = 1231 , sup({Shoe Size; Height}) = 261 , conf (Shoe Size → Height) = 261 × 1231 = 163 = 0:46. This candidate rfd will not be considered as valid, unless the coverage threshold speci ed in input is less than 0:46.
Algorithm 1 The general GA-rfd algorithm 1: procedure GA-RFD(di erence dataset D, extent threshold , int maxgen, int
pop size, int k, double p1, double p2) 2: Set pop, final pop, new pop 3: int gen ← 0 4: final pop ← initialize(pop size, k, numCols(D)) 5: while gen ≤ maxgen do 6: if (allOf(final pop, )) then 7: break 8: end if 9: new pop ← select(final pop, ) 10: pop ← ∅ 11: pop ← crossover(new pop, k, p1) 12: pop ← mutate(pop, k, numCols(D), p2) 13: final pop ← new pop ∪ pop 14: g ← g + 1 15: end while 16: return final pop 17: end procedure Algorithm. The pseudo-code of the main procedure of GA-rfd is shown in Algorithm 1. It rst produces the initial population through the initialize procedure, and then, within a cycle, it selects only the individuals that reach the tness function objective (select procedure), makes crossover on selected individuals according to a xed probability p1 (crossover procedure), mutates some of them according to a xed probability p2 (mutate procedure). The new population is evaluated in the next iteration of the cycle. GA-rfd terminates if and only if either the population is composed of individuals, each one representing a valid rfd according to the -threshold for the coverage measure, which determines the tness objective; or the number of iterations exceeds the speci ed maximum number.
The initialize procedure shown in Algorithm 2 creates a set of individuals representing the initial population, according to the size pop size speci ed as input. The used random values are ranged in the number of columns of the dataset, since each individual element will represent a column index.
The select procedure shown in Algorithm 3 analyzes the individuals of the population pop and constructs a new population (selected pop) by including individuals with a probability related to the tness function objective .
Algorithm 2 The initialize procedure 1: procedure initialize(int pop size, int k, int numCols) 2: Set pop 3: for i ≤ pop size do 4: List x 5: for j ≤ k do 6: add randInt(1,numCols) to x 7: end for 8: add x to pop 9: end for 10: return pop 11: end procedure Algorithm 3 The select procedure 1: procedure select(Set pop, double ) 2: Set selected pop → {} 3: double fitness, confidence 4: for each c Î pop do 5: confidence = supspu(pcp:({cX:X∪Y) }) 6: if confidence ≥ then 7: fitness = 1 8: else 9: fitness = confidence~ 10: end if 11: if rand() < fitness then 12: selected pop = selected pop ∪ {c} 13: end if 14: end for 15: return selected pop 16: end procedure
The crossover procedure shown in Algorithm 4 creates a new population of individuals (new pop) by crossing individual pairs. We use a one-point crossover to recombine individuals; the crosspoint is selected randomly. In this procedure we use the function swap, which changes a sublist of two individuals by swapping one to each other.
The mutate procedure shown in Algorithm 5 creates a new population of individuals (new pop) by mutating one value in each individual. The individual element that has to be changed (gene) and the new value (new gene) are selected randomly. In this procedure we use the function swapV alue, which changes a value in a individual by swapping it with the new value. The mutate procedure permits to detect candidate rfds that do not directly depend on the initial population. It has associated a low probability, which limits the randomness of the whole methodology.
Algorithm 4 The crossover procedure 1: procedure crossover(Set pop, int k, double p) 2: Set new pop → {} 3: int crosspoint 4: for each c1,c2 Î pop with c1 ≠ c2 do 5: if rand() < p then 6: crosspoint = randInt(1,k) 7: for i ≤ crosspoint do 8: swap(c1,c2, i) 9: end for 10: add c1 to new pop 11: add c2 to new pop 12: end if 13: end for 14: return new pop 15: end procedure Algorithm 5 The mutate procedure 1: procedure crossover(Set pop, int k, int numCols, double p) 2: Set new pop 3: int gene, new gene 4: for each c Î pop do 5: if rand() < p then 6: gene = randInt(1,k) 7: new gene = randInt(1,numCols) 8: swapValue(c, gene, new gene) 9: end if 10: add c to new pop 11: end for 12: return new pop 13: end procedure 5
In this section we describe the performed empirical evaluation to verify the e ectiveness of the proposed GA-rfd algorithm. In particular, we rst evaluate the performance of the algorithm when used to discover fds, then we evaluated the rfd discovery performance.
The evaluation has been performed on a version of GA-rfd implemented
in the Python language, and on a machine with an AMD Opteron (TM) CPU,
8 GB RAM, and Linux Ubuntu 16.10 OS. Moreover, we used two real-world
datasets, also employed for evaluating several fd discovery algorithms [
Table 3 reports for each dataset: (i) the number of errors introduced in the dataset, (ii) the number fds of discovered on the dataset with dirty data, (iii) the number of discovered rfds by associating a threshold ≤1 to one attribute in order to manage similarities in the value comparison1, (iv) the number of rfds discovered with a coverage threshold of 0:9.
We can observe that the errors introduced in sample-dataset2 and iris2 have reduced the number of discovered fds. On the contrary, for bridge2 such a number increases, since a minimal fd 1 has been violated by errors and three new fds, whose LHS has more attributes than LHS( 1), have been discovered. The relaxation on attribute comparison has allowed to capture the errors introduced in the datasets. However, for bridge2 a new dependency has been discovered 1In particular, we have associated the threshold 1 to the rst attribute in the sampledataset2, and to the fth attribute in both iris2 and bridges2. The other attributes have associated threshold 0. beyond those reported in 2. Regarding the relaxation of tuple coverage, for sample-dataset2 the threshold is too narrow to capture the introduced error; for iris2 we obtained less but more general dependencies than those reported in 2; for bridge2 many more dependencies were discovered, due to the fact that the introduced errors is not signi cant compared to the size of the dataset, and to the number of dependencies holding in it, as reported in 2. 6
In this paper we have proposed GA-rfd, a GA for discovering rfds from data. It analyzes tuple pairs similarity through a di erence dataset, and validates rfds by calculating the con dence on each candidate rfd. A preliminary evaluation of the algorithm has been carried out to assess the e ectiveness of the approach.
In the future, we would like to further improve this approach in order to
automatically discover the rfds and the threshold ranges of validity, without
requesting their speci cation to the user. Furthermore, we would like to investigate
the discovery of GA-rfd in the context of user interaction logs, especially in web
applications, aiming to mine user intent [