Fast Discovery of Inclusion Dependencies with Desbordante

This paper focuses on the implementation engineering behind efficient inclusion dependency (IND) discovery, a task useful for identifying possible primary-key/foreign-key relationships across tables. The authors optimize two algorithms: Spider, a classic exact approach, and Faida, a state-of-the-art approximate method. Their Desbordante implementation uses parallelization and memory-conscious execution for Spider, while Faida additionally benefits from data buffering, SIMD execution, hash-table selection, and parallelization. The paper reports up to 5x runtime reduction for Spider and up to 8x for Faida, and compares the implementations with the Java-based Metanome profiler.