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 Lunar calendar is \emph{Corner} $\prec$ \emph{Apricot} $\prec$ \emph{Peach}, and so on. To do so, we enhance data profiling methods by discovering implicit domain orders in data through order dependencies (ODs). We first identify tractable special cases and then proceed towards the most general case, which we prove is NP-complete. Nevertheless, we show that the general case can be still handled by a SAT solver. We also propose an interestingness measure to rank the discovered implicit domain orders. Finally, we implement our solutions in an attribute-lattice discovery framework, and we perform an experimental evaluation using real-world datasets.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Efficient Bidirectional Order Dependency Discovery2020
- Incremental Discovery of Order Dependencies on Tuple Insertions2019
- Effective and complete discovery of bidirectional order dependencies via set-based axiomsThe VLDB Journal, 2018
- Effective and complete discovery of order dependencies via set-based axiomatizationProceedings of the VLDB Endowment, 2017
- Efficient order dependency detectionThe VLDB Journal, 2015
- Expressiveness and complexity of order dependenciesProceedings of the VLDB Endowment, 2013
- Predicate Derivation and Monotonicity Detection in DB2 UDB2005
- An extension of the relational data model to incorporate ordered domainsACM Transactions on Database Systems, 2001
- Fundamental techniques for order optimizationACM SIGMOD Record, 1996
- Business-Intelligence Queries with Order Dependencies in DB2