Relaxed functional dependencies (rfds) are properties expressing important relationships among data. Thanks to the introduction of approximations in data comparison and/or validity, they can capture constraints useful for several purposes, such as the identi cation of data inconsistencies or patterns of semantically related data. Nevertheless, rfds can provide bene ts only if they can be automatically discovered from data. In this discussion paper we present an rfd discovery algorithm relying on a lattice structured search space, and a new candidate rfd validation method. An experimental evaluation demonstrates the discovery performances of the proposed algorithm on real datasets.
Functional dependencies (fds) were originally used to verify database design
and assess schema quality. In the last decades, they have been used for several
new purposes, such as data pro ling [
Recent literature refers to extended fd de nitions with the term relaxed
functional dependencies (rfds) [
In order to exploit fds in practical domains several algorithms to discover
them from data have been proposed [
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). This volume is published and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy.
In this discussion paper, we describe the algorithm proposed in [
The paper is organized as follows. Section 2 reviews the rfd discovery algorithms existing in the literature. Section 3 provides some background de nitions concerning rfds. Section 4 presents the DiM" algorithm, whereas Section 5 shows the experimental results. Concluding remarks are included in Section 6. 2
The automatic discovery of fds is accomplished either through column-based or
row-based methods [
Several discovery algorithms have been proposed for Matching dependencies,
e.g., [
Informally, an rfd is a functional dependency that relaxes on the tuple
comparison, by using constraints on the distance or similarity between attribute values,
and/or that relaxes on the extent, by using a coverage measure to indicate the
minimum number or percentage of tuples on which the rfd must hold, and/or
by using conditions restricting the applicability domain of the rfd. In what
follows, we recall a formal de nition of rfd from our previous survey [
X 1 ÐÐ→" Y 2 ≤ (1) where { X = X1; : : : ; Xh and Y = Y1; : : : ; Yk, with X; Y ⊆ attr(R) and X ∩ Y = ∅; { j [Yj ], resp.), where i ( j , resp.) is a conjunc1 = X⋀i∈X i[Xi] ( 2 = Yj⋀∈Y tion of predicates on Xi (Yj , resp.) with i = 1; : : : ; h (j = 1; : : : ; k, resp.). For any pair of tuples (t1, t2)∈ dom(R), the constraint 1 ( 2, resp.) is true if t1[Xi] and t2[Xi] (t1[Yj ] and t2[Yj ], resp.) satisfy the constraint i ( j , resp.) ∀ i ∈ [1; h] (j ∈ [1; k], resp.). { is a coverage measure de ned on dom(R), quantifying the amount of tuples violating or satisfying '. Among the most commonly used coverage measures there are the con dence, the g3-error, and the probability. { " is a threshold indicating the upper bound (or lower bound in case the comparison operator is ≥) for the result of the coverage measure.
Given r ⊆ dom(R) a relation instance on R, r satis es the rfd ', denoted
by r ⊧ ', if and only if: ∀ t1; t2 ∈ r, if 1 indicates true, then almost always 2
indicates true. Here, almost always is expressed by the constraint ≤ ". A more
general de nition of rfd is provided in [
As an example, in a database of scienti c publications it is likely to have the same address and a liation for authors with the same name. Thus, an fd fAuthorg → fAddress, Affiliationg might hold. However, these attributes might have been stored using di erent abbreviations, hence the following rfd might hold: Author 1 Ð→ {Address 2 ; Affiliation 3 }, where 1, 2, and 3 are constraints on a string similarity function. Moreover, since authors might change a liation during their life, or there might be homonimies, the previous rfd should tolerate possible exceptions. This can be modeled by the following rfd:
(Author;Address;Affiliation)≤0:02
Author 1 ÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐÐ→ {Address 2 ; Affiliation 3 } 4
The discovery of rfds is the problem of nding a set of minimal rfds holding ≤" on a relation instance r. An rfd X 1 ÐÐ→ Y 2 is minimal if there not exists a subset Z ⊂ X such that Z 1 ÐÐ→" Y 2 holds on r.
≤
For sake of simplicity and w.l.o.g, in the rest of the article we assume that Y consists of a single attribute.
The Di erence Matrix and "-threshold (DiM") discovery algorithm presented
in [
(b) MHeightabs;Weightabs
Candidate RFD validation The validation of candidate rfds entails verifying that two tuples are similar on the RHS attribute, whenever they are similar on the LHS ones, and the property holds for a signi cant portion of the database. This is done by generating similarity subsets of tuples and using them to validate candidate rfds. As opposed to tuple partitions built in most fd discovery algorithms, similarity subsets might also intersect. To better explicate the generation process of similarity subsets, we introduce the concept of di erence matrix. De nition 2 (Di erence matrix of an attribute). Let r be an instance of a relation schema R, A an attribute of R, and a distance function de ned on the domain of A. The di erence matrix for A is a matrix MA whose entry (i,j) contains the value (ti[A]; tj [A]) of the projections of tuples ti and tj on A.
As an example, let us consider the sample dataset in Table 1. Since it has all numerical attributes, we use the absolute di erence, denoted with abs, as a distance function to construct the di erence matrix MHeightabs (Figure 1(a)).
The de nition of di erence matrix can be easily generalized to attribute sets, in which an entry will contain an n-tuple of distance values, one for each attribute in the set. The di erence matrix for an attribute set X can be derived from the di erence matrices for the single attributes composing it, by concatenating elements with the same coordinates. An example is provided in Figure 1(b).
We exploit the notion of di erence matrix to generate the similar pattern of a tuple t or a matrix row, which represents sets of tuples or matrix columns satisfying a given constraint wrt t. Successively, we group the tuples sharing the same similar patterns into similar pattern subsets.
De nition 3 (Similar pattern subsets). Let r be an instance of a relation schema R, X = {A1; : : : ; An} an attribute set of R, MX a di erence matrix for X, and = ( 1; : : : ; n) a sequence of constraints on the values of MX . A similar pattern of tuple ti of MX , denoted as Xti , is the sequence (j1; : : : ; jh) with h ≤ SrS and M [i; jk] = (d1; : : : ; dn), where dq satis es the constraints q ∀q ∈ [1; n] and ∀k ∈ [1; h]. A similar pattern subset SX for X is de ned as SX = {j1; : : : ; jh}{i1;:::;ik} with 1 ≤ k ≤ h ≤ SrS, Xip = (j1; : : : ; jh) ∀p ∈ [1; k] and Xiv ≠ (j1; : : : ; jh) ∀v ∉ [1; k]. The set of di erent similar pattern subsets for X is denoted as IX .
Example 1. If in the dataset of Table 1 the user speci es constraints based on the abs function, the ≤ comparison operator, 1 as a threshold for both the attributes Height and Shoe Size, and 10 for the attribute Weight, then the following sets of similar pattern subsets are generated: { IHeight = {{1; 2; 3; 4}{1;2;3;4}; {5}{5}; {6; 7}{6;7}}; { IWeight = {{1; 2; 3; 4; 6; 7}{1;3}; {1; 2; 3; 4; 5; 6}{2;6}; {1; 2; 3; 4; 5; 6; 7}{4}; {2; 4; 5; 6}{5}; {1; 3; 4; 7}{7}}; { IShoe Size = {{1; 2; 3; 4; 5; 7}{1;3;4}; {1; 2; 3; 4; 7}{2;7}; {1; 3; 4; 5}{5}; {6}{6}}.
In order to validate candidate rfds, DiM" reduces the number of similar pattern subsets for the attributes of the LHS, by eliminating singletons (since they correspond to the matrix diagonal entries that trivially compare each tuple with itself) obtaining stripped similar pattern subsets.
Validation of RFDs relaxing only on the tuple comparison. Stripped similar pattern subsets can be used to validate candidate rfds based on the concept of similar pattern subset re nement.
De nition 4. A set ÎX is said to re ne another set ÎX∪A if every similar pattern subset in ÎX is contained in one of the subsets in ÎX∪A.
Based on the re nement notion, we derive the following lemma for rfds. Lemma 1. A relaxed functional dependency X 1 Ð→ A 2 holds on an entire database instance if and only if ÎX re nes ÎA.
Example 2. Let us consider the database instance of Table 1. If we set the constraints as de ned in Example 1, then according to Lemma 1 the rfd {Height 1 ; Weight 2 } Ð→ Shoe Size 3 holds on the entire database. In fact, since ÎHeight;Weight = {{1; 2; 3; 4}{1;2;3;4}} and ÎShoe Size = {{1; 2; 3; 4; 5; 7}{1;3;4}; {1; 2; 3; 4; 7}{2;7}; {1; 3; 4; 5}{5}}, each similar pattern in ÎHeight;Weight is included in a similar pattern of ÎShoe Size.
Alternatively, the re nement property between sets of stripped similar pattern subsets can be veri ed by calculating SSÎZ SS, which is de ned as: SSÎZ SS = ∑ti∈r(S2sti S − 1) ∀sti ∈ ÎZ (2) It represents the number of pairwise similar tuples in ÎZ . Since for an attribute set W ⊂ Z, ÎZ always re nes ÎW , it means that ÎX∪A always re nes ÎX . However, we know that an rfd X 1 Ð→ A 2 holds only if ÎX is a re nement of ÎA. Thus, since ÎX∪A cannot have similar pattern subsets of size greater than those in ÎX , the rfd holds if ÎX∪A and ÎX are equal, which yields the following lemma. Lemma 2. A relaxed functional dependency X 1 Ð→ A 2 holds on an entire database instance if and only if SSÎX∪ASS = SSÎX SS.
Validation of hybrid RFDs. In case of hybrid rfds, DiM" should also
consider as valid the rfds holding on a subset of tuples, according to a coverage
measure and a user-de ned threshold. In this case, it is not possible to use the
previously de ned lemma to validate candidate rfds. In particular, to
accomplish the validation process it is necessary to calculate the satis ability degree of
the instance according to a coverage measure. In this paper, DiM" relies on the
g3-error coverage measure [
The computation of the g3-error for rfds with hybrid relaxation is an
np-complete problem [
We implemented DiM"1 in the Java, by using the Levenshtein distance for
comparing textual attributes, the absolute di erence for comparing numerical ones,
and the g3-error as the coverage measure for extent evaluation [
Figure 2 shows the number of rfds extracted by DiM" according to several tuple comparison thresholds, whereby each line represents a di erent extent threshold. We can observe that the highest number of rfds is usually discovered with g3-error thresholds slightly above zero. Concerning the variation of tuple 1https://dastlab.github.io/dime/. 2https://archive.ics.uci.edu/ml/index.php (a) Car-Data (b) Cars (d) Breast-cancer (e) Bridges (f) Lymphography comparison thresholds, in most cases the number of rfds drastically drops when increasing them from 0 to 1. This is mainly due to the fact that with a zero threshold many key dependencies are obtained, which are likely to be invalidated when the tuple comparison threshold becomes greater than zero.
Figure 3 shows the execution times of DiM". In general, although we expect higher execution times on datasets with more columns and/or rows, this is not necessarily true, because the attribute value distributions might heavily a ect the computation steps to be performed, since they in uence the number of tuple similarities, and hence the number of rfd candidates to be processed.
The problem of discovering rfds adds a considerable complexity to the
dependency discovery process, since the relaxation criteria reduce the possibilities of
pruning search paths, and prevent the possibility to exploit the properties of
disjoint partitions during the validation phase. The performed evaluation
highlights the e ectiveness of DiM" in the discovery of rfds relaxing on both the
tuple comparison and the extent dimensions. In the future, we would like to
further investigate the considered problem in order to derive an algorithm for
rfd discovery capable of automatically inferring the threshold ranges of their
validation, as done in [