Search papers, labs, and topics across Lattice.
This paper addresses the automatic discovery of inclusion dependencies, a crucial task for establishing Primary Key-Foreign Key relationships in databases, by focusing on both algorithmic efficiency and practical implementation. The authors enhance two algorithms, Spider and Faida, through innovative parallelization and optimization techniques, resulting in significant performance improvements. Experimental results show that their implementations in the open-source tool Desbordante achieve up to 5x and 8x runtime reductions for Spider and Faida, respectively, compared to existing solutions like Metanome.
Achieving up to 8x faster inclusion dependency discovery could revolutionize database design and optimization practices.
Inclusion dependency is a relation between attributes of tables that indicates possible Primary Key-Foreign Key references. Automatic discovery of inclusion dependencies is a relevant problem for both academic and industrial communities. The core concern for this problem is the efficiency of discovery process, since it is a computationally expensive task. However, existing studies only address the algorithmic side, while leaving out the implementation aspect. At the same time, engineering details are at least as important as the algorithmic ones for achieving good performance. In this paper, we describe techniques for efficient implementation of two algorithms for discovery of inclusion dependencies - Spider and Faida. The first one is a classic algorithm whose ideas lie in the foundation of many other inclusion dependency discovery algorithms. We propose an efficient parallelization technique, which greatly speeds up the algorithm while simultaneously reducing its memory consumption. The second one is the state-of-the-art approximate algorithm, which we approach by applying four types of optimizations: data buffering, SIMD-enabled execution, careful hash-table selection and parallelization. In order to experimentally evaluate our techniques, we have implemented these algorithms in Desbordante - an open-source science-intensive data profiler written in C++. For Spider, we have evaluated several different options, and in case of Faida we have demonstrated that all our optimization techniques yield results. We also compared our implementations with Metanome - a Java-based data profiler. Overall, we report up to 5x improvement in terms of run time reduction for Spider and up to 8x for Faida.
