The search for functional dependencies in data is applied in various areas of data analysis: database management, data cleaning, database reverse engineering, and data exploration. We have already published about the dependencies themselves. Anastasia Birillo and Nikita Bobrov. This time, Anastasia — a graduate of this year's Computer Science Center — shares the development of this work as part of the research project she defended at the center.
Choosing a Challenge
During my studies at the CS Center, I began to delve deeply into databases, specifically the search for functional and difference dependencies. This topic was related to my thesis at the university, so while working on my thesis, I started reading articles on various dependencies in databases. I wrote a review of this area — one of my first. in English and submitted it to the SEIM-2017 conference. I was very pleased when I learned that it was accepted, and I decided to dive deeper into the topic. The concept itself is not new — it has been applied since the 1990s, but it is still finding applications in many fields today.
In the second semester of my studies at the center, I began a research project to improve algorithms for finding functional dependencies. I worked on it together with SPbGU graduate student Nikita Bobrov at JetBrains Research.
The computational complexity of finding functional dependencies
The main problem is computational complexity. The number of possible minimal and non-trivial dependencies is bounded above by the value 
, where 
— the number of attributes in the table. The runtime of the algorithms depends not only on the number of attributes but also on the number of rows. In the 1990s, algorithms for finding functional dependencies on a regular desktop PC could process datasets containing up to 20 attributes and tens of thousands of rows in a few hours. Modern algorithms, running on multi-core processors, can discover dependencies for datasets consisting of hundreds of attributes (up to 200) and hundreds of thousands of rows approximately in the same amount of time. However, this is not sufficient: such time is unacceptable for most real applications. Therefore, we developed approaches to speed up existing algorithms.
Caching schemes for partition intersections
In the first part of the work, we developed caching schemes for a class of algorithms using the method of partition intersection. A partition for an attribute consists of a set of lists, where each list contains the row numbers with identical values for that attribute. Each such list is called a cluster. Many modern algorithms use partitions to determine whether a dependency is maintained or not, adhering to the lemma: Dependency 
is maintained if 
. Here, a partition is denoted and the concept of partition size is used — the number of clusters within it. Algorithms utilizing partitions, upon violating a dependency, add additional attributes to the left side of the dependency and then recalculate it by performing the partition intersection operation. This operation is referred to as specialization in the articles. However, we noticed that partitions for dependencies that will be maintained only after several rounds of specialization can be actively reused, which can significantly reduce the runtime of the algorithms, as the intersection operation is costly. 
Therefore, we proposed a heuristic based on Shannon's Entropy and Gini's uncertainty, as well as our metric, which we named Inverse Entropy. It is a minor modification of Shannon's Entropy and increases as the uniqueness of the dataset grows. The proposed heuristic is as follows:
— the degree of uniqueness of the recently computed partition.
Here 
— the uniqueness level of the recently calculated partition 
, and 
is the median degree of uniqueness for individual attributes. All three uniqueness metrics described above were tested as uniqueness metrics. It can also be noted that there are two modifiers in the heuristic. The first indicates how close the current partition is to the primary key and allows for greater caching of those partitions that are far from the potential key. The second modifier helps track cache occupancy and thereby encourages the addition of more partitions to the cache when there is free space. Successfully solving this problem allowed for a 10-40% speed increase of the PYRO algorithm depending on the dataset. It is worth noting that the PYRO algorithm is the most successful in this area.
The figure below shows the results of applying the proposed heuristic compared to the basic caching approach based on coin tossing. The X-axis is logarithmic.
Alternative way of storing partitions
Then we proposed an alternative method of storing partitions. Partitions represent a set of clusters, each containing the tuple numbers with the same values for certain attributes. These clusters can contain long sequences of tuple numbers, for example, if the data is ordered in the table. Therefore, we proposed a compression scheme for storing partitions, namely interval storage of values in partition clusters:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
This method was able to reduce memory consumption during the operation of the TANE algorithm by 1 to 25%. The TANE algorithm is a classical algorithm for discovering functional dependencies, which uses partitions during its operation. TANE was chosen in practice because implementing interval storage in it was significantly easier than, for example, in PYRO, to assess whether the proposed approach works. The results obtained are presented in the figure below. The X-axis is logarithmic.
ADBIS-2019 Conference
Based on the research results in September 2019, I presented a paper at the 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). During the presentation, the work was highlighted by Bernhard Thalheim, a prominent figure in the field of databases. The research results formed the basis of my master's thesis in the Mathematics and Mechanics department of St. Petersburg State University, where both proposed approaches (caching and compression) were implemented in both algorithms: TANE and PYRO. The results showed that the proposed approaches are universal, as both algorithms exhibited significant reductions in memory consumption and markedly decreased execution time.
Source: habr.com
