Functional Dependencies Unleashed for Scalable Data Exchange

Abstract : We address the problem of efficiently evaluating target functional dependencies (fds) in the Data Exchange (DE) process. Target fds naturally occur in many DE scenarios, including the ones in Life Sciences in which multiple source relations need to be structured under a constrained target schema. However, despite their wide use, target fds' evaluation is still a bottleneck in the state-of-the-art DE engines. Systems relying on an all-SQL approach typically do not support target fds unless additional information is provided. Alternatively, DE engines that do include these dependencies typically pay the price of a significant drop in performance and scalability. In this paper, we present a novel chase-based algorithm that can efficiently handle arbitrary fds on the target. Our approach essentially relies on exploiting the interactions between source-to-target (s-t) tuple-generating dependencies (tgds) and target fds. This allows us to tame the size of the intermediate chase results, by playing on a careful ordering of chase steps interleaving fds and (chosen) tgds. As a direct consequence, we importantly diminish the fd application scope, often a central cause of the dramatic overhead induced by target fds. Moreover, reasoning on dependency interaction further leads us to interesting parallelization opportunities, yielding additional scalability gains. We provide a proof-of-concept implementation of our chase-based algorithm and an experimental study aimed at gauging its scalability and efficiency. Finally, we empirically compare with the latest DE engines, and show that our algorithm outperforms them.
Type de document :
Communication dans un congrès
ACM. International Conference on Scientific and Statistical Database Management (SSDBM), Jul 2016, Budapest, Hungary. Proceedings of the 28th International Conference on Scientific and Statistical Database Management (SSDBM), pp.12, 2016, 〈10.1145/2949689.2949698〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01401405
Contributeur : Angela Bonifati <>
Soumis le : mercredi 23 novembre 2016 - 12:03:32
Dernière modification le : jeudi 19 avril 2018 - 14:38:05

Lien texte intégral

Identifiants

Citation

Angela Bonifati, Ioana Ileana, Michele Linardi. Functional Dependencies Unleashed for Scalable Data Exchange. ACM. International Conference on Scientific and Statistical Database Management (SSDBM), Jul 2016, Budapest, Hungary. Proceedings of the 28th International Conference on Scientific and Statistical Database Management (SSDBM), pp.12, 2016, 〈10.1145/2949689.2949698〉. 〈hal-01401405〉

Partager

Métriques

Consultations de la notice

276