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.

Supplementary data:

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 View Item