Inspired by the visualization of dental plaque at the dentist's ofice, this article proposes a novel visualization of redundancies in relational data. Our approach is based on a well-principled information-theoretic framework that has seen limited practical application in systems and tools. In this framework, we quantify the information content (or entropy) of each cell in a relation instance, given a set of functional dependencies. The entropy value signifies the likelihood of recovering the cell value based on the dependencies and the remaining tuples. By highlighting cells with lower entropy, we efectively visualize redundancies in the data. We present an initial prototype implementation and demonstrate that a straightforward approach is insuficient to handle practical problem sizes. To address this limitation, we propose several optimizations, which we prove to be correct. Additionally, we present a Monte Carlo approximation with a known error, enabling computationally tractable analysis. By applying our visualization technique to real-world datasets, we showcase its potential. Our vision is to empower data analysts by directing their focus in data profiling toward pertinent redundancies, analogous to the diagnostic role of a plaque test at the dentist's ofice.
ID AlbumTitle
Band 1 Not That Kind Anastacia 1999 2000 1 Not That Kind Anastacia 1999 2000 1 Not That Kind Anastacia 1999 2000 2 Wish You Were Here Pink Floyd 1965 1975 3 Freak of Nature Anastacia 1999 2001 1 Not Th. . . 2 I’m Out. . . 3 Cowboy. . . 1 Shine O. . . 1 Paid my. . .
(a) The relational input data.
ID
AlbumTitle Band
BYear RYear Track TrackTitle
Contributions • We apply an existing information-theoretical framework for a “plaque test” that visualizes redundancies inherent in relational data. • We show that a straightforward implementation for computing the entropy values underlying our “plaque test” does not scale beyond toy examples. • Thus we propose several efective optimizations: 1. We discuss scenarios where entropy values can be immediately assigned to 1, thereby skipping computation, and where one can focus on a subset of the data instance when computing entropy values.
We prove the correctness of these optimizations. 2. We present a Monte Carlo approximation to compute entropy values. We provide the formula to determine the number of iterations required to achieve a given accuracy with a certain confidence. • We present visual plaque tests for several real-world datasets and discuss how the discovered “plaque” can indeed be helpful for data exploration. • We conduct run-time experiments with our implementation and explore the efect of our optimizations. Reproducibility Our research artifacts, including our prototype implementation, can be found at https://doi. org/10.5281/zenodo.8220684.
Long version Further experiments and the full set of proofs can be found in the long version of this article at https://doi.org/10.48550/arXiv.2306.02890.
Structure We provide preliminaries on functional dependencies, entropy, and information content in Section 2. In Section 3 we introduce two lines of optimization, one is an exact method, and the other an approximation. We present our experiments in Section 4. We discuss related work in Section 5 and conclude in Section 6.
(b) Entropies for 6 unary FDs.
AlbumTitle Band
BYear RYear Track TrackTitle (c) Entropies for 23 unary FDs.
Example 1.2. The Metanome tool [
Figure 1c shows the result of our plaque test, given we take into account the order of tuples. This allows us to
this new set of functional dependencies. Throughout, identify individual cells in a relation instance. The notion
the coloring of the cells is darker. Moreover, more cells of entropy-related information content originates from
are colored. This reveals that the instance now contains the work by Arenas and Libkin [
Notably, the entropy value for the band name “Anasta- the corresponding entropy values (Section 2.3). cia” is as low as 0.4, since it may be recovered from several dependencies, such as “ID Ñ Band” and “BYear Ñ Band”. 2.1. Functional Dependencies Thus, plaque is additive when an attribute occurs on the right-hand side of several functional dependencies. Denote by N the set of positive integers, N :“ t1, 2, . . . u.
Definition 2.1. A relation of arity is specified by a finite set sortpq :“ t1, . . . , u of attributes . The domain of an attribute is denoted by Dompq.
: N á
ą Psortpq
Dompq obtained by replacing the positions from by variables, and then position by the value , is pÐ qÐ).
An instance containing distinct variables at positions “ t1, . . . , u fulfills a set of functional dependencies (write |ù ) if there exists a set of values Defpq :“ t P N | “ p1, . . . , q such that Ð |ù . For one functional dependency P we write |ù if |ù t u. with finite domain of definition pq is defined u.
duplicate tuples and preserves the order of the tuples.
To simplify the exposition, in this work we assume that Dompq “ N for all P sortpq, i.e., each tuple consists of positive integers. Thus an instance of a relation of arity can be seen as just a partial map : N á N.
Definition 2.2. Let be a relation and an instance of . For a subset :“ t1, . . . , u Ď sortpq of attributes, we have the projection pq of the tuples in to the attributes in . Moreover, for a subset Ď Defpq we have the restricted map | : Ñ N defined for all indices P .
rs the value of the attribute in the -th tuple :“ pq of .
Similarly, for a subset “ t1, . . . , u Ď sortpq of attributes we denote by r1 . . . s the tuple of values r1s, . . . , rs, that is, the -th tuple ppqq of the projection pq.
Definition 2.3. A functional dependency in a relation is a pair :“ pt1, . . . , u, q, where 1, . . . , , P sortpq are attributes. We write such a pair as 1 . . . Ñ .
An instance of a relation is said to fulfill the functional dependency (write |ù ) if for all 1, 2 P Defpq it holds 1 r1 . . . s “ 2 r1 . . . s ñ 1 rs “ 2 rs.
dependencies (write |ù ) if |ù for all P .
values at some positions. Let var be a (countably infinite) set of variables.
Definition 2.4. Let be an instance of a relation with attributes sortpq “ t1, . . . , u. A position in is a pair p, q with P Defpq and P t1, . . . , u; it represents the cell of the -th attribute of the -th tuple, with value rs. The instance obtained by putting the value at position “ p, q is denoted by Ð.
Let “ t1, . . . , u be a set of positions, “ p1, . . . , q distinct variables, and “ p1, . . . , q values in N. The instance obtained by replacing each position by the variable resp. by value for 1 ď ď is denoted by Ð resp. Ð (hence, the instance For :“ 1 . . . Ñ (and possibly containing variables) we immediately obtain that |ù holds if and only if for all 1, 2 P Defpq such that 1 rs R var and 2 rs R var there holds 1 r1 . . . s “ 2 r1 . . . s ñ 1 rs “ 2 rs. So the above definition requires a single functional dependency to be fulfilled only for tuples without variables. Indeed, since all variables are distinct, it is always possible to set values in their positions so that the functional dependency is fulfilled.
For a set of functional dependencies, it can be shown
that |ù if and only if |ù for all P ˚, where ˚
is the transitive closure of . This equivalence ensures
the same semantics as in the original work by Arenas
and Libkin [
In the following, we deal with discrete probability spaces “ p, q on finite sets , where pq for P denotes the probability of the event tu. The informationtheoretic entropy of the probability space is given by p q :“ ´ ÿ pq log pq.
P
If “ p, q and ℬ “ p, ℬq are probability spaces on finite sets and with joint distribution ˆℬ, then the conditional probability of P given P is defined by p|q :“ ˆℬp, q ℬpq provided that ℬpq is non-zero.
Conversely, the conditional probabilities p|q with the probabilities ℬpq determine the joint distribution ˆℬ by the above formula.
Definition 2.5. Let “ p, q, ℬ “ p, ℬq be probability spaces. The conditional entropy of given ℬ is p | ℬq :“ ´ ÿ ℬpq ÿ p|q log p|q.
P P
ability space given the outcome in ℬ. If the probability distributions of and ℬ are independent, then p|q “ pq for all P , and thus we obtain p | ℬq “ ´ řP pq log pq “ pq.
denote by Pos :“ Defpq ˆ t1, . . . , u its set of positions. Let be a set of functional dependencies fulfilled by and P Pos a position. We define two probability spaces as follows.
First, let ℬp, q :“ ppPos ztuq, ℬq, where ℬ is the uniform distribution on the set of all subsets of Pos ztu. This space models the possible cases when we lose a set of possible values from the instance on positions other than the considered one .
Then, for P N we let p, q :“ pt1, . . . , u, q, where the conditional probability of P t1, . . . , u given Ď Pos ztu is p|q :“ #1{# if P ,
0 otherwise, with :“ t P t1, . . . , u | pÐ qÐ |ù u. This probability space models the possible values in t1, . . . , u to be put in at position for which we lost the value, when is the set of positions of the other lost values in the instance.
Definition 2.6. Let be a set of functional dependencies for a relation and let be an instance of with |ù . The information content of position with respect to in instance is given as
INF p | q :“ lÑim8
INFp | q log , where INFp | q :“ p p, q | ℬp, qq is the conditional entropy of the probability space modeling the possible values for the considered position given the space modeling the possible sets of other lost values in the instance.
Unfortunately, when using the above formula for the conditional entropy INFp | q directly, the computation grows exponentially with the number of cells in the given instance. Indeed, for each cell except the one at position the value can be deleted or not, so every subset of Pos ztu is an elementary event in the probability space ℬp, q. Therefore, each additional cell in the instance doubles the number of events to be taken into account for the computation of the information content.
1 INF p | q “ 2# Pos ´1 ÿ lim log # , ĎPos ztuÑ8 log
Definition 3.1. Let “ p, q P Pos be a position with We now provide more compact and simplified (but still attribute in an instance and let be a functional exponentially complex) formulas for the information con- dependency 1 . . . Ñ with |ù . We say that tent. The first result easily follows from the definition of the value at is unique with respect to if for every conditional entropy. 1 P Defpq there holds Proposition 2.7. Let be a set of functional dependencies r1 . . . s “ 1 r1 . . . s ñ “ 1 and an instance with |ù . Then the information content of a position in with respect to is given by (so if ‰ 1, then r1 . . . s ‰ 1 r1 . . . s).
For a set of functional dependencies with |ù , the value at is unique with respect to if it is unique with respect to all P of the form 1 . . . Ñ . where :“ t P t1, . . . , u | pÐ qÐ |ù u.
The values INF p | , q :“ limÑ8 loglo#g can be seen as the information content of in with respect to given a fixed subset Ď Pos ztu to be substituted by variables. The next result shows that for these, there are only two possible outcomes.
Lemma 2.8. Let , and be as above. For any Ď Pos ztu we have INF p | , q P t0, 1u.
Proof. Consider any “fresh” value P N, which does not appear in the column of position in the relation instance . It is easy to see that, whether the instance pÐ qÐ fulfills or not, does not depend on the choice of those values . Therefore, as Ñ 8 we either have log #{ log Ñ 1 or log #{ log Ñ 0.
simplification for computing information content. Proposition 2.9. Let be a set of functional dependencies and an instance with |ù . Let be a position in with attribute , and let P N be any value that does not appear in the column of attribute . This yields: INF p | q “ #t Ď Pos ztu | pÐ qÐ |ù u 2# Pos ´1
information content somewhat, one still needs to consider all subsets of Pos ztu, leading to exponential complexity. Therefore, we present in the following several optimizations for this computation.
In this section, we provide optimizations to speed up the computation of information content. In Section 3.1 we deal with exact methods and prove their correctness, while in Section 3.2 we present an approximation.
We give two shortcuts for computing the information content in a relation instance. The first identifies the positions where there cannot be any redundancy, so that the information content equals 1.
Proposition 3.2. Let P Pos be a position in an instance , where |ù for a set of functional dependencies .
Then INF p | q “ 1 if and only if the value at is unique with respect to .
Proof (of the “if” direction). Let be the attribute of position and let be a “fresh” value not appearing in the column of attribute in the instance . By Prop. 2.9 it sufices to show that for every subset Ď Pos ztu it holds that pÐ qÐ |ù . So let P be a functional dependency 1 . . . Ñ 1. From |ù we know that Ð |ù . Then we have to show that pÐ qÐ |ù , i.e., if 1 r1 . . . s “ 2 r1 . . . s for some 1, 2 P Defpq it still holds that 1 r1s “ 2 r1s, even after and the set of functional dependencies :“ tA Ñ Cu. inserting value at position . Since the attributes A, B or D do not appear on the
Suppose first that ‰ 1. If R t1, . . . , u (and right-hand side of the functional dependency, Prop. 3.2 ‰ 1q the assertion above is clear for any value , implies that INF p | q “ 1 for all “ p, q since the statement is not afected. On the other hand, if with ‰ C. Additionally, by Prop. 3.2 we obtain “ for some 1 ď ď , then by inserting the fresh that INF pp2, Cq | q “ 1, since the value at position value the hypothesis becomes false, so the statement “ p2, Cq is unique with respect to . remains valid. We can reduce the table using Prop. 3.3 by removing
Now consider the case “ 1 and let “ p, q. the second tuple and the attributes B and D. The resulting We may assume that one of 1, 2 equals and write 1 for subtable is the other index. Then if r1 . . . s “ 1 r1 . . . s, then by the uniqueness property we infer that “ 1. So A C the above statement still holds after inserting the value , since the tuple indices coincide.
instance to the relevant tuples and attributes. This may for which the number of subsets in Posp, qztu is reduce the number of cells, and thus decrease the runtime reduced from 215 to 23, i.e., by a factor over 4’000. exponentially. After performing this step, we can apply Consider position “ p1, Cq and the subsets Ď the first shortcut in the smaller table and use the outcome Posp, qztu. For “ ∅, i.e., the values in all pofor the original instance. sitions diferent from p1, Cq are present, the instance
Let be a relation instance of arity and let Ď pÐ qÐ “ Ð fulfills the functional dependency Defpq, Ď t1, . . . , u where the are the at- A Ñ C only if “ 8. For all other subsets , i.e., at least tributes of the relation. The subinstance p, q consists one more value is lost, we obtain pÐ qÐ |ù for of all tuples of the projection pq with index P . all values . Therefore, INF p | q “ 87 “ 0.875. The We also let Posp, q :“ ˆ Ď Pos be the corre- computation of INFpp3, Cq | q is similar, and we get sponding set of positions.
Proposition 3.3. Let be a set of functional dependencies ¨1 1 0.875 1˛ and an instance with |ù . Denote by 0 the set ` INF pp, q | q˘ “ ˝1 1 1 1‚. of all indices 0 P Defpq such that for some position 1 1 0.875 1 “ p0, q P Pos the value at is not unique with respect to . Denote by 0 the union of all attributes 3.2. Monte Carlo Approximation t1, . . . , , u involved in any functional dependency 1 . . . Ñ in . Then for every Ě 0 and Ě 0 there holds Next, we present an approximation of the information content. This approach is complementary to the previous optimizations for computing exact values, e.g., by identifying cells with full information content first, then @ P Posp, q : INF p | q “ INFp,qp | q.
Our experiments target the following research questions: RQ1 Is the plaque test useful for real-world datasets? RQ2 Can we aford to compute exact entropy values or do we need the Monte Carlo approximation? RQ3 How does the runtime of the Monte Carlo approximation scale with the number of iterations?
In the following, we report on our insights with a first prototype and three real-world datasets.
Implementation Our prototype implements our algorithms as a single-threaded Java implementation. As a dispatcher, we use a Python script that also measures the end-to-end runtimes.
Datasets We explore three real-world datasets. All
functional dependencies are left-reduced with a single
attribute on the right and were discovered by Metanome [
Our first dataset describes natural satellites and originates from the WDC Web Table Corpus3. Metanome finds 35 functional dependencies, we analyze the first 150 rows. We study two additional datasets4: The adult dataset (where we analyze the first 150 rows) with 78 functional dependencies captures census data. The echocardiogram dataset (all 132 rows) with 538 functional dependencies describes heart attack patients. reducing the problem to a smaller subtable (if possible), and finally computing the values on this subtable with an approximation algorithm.
The approximation is computed with a randomized
algorithm, the Monte Carlo method, as introduced in [
Proposition 3.5 (Hoefding’s inequality) . Let 1, . . . , be independent identically distributed random variables such that ď ´ Ers ď . Then for any ą 0 it holds Pr ´ ř p ´Ersq ě “1 ¯ ď exp ´
´22 “1p ´ q2 . ř ¯
the probability space ℬp, q :“ ppPos ztuq, ℬq from Section 2 with uniform distribution ℬ. Define random variables : pPos ztuq Ñ r0, 1s, ÞÑ lÑim8 log # ,
log with :“ t P t1, . . . , u | pÐ qÐ |ù u. Then by Prop. 2.9 there holds Ers “ INF p | q.
This motivates the next theorem on the randomized Environment Our server has an Intel Xeon Gold 6242R approach to compute the information content with accu- (3.1 GHz) CPU and 192GB of RAM, and runs Ubuntu 22.04 racy and confidence 1´ . with Java 18.
Theorem 3.6. Let P Pos be a position in a relation Results We now address the research questions in turn. instance , where |ù for a set of functional dependencies. Let 1, . . . , be independent identically distributed random variables as above and :“ 1 ř “1 their average. Then for all , ą 0 it holds RQ1 We computed the plaque tests for the three datasets and show the results in Figure 3. Entropies are computed with Monte Carlo simulation set to 100’000 iterations, an accuracy of approx. 0.01, and a confidence of 99%.
Pr `| ´ INF p | q| ě ˘ ď Cells with an entropy value of 1 are shown in white, provided that ě 2 lnp2{ q{2. adnardkceerlslshawdietshivnadliuceastebleolwo wer1enatrreocpoylovraeludeisn. Cblouleo,rwschaeleres are calibrated individually, so colors cannot be compared wiPbnroegouofinnHf.ddoWeefofdxeripnphg´aP’svreipnř´2e{q12“uq1aď,plsiotythw´a´ittEhPErrrpř|sqs“´1ďěpE1r,´sqostb|hqyeě2au“ppqpp4leďyr- sbaettSewallteietelelnitddeasa.ttaFasisegetut.srP.elW3aaqeusdheiosiwcsuslostschaeelalpyclhacqodunaetcateesnsetttr.aaptpedli,eadstoonthlye 2 expp´2{2q ď . the column “Planet” and very few cells in column “Notes” contain entropy values below 1.
Example 3.7. Assume that for the approximation of in- We zoom in on a subset of the rows, omitting cells formation content for an instance at position with with an entropy value of 1 and showing the values for respect to , we allow an error of at most 0.001 with columns “MeanRadius”, “DiscoveredBy”, and “Planet”. probability at least 99.9%. This can be achieved by For tuples with a mean radius of 3.0, the entropy of sampling Ď Pos ztu and computing pq at least the attribute planet is the lowest. A mean radius of 3.0 2 lnp2{10´3q{p10´3q2 ě 1.52¨107 times. occurs only for Saturn satellites. Closer inspection re
If a less exact approximation is suficient, say with an veals that “MeanRadius” is on the left-hand side of several error of at most 0.01 with the same probability as be- functional dependencies (as discovered by Metanome), fore, then the required number of runs is lowered by a including “MeanRadius, DiscoverdBy Ñ Planet”. factor 100, thus only 1.52¨105 samples are necessary. Fig- 3http://webdatacommons.org/webtables/index.html#results-2015 ure 2 shows a plot of the iterations required for reaching 4Retrieved from https://hpi.de/naumann/projects/repeatability/ a certain accuracy () and a certain confidence ( 1´ ). data-profiling/fds.html, on June 02, 2023 (a) Satellites (150, Min: 0.61)
Results. We applied our visual plaque tests to standard datasets used in dependency discovery research. The (b) Adult (150, Min: 0.50) (c) Echoc. (132, Min: 0.00) plaque tests appear to be helpful in data exploration: Figure 3: “Plaque tests” applied to real-world data. The sub- When “plaque” is detected, we can always find an intucaptions state the numbers of rows analyzed and minimum itive explanation for its causes. entropy values computed (rounded). The color scale is normal- In the examples discussed, it highlighted a particularly ized individually with respect to the minimum entropy value. prominent functional dependency, it revealed a good The zoom-in in Subfigure (a) highlights a subset of rows. opportunity for schema normalization, and it exposed data with no informational value.
Moreover, the plaque test is very selective: The test is
By inspecting the causes for low entropy values in strongly positive for only a few attributes. This efect is this fashion, data analysts can gain insight into why au- also observable for two further datasets that we analyzed tomated tools discover certain dependencies. They can in the long version of this article. then decide whether the dependency is genuine or merely This sparsity of cells that test strongly positive for an artifact of the data. plaque is particularly notable in the case of the echocar
Adult. Figure 3b shows the plaque test applied to diagram dataset, despite the over 500 automatically disthe census data. Only two columns, “education” and covered dependencies. Compared to this high number of “education-num” have entropy values below 1. More- dependencies, the result of the plaque test is easily conover, in each row, both columns have the same entropy sumable, and data analysts are visually directed towards value. Closer inspection reveals that there are functional the most pertinent redundancies. dependencies “education-num Ñ education” as well as RQ2 Table 1 shows the runtime in seconds for computing “education Ñ education-num”. This causes the respec- the entropy values on subsets of the satellite data. We tive entropy values to agree. compute exact entropies and do not yet apply the Monte
In consequence, a data analyst might decide to decom- Carlo approximation. We compare the algorithm with pose this relation into the second normal form, by storing the optimizations from Section 3 disabled/enabled. the mapping between “education” and “education-num” The unoptimized algorithm can process only three in a separate relation. rows in 24 hours. Using the optimizations, up to five
In fact, normalization theory was a main motivator rows could be computed in 24 hours. behind the original work by Arenas and Libkin.
Results. Although the optimizations are efective, such
Echocardiogram. Figure 3c shows the plaque test ap- runtimes are still too slow for practical purposes. plied to the patient data. Among the three datasets, this dataset has the highest number of columns with entropy RQ3 We next explore the Monte Carlo approximation, values below 1: This afects 11 out of 13 columns, but in combination with our optimizations from Section 3. mostly only sparsely. Figure 4 shows the runtimes in seconds for diferent
One column stands out, where all entropy values are subsets of the satellite data and diferent numbers of zero. Inspection reveals that this is the column that origi- Monte Carlo iterations. nally contained the patient’s name, which was changed to For reasonably large subsets, runtime scales linearly a single global string constant as a means of anonymiza- with the number of iterations, while input size influences tion. Consequently, for every attribute, there is an ob- runtime more heavily. Calculating the entropies for 150 Results. The approximation greatly improves the runtime behavior. Since we use the entropy values as a basis for visualization, small deviations in accuracy lead to equally small deviations in the color scale. The diferences will most likely not be discernible to the human eye.
However, scalability to larger inputs remains a challenge and will require further improvements.
Acknowledgments This work was partially funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) grant #385808805. We thank Meike Klettke for her feedback on an earlier version of this article.
Dependency discovery is an established and active field,
and we refer to [
In our visualization, we impose heat maps over
relational data. Heat maps have also been explored elsewhere,
such as to visualize the frequency of updates [
We build on an information-theoretic framework
developed by Arenas and Libkin [
In an orthogonal efort, Lee [
We propose a plaque test to visualize redundancies in relational data, based on functional dependencies. As our discussion of real-world examples shows, the presence of plaque reveals interesting redundancies in the data.