An Efficient and Scalable Algorithm to Mine Functional Dependencies from Distributed Big Data.

Area of Science:

• Data Science
• Database Systems
• Big Data Analytics

Background:

• Discovering semantic relationships is vital for data quality improvement.
• Functional dependencies (FDs) define these relationships in relational databases.
• Existing FD discovery algorithms struggle with distributed and large-scale data.

Purpose of the Study:

• To propose a novel distributed functional dependency discovery algorithm.
• To address scalability and accuracy issues of traditional methods in distributed environments.
• To enhance data quality through efficient semantic relationship discovery.

Main Methods:

• Developed a distributed functional dependency discovery algorithm leveraging Apache Spark.
• Employed data redistribution for parallel processing across multiple nodes.
• Utilized a sampling approach for rapid invalid FD elimination and a greedy task assignment for load balancing.
• Incorporated prefix trees to optimize intermediate result storage and avoid redundant computations.

Main Results:

• The proposed algorithm demonstrates high efficiency in discovering functional dependencies on large-scale datasets.
• Experimental results confirm superior performance compared to existing methods on both real and synthetic data.
• The algorithm effectively ensures accuracy while improving computational efficiency.

Conclusions:

• The novel distributed algorithm based on Apache Spark offers an effective solution for large-scale functional dependency discovery.
• This approach significantly enhances data quality management in distributed big data systems.
• The method provides a scalable and accurate solution for identifying semantic relationships in complex datasets.