OceanRep
Constructing Armstrong tables for general cardinality constraints and not-null constraints.
Hartmann, Sven, Kohler, Henning, Leck, Uwe, Link, Sebastian, Thalheim, Bernhard and Wang, Jing (2015) Constructing Armstrong tables for general cardinality constraints and not-null constraints. Annals of Mathematics and Artificial Intelligence, 73 (1-2). pp. 139-165. DOI 10.1007/s10472-014-9423-9.
Full text not available from this repository.Abstract
Integrity constraints capture relevant requirements of an application that should be satisfied by every state of the database. The theory of integrity constraints is largely a theory over relations. To make data processing more efficient, SQL permits database states to be partial bags that can accommodate incomplete and duplicate information. Integrity constraints, however, interact differently on partial bags than on the idealized special case of relations. In this current paper, we study the implication problem of the combined class of general cardinality constraints and not-null constraints on partial bags. We investigate structural properties of Armstrong tables for general cardinality constraints and not-null constraints, and prove exact conditions for their existence. For the fragment of general max-cardinality constraints, unary min-cardinality constraints and not-null constraints we show that the effort for constructing Armstrong tables is precisely exponential. For the same fragment we provide an axiomatic characterization of the implication problem. The major tool for establishing our results is the Hajnal and Szemer,di theorem on the equitable colorings of graphs.
Document Type: | Article |
---|---|
Additional Information: | Times Cited: 2 |
Keywords: | SQL table, Incomplete database, Cardinality constraints, Null-free subschema, Implication, Inference, Armstrong database |
Research affiliation: | Kiel University OceanRep > The Future Ocean - Cluster of Excellence |
Refereed: | Yes |
Open Access Journal?: | No |
Publisher: | American Medical Association |
Projects: | Future Ocean |
Date Deposited: | 18 Oct 2016 03:47 |
Last Modified: | 23 Sep 2019 23:07 |
URI: | https://oceanrep.geomar.de/id/eprint/32508 |
Actions (login required)
View Item |
Copyright 2023 | GEOMAR Helmholtz-Zentrum für Ozeanforschung Kiel | All rights reserved
Questions, comments and suggestions regarding the GEOMAR repository are welcomed
at bibliotheksleitung@geomar.de !