Fast Accurate Discovery of Tuple Inclusion Dependencies

Inclusion dependencies (IND) is an important problem in relational database, relevant to data integration, query optimization and various data management tasks. The discovery of IND has been addressed by many studies following different strategies, while IND detection still needs improvement as the complexity and diversity of real-life data increase. Conventional IND is only for column-to-column dimension, which is not applicable to lots of data processing tasks. The concept of dependency can be expanded. Based on the understanding of the conventional IND and approximate approach FAIDA, we present our algorithm for detecting tuple IND, converting column-to-column detection to row-to-row dimension, more in line with real-world data retrieval tasks in distributed system. Through probabilistic and accurate detection and the use of multi-threading, both accuracy and performance are guaranteed and IND detection performance is taken to a new level.