### Polynomial-time implication problems for unary inclusion dependenciesPolynomial-time implication problems for unary inclusion dependencies

Access Restriction
Subscribed

 Author Cosmadakis, Stavros S. ♦ Kanellakis, Paris C. ♦ Vardi, Moshe Y. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated. As shown by Casanova et al., the unrestricted and finite implication problems are different for the class of functional and unary inclusion dependencies; also, for this class and for any fixed $\textit{k},$ finite implication has no $\textit{k}-ary$ complete axiomatization. For both of these problems, complete axiomatizations and polynomial-time decision procedures are provided: linear time for unrestricted implication and cubic time for finite implication. It follows that functional and unary inclusion dependencies form a semantically natural class of first-order sentences with equality, which although not finitely controllable, is efficiently solvable and docile. Generalizing from these results, it is shown that the interaction between functionaland inclusion dependencies characterizes: (1) unrestricted implication of unary inclusion and all embedded implicational dependencies; (2) finite implication of unary inclusion and all full implicational dependencies; (3) finite implication of unary inclusion and all embedded tuple-generating dependencies. As a direct consequence of this analysis, most of the applications of dependency implication are extended, within polynomial-time, to database design problems involving unary inclusion dependencies. Such examples are tests for lossless joins and tests for complementarity of projective views. Finally, if one additionally requires that ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-01-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 1 Page Count 32 Starting Page 15 Ending Page 46

#### Open content in new tab

Source: ACM Digital Library