一句话：定义满足度上的近似蕴含，研究数据库依赖与概率条件独立的精确蕴含何时能松弛为线性不等式。
功能依赖（FD）、多值依赖（MVD）等完整性约束是数据库模式设计的核心，概率条件独立（CI）则用于多元概率分布推理。传统蕴含问题假设约束精确成立，但许多应用只要求近似成立。本文用信息论定义约束满足度，将近似蕴含定义为前件与后件满足度之间的线性不等式，并研究精确蕴含何时能松弛为近似蕴含。结果表明：MVD+FD 的任意蕴含可松弛为变量数至多二次因子的线性不等式，后件为 FD 时因子为 1；CI 间存在不可松弛的蕴含，但所有 CI 蕴含在极限下可松弛；市场篮子分析中的微分约束也可因子为 1 松弛。作者还用 I-measure 理论推导部分结果，并恢复、扩展了 MVD/FD 蕴含只需考察 2-tuple relations 等已知结论。
Integrity constraints such as functional dependencies (FD) and multi-valued dependencies (MVD) are fundamental in database schema design. Likewise, probabilistic conditional independences (CI) are crucial for reasoning about multivariate probability distributions. The implication problem studies whether a set of constraints (antecedents) implies another constraint (consequent), and has been investigated in both the database and the AI literature, under the assumption that all constraints hold exactly. However, many applications today consider constraints that hold only approximately. In this paper we define an approximate implication as a linear inequality between the degree of satisfaction of the antecedents and consequent, and we study the relaxation problem: when does an exact implication relax to an approximate implication? We use information theory to define the degree of satisfaction, and prove several results. First, we show that any implication from a set of data dependencies (MVDs+FDs) can be relaxed to a simple linear inequality with a factor at most quadratic in the number of variables; when the consequent is an FD, the factor can be reduced to 1. Second, we prove that there exists an implication between CIs that does not admit any relaxation; however, we prove that every implication between CIs relaxes "in the limit". Then, we show that the implication problem for differential constraints in market basket analysis also admits a relaxation with a factor equal to 1. Finally, we show how some of the results in the paper can be derived using the I-measure theory, which relates between information theoretic measures and set theory. Our results recover, and sometimes extend, previously known results about the implication problem: the implication of MVDs and FDs can be checked by considering only 2-tuple relations.
@article{paperbot1750,
title = {Integrity Constraints Revisited: From Exact to Approximate Implication},
author = {Batya Kenig and Dan Suciu},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:5)2022}
}