Discovering Domain Orders through Order Dependencies
Preprint
Abstract
Much real-world data come with explicitly defined domain orders; e.g., lexicographic order for strings, numeric for integers, and chronological for time. Our goal is to discover implicit domain orders that we do not already know; for instance, that the order of months in the Chinese Lunar calendar is Corner < Apricot < Peach. To do so, we enhance data profiling methods by discovering implicit domain orders in data through order dependencies. We enumerate tractable special cases and proceed towards the most general case, which we prove is NP-complete. We show that the general case nevertheless can be effectively handled by a SAT solver. We also devise an interestingness measure to rank the discovered implicit domain orders, which we validate with a user study. Based on an extensive suite of experiments with real-world data, we establish the efficacy of our algorithms, and the utility of the domain orders discovered by demonstrating significant added value in three applications (data profiling, query optimization, and data mining).Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Efficient Bidirectional Order Dependency Discovery2020
- Effective and complete discovery of bidirectional order dependencies via set-based axiomsThe VLDB Journal, 2018
- Efficient order dependency detectionThe VLDB Journal, 2015
- Detecting and exploiting near-sortedness for efficient relational query evaluation2011
- Discovering data quality rulesProceedings of the VLDB Endowment, 2008
- Predicate Derivation and Monotonicity Detection in DB2 UDB2005
- An extension of the relational data model to incorporate ordered domainsACM Transactions on Database Systems, 2001
- Tane: An Efficient Algorithm for Discovering Functional and Approximate DependenciesThe Computer Journal, 1999
- Fundamental techniques for order optimizationACM SIGMOD Record, 1996
- Order dependency in the relational modelTheoretical Computer Science, 1983