Skip to Main content Skip to Navigation
Conference papers

Provenance-aware Discovery of Functional Dependencies on Integrated Views

Abstract : The automatic discovery of functional dependencies(FDs) has been widely studied as one of the hardest problems in data profiling. Existing approaches have focused on making the FD computation efficient while inspecting single relations at a time. In this paper, for the first time we address the problem of inferring FDs for multiple relations as they occur in integrated views by solely using the functional dependencies of the base relations of the view itself. To this purpose, we leverage logical inference and selective mining and show that we can discover most of the exact FDs from the base relations and avoid the full computation of the FDs for the integrated view itself, while at the same time preserving the lineage of FDs of base relations. We propose algorithms to speedup the inferred FD discovery process and mine FDs on-the-fly only from necessary data partitions. We present InFine(INferred FunctIoNal dEpendency), an end-to-end solution to discover inferred FDs on integrated views by leveraging provenance information of base relations. Our experiments on a range of real-world and synthetic datasets demonstrate the benefits of our method over existing FD discovery methods that need to rerun the discovery process on the view from scratch and cannot exploit lineage information on the FDs. We show that InFine outperforms traditional methods necessitating the full integrated view computation by one to two order of magnitude in terms of runtime. It is also the most memory efficient method while preserving FD provenance information using mainly inference from base table with negligible execution time.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03474955
Contributor : Ugo Comignani Connect in order to contact the contributor
Submitted on : Friday, December 10, 2021 - 3:02:33 PM
Last modification on : Wednesday, March 16, 2022 - 3:48:26 AM

Files

ICDE22_preprint.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03474955, version 1
  • ARXIV : 2112.09011

Citation

Ugo Comignani, Laure Berti-Équille, Noël Novelli, Angela Bonifati. Provenance-aware Discovery of Functional Dependencies on Integrated Views. ICDE 2022 - 38th IEEE International Conference on Data Engineering, May 2022, Kuala Lumpur, Malaysia. pp.1-15. ⟨hal-03474955⟩

Share

Metrics

Record views

398

Files downloads

52