Guided conditional functional dependency discovery. Issue 114 (March 2023)

• Record Type: Journal Article
• Authors: Jiang, Sijia; Tan, Zijing; Wang, Jiawei; Wang, Zhikang; Ma, Shuai
• Is Part Of: Information systems. Issue 114(2023)
• Publication Date: 2023-03
• Subjects: Conditional functional dependency -- Dependency discovery -- Metadata; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2022.102158
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Conditional functional dependencies (CFDs) generalize functional dependencies and lend themselves to wide applicability. CFDs on data are usually unknown and too costly to be designed manually. To this end, CFD discovery methods are studied for discovering hidden CFDs from data. In the setting of data cleaning, only a small number of CFDs are used to detect and repair errors, while common CFD discovery methods find all CFDs (approximately) holding on data, and an expensive post-processing step is further required for selecting those relevant ones. In this paper, we present an approach to discover CFDs that can detect errors in data, guided by a small set of erroneous attribute values labeled by users. (1) We present a method that consists of several modules of data sampling, CFD discovery and refinement guided by the user labeling and data re-sampling guided by the discovered CFDs, working in an iterative way. (2) We present novel efficient techniques to facilitate our approach, aiming at identifying CFDs useful for cleaning and reducing user interactions. (3) We conduct extensive experimental evaluations to verify our approach, against the state-of-the-art CFD discovery algorithms with or without user interactions. Highlights: A framework of conditional functional dependency discovery leveraging user labeling. A set of techniques underlying the framework. Evaluations of the effectiveness and efficiency of user-guided discovery.