{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T09:50:13Z","timestamp":1791366613050,"version":"4.3.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T00:00:00Z","timestamp":1641859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["1907997"],"award-info":[{"award-number":["1907997"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Integrity constraints such as functional dependencies (FD) and multi-valued\ndependencies (MVD) are fundamental in database schema design. Likewise,\nprobabilistic conditional independences (CI) are crucial for reasoning about\nmultivariate probability distributions. The implication problem studies whether\na set of constraints (antecedents) implies another constraint (consequent), and\nhas been investigated in both the database and the AI literature, under the\nassumption that all constraints hold exactly. However, many applications today\nconsider constraints that hold only approximately. In this paper we define an\napproximate implication as a linear inequality between the degree of\nsatisfaction of the antecedents and consequent, and we study the relaxation\nproblem: when does an exact implication relax to an approximate implication? We\nuse information theory to define the degree of satisfaction, and prove several\nresults. First, we show that any implication from a set of data dependencies\n(MVDs+FDs) can be relaxed to a simple linear inequality with a factor at most\nquadratic in the number of variables; when the consequent is an FD, the factor\ncan be reduced to 1. Second, we prove that there exists an implication between\nCIs that does not admit any relaxation; however, we prove that every\nimplication between CIs relaxes \"in the limit\". Then, we show that the\nimplication problem for differential constraints in market basket analysis also\nadmits a relaxation with a factor equal to 1. Finally, we show how some of the\nresults in the paper can be derived using the I-measure theory, which relates\nbetween information theoretic measures and set theory. Our results recover, and\nsometimes extend, previously known results about the implication problem: the\nimplication of MVDs and FDs can be checked by considering only 2-tuple\nrelations.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:5)2022","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T17:31:31Z","timestamp":1642095091000},"source":"Crossref","is-referenced-by-count":3,"title":["Integrity Constraints Revisited: From Exact to Approximate Implication"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Batya","family":"Kenig","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2022,1,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/8943\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/8943\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:18:28Z","timestamp":1687292308000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/6925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:5)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"1812.09987v6","asserted-by":"subject"},{"id-type":"arxiv","id":"1812.09987v5","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1812.09987","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1812.09987","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,11]]},"article-number":"6925"}}