Approximate Functional Dependencies---Implication Problem Revisited
2026-08-17 • Logic in Computer Science
Logic in Computer ScienceDatabases
AI summaryⓘ
The authors explain that functional dependencies, which are rules about how data in a database should relate, can sometimes be broken by small errors. Väänänen (2017) studied a way to allow some violations in these rules, called approximate dependence. The authors found that these approximate dependencies behave more complexly than initially thought, revealing some missing reasoning rules, though the original rules still work when the dependencies involve just one attribute. They also studied how hard it is to check if data follows these approximate rules, finding it difficult in some cases but easier in others.
Functional dependenciesDatabase constraintsTeam logicApproximate dependenceAxiomatisationInference rulesModel checkingNP-completeLOGSPACE-hardUnary dependencies
Authors
Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen, Minna Hirvonen
Abstract
Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data often contain errors, so in some cases it might be useful to allow the database to have a small number of tuples that violate the desired dependency. Väänänen (2017) studied the axiomatisation of a notion of approximate dependence that specifies for each dependence atom how much of the database can be disregarded. We demonstrate that the interaction of approximate dependence atoms is more complicated than previously thought in the sense that there is a semantic consequence that is not captured by the inference rules introduced before. We show that Väänänen's axiomatisation is still complete in the restricted case of unary dependencies. We also consider the complexity of model checking for approximate dependence: it is NP-complete for disjunctions of two atoms and LOGSPACE-hard for individual atoms.