The Implication Problem of Data Dependencies over SQL Table Definitions: Axiomatic, Algorithmic and Logical Characterizations

Show simple item record Hartmann, S. en Link, S. en 2013-01-06T23:09:23Z en 2013-01-06T23:09:23Z en 2012 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-425 (2012) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri en
dc.description.abstract We investigate the implication problem for classes of data dependencies over SQL table definitions. Under Zaniolo’s “no information” interpretation of null markers we establish an axiomatization and algorithms to decide the implication problem for the combined class of functional and multivalued dependencies in the presence of NOT NULL constraints. The resulting theory subsumes three previously orthogonal frameworks. We further show that the implication problem of this class is equivalent to that in a propositional fragment of Cadoli and Schaerf’s family of para-consistent S-3 logics. In particular, S is the set of variables that correspond to attributes declared NOT NULL. We also show how our equivalences for multivalued dependencies can be extended to Delobel’s class of full first-order hierarchical decompositions, and the equivalences for functional dependencies can be extended to arbitrary Boolean dependencies. These dualities allow us to transfer several findings from the propositional fragments to the corresponding classes of data dependencies, and vice versa. We show that our results also apply to Codd’s null interpretation "value unknown at present", but not to Imielinski’s or-relations utilizing Levene and Loizou’s weak possible world semantics. Our findings establish NOT NULL constraints as an effective mechanism to balance not only the 1certainty in database relations but also the expressiveness with the efficiency of entailment relations. They also control the degree by which the implication of data dependencies over total relations is soundly approximated in SQL table definitions. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights.uri en
dc.source.uri en
dc.title The Implication Problem of Data Dependencies over SQL Table Definitions: Axiomatic, Algorithmic and Logical Characterizations en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en
dc.rights.holder The author(s) en
dc.rights.accessrights en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace