License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2020.18
URN: urn:nbn:de:0030-drops-119420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11942/
Go to the corresponding LIPIcs Volume Portal

Kenig, Batya ; Suciu, Dan

Integrity Constraints Revisited: From Exact to Approximate Implication

pdf-format:
LIPIcs-ICDT-2020-18.pdf (0.6 MB)

Abstract

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". Finally, we show that the implication problem for differential constraints in market basket analysis also admits a relaxation with a factor equal to 1. Our results recover, and sometimes extend, several previously known results about the implication problem: implication of MVDs can be checked by considering only 2-tuple relations, and the implication of differential constraints for frequent item sets can be checked by considering only databases containing a single transaction.

BibTeX - Entry

@InProceedings{kenig_et_al:LIPIcs:2020:11942,
  author =	{Batya Kenig and Dan Suciu},
  title =	{{Integrity Constraints Revisited: From Exact to Approximate Implication}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11942},
  URN =		{urn:nbn:de:0030-drops-119420},
  doi =		{10.4230/LIPIcs.ICDT.2020.18},
  annote =	{Keywords: Integrity constraints, The implication problem}
}

Keywords: Integrity constraints, The implication problem
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46828

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI