Efficient Bidirectional Order Dependency Discovery
Authors:
- 1 April 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 61-72
Abstract
Bidirectional order dependencies state relationships of order between lists of attributes. They naturally model the order-by clauses in SQL queries, and are proved effective in query optimizations concerning sorting. Despite their importance, order dependencies on a dataset are typically unknown and are too costly, if not impossible, to design or discover manually. Techniques for automatic order dependency discovery are recently studied. It is challenging for order dependency discovery to scale well, since it is by nature factorial in the number m of attributes and quadratic in the number n of tuples. In this paper, we adopt a strategy that decouples the impact of m from that of n, and that still finds all minimal valid bidirectional order dependencies. We present carefully designed data structures, a host of algorithms and optimizations, for efficient order dependency discovery. With extensive experimental studies on both real-life and synthetic datasets, we verify our approach significantly outperforms state-of-the-art techniques, by orders of magnitude.Keywords
This publication has 17 references indexed in Scilit:
- Discovering denial constraintsProceedings of the VLDB Endowment, 2013
- Foundations of Data Quality ManagementSynthesis Lectures on Data Management, 2012
- Fundamentals of order dependenciesProceedings of the VLDB Endowment, 2012
- Differential dependenciesACM Transactions on Database Systems, 2011
- Discovering data quality rulesProceedings of the VLDB Endowment, 2008
- On generating near-optimal tableaux for conditional functional dependenciesProceedings of the VLDB Endowment, 2008
- Trends in databases: reasoning and miningIEEE Transactions on Knowledge and Data Engineering, 2001
- Tane: An Efficient Algorithm for Discovering Functional and Approximate DependenciesThe Computer Journal, 1999
- Sort sets in the relational modelJournal of the ACM, 1986
- Order dependency in the relational modelTheoretical Computer Science, 1983