Discovering Domain Orders via Order Dependencies
Authors:
- 1 May 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1098-1110
Abstract
Most real-world data come with explicitly defined domain orders; e.g., lexicographic 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 show that the general case is NP-complete but can be effectively handled by a SAT solver. We also devise an interestingness measure to rank the discovered implicit domain orders. Based on an extensive suite of experiments with real-world data, we establish the efficacy of our algorithms.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Informative Summarization of Numeric Data2019
- Effective and complete discovery of bidirectional order dependencies via set-based axiomsThe VLDB Journal, 2018
- Efficient order dependency detectionThe VLDB Journal, 2015
- Queries on dates2011
- Predicate Derivation and Monotonicity Detection in DB2 UDB2005
- Introduction to Lattices and Order2002
- 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