Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization
ACM Transactions on Database Systems · 31.12.2026 · 51 (4) · 1-45
DOI: 10.1145/3800938 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 16.04.2026. Verfasst von Pierre Faure–Giovagnoli und 3 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben. Gefördert von: Compagnie Nationale du Rhône.
Abstract (Originalsprache)
The incorporation of domain knowledge (DK) in AI has been studied for years and turns out to be critical in practice. Functions are also a basic notion for dealing with data science projects and are somehow related to DK. Consider the following scenario. Let \(D(y, z_1, \ldots , z_n)\) be a dataset, Alice a data scientist, Bob a domain expert and \(y = f(z_1, \ldots , z_n)\) a function known to Bob from his background knowledge. Alice is interested in the following simple yet crucial questions: How to define the satisfaction of f in D ? How to measure that satisfaction efficiently? How does this satisfaction relate to the supervised learning task of learning f from D ? It turns out that these problems are related to the study of counterexamples through the use of functional dependencies (FDs) and, in particular, FD measures used to quantify their satisfaction in a dataset such as the \(g_3\) indicator where the equality is replaced by more flexible predicates. In this article, we first examine the complexity of computing \(g_3\) . It is known that \(g_3\) can be computed in polynomial time when using equality, while it becomes NP -hard when using general predicates. Our goal is to refine this dichotomy by studying the impact of the following common properties: reflexivity, transitivity, symmetry, and antisymmetry. We show that symmetry and transitivity together are sufficient to guarantee that the \(g_3\) can be computed in polynomial time. However, removing one of them makes the problem NP -hard. Second, we study the computation of \(g_3\) in the polynomial and NP -hard cases identified previously. We propose different exact and approximate solutions for the computation of \(g_3\) in both cases. We compare these solutions in a detailed experimental study of time performance and approximation accuracy. All the algorithms are also made available via fastg3 , an open-source Python library with an underlying C++ implementation. Finally, we link counterexamples and \(g_3\) to supervised learning with a web application called adesit . adesit is intended to be part of an iterative data refinement process right after data selection and just before the machine learning process itself. It provides a way to evaluate the ability of a dataset to perform well for a given supervised learning problem through statistical and visual exploration. In a last section, we validate our approach by applying it to the industrial problem of air gap monitoring in compact hydro-generators.
Förderung
- Compagnie Nationale du Rhône
Zitieren
APA
Faure–Giovagnoli, P., Vilmin, S., Petit, J., & Scuturici, V. (2026). Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization. ACM Transactions on Database Systems, 51(4), 1-45. https://doi.org/10.1145/3800938
Vancouver
Faure–Giovagnoli P, Vilmin S, Petit J, Scuturici V. Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization. ACM Transactions on Database Systems. 2026;51(4):1-45. doi:10.1145/3800938
BibTeX
@article{FaureGiovagnoli2026,
author = {Faure–Giovagnoli, Pierre and Vilmin, Simon and Petit, Jean-Marc and Scuturici, Vasile-Marian},
title = {Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization},
journal = {ACM Transactions on Database Systems},
year = {2026},
volume = {51},
number = {4},
pages = {1--45},
doi = {10.1145/3800938}
}
EUVIMED