Cardinality constraints and functional dependencies in SQL: Taming data redundancy in logical database design. Issue 115 (May 2023)

• Record Type: Journal Article
• Authors: Link, Sebastian; Koehler, Henning; Gandhi, Aniruddh; Hartmann, Sven; Thalheim, Bernhard
• Is Part Of: Information systems. Issue 115(2023)
• Publication Date: 2023-05
• Subjects: Armstrong database -- Cardinality constraint -- Data redundancy -- Functional dependency -- Normal form -- Reasoning -- SQL; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2023.102208
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: We investigate the combined class of cardinality constraints and functional dependencies over SQL tables. As our first contribution, we establish a finite ground axiomatization and quadratic-time algorithm for deciding their implication problem. As our second contribution, we characterize when finite Armstrong tables exist for this class, and show how to compute finite representations of Armstrong tables for every given input. While there are extreme cases where the size of an Armstrong representation is logarithmic or necessarily exponential, our extensive experiments suggest that the size is low-degree polynomial on average. As our third contribution, we propose a new family of syntactic normal forms for the logical design of SQL tables, of which the well-known Boyce–Codd Normal Form is a special case. Our normal form characterizes SQL schemata that have an a priori upper bound on the number of records in which any redundant data value may occur in any database instance over the schema. Such bounds tame the number of records requiring updates to preserve data consistency. Highlights: Functional dependencies, cardinality and NOT NULL constraints are studied over partial bags. Axiomatic and quadratic-time algorithmic characterizations are proven for the associated implication problem. Structural and computational properties of Armstrong representations are established for the class. Experiments provide insight on the size of Armstrong representations and the time to compute them. A family of syntactic normal forms captures instances that limit redundant data value occurrences.