2023/06/15 by Simon Vilmin, Vilmin, Simon, Pierre Faure–Giovagnoli +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Mining Algorithms and Applications #Data Quality and Management #Databases (cs.DB) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2306.09006
openalex publication_date 2023/06/15 · openalex created_date 2023/06/17 · openalex updated_date 2026/07/28
The notion of functional dependencies (FDs) can be used by data scientists and domain experts to confront background knowledge against data. To overcome the classical, too restrictive, satisfaction of FDs, it is possible to replace equality with more meaningful binary predicates, and use a coverage measure such as the g3-error to estimate the degree to which a FD matches the data. It is known that the g3-error can be computed in polynomial time if equality is used, but unfortunately, the problem becomes NP-complete when relying on more general predicates instead. However, there has been no analysis of which class of predicates or which properties alter the complexity of the problem, especially when going from equality to more general predicates. In this work, we provide such an analysis. We focus on the properties of commonly used predicates such as equality, similarity relations, and partial orders. These properties are: reflexivity, transitivity, symmetry, and antisymmetry. We show that symmetry and transitivity together are sufficient to guarantee that the g3-error can be computed in polynomial time. However, dropping either of them makes the problem NP-complete.